Discrete Math - Problems On Logic

Department of Mathematics
MAL 180: Discrete Mathematical Structures

Problems on Logic
1. Let p be the proposition “I will do every exercise in this book” and q be the proposition “I
will get an ‘A’ in this course”. Express each of the following in terms of p and q:
(i) I will get an ‘A’ in this course only if I do every exercise in this book.
(ii) I will get an ‘A’ in this course and I will do every exercise in this book.
(iii) Either I will get an ‘A’ in this course or I will not do every exercise in this book.
(iv) For me to get an ‘A’ in this course it is necessary and sufficient that I do every exercise
in this book.
2. Write the truth table of the compund proposition (p ∨ q) → (p ∧ ¬ r).
3. Show that the following two compound statements are tautologies:
(i) (¬ p ∧ (p → q)) → ¬ p.
(ii) ((p ∨ q) ∧ ¬ p) → q.
4. Give the converse, the contrapositive, and the inverse of the following conditional statements:
(i) If it rains today, then I will drive to work.

(ii) If |x| = x, then x ≥ 0.
(iii) If n is greater than 3, then n2 is greater than 9.
5. Show that these statements are inconsistent:
• “If Mr. T does not take a course in Discrete Mathematics, then he will not graduate.”
• “If Mr. T does not graduate, then he is not qualified for the job.”
• “If Mr. T reads Rosen’s ‘Discrete Mathematics’, then he is qualified for the job.”
• “Mr. T does not take a course in Discrete Mathematics but he reads Rosen’s ‘Discrete
Mathematics’.”
6. There are only two kinds of people who reside in an island: knights and knaves. Knights
always speak the truth and knaves always lie. Three people in this island A, B, C make the
statements:
A: “I am a knave and B is a knight.”
B: “Exactly one of the three of us is a knight.”
What can you say about A, B, and C?
7. Let S be the conditional statement (If S is true, then unicorns live) → (Unicorns live). If S
is true, prove that S cannot be a proposition.
8. Let P (x) be the statement “student x knows Calculus” and let Q(y) be the statement “class
y contains a student who knows Calculus”. Express each of the following as quantifications
of P (x) and Q(y):
(i) Some students know Calculus.

(ii) Not every student knows Calculus.
(iii) Every class has a student in it who knows Calculus.
(iv) Every student in every class knows Calculus.
(v) There is at least one class with no student who know Calculus.
1
9. Find domains for the quantifiers in

∃x ∃y x 6= y ∧ ∀z((z = x) ∨ (z = y))
such that this statement is true/false.
10. Use existential and universal quantifiers to express the statement “Everybody has exactly
two biological parents” using the propositional function P (x, y), which represents “x is the
biological parent of y.”
11. Let P (x, y) be a propositional function. Show that
∃x ∀y P (x, y) → ∀y ∃x P (x, y)
is a tautology.
12. If ∀y ∃x P (x, y) is true, does it necessarily follow that ∃x ∀y P (x, y) is true?
13. Find the negation of the following statements:
(i) If it snows today, then I will go skiing tomorrow.

(ii) Every person in this class understands mathematical induction.
(iii) Some students in this class do not like Discrete Mathematics.
(iv) In every Mathematics class there is some student who falls asleep during lectures.
14. Express the statement “There is a building on the campus of some college in India in which
every room is painted white” using quantifiers.
15. Use the Rules of Inference to show that if the premises ∀x (P (x) → Q(x)), ∀x (Q(x) → R(x))
and ¬R(a) where a is in the domain, are true, then the conclusion ¬P (a) is true.
16. Prove that given a nonnegative integer n, there is a unique nonnegative integer m such that
m2 ≤ n < (m + 1)2 .
17. Disprove the statement that every positive integer is the sum of the cubes of 8 nongetaive
integers.
√
18. Assuming the truth of the theorem that states that
√ √n is irrational whenever n is a positive
integer that is not a perfect square, prove that 2 + 3 is irrational.

Discrete Math - Problems On Logic

Uploaded by

Copyright:

Available Formats

Discrete Math - Problems On Logic

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Discrete Math - Problems On Logic

Uploaded by

Copyright:

Available Formats

Department of Mathematics

MAL 180: Discrete Mathematical Structures

2. Write the truth table of the compund proposition (p ∨ q) → (p ∧ ¬ r).

3. Show that the following two compound statements are tautologies:

(i) If it rains today, then I will drive to work.

5. Show that these statements are inconsistent:

(i) Some students know Calculus.

such that this statement is true/false.

11. Let P (x, y) be a propositional function. Show that

12. If ∀y ∃x P (x, y) is true, does it necessarily follow that ∃x ∀y P (x, y) is true?

13. Find the negation of the following statements:

(i) If it snows today, then I will go skiing tomorrow.

You might also like