Logic 1, WS 2004. Homework 3, given Oct 21, due Oct 28

1. Prove the following lemma: For any formulae ϕ, ϕ_{1}, ϕ_{2}, if ϕ_{1} ≡ ϕ_{2}, then (ϕ ⇒ ϕ_{1}) ≡ (ϕ ⇒ ϕ_{2}).

2. Prove the correctness of the following two sequent rules:

(∧ ⊢) \frac{Φ, φ_{1}, φ_{2} ⊢ Ψ}{Φ, φ_{1} ∧ φ_{2} ⊢ Ψ} (⊢ ¬) \frac{Φ, ψ ⊢ Ψ}{Φ ⊢ Ψ, ¬ψ}

3. Formulate the correctness of the sequent calculus presented in the lecture and give a summary of the proof of it.

4. Construct the sequent deduction for the following formula using the sequent rules which you find appropriate (preferably those ones which correspond to the natural style proof shown during the lecture):

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