代做Assignment 5代做迭代

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.