Question 1
- Construct a truth table for the following compound proposition.
(q →¬p) ↔ (p ↔¬q)
- 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.
- p → q,r → s ` (p ∨ r) → (q ∨ s)
- ` (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.
- ∀xP(x) ∨∀xQ(x) `∀x(P(x) ∨ Q(x))
- ∀xP(x) → S `∃x(P(x) → S)
