In past lessons, we did proofs of various rules of replacement. In Introducing Conditional Proof, we did proofs of Tautology, then as homework, proofs of Transposition and the conjunctive forms of Commutation and Association. In Rules of Inference for Biconditionals, we did proofs of Material Equivalence. In Nesting Conditional Proofs, we did a proof of Exportation. And in Proving Disjunctions with Conditional Proof, we did proofs of the disjunctive forms of Commutation and Association. In this lesson, we are doing proofs of the rule of Distribution.
Distribution: Prove: (P & (Q ∨ R)) ≡ ((P & Q) ∨ (P & R)) [spoiler title=”Click for solution”]1. | P & (Q ∨ R) // Assumption 2. || ~(P & Q) // Assumption 3. || P // 1 Simplification 4. || Q ∨ R // 3 Simplification 5. || ~P ∨ ~Q // 2 De Morgan's 6. || ~~P // 3 Double Negation 7. || ~Q // 5,6 Disjunctive Syllogism 8. || R // 4,7 Disjunctive Syllogism 9. || P & R // 3,8 Conjunction 10. | ~(P & Q) ⊃ (P & R) // 1-9 Conditional Proof 11. | ~~(P & Q) ∨ (P & R) // 10 Material Implication 12. | (P & Q) ∨ (P & R) // 11 Double Negation 13. (P & (Q ∨ R)) ⊃ ((P & Q) ∨ (P & R)) // 1-12 Conditional Proof 14. | (P & Q) ∨ (P & R) // Assumption 15. || P & Q // Assumption 16. || Q // 15 Simplification 17. | (P & Q) ⊃ Q // 15-16 Conditional Proof 18. || P & R // Assumption 19. || R // 18 Simplification 20. | (P & R) ⊃ R // 18-19 Conditional Proof 21. | Q ∨ R // 14,17,20 Constructive Dilemma 22. || P & Q // Assumption 23. || P // 22 Simplification 24. | (P & Q) ⊃ P // 22-23 Conditional Proof 25. || P & R // Assumption 26. || P // 25 Simplification 27. | (P & R) ⊃ P // 25-26 Conditional Proof 28. | P ∨ P // 14,24,27 Constructive Dilemma 29. | P // 28 Tautology 30. | P & (Q ∨ R) // 21,29 Conjunction 31. ((P & Q) ∨ (P & R)) ⊃ (P & (Q ∨ R)) // 14-30 Conditional Proof 32. (P & (Q ∨ R)) ≡ ((P & Q) ∨ (P & R)) // 13,31 Biconditional Intro.[/spoiler] [spoiler title=”Click for shorter solution.”]1. | P & (Q ∨ R) // Assumption 2. | P // 1 Simplification 3. | Q ∨ R // 1 Simplification 4. || Q // Assumption 5. || P & Q // 2,4 Conjunction 6. | Q ⊃ (P & Q) // 3-4 Conditional Proof 7. || R // Assumption 8. || P & R // 2,7 Conjunction 9. | R ⊃ (P & R) // 7-8 Conditional Proof 10. | (P & Q) ∨ (P & R) // 3,6,9 Constructive Dilemma 11. (P & (Q ∨ R)) ⊃ ((P & Q) ∨ (P & R)) // 1-10 Conditional Proof 12. | (P & Q) ∨ (P & R) // Assumption 13. || P & Q // Assumption 14. || Q // 13 Simplification 15. | (P & Q) ⊃ Q // 13-14 Conditional Proof 16. || P & R // Assumption 17. || R // 16 Simplification 18. | (P & R) ⊃ R // 16-17 Conditional Proof 19. | Q ∨ R // 12,15,18 Constructive Dilemma 20. || P & Q // Assumption 21. || P // 20 Simplification 22. | (P & Q) ⊃ P // 20-21 Conditional Proof 23. || P & R // Assumption 24. || P // 23 Simplification 25. | (P & R) ⊃ P // 23-24 Conditional Proof 26. | P ∨ P // 12,22,25 Constructive Dilemma 27. | P // 26 Tautology 28. | P & (Q ∨ R) // 19,27 Conjunction 29. ((P & Q) ∨ (P & R)) ⊃ (P & (Q ∨ R)) // 12-28 Conditional Proof 30. (P & (Q ∨ R)) ≡ ((P & Q) ∨ (P & R)) // 11,29 Biconditional Intro.[/spoiler] Prove: (P ∨ (Q & R)) ≡ ((P ∨ Q) & (P ∨ R)) [spoiler title=”Click for solution.”]1. | P ∨ (Q & R) // Assumption 2. || ~P // Assumption 3. || Q & R // 1,2 Disjunctive Syllogism 4. || Q // 3 Simplification 5. | ~P ⊃ Q // 2-4 Conditional Proof 6. | ~~P ∨ Q // 5 Material Implication 7. | P ∨ Q // 6 Double Negation 8. || ~P // Assumption 9. || Q & R // 1,8 Disjunctive Syllogism 10. || R // 9 Simplification 11. | ~P ⊃ R // 8-10 Conditional Proof 12. | ~~P ∨ R // 11 Material Implication 13. | P ∨ R // 12 Double Negation 14. | (P ∨ Q) & (P ∨ R) // 7,13 Conjunction 15. (P ∨ (Q & R)) ⊃ ((P ∨ Q) & (P ∨ R)) // 1-14 Conditional Proof 16. | (P ∨ Q) & (P ∨ R) // Assumption 17. || ~P // Assumption 18. || P ∨ Q // 16 Simplification 19. || Q // 17,18 Disjunctive Syllogism 20. || P ∨ R // 16 Simplification 21. || R // 17,20 Disjunctive Syllogism 22. || Q & R // 19,21 Conjunction 23. | ~P ⊃ (Q & R) // 16-22 Conditional Proof 24. | ~~P ∨ (Q & R) // 23 Material Equivalence 25. | P ∨ (Q & R) // 24 Double Negation 26. ((P ∨ Q) & (P ∨ R)) ⊃ (P ∨ (Q & R)) // 16-25 Conditional Proof 27. (P ∨ (Q & R)) ≡ ((P ∨ Q) & (P ∨ R)) // 15,26 Biconditional Intro. [/spoiler]
We have three rules of replacement left to prove. These are Double Negation, De Morgan's, and Material Implication. What these share in common is the appearance of the negation operator, which we have been representing with a tilde. One of these can be proven with just the rules of inference, the rules of replacement, and conditional proof. The others, as far as I can tell, cannot. Before the next lesson, look into which one can be proven and try to prove it. In the next lesson, we will be learning about a method for proving the negation of our assumption, and we will use it in proofs for the rules of replacement we can't yet prove.
For Next Time, try to prove: Double Negation: P ≡ ~~P Material Implication: (~P ∨ Q) ≡ (P ⊃ Q) De Morgan's: ~(P & Q) ≡ (~P ∨ ~Q) ~(P ∨ Q) ≡ (~P & ~Q)
