Introducing Conditional Proof

Conditional Proof is used to prove a conditional, an if-then statement, such as

If an argument is sound, then it is valid.

This post assumes that you already know how to do proofs with the rules of inference and that you’re already familiar with material equivalence and the rules of replacement. What follows in this post is based on this video, which goes over some examples of conditional proof, then assigns some proofs for you to do on your own. If you would like to try the examples before seeing the solutions, just page down before watching the video. Solutions to the homework, and the video going over them, are at the bottom of this post.

To use conditional proof to prove a conditional, start by assuming its antecedent. Using its antecedent as a premise, construct a proof for its consequent. From the assumption of the antecedent to the conclusion of the consequent, each line of your argument should occur in a new scope. This is like scoping in programming languages. Here’s an example from PHP:

function set_a ($val) {
  local $a;
  $a = $val;
}
$a = 6;
set_a(5);
echo $a;

In this brief example, $a is used as both a global variable and as a local variable. If you don’t know any better, you might expect the last line to print 5, but it will actually print 6. This is because the variable $a in the function was at a higher scope than $a in the main part of the program. When the set_a function ended, its scope disappeared from the program, and whatever was set in that scope was no longer available. It will be like this in symbolic logic proofs too. When a scope closes, you can no longer use any lines from that scope in your proof. This restriction is to keep you from drawing illogical conclusions. With this restriction in place, conditional proof lets you make assumptions to prove conditionals without letting your prove anything you assume. Here is a brief summary of conditional proof:

To prove P ⊃ Q
Assume P
Derive Q
Conclude P ⊃ Q

In this first example, notice that I use the | to set off a new scope. When I close the scope, I cease to place the | at the beginning of the line. Once the scope is closed, the rule of conditional proof can be used on the whole scope to conclude a conditional whose antecedent is the assumption that started the new scope and whose consequent is the last line of the scope. You may not conclude anything from individual lines of a closed scope.

1. P ⊃ Q // Premise
Prove: P ⊃ (Q ∨ R)
2. | P // Assumption
3. | Q // 1,2 Modus Ponens
4. | Q ∨ R // 3 Addition
5. P ⊃ (Q ∨ R) // 2-4 Conditional Proof

From here on out, I will use a spoiler shortcode to hide the solutions in case you would like to try them before looking at them. If you need any help understanding the solutions, watch the video.

1. P ⊃ Q // Premise
2. (Q ∨ $) ⊃ (S & T) // Premise
Prove: P ⊃ S
Click to view solution.
3. | P // Assumption
4. | Q // 1,3 Modus Ponens
5. | Q ∨ R // 4 Addition
6. | S & T // 2,5 Modus Ponens
7. | S // Simplification
8. P ⊃ S // 3-7 Conditional Proof

1. P ⊃ Q // Premise
2. R ⊃ S // Premise
3. T ⊃ U // Premise
4. P ∨ (R ∨ T) // Premise
Prove: Q ∨ (S ∨ U)
Click to view solution.
5. | ~Q // Assumption
6. || ~S // Assumption
7. || ~P // 1,5 Modus Tollens
8. || R ∨ T // 4,7 Disjunctive Syllogism
9. || ~R // 2,6 Modus Tollens
10. || T // 8,9 Disjunctive Syllogism
11. || U // 3,10 Modus Ponens
12. | ~S ⊃ U // 6-11 Conditional Proof
13. | ~~S ∨ U // 12 Material Implication
14. | S ∨ U // 13 Double Negation
15. ~Q ⊃ (S ∨ U) // 5-14 Conditional Proof
16. ~~Q ∨ (S ∨ U) // 15 Material Implication
17. Q ∨ (S ∨ U) // 16 Double Negation

Prove: P ⊃ (P ∨ P)
Click to view solution.
1. | P // Assumption
2. | P ∨ P // 1, Addition
3. P ⊃ (P ∨ P) // 1-2 Conditional Proof

Without using Tautology,
Prove: P ≡ (P & P)
Click to view solution.
1. | P // Assumption
2. | P & P // 1,1 Conjunction
3. P ⊃ (P & P) // 1-2 Conditional Proof
4. | P & P // Assumption
5. | P // Simplification
6. (P & P) ⊃ P // 4-5 Conditional Proof
7. (P ⊃ (P & P)) & ((P & P) ⊃ P) // 3,6 Conjunction
8. P ≡ (P & P) // 7 Material Equivalence

Without using Tautology,
Prove: P ≡ (P ∨ P)
Click to view solution.
1. | P // Assumption
2. | P ∨ P // Addition
3. P ⊃ (P ∨ P) // 1-2 Conditional Proof
4. | P ∨ P // Assumption
5. || ~P // Assumption
6. || P // 4.5 Disjunctive Syllogism
7. || P ∨ ~(P ∨ P) // 6 Addition
8. || ~(P ∨ P) // 5,7 Disjunctive Syllogism
9. | ~P ⊃ ~(P ∨ P) // 5-8 Conditional Proof
10. | ~~(P ∨ P) // 4 Double Negation
11. | ~~P // 9,10 Modus Tollens
12. | P // 11 Double Negation
13. (P ∨ P) ⊃ P // 4-12 Conditional Proof
14. (P ⊃ (P ∨ P)) & ((P ∨ P) ⊃ P) // 3,13 Conjunction
15. P ≡ (P ∨ P) // 14 Material Equivalence

Homework

These proofs were assigned as homework at the end of the video. Solutions are hidden by spoiler shortcodes, and the video going over the solutions is embedded below the proofs.

Without using Commutation,
Prove: (P & Q) ≡ (Q & P)
Click to view solution.
1. | P & Q // Assumption
2. | P // 1 Simplification
3. | Q // 1 Simplification
4. | Q & P // 2,3 Conjunction
5. (P & Q) ⊃ (Q & P) // 1-4 Conditional Proof
6. | Q & P // Assumption
7. | Q // 6 Simplification
8. | P // 6 Simplification
9. | P & Q // 7,8 Conjunction
10. (Q & P) ⊃ (P & Q) // 6-9 Conditional Proof
11. ((P & Q) ⊃ (Q & P)) & ((Q & P) ⊃ (P & Q)) // 5,10 Conjunction
12. (P & Q) ≡ (Q & P) // 11 Material Equivalence

Without using Transposition,
Prove: (P ⊃ Q) ≡ (~Q ⊃ ~P)
Click to view solution.
1. | P ⊃ Q // Assumption
2. || ~Q // Assumption
3. || ~P // 1,2 Modus Tollens
4. | ~Q ⊃ ~P // Assumption
5. (P ⊃ Q) ⊃ (~Q ⊃ ~P) // 1-4 Conditional Proof
6. | ~Q ⊃ ~P // Assumption
7. || P // Assumption
8. || ~~P // 7 Double Negation
9. || ~~Q // 6,8 Modus Tollens
10. || Q // 9 Double Negation
11. | P ⊃ Q // 7-10 Conditional Proof
12. (~Q ⊃ ~P) ⊃ (P ⊃ Q) // 6-11 Conditional Proof
13. ((P ⊃ Q) ⊃ (~Q ⊃ ~P)) & ((~Q ⊃ ~P) ⊃ (P ⊃ Q)) // 5,12 Conjunction
14. (P ⊃ Q) ≡ (~Q ⊃ ~P) // 13 Material Equivalence

Without using Association,
Prove: (P & (Q & R)) ≡ ((P & Q) & R)
Click to view solution.
1. | (P & (Q & R)) // Assumption
2. | P // 1 Simplification
3. | Q & R // 1 Simplification
4. | Q // 3 Simplification
5. | R // 3 Simplification
6. | P & Q // 2,4 Conjunction
7. | (P & Q) & R // 5,6 Conjunction
8. (P & (Q & R)) ⊃ ((P & Q) & R) // 1-7 Conditional Proof
9. | (P & Q) & R // Assumption
10. | P & Q // 9 Simplification
11. | R // 9 Simplification
12. | P // 10 Simplification
13. | Q // 10 Simplification
14. | Q & R // 12,13 Conjunction
15. | P & (Q & R) // 11,14 Conjunction
16. ((P & Q) & R) ⊃ (P & (Q & R)) // 9-15 Conditional Proof
17. ((P & (Q & R)) ⊃ ((P & Q) & R)) & (((P & Q) & R) ⊃ (P & (Q & R))) // 8,16 Conjunction
18. (P & (Q & R)) ≡ ((P & Q) & R) // 17 Material Equivalence

1. P ⊃ Q // Premise
2. R ⊃ ~Q // Premise
Prove: ~(P & R)
Click to view first solution.
3. | P // Assumption
4. | Q // 1,3 Modus Ponens
5. | ~~Q // 4 Double Negation
6. | ~R // 2,5 Modus Tollens
7. P ⊃ ~R // 3-6 Conditional Proof
8. ~P ∨ ~R // 7 Material Implication
9. ~(P & R) // 8 De Morgans
Click to view second solution.
3. | Q // Assumption
4. | ~~Q // 3 Double Negation
5. Q ⊃ ~~Q // 3-4 Conditional Proof
6. ~Q ∨ ~~Q // 5 Material Implication
7. (P ⊃ Q) & (R ⊃ ~Q) // 1,2 Conjunction
8. ~P ∨ ~R // 6,7 Destructive Dilemma
9. ~(P & R) // 8 De Morgan’s

https://www.youtube.com/watch?v=LGYeqR4-S5I