Discrete Computational Structures
Question 1
a) Construct a truth table for the following compound proposition.
(q →¬p) ↔ (p ↔¬q)
b) 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:
1) Everybody has a mother.
2) Everybody has a father and a mother.
3) Whoever has a mother has a father.
4) Sam is a grandfather.
5) All fathers are parents.
6) All husbands are spouses.
7) No uncle is an aunt.
8) All brothers are siblings.
9) Nobody’s grandmother is anybody’s father.
10) 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.
a) p → q,r → s ` (p ∨ r) → (q ∨ s)
b) ` (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.
a) ∀xP(x) ∨∀xQ(x) `∀x(P(x) ∨ Q(x))
b) ∀xP(x) → S `∃x(P(x) → S)
