Assignment 5
1. For each of the following derivations, provide the justifications for each line of the derivation.
(a) For any formulas ϕ and ψ, we have {¬ϕ} (ϕ → ψ).
(1) ((¬ψ → ¬ϕ) → (ϕ → ψ))
(2) (¬ϕ → (¬ψ → ¬ϕ))
(3) ¬ϕ
(4) (¬ψ → ¬ϕ)
(5) (ϕ → ψ)
(b) For any formulas ϕ and ψ, we have (¬ψ → (ψ → ϕ)).
(1) (¬ψ → (¬ϕ → ¬ψ))
(2) ((¬ϕ → ¬ψ) → (ψ → ϕ))
(3) (((¬ϕ → ¬ψ) → (ψ → ϕ)) → (¬ψ → ((¬ϕ → ¬ψ) → (ψ → ϕ))))
(4) (¬ψ → ((¬ϕ → ¬ψ) → (ψ → ϕ)))
(5) ((¬ψ → ((¬ϕ → ¬ψ) → (ψ → ϕ))) → ((¬ψ → (¬ϕ → ¬ψ)) → (¬ψ → (ψ → ϕ))))
(6) ((¬ψ → (¬ϕ → ¬ψ)) → (¬ψ → (ψ → ϕ)))
(7) (¬ψ → (ψ → ϕ))
2. Determine whether each of the following proposed proof systems are sound. Justify your answers.
(a) Axioms: All formulas.
Rules: None.
(b) Axioms: All formulas of the form. (ϕ → ϕ).
Rules: Hypothetical Syllogism.
(c) Axioms: All formulas of the form. (ϕ → ψ).
Rules: Modus Ponens.
(d) Axioms: All tautologies.
Rules: From any ϕ that is not a tautology, infer any formula.
3. For each of the following, show that the formula is derivable from the set as indicated. You may use anything proved in the Week 5 Slides, such as the Deduction Theorem and Hypothetical Syllogism, and anything occurring earlier in this assignment or question. You may not use the Completeness Theorem.
(a) For any formulas ϕ, ψ and γ,
{ψ,(ϕ → (ψ → γ))} (ϕ → γ).
(b) For any formulas ϕ, ψ and γ,
{(ϕ → (ψ → γ))} (ψ → (ϕ → γ)).
(c) For propositional variables P, Q and R,
{(P → Q),(¬R → ¬Q)} (P → R).
4. Let P, Q and R be propositional variables. Is it the case that
{((P → Q) → R)} (P → R) ? Justify your answer.