Deduction

E1

Find a proof of ((A ∨ B) ⇒ C) ≡ ((A ⇒ C) ∧ (B ⇒ C)).

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

E2

Find a proof of (A ⇒ B) ⇒ (B ⇒ A).

There is not such a proof: the formula is not a tautology.

E3

Find a proof of A ⇒ ¬¬A.

A ¬ A False ¬¬A A ⇒ ¬¬A

E4*

Find a proof of A ⇒ (A ∧ A).

A A A ∧ A A ⇒ (A ∧ A)

E5*

Find a proof of ((A ∨ B) ∧ (A ⇒ B)) ⇒ B.

A∨B A⇒B A B B B ((A ∨ B) ∧ (A ⇒ B)) ⇒ B

*E6

Find a proof of (A ∨ B) ⇒ ((A ⇒ C) ⇒ ((B ⇒ C) ⇒ C)).

A∨B A⇒C A C B⇒C B C C (B ⇒ C) ⇒ C (A ⇒ C) ⇒ ((B ⇒ C) ⇒ C) (A ∨ B) ⇒ ((A ⇒ C) ⇒ ((B ⇒ C) ⇒ C))

E7*

Find a proof of ((A ∧ B) ∧ C) ⇒ (A ∧ (B ∧ C)).

(A ∧ B) ∧ C A ∧ B A (A ∧ B) ∧ C A ∧ B B (A ∧ B) ∧ C C B ∧ C A ∧ (B ∧ C) ((A ∧ B) ∧ C) ⇒ (A ∧ (B ∧ C))

*E8

Find a proof of ((A ⇒ C) ∧ (B ⇒ C)) ⇒ ((A ∨ B) ⇒ C).

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

E9*

Find a proof of ((A ∨ B) ∧ (A ∨ ¬B)) ⇒ A.

(A ∨ B) ∧ (A ∨ ¬B) A ∨ B A (A ∨ B) ∧ (A ∨ ¬B) A ∨ ¬B A ¬B B False A A A ((A ∨ B) ∧ (A ∨ ¬B)) ⇒ A

E10*

Find a proof of ((A ∨ ¬B) ∧ B) ⇒ A.

(A ∨ ¬B) ∧ B A ∨ ¬B A ¬B B False A A ((A ∨ ¬B) ∧ B) ⇒ A

E11*

Find a proof of ((A ⇒ B) ∧ (B ⇒ ¬A)) ⇒ ¬A.

(A ⇒ B) ∧ (B ⇒ ¬A) B ⇒ ¬ A (A ⇒ B) ∧ (B ⇒ ¬A) A ⇒ B A B ¬A A False ¬A ((A ⇒ B) ∧ (B ⇒ ¬A)) ⇒ ¬A

E12*

Find a proof of ((A ⇒ ¬B) ∧ B) ⇒ ¬A.

(A ⇒ ¬B) ∧ B A ⇒ ¬ B A ¬B B False ¬A ((A ⇒ ¬B) ∧ B) ⇒ ¬A

E13

Find a proof of ¬¬A ⇒ A.

¬A ¬¬ A False A ¬¬A ⇒ A

E14

Find a proof of ((A ⇒ B) ⇒ A) ⇒ A.

A ¬ A False B A ⇒ B A ⇒ B (A ⇒ B) ⇒ A A ¬A False ¬(A ⇒ B) False A ((A ⇒ B) ⇒ A) ⇒ A

E15

Find a proof of ((A ⇒ B) ∨ C) ⇒ ((A ⇒ C) ∨ B).

(A ⇒ B) ∨ C A⇒B A B (A ⇒ C) ∨ B ¬((A ⇒ C) ∨ B) False C A⇒C A ⇒ C (A ⇒ C) ∨ B ¬((A ⇒ C) ∨ B) False ¬(A⇒C) False (A ⇒ C) ∨ B C A ⇒ C (A ⇒C) ∨ B (A ⇒ C) ∨ B ((A ⇒ B) ∨ C) ⇒ ((A ⇒ C) ∨ B)

Monica Nesi