Logic 1, WS 2004. Homework 2, given Oct 14, due Oct 21

1. Write the truth tables for:

(a) (¬(P ∨ Q)) ∨ (¬Q)

(b) (P ⇒ Q) ⇒ (Q ⇒ P)

(c) (¬P) ∧ (¬(P ⇒ Q))

2. Prove the following equivalences using equivalent rewriting (e.g. by transforming both sides into conjunctive or disjunctive normal form):

(1) P ∧ Q ∧ (¬P ∨ ¬Q) ≡ ¬P ∧ ¬Q ∧ (P ∨ Q)

(2) P ∨ (P ⇒ (P ∧ Q)) ≡ ¬P ∨ ¬Q ∨ (P ∧ Q)

3. Prove the following formula using the natural style inferences which you find appropriate, in a style similar to our natural style proofs from the lecture:

((A ∨ B) ⇒ C) ⇔ ((A ⇒ C) ∧ (B ⇒ C))