Question 1

1. Construct a truth table for the following compound proposition.

(q →¬p) ↔ (p ↔¬q)

1. Show that whether the following conditional statement is a tautology by using a truth table.

[(p ∨ q) ∧ (r → p) ∧ (r → q)] → r

Question 2

Show that (p → q) ∧ (p → r) and (¬q ∨¬r) →¬p are logically equivalent. Use tables 6,7 and 8 given under the section ”Propositional Equivalences” in the course textbook and give the reference to the table and the law in each step.

Question 3

Let F(x, y) mean that x is the father of y; M(x, y) denotes x is the mother of y. Similarly, H(x, y), S(x, y), and B(x, y) say that x is the husband/sister/brother of y, respectively. You may also use constants to denote individuals, like Sam and Alex. You can use ∨,∧,→,¬,∀,∃ rules and quantifiers. However, you are not allowed to use any predicate symbols other than the above to translate the following sentences into predicate logic. ∃! and exclusive-or (XOR) quantifiers are forbidden:

• Everybody has a mother.
• Everybody has a father and a mother.
• Whoever has a mother has a father.
• Sam is a grandfather.
• All fathers are parents.
• All husbands are spouses.
• No uncle is an aunt.
• All brothers are siblings.
• Nobody’s grandmother is anybody’s father.
• Alex is Ali’s brother-in-law.

1

11) Alex has at least two children.Question 4

12) Everybody has at most one mother.

Prove the following claims by natural deduction. Use only the natural deduction rules ∨, ∧, →, ¬ introduction and elimination. If you attempt to make use of a lemma or equivalence, you need to prove it by natural deduction too.

1. p → q,r → s ` (p ∨ r) → (q ∨ s)
2. ` (p → (r →¬q)) → ((p ∧ q) →¬r)

Question 5

Prove the following claims by natural deduction. Use only the natural deduction rules ∨,∧,→ ,¬,∀,∃ introduction and elimination. If you attempt to make use of a lemma or equivalence, you need to prove it by natural deduction too.

1. ∀xP(x) ∨∀xQ(x) `∀x(P(x) ∨ Q(x))
2. ∀xP(x) → S `∃x(P(x) → S)