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)