Proving Disjunctions with Conditional Proof

Here we look at how to prove disjunctions through conditional proof. This lesson is available as a video or as text. Scroll past the video for the text version.

First, let’s take a look at the rule of material implication.

Material Implication:
(P ⊃ Q) ≡ (~P ∨ Q)

This rule shows that a conditional is materially equivalent to a disjunction where the first disjunct is the negation of the conditional’s antecedent, and the second disjunct is the consequent of the conditional. Remember that the conditional here is just a material conditional. It expresses relations between truth values, not cause and effect. Even though it doesn’t richly capture what we always mean by “If … then …”, it normally captures the logically relevant characteristics of if-then statements. A conditional is true for three combinations of truth values, and so is a disjunction. When we negate the first disjunct of a disjunction, its truth values line up with those of a conditional, as seen in this truth table for material implication.

Using the rule of material implication, we can prove a disjunction like so:

To Prove ~P ∨ Q:

1. Assume P
2. Derive Q
3. Infer P ⊃ Q with Conditional Proof
4. Infer ~P ∨ Q with Material Implication

This works well for a disjunction that is already in the form that corresponds to a conditional. But what if we want to prove one of the form P ∨ Q instead?

To Prove P ∨ Q

1. Assume ~P
2. Derive Q
3. Infer ~P ⊃ Q with Conditional Proof
4. Infer ~~P ∨ Q with Material Implication
5. Infer P ∨ Q with Double Negation

This is essentially the same with the additional step of double negation.

Without using Commutation for disjunctions, prove it:
(P ∨ Q) ≡ (Q ∨ P)

 1. | P ∨ Q // Assumption

 2. || ~Q // Assumption

 3. || P // 1,2 Disjunctive Syllogism

 4. | ~Q ⊃ P // 2-3 Conditional Proof

 5. | ~~Q ∨ P // 4 Material Implication

 6. | Q ∨ P // 5 Double Negation

 7. (P ∨ Q) ⊃ (Q ∨ P) // 1-6 Conditional Proof

 8. | Q ∨ P // Assumption

 9. || ~P // Assumption

10. || Q // 8,9 Disjunctive Syllogism

11. | ~P ⊃ Q // 9-10 Conditional Proof

12. | ~~P ∨ Q // 11 Material Implication

13. | P ∨ Q // 12 Double Negation

14. (Q ∨ P) ⊃ (P ∨ Q) // 8-13 Conditional Proof

15. (P ∨ Q) ≡ (Q ∨ P) // 7,14 Biconditional Intro.

Without using Association,
Prove the rule of Association for disjunctions:
Prove: (P ∨ (Q ∨ R)) ≡ ((P ∨ Q) ∨ R)

1. | P ∨ (Q ∨ R) // Assumption

2. | | ~(P ∨ Q) // Assumption

3. | | ~P & ~Q // 2 De Morgan’s

4. | | ~P // 3 Simplification

5. | | Q ∨ R // 1,4 Disjunctive Syllogism

6. | | ~Q // 3 Simplification

7. | | R // 5,6 Disjunctive Syllogism

8. | ~(P ∨ Q) ⊃ R // 2-7 Conditional Proof

9. | ~~(P ∨ Q) ∨ R // 8 Material Implication

10. | (P ∨ Q) ∨ R // 9 Double Negation

11. (P ∨ (Q ∨ R)) ⊃ ((P ∨ Q) ∨ R) // 1-10 Conditional Proof

12. | ((P ∨ Q) ∨ R) // Assumption

13. | | ~(Q ∨ R) // Assumption

14. | | ~Q & ~R // 13. De Morgan’s

15. | | ~R // 14 Simplification

16. | | P ∨ Q // 12,15 Disjunctive Syllogism

17. | | ~Q // 14 Simplification

18. | | P // 16,17 Disjunctive Syllogism

19. | ~(Q ∨ R) ⊃ P // 12-18 Conditional Proof

20. | ~~(Q ∨ R) ∨ P // 19 Material Implication

21. | (Q ∨ R) ∨ P // 20 Double Negation

22. | P ∨ (Q ∨ R) // 21 Commutation

23. ((P ∨ Q) ∨ R) ⊃ (P ∨ (Q ∨ R)) // 12-22 Conditional Proof

24. (P ∨ (Q ∨ R)) ≡ ((P ∨ Q) ∨ R) // 11,23 Biconditional Intro.

For the next two lessons, try to prove these:

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

Material Implication
(~P ∨ Q) ≡ (P ⊃ Q)