Conditional Proof

 
The derivations we've constructed begin with premises, and derive subsequent lines using the rules of inference and the equivalence rules.  In this section and the next, we'll learn how to introduce assumptions into a derivation, and to use those assumptions in order to derive a desired wff.  Assumptions function like premises. Once introduced, we can use them just as we use premises or other lines to derive further wffs.  However, there are restrictions on their use. When we introduce an assumption in a derivation, we must eventually discharge the assumption before completing the derivation. We do that by using one of two special rules, the rule of conditional proof or the rule of indirect proof

The rule,  Conditional Proof  (CP) is used when we want to derive a conditional.  We begin using the rule by introducing an assumption, which is the antecedent of the conditional we wish to derive. We then proceed "normally", that is, using our rules of inference and equivalence rules, until we derive the consequent of the desired conditional. Finally, we invoke CP to infer the conditional.

Let's look at an example.  We'll use conditional proof to prove the following:

(R v S)
(S Q)
~R      
(P Q)

 

1. (R v S) premise  
2. (S Q) premise  
3. ~R premise  
4. P assump., cp SP1
5. S ds, 1, 3 SP1
6. Q mp, 2, 5 SP1
7. (P Q) cp 4-6  

Let's consider the way this derivation is different from any of our earlier derivations.  First, you'll note that the rule "cp" is given as a justification twice, first when we introduce the assumption at line 4, and at line 7 where we infer the conditional. Note too that this proof has a fourth column, for which there are entries only at lines 4-7. Lines 4-7 are the lines in which the assumption introduced in line 4 are in force. We call these lines a subproof, and we indicate that it's a subproof by the additional entry to the right of the justification.  We use "SP1" as an abbreviation for "subproof 1."  If we used conditional proof again later in the proof, we'd begin a new subproof and call it "SP2."  Until we use cp to infer the conditional, we must continue the subproof, which indicates that our assumption is still in force. When we use "cp," we discharge the assumption and bring the subproof to an end.

Here's an example where we can use conditional proof more than once:

(B & N)                
(A B) & (L N)

In earlier sections we have emphasized the importance of developing strategies when constructing proofs. Conditional Proof and Indirect Proof both require (and reward!) thinking about strategy. Let's see how that works with our current example. Consider the conclusion. It's a conjunction. We know that we can get a conjunction if we have both conjuncts, and we use conjoining. So how do we get the conjuncts? Each conjunct is a conditional. We know that the rule, "conditional proof" is designed to yield conditionals. So we'll do conditional proofs, one for each conditional. We'll then conjoin them, and we'll be done.  So here we go:

 

1. (B & N) premise  
2. A assump., cp SP1
3. B simp, 1 SP1
4. (A B) cp, 2, 3  
5. L assump., cp SP2
6. N simp 1 SP2
7. (L N) cp 5, 6  
8. (A B) & (L N) conj., 4,7  

 

Notice that we used "SP2" for "subproof 2" to distinguish it from the first subproof.  

We're now in a position to state formally a few restrictions on subproofs which we've obeyed, but haven't explicitly mentioned.  

  1. Any assumption made in a subproof must be discharged by using the rule cp. 

  2. Until cp is used and you infer the conditional whose antecedent is the assumption and whose consequent is the last line, you must indicate that the assumption is in play by using an "SP" indicator.  

  3. Assumptions, once discharged, can't be used in other parts of the proof. 

  4. In addition, you may not use any line which has a SP indicator outside the subproof in which it occurs.  

  5. Where you have multiple subproofs, you must discharge assumptions in the order reversing the order of introduction.  That is, always discharge the most recently introduced assumption first.

We'll see how this last restriction comes into play when we have nested subproofs in the following example:

(~Q  ~T)
(M v ~T)
(T & ~B)
(M S)                
(R ((P Q) & S))           

 

The conclusion of this argument is a conditional. We'll use conditional proof, assuming the antecedent, and deriving the consequent.  But the consequent is a conjunction whose left conjunct is a conditional. So we'll also use conditional proof to get that conditional.  Order is important here. Thinking backwards helps. The final line of the derivation will be the conditional (R ((P Q) & S)).  We'll derive that line by assuming R and deriving the consequent,  ((P Q) & S) by conditional proof.  So we can begin the proof by assuming R.  Then we can move to concentrating on deriving the consequent. As noted, since the consequent contains the conditional (P Q), so we can assume the antecedent of that conditional, namely P. But when we do that, we're still within the subproof introduced when we assumed R.  Thus we need to start a second subproof with the introduction of P. Finally, we must discharge our assumptions beginning with the last assumption and ending with the first. Here's the proof:

1.

(~Q  ~T) premise  
2. (M v ~T) premise  
3. (T & ~B) premise  
4. (M S) premise  
5. R assump, cp  SP1
6. P assump, cp SP1, SP2
7. T simp, 3 SP1, SP2
8. ~~T DN, 7 SP1, SP2
9. ~~Q mt, 1, 8 SP1, SP2
10. Q DN 9 SP1, SP2
11. (P Q) cp, 6-10 SP1
12. M ds, 2, 8 SP1
13.  S mp, 4, 12 SP1
14. (P Q) & S) conj, 11, 13 SP1
15. (R ((P Q) & S)) cp, 5-14  

Follow this proof in steps in Powerpoint

 

back
table of contents   List of Exercises