Proving De Morgan’s with Indirect Proof

This is the last lesson to focus on sentential logic, which involves symbolizing entire sentences or propositions with single letters. So far, we have proven every rule of replacement except De Morgan’s. That’s what this lesson covers. Watch the video for a detailed presentation of the solutions that includes the strategy used to solve them, or just page past the video to examine the solutions directly. The next lesson will be turning from sentential logic to predicate logic, which uses different symbols for subjects and predicates.

From De Morgan's
Prove: ~(P ∨ Q) ≡ (~P & ~Q)
Click here for solution

1. | ~(P ∨ Q) // Assumption
2. || P // Assumption
3. || P ∨ Q // 2 Addition
4. || (P ∨ Q) & ~(P ∨ Q) // 1,3 Conjunction
5. | ~P // 2-4 Indirect Proof
6. || Q // Assumption
7. || Q ∨ P // 6 Addition
8. || P ∨ Q // 7 Commutation
9. || (P ∨ Q) & ~(P ∨ Q) // 1,8 Conjunction
10. | ~Q // 6-9 Indirect Proof
11. | ~P & ~Q // 5,10 Conjunction
12. ~(P ∨ Q) ⊃ (~P & ~Q) // 1-11 Conditional Proof
13. | ~P & ~Q // Assumption
14. || P ∨ Q // Assumption
15. || ~P // 13 Simplification
16. || Q // 14,15 Disjunctive Syllogism
17. || ~Q // 13 Simplification
18. || Q & ~Q // 16,17 Conjunction
19. | ~(P ∨ Q) // 14-18 Indirect Proof
20. (~P & ~Q) ⊃ ~(P ∨ Q) // 13-19 Conditional Proof
21. ~(P ∨ Q) ≡ (~P & ~Q) // 12,20 Biconditional Intro.

From De Morgan's,
Prove: ~(P & Q) ≡ (~P ∨ ~Q)
Click here for solution

1. | ~(P & Q) // Assumption
2. || ~(~P ∨ ~Q) // Assumption
3. || ~~P & ~~Q // 2 De Morgan’s
4. || P & Q // 3 Double Negation x2
5. || (P & Q) & ~(P & Q) // 1,4 Conjunction
6. | ~P ∨ ~Q // 2-5 Indirect Proof
7. ~(P & Q) ⊃ (~P ∨ ~Q) // 1-6 Conditional Proof
8. | ~P ∨ ~Q // Assumption
9. || P & Q // Assumption
10. || P // 9 Simplification
11. || ~~P // 10 Double Negation
12. || ~Q // 8,11 Disjunctive Syllogism
13. || Q // 9 Simplification
14. || Q & ~Q // 12,13 Conjunction
15. | ~(P & Q) // 9-14 Indirect Proof
16. (~P ∨ ~Q) ⊃ ~(P & Q) // 8-15 Conditional Proof
17. ~(P & Q) ≡ (~P ∨ ~Q) // 7,16 Biconditional Intro.

From De Morgan's,
Prove: ~(P & Q) ≡ (~P ∨ ~Q)
Click here for solution that doesn't use other version of De Morgan's

1. | ~(P & Q) // Assumption
2. || ~(~P ∨ ~Q) // Assumption
3. ||| ~P // Assumption
4. ||| ~P ∨ ~Q // 3 Addition
5. ||| (~P ∨ ~Q) & ~(~P ∨ ~Q) // 2,4 Conjunction
6. || P // 3-5 Indirect Proof
7. ||| ~Q // Assumption
8. ||| ~Q ∨ ~P // 7 Addition
9. ||| ~P ∨ ~Q // 8 Commutation
10. ||| (~P ∨ ~Q) & ~(~P ∨ ~Q) // 2,9 Conjunction
11. || Q // 7-10 Indirect Proof
12. || P & Q // 6,11 Conjunction
13. || (P & Q) & ~(P & Q) // 1,12 Conjunction
14. | ~P ∨ ~Q // 2-13 Indirect Proof
15. ~(P & Q) ⊃ (~P ∨ ~Q) // 1-14 Conditional Proof
16. | ~P ∨ ~Q // Assumption
17. || P & Q // Assumption
18. || P // 17 Simplification
19. || P ⊃ ~Q // 16 Material Implication
20. || ~Q // 18,19 Modus Ponens
21. || Q // 17 Simplification
22. || Q & ~Q // 20,21 Conjunction
23. | ~(P & Q) // 17-22 Indirect Proof
24. (~P ∨ ~Q) ⊃ ~(P & Q) // 16-23 Conditional Proof
25. ~(P & Q) ≡ (~P ∨ ~Q) // 15,24 Biconditional Introduction