# 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*)

## Reviews

There are no reviews yet.