Indirect Proof
Like conditional proof, indirect proof is a rule which allows us to temporarily introduce an assumption into a derivation, where the assumption remains in force through the subproof; we discharge that assumption with the application of the rule.
Here's how indirect proof works: Suppose we wish to derive some proposition a. We introduce ~a as an assumption, and then attempt to derive a contradiction, that is a wff of the form (b & ~b). Then, by the rule indirect proof, we infer the negation of our assumption, namely a. We can use indirect proof (ip) anywhere in our proof, either to reach our final conclusion, or any intermediate goal. The restrictions on subproofs introduced for conditional proof apply here as well.
We used conditional proof to derive conditionals. Indirect proof is more general. It can be used to derive any wff whatsoever, as long as that wff is derivable!
Let's prove the same argument we did at the beginning of the last section, though now with indirect proof instead of conditional proof :
| (R v S) |
| (S ⊃ Q) |
| ~R |
| (P ⊃ Q) |
After listing the premises, we assume the negation of what we want to prove on line 4.
| 1. | (R v S) | premise | |
| 2. | (S ⊃ Q) | premise | |
| 3. | ~R | premise | |
| 4. | ~(P ⊃ Q) | assump., ip | SP1 |
| 5. | ~(~P v Q) | CE, 4 | SP1 |
| 6. | (~~P & ~Q) | DEM, 5 | SP1 |
| 7. | ~Q | simp, 6 | SP1 |
| 8. | ~S | mt, 2, 7 | SP1 |
| 9. | R | ds, 1,8 | SP1 |
| 10. | R & ~R | conj, 3, 9 | SP1 |
| 11. | (P ⊃ Q) | ip 4-10 |
Our goal is to derive a contradiction. This simplifies our proof strategy considerably. Just go for the easiest contradiction. Since a contradiction is a conjunction, we look for each conjunct. We already have ~R as a premise. If we can derive R we've got our contradiction. And R is derivable if we can get ~S and use dilemma. We get ~S from ~Q and an application of modus tollens. We get ~Q by using conditional exchange and DeMorgan's successively from line 4.
We've covered all the rules for constructing proofs in propositional logic. We now have the rules to prove any argument which is capable of proof. This feature of our proof theory is called completeness, and we'll explain it in detail in the final section of this chapter. But first take the time to do many proofs. The following exercise will give you lots of practice.
 |
 |