Proving De Morgan’s laws with natural deduction

1. ~(A ^ B) -> ~A v ~B
2. ~(A v B) -> ~A ^ ~B

Proof for 1.1

01. ~(A ^ B)
02.     ~(~A v ~B)                     [assume]
03.         ~A                         [assume]
04.         ~A v ~B                    [3, vI]
05.     A                              [RAA 3,4,2]    
06.         ~B                         [assume]
07.         ~A v ~B                    [6, vI]
08.     B                              [RAA 6,7,2]
09.     A ^ B                          [5,8, ^I]
10. ~A v ~B                            [RAA 2,9,1]
11. ~(A ^ B) -> ~A v ~B             [1,10, ->I]

Proof for 1.2

01. ~A v ~B
02.     ~A                             [assume]
03.         A ^ B                      [assume]
04.         A                          [3, ^E]
05.     ~(A ^ B)                       [RAA 3,4,2]
06. ~A -> ~(A ^ B)                     [2,5 ->I]
07.     ~B                             [assume]
08.         A ^ B                      [assume]
09.         B                          [8, ^E]
10.     ~(A ^ B)                       [RAA 8,9,7]
11. ~B -> ~(A ^ B)                     [7, 10 ->I]
12. ~A v ~B -> ~(A ^ B)                [1,6,11 vE]

Proof for 2.1

01. ~(A v B)
02.     A
03.     A v B
04. ~A
05.     B
06.     A v B
07. ~B
08. ~A ^ ~B
09. ~(A v B) -> ~A ^ ~B

Proof for 2.2

01. ~A ^ ~B
02. ~A
03. ~B
04.     A v B
05.     A
06.     -contr
07.     B
08.     -contr
09. ~(A v B)
10. ~A ^ ~B -> ~(A v B)
|