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