MAT 3361, INTRODUCTION TO MATHEMATICAL LOGIC, Fall 2004

Answers to Problem Set 2: Handout 1, 11, 21, 31, 41, 51 (using Prawitz style natural deduction), 12, 22, 32, 42, 52 (using analytic tableaux) Peter Selinger

Problem 11

(a) A ∧ (A ∨ B) ; (∧E) ; A (b) \begin{matrix}A & \begin{aligned}A \\ & (∨I) \\ A ∨ B \end{aligned} \\ (∧I) \\ A ∧ (A ∨ B) \end{matrix}

Problem 21

[A ∧ B]_{1} ; (∧E) ; B A ∧ ¬ B ; (∧E) ; ¬ B (¬ E) ⊥ (¬ I_{1}) ¬(A ∧ B)

Problem 31

(a) \begin{matrix}\begin{aligned}\begin{aligned}[A]_{1} \\ & (∨I) \\ A ∨ B \end{aligned} & & A ∨ B → C \\ & & & (→E) \\ & C \end{aligned} ; (→I_{1}) ; A → C & \begin{aligned}\begin{aligned}[B]_{2} \\ & (∨I) \\ A ∨ B \end{aligned} & & A ∨ B → C \\ & & & (→E) \\ & C \end{aligned} ; (→I_{2}) ; B → C \\ (∧I) \\ (A → C) ∧ (B → C) \end{matrix}

(b) \begin{aligned}[A ∨ B]_{1} & \begin{aligned}[A]_{2} & (A → C) ∧ (B → C) ; (∧E) ; A → C \\ & (→E) \\ & C \end{aligned} & \begin{aligned}[B]_{2} & (A → C) ∧ (B → C) ; (∧E) ; B → C \\ & (→E) \\ & C \end{aligned} \\ & & (∨E_{2,3}) \\ & C \end{aligned} ; (→I_{1}) ; (A ∨ B) → C

Problem 41

[¬(A ∨ ¬ A)]_{1}  \begin{aligned}[¬(A ∨ ¬ A)]_{1} & \begin{aligned}[A]_{2} \\ & (∨I) \\ A ∨ ¬ A \end{aligned} \\ & (∨E) \\ ⊥ \end{aligned} ; (¬ I_{2}) ; ¬ A ; (∨I) ; A ∨ ¬ A (¬ E) ⊥ (RAA_{1}) A ∨ ¬ A

Problem 51

[¬((A → B) ∨ (B → A))]_{1} \begin{aligned}[¬((A → B) ∨ (B → A))]_{1} & \begin{aligned}[A]_{2} \\ & (→I_{3}) \\ B → A \end{aligned} ; (∨E) ; (A → B) ∨ (B → A) \\ & (¬ E) \\ ⊥ \end{aligned} ; (⊥E) ; B ; (→I_{2}) ; A → B ; (∨E) ; (A → B) ∨ (B → A) (¬ E) ⊥ (RAA_{1}) (A → B) ∨ (B → A)

Problem 12 (a) A ∨ (A ∧ B) ⊢ A

\begin{matrix}F A \\ T (A ∨ (A ∧ B)) \end{matrix} ; \begin{matrix}T A \\ × \end{matrix} \begin{matrix}T (A ∧ B) \\ T A \\ T B \\ × \end{matrix}

(b) A ⊢ A ∨ (A ∧ B)

T A
F (A ∨ (A ∧ B))
F A
×

Problem 22

\begin{matrix}F (B → (¬(A → (¬ B)))) \\ T ((¬ A) → (¬ B)) \\ T B \\ F (¬(A → (¬ B))) \\ T (A → (¬ B)) \end{matrix} ; \begin{matrix}F (¬ A) \\ T A \end{matrix} ; \begin{matrix}F A \\ × \end{matrix} \begin{matrix}T (¬ B) \\ F B \\ × \end{matrix} \begin{matrix}T (¬ B) \\ F B \\ × \end{matrix}

Problem 32

\begin{matrix}F (A → (B ∨ C)) \\ T ((A → B) ∨ (A → C)) \\ T A \\ F (B ∨ C) \\ F B \\ F C \end{matrix} ; \begin{matrix}T (A → B) \\ \begin{matrix}F A \\ × \end{matrix} & \begin{matrix}T B \\ × \end{matrix} \end{matrix} \begin{matrix}T (A → C) \\ \begin{matrix}F A \\ × \end{matrix} & \begin{matrix}T C \\ × \end{matrix} \end{matrix}

\begin{matrix}T ((A → B) ∨ C) \\ T (A → ¬ C) \\ F ((B → C) → ¬ A) \\ T (B → C) \\ F (¬ A) \\ T A \end{matrix} ; \begin{aligned}& T (A → B) \\ \begin{matrix}F A \\ × \end{matrix} & \begin{aligned}& T B \\ \begin{matrix}F A \\ × \end{matrix} & \begin{matrix}T (¬ C) \\ F C \end{matrix} ; \begin{matrix}F B \\ × \end{matrix} \begin{matrix}T C \\ × \end{matrix} \end{aligned} \end{aligned} \begin{aligned}& T C \\ \begin{matrix}F A \\ × \end{matrix} & \begin{matrix}T (¬ C) \\ F C \\ × \end{matrix} \end{aligned}

Problem 52

\begin{matrix}T (A → (B ∨ C)) \\ F ((A → B) ∨ (A → C)) \\ F (A → B) \\ F (A → C) \\ T A \\ F B \\ T A \\ F C \end{matrix} ; \begin{matrix}F A \\ × \end{matrix} \begin{matrix}T (B ∨ C) \\ \begin{matrix}T B \\ × \end{matrix} & \begin{matrix}T C \\ × \end{matrix} \end{matrix}