Proving Distribution with Conditional Proof

Last updated: Sunday, May 26, 2019

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))

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.

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.


Prove: (P ∨ (Q & R)) ≡ ((P ∨ Q) & (P ∨ R))

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.

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)