Unit 9

UNIT9

Conditional Proof

and Indirect Proof

A. INTRODUCTION

In this unit we will be rounding out our rule system for sentential logic with two

very powerful rules that are designed for very special purposes and that have a

structure quite different from the rules you have learned so far. These rules are

Conditional Proof (C.P.), which, as its name indicates, is used to prove condition-

als, and Indirect Proof (J.P.), which is used to prove negations. These rules differ

radically from the ones you have learned so far in that they do not have premises

in the usual sense. How, you may reasonably ask, can we infer something when we

have no premises from which to infer it? The answer is that in both these rules we

make assumptions and then see what follows from the assumptions. In Conditional

Proof, we assume the antecedent of the conditional we wish to prove and see

whether the consequent follows. If it does, we may infer the conditional itself. In

Indirect Proof, we assume the opposite of what we want to prove and see whether

this leads to a contradiction. If it does, then that assumption, the opposite of the de-

sired conclusion, must be rejected, and so we may infer the conclusion itself.

Both these rules are extremely powerful and can be used in a wide variety of

proof constructions, and they will considerably simplify the proof process. Once

you have learned these rules, you will find that your proofs go much more quickly

and are much easier and more "natural" to construct. Using these rules, it will be

easier to figure out strategies and to see where you are going; in particular, the

working-backward method will be greatly enhanced. Both rules are used frequently

in everyday life, and both have a long history in formal logic and mathematics; the

175176 Unit 9 Conditional Proof and Indirect Proof

rule of I.P., for instance, has been used explicitly for millennia under the name

Reductio ad absurdum (reducing an assumption to an absurdity).

Because these rules require no previously given premises, they can be used

in a special kind of proof: proofs without premises, which are used to derive theo-

rems. A theorem is simply a formula that can be proved without any initially given

premises. Theorems are "obvious truths" such as «p' q) ::J p) (if both p and q,

then p), and, in fact, as we shall see at the end of the unit, the set of theorems turns

out to be exactly the same as the set of tautologies. We will now need a new defi-

nition of proof, since, included among the steps in our proof, we will have as-

sumptions as well as premises and derived lines. What you will need to master in

this unit is listed below.

B. UNIT 9 OBJECTIVES

• Learn the rules of Conditional Proof (C.P.) and Indirect Proof (I.P.) in their

symbolic forms and understand the explanations that accompany them.

• Learn the restrictions that apply to the rules of C.P. and I.P.

• Be able to use the rule of c.P. in constructing proofs.

• Be able to use the rule of I.P. in constructing proofs.

• Learn the definition of theorem and be able to construct proofs of theorems.

• Learn the new definitions of justified step and proof

• Be able to demonstrate that an argument is invalid.

C. UNIT 9 TOPICS

1. Conditional Proof

A conditional is a formula that asserts that if one thing (say, A) is the case,

then another (say, B) is the case. As we saw in Unit 8, one way to prove a condi-

tional is to derive the corresponding disjunction and then use C.E., but this is not a

particularly direct or intuitive way to validate if-then statements. A far simpler and

more direct method is just to assume that the first thing, A, is the case, and then to

see whether the second, B, follows from that assumption. If it does, then we are

justified in concluding that if A, then B, that is, (A ::J B). This, in a nutshell, is the

rule of Conditional Proof: to prove a conditional (A ::J B), simply assume A tem-

porarily and see whether, given A, B follows. If it does, then you are permitted to

infer (A ::J B). There is nothing especially mysterious about the rule of c.P .. (al-

though it may take some practice to catch on to how it works); it simply reflects

the meaning of the conditional: if-then.

Let us now take a rather simple example to demonstrate the application of

the rule of Conditional Proof.Unit 9 Conditional Proof and Indirect Proof 177

a. 1.

2.

3.

4.

5.

6.

(A V B) :) (C· D)

[~VB

C·D

C

A:)C

Pr./". A:)C

Assp. (C.P.)

Add. 2

M.P. 1,3

Simp. 4

C.P.2-5

Notice that we have assumed A, since this is the antecedent of the condi-

tional we are trying to prove, and, given A, we have been able to deduce the con-

sequent C. Thus, at step 6 we are permitted to infer (A :) C), because we have

shown in steps 2 through 5 that indeed if A is the case, then so is C. In using c.P.,

remember that you must always assume the antecedent of the conditional you

want to prove.

Note also that we have here set in our assumption and the steps that followed

from it and marked them off with an arrow and a vertical line. As we will empha-

size later, assumptions are not on a par with the given premises; premises are

given for the duration of the proof, whereas assumptions are only temporary and

are made for very specific purposes. (Here, for instance, we assumed A to see

whether C would follow.) To emphasize this difference between premises and as-

sumptions, we will always set in the assumption and what follows from it and

mark it off with an arrow and a vertical line. Note also that we must always justify

our assumptions, like every other step in a proof. We will justify an assumption

simply by noting that it is an assumption (which we will abbreviate Assp.) and in-

dicating whether the assumption is for c.P. or LP.

The rule of C.P. will help you enormously in constructing proofs of condi-

tionals, especially where premises and conclusion are rather complex. Instead of

having to manipulate long and complicated formulas, using our most complex

rules, you are permitted to assume just the antecedent, a simpler formula, which

then makes it possible to break the proof down into easier bits. At the end of the

last unit you were given a rather complex example, and it was suggested that you

try to carry out the proof with only your basic rules and replacement rules. If you

tried (and succeeded), you discovered that it required almost 30 steps and that

those steps required the frequent use of one of your more complex rules, Distrib-

ution. Furthermore, there was no very good way of planning strategy, no natural

way to "reason through" the proof; without c.P. on problems like this, it is often

just a matter of perseverance and blind luck. If you happen to hit on the right

combination, well and good; if not, you may go round in circles indefinitely. The

rule of Conditional Proof is by far the more rational approach to problems like this,

and since logic is supposed to be a rational discipline, C.P. is the appropriate

strategy. Let us use this rule, then, in constructing a proof of that rather refractory

problem from the last unit.178 Unit 9 Conditional Proof and Indirect Proof

b. 1. (A V B) :J ~ (C V D)

2. ( ~ C . E) :J (F • ~ 0)

3. (F V H) :J (J . ~ K)

Pro

Pro

Pro I .'. (A· E) :J ~ K

Here the antecedent of the conclusion is (A • E), and since our assumption

for c.P. will always be the antecedent, at step 4 we may assume (A • E). Given that

assumption, the consequent ~ K follows quite directly (assuming you learned the

material in the last two units), so we can infer the conclusion, (A· E) :J ~ K, at

step 17.

4. 

A·E 

Assp. (C.P.)

5. 

A 

Simp. 4

6. 

E 

Simp. 4

7. 

AvB 

Add. 5

8. 

~(Cv D) 

M.P. 1,7

9. 

~C·~D 

DeM.8

10. 

~C 

Simp. 9

11. 

~C·E 

Conj.6,10

12. 

F·~O 

M.P. 2,11

13. 

F 

Simp. 12

14. 

FvH 

Add. 13

15. 

J·~K 

M.P. 3,14

16. 

~K 

Simp. 15


17. (A· E):J ~ K 

C.P.4-16


Note that this proof is just half as long as the one that did not make use of

Conditional Proof. Note also that, given the assumption (A· E), we are able to use

all our most basic rules-Simp., Add., M.P.-instead of the rather complicated re-

placement rules we would have to use otherwise. Not only are proofs generally

shorter using c.P., but they are almost always easier as well.

Now that you have seen some examples of the way in which Conditional

Proof works, it is time to state the rule itself.

CONDITIONAL PROOF (C.P.)

If, given the assumption p, we are able to derive q, then we

are allowed to infer (p :J q), citing all the steps from p to q

inclusive.

1.'.p:JqUnit 9 Conditional Proof and Indirect Proof 179

In using C.P., it is important to remember that the conclusion of the rule must

always be a conditional; this is why it is called Conditional Proof. You may then go

on to use the conditional in other inferences-it could be a premise for H.S., for in-

stance-but the immediate conclusion of the rule will be a horseshoe formula. Also,

as noted, you must always assume the antecedent of the conditional you are trying

to prove and then derive the consequent. It is essential, of course, that you be able

to figure out what the antecedent and consequent of the formula are; this is a matter

of being able to analyze structure. Some examples are given below. To prove

((A =:; B) =:; C) assume (A =:; B), derive e

(A =:; (B =:; e)) assume A, derive (B =:; e)

((A =:; B) =:; e) =:; (D =:; F) assume ((A =:; B) =:; e), derive (D =:; F)

((A' B) =:; e) =:; (A =:; (B =:; e)) assume ((A' B) =:; e), derive (A =:; (B =:; e))

(A =:; B) =:; (e =:; (A =:; (B =:; e))) assume (A =:; B), derive (e =:; (A =:; (B =:; e)))

As noted earlier, we will set in the assumption and all the steps leading to the

consequent we are trying to derive and mark them off by an arrow and a vertical

line. We will call the sequence of steps set in and marked off by this vertical line a

subproof, since it is really a little proof within a proof (just as a subformula is a for-

mula within a formula); it demonstrates (for C.P.) that if the antecedent is true,

then the consequent is true. The first step of a subproof for c.P. will be the as-

sumption-the antecedent of the conditional to be proved-and the last step of the

subproof will be the consequent of the conditional.

Another important and closely related concept is the scope of an assumption,

which is roughly its extent or for how long it is operative, for how long we are as-

suming it. The scope of an assumption includes all (and only) the steps of the sub-

proof and is indicated by the arrow and vertical line. This concept will be

especially important when we talk about discharging assumptions.

The arrow and vertical line, which we will call the scope marker, must be in-

cluded in any application of C.P. or LP., the rules in which we make assumptions.

It is essential in such proofs to know exactly how far the scope of the assumption

extends, and it is the scope marker that gives us this information. These scope

markers will also be extremely useful as visual aids and will help you to plot strat-

egy and keep your assumptions straight, especially in proofs with several uses of

C.P. and LP.

Finally, in the step in which we apply C.P.-in which we infer the conditional

we wanted to prove-we will cite all the steps included in the subproof. This is be-

cause no one step suffices to show that the antecedent implies the consequent; it is

all the steps taken together that do this, and so we cite them all.

It is perfectly possible to use more than one application of c.P. within a sin-

gle proof, just as you may use more than one application of M.P. or Add. There are

c. 1. A :J (B :J C) 


~B:J~A 

Assp. (C.P.)

A 

Assp. (C.P.)

A:JB 

Contrap.2

B 

M.P. 3,4

B:JC 

M.P. 1,3

C 

M.P. 5,6

A:JC 

C.P.3-7

(~ B :J ~ A) :J (A :J C) 

C.P.2-8


180 Unit 9 Conditional Proof and Indirect Proof

some restrictions on this procedure, but these will be discussed in more detail in a

later section; here it will be sufficient to note that it is possible and to give one

rather simple example.

Pr. j ... (~B :J ~ A) :J (A :J C)

2. 3. 4. 5. 6. 7. 8. 9. At step 2, we assumed (~ B :J ~ A) because that was the antecedent of the

conclusion we wanted to prove. Given that assumption, we wanted to derive the

consequent of our conclusion, (A :J C). Since this is also a conditional, we can

use C.P. to prove it, which means assuming its antecedent, which is just A, and try-

ing to derive its consequent, which is C. Thus we assumed A at step 3. Given the

two assumptions, we were able to derive C at step 7, which showed that if A then

C. Thus we were entitled to infer (A :J C) at step 8. Then, since we did derive the

consequent of the conclusion of our problem from its antecedent, we were entitled

at step 9 to infer the entire conclusion. We will see more such problems, with as-

sumptions inside assumptions, in later sections.

2. Indirect Proof

The rule of Indirect Proof (LP.) has a structure similar to that of c.P.-we

also make an assumption-but its intent is a little different. In LP., which is some-

times called the rule of Reductio ad absurdum (reducing to an absurdity), we try to

show that the assumption we make has absurd consequences, leads to a contradic-

tion. Why would we want to do this? Well, sometimes it is very difficult to prove

your conclusion directly, just by applying the rules of inference you have learned

so far. In these cases, the best way to proceed is often to assume the opposite of

what you want to prove and show that it results in a contradiction. If you want to

prove ~ A, for instance, and can see no direct method of proceeding from premises

to conclusion, you can try an indirect proof by assuming A and seeing whether this

assumption leads to a contradiction. If it does, your assumption, A, must be wrong,

since it leads to absurd consequences; thus you are permitted to infer the negation

of what you assumed, namely, ~ A, which is the conclusion you wanted.Unit 9 Conditional Proof and Indirect Proof 181

An example of a proof using the rule of I.P. is worked out below.

d. 1. N~O Pro

2. (NoO) ~ p Pr.

3. p~ ~O

Pr./".~N

4. N Assp. (I.P.)

5. 6. 7. 8. 0 M.P. 1,4

NoO Conj.4,5

p M.P. 2,6

~O M.P. 3,7

9. Oo~O Conj. 5,8

10. ~N I.P.4-9

Here the assumption N is shown in steps 4 through 9 to lead to a contradiction; it

results in both 0 and ~ o. Thus N cannot be the case, and we are permitted to infer

~ N by I.P. Notice that here, as in C.P., we cite all the steps 4 through 9, which,

taken together, show that N results in a contradiction.

We may state the rule of I.P. schematically as follows:

INDIRECT PROOF (I.P.)

p

If, given an assumption p, we are able to derive a contradiction

(q 0 ~ q), then we may infer the negation of our assumption, ~ p,

citing all the steps from p to (q 0 ~ q) inclusive.

Just as in C.P., there is a certain pattern in the use of I.P., and certain condi-

tions that must be fulfilled. First, the conclusion of 1.P' is always a negation, the

negation of what was assumed, just as the conclusion of c.P. is always a condi-

tional. Second, when using I.P., always assume the opposite of what you want to

prove. If you want to prove the negation ~ p, simply assume p, and if you want to

prove an unnegated formula p, assume ~ p. In the latter case, if you assume ~ p

and derive a contradiction, you will be able to infer ~ ~ p by I.P., and p will fol-

low by D.N. Thefirst step in the subprooffor J.P., then, will be the opposite of the

conclusion you wish to derive. Finally, the last step in the subproof for 1.P' is a

contradiction.182 Unit 9 Conditional Proof and Indirect Proof

A contradiction, for purposes of I.P., is simply any formula conjoined to

its negation. 1 (A • ~ A) is a contradiction, but so is (A B)' ~ (A B), and so is

(A v (B' C))· ~ (A v (B' C)). The contradiction need not be just a single letter

and its negation. But beware: there are certain combinations that may look like

contradictions, but that are not, such as (A ~ B) • (A ~ ~ B). Here only part of the

first formula is negated in the second, but to be a contradiction, the whole of the

first conjunct must be negated in the second conjunct. A "proper" contradiction

would be (A ~ B)' ~ (A ~ B), where the second conjunct is exactly the negation

of the first. Finally, the contradiction you derive may include the assumption itself.

If you assume A, and manage to get ~ A, the conjunction A • ~ A is a perfectly

good contradiction and will allow you to conclude ~ A by I.P. An example in

which this situation occurs is given below.

e. 1. A ~ ~(BvC) Pro

2. (~Bv ~ D) ~ F Pro

3. F~~A Pro I:. ~A

4. A Assp. (I.P.)

5. ~ (B v C) M.P. 1,4

6. ~B'~C DeM.5

7. ~B Simp. 6

8. ~Bv~D

Add. 7

9. F M.P. 2,8

10. ~A

M.P. 3,9

11. A'~A

Conj.4,10

12. ~A

I.P.4-11

Notice here that we are not finished with the proof at step 10, even though

we have derived ~ A. The reason is that we have not yet discharged our assump-

tion; that is, we are still within the subproof, and no proof is complete until all as-

sumptions have been discharged. More will be said about this in the next section.

Another example of the use of I.P. is the following, in which the conclusion

is a negated compound.

f. 1. A ~ (~ F ~ D) Pro

2. D ~ «B v ~ C) ~ F) Pro

3. ~ (E ~ F) Pro I:. ~ (A . B)

I Such a formula will also be a contradiction in the sense of Unit 6: a statement whose form is false

for every substitution instance.

A·B 

Assp. (I.P.)

A 

Simp. 4

B 

Simp. 4

~F-:JD 

M.P. 1,5

~ (~EvF) 

C.E.3

~ ~E'~ F 

DeM.8

~F 

Simp. 9

D 

M.P. 7,10

(Bv~ C) -:J F 

M.P. 2,11

Bv~C 

Add. 6

F 

M.P. 12,13

F'~F 

Conj.14,10

16. ~ (A' B) I.P.4-15



Unit 9 Conditional Proof and Indirect Proof 183

4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. Notice here that our conclusion is the negation of the entire conjunction, not

just of one of the conjuncts. To conclude ~ A, or (~ A • ~ B), would be incorrect,

since it is the conjunction (A • B) that led to the contradiction and that must there-

fore be rejected.

The rules of C.P. and I.P. may be used at any point in a proof, as may any of

our other rules. You may need to prove a negation or a conditional in the middle of

a proof and, if so, it is perfectly correct to make use of the rules in this way. An as-

sumption for C.P. or I.P. may be introduced at any point in a proof (except for the

last step, since then, by definition, it would not be the last step, as we shall see in

the next section). Furthermore, we may introduce assumptions within assump-

tions, use C.P. inside an assumption for I.P., and vice versa. There is no limit (the-

oretically) to the number of assumptions we may make in a proof, provided we

discharge them all, as we will see in the next section.

At this point we need to revise our definitions of justified step and proof. In Unit

7 we defined a proof as a sequence of justified steps that resulted in the conclusion,

and a justified step was defined as either a premise or else a step that was derived

from previous steps by application of one of the given rules of inference. At this point,

however, we can also make assumptions, and our definition must be modified to ac-

commodate these new steps. The modification is very simple and is exactly what you

would expect; we will just add to our definition of justified step the assumptions we

can now make. Thus, our new definition must read: a justified step is either a premise,

or an assumption, or else a step that follows from previous steps according to one of

the given rules of inference. A proof is still a derivation (a sequence of justified steps)

in which the last step is the desired conclusion, but we could also define it now as a

sequence of steps, each of which must be either a premise, or an assumption, or a step

that follows from previous steps according to one of the given rules of inference, and

such that the last step in the sequence is the desired conclusion.184 Unit 9 Conditional Proof and Indirect Proof

3. Discharging Assumptions; Restrictions on c.P. and I.P.

An assumption for C.P. or I.P. is not on the same footing as a premise. A

premise is given "for keeps," at least within a certain problem, whereas an as-

sumption is only temporary. An assumption is made for a particular purpose: in

C.P. to see whether the consequent follows from the antecedent, and in I.P. to see

whether a contradiction follows. Once it has served its purpose, that is, once the

consequent (for c.P.) or the contradiction (for I.P.) has been derived, it must be ren-

dered inoperative, or discharged. The notion of discharging an assumption fits

hand in glove with the concept of the scope of an assumption, the set of steps from

the assumption through the consequent or contradiction. To discharge an assump-

tion is simply to cut off the scope of that assumption, to end the subprooj Once we

reach the last step in the subproof, we have reached our goal, we know what hap-

pens given the assumption; at this point, since the assumption is no longer needed,

we discharge it.

Note that the conclusion of C.P. or I.P., the conditional or negation, is not in-

cluded within the scope of the assumption, does not occur within the subproof.

This is because it is not derived from that assumption, but rather, sums up the re-

sults of the subproof, "describes" in a way (a highly metaphorical way) what has

gone on in the subproof, reflects a kind of "overview" of the subproof. Thus it

does not occur within the subproof itself, but rather, falls outside it. We look over

the completed subproof and then write down outside the subproof the results of

our investigation.

We will say, then, that the assumption is discharged at the step in which we

apply c.P. or 1.P' In example f, for instance, where we used Indirect Proof, the as-

sumption is discharged at step 16, where we apply I.P. to conclude ~ (A' B), and

in example a, our first c.P. example, the assumption is discharged at step 6, where

we used C.P. to infer (A :J C).

There are certain restrictions related to the notion of discharging an assump-

tion. First, every assumption made in a proof must eventually be discharged. The

reason for this is that in a proof the goal is to derive the conclusion from the given

premises and no others. If we left assumptions undischarged, we would in effect be

adding further premises and would not be giving an answer to the problem posed.

Second, and just as important, once an assumption has been discharged you may

not use that assumption or any step that falls within the scope of that assumption

again. The steps derived within the scope of an assumption should be thought of

as just temporary, as steps derived for the particular purposes of C.P. or I.P. Once

they have done their job of generating the consequent of the conditional (for C.P.)

or the contradiction (for I.P.), they are out of the picture, as is the assumption itself.

This is reasonable, since these steps were derived only given that assumption,

and once the assumption has been discharged, we are no longer operating under itsUnit 9 Conditional Proof and Indirect Proof 185

scope, or influence. Thus we have no right to the steps derived from that assumption.

So, again, once the assumption has been discharged, neither it nor any step that

falls within its scope may be used again. Another way to put this is to say that once

the assumption has been discharged, no step in its subprooj may be used again. An

instance of this kind of error is made in the "proof' below.

g. 1. (A v B) =:) C Pro

2. (F v G) =:) R Pro / .'. C·R

4. Add. 3

3. GVB Assp. (C.P.)

5. M.P. 1,4

6. A=:)C C.P.3-5

7.

Assp. (C.P.)

S. Add. 7

[~VG

9. M.P.2,S

10. F=:)R C.P. 7-9

11. C·R Conj. 5,9 X Error

Here the error comes in step 11, where we have used steps from previously dis-

charged assumptions. The proper use of the scope markers and set-in steps should

help you to avoid this kind of mistake; once an assumption has been discharged,

this should be fairly clear just from the way the proof is written. You might even

draw a big X through the whole subproof once it has been discharged, to make

sure you won't be tempted to use anything inside it again. A third restriction must

be imposed for cases in which one assumption is made within the scope of anoth-

er; this restriction will be discussed in the next section.

4. Using c.P. and loP.

The use of c.P. and J.P. can greatly simplify the process of constructing proofs.

This will be true, however, only if you know how to use them effectively and to their

best advantage. In this section we will go over several points of strategy for using

these rules, which should help you to understand some of the finer points of their ap-

plication. We will also discuss the third restriction on the use of the rules.

In using these rules, it is of the utmost importance that you make the proper

assumption; for C.P., this means the antecedent of the conditional you want to

prove, and for J.P., it means the opposite of what you want to prove. Theoretically,

you can make any assumption you want provided it is discharged in the end, but

unless you keep clearly in mind where you are going and make your assumptions

accordingly, you will run into a lot of dead ends. You should never make an as-

sumption unless you know exactly what it is jor-what you are aiming at.186 Unit 9 Conditional Proof and Indirect Proof

You may sometimes have to use C.P. or LP. in the middle of a proof. You

might have to derive a negation, for instance, to use in M.T. or D.S., and you might

need a conditional for use in H.S. or M.P. The following is an example of this sort

of proof:


h. 1. (A ::J B) ::J (~ C ::J D) Pro


2. 

~ (C v E) 

Pro

3. 

(A v F) ::J B 

Pro / .'. D




4. 5. 

GVF 

Assp. (C.P.)

Add. 4

6. 


M.P. 3,5

7. 

A::JB 

C.P.4-6

8. 

~C::JD 

M.P. 1,7

9. 

~C·~E 

DeM.2

10. 

~C 

Simp. 9


11. D M.P. 8,10



Here we need to derive (A ::J B) in order to use M.P. with Premise 1. We can do

this by assuming A at step 4 and deriving B at step 6. We then go on to complete

the proof using the formula we have derived by c.P.

In the following problem there are a number of assumptions inside the

scopes of other assumptions. Notice also that an LP. subproof occurs within a c.P.

subproof. This is perfectly acceptable; there is no limit to the number or variety of

assumptions we may make in a proof. However, a third restriction applies to those

cases in which one assumption is made inside the scope of another: assumptions

made inside the scope of other assumptions must be discharged in the reverse

order in which they were made. If you have a second assumption inside the scope

of a first and a third inside the scope of the second, the third must be discharged

first, the second next, and the first assumption discharged last. Note that this is the

procedure used in problem i, which follows. What this amounts to is that our sub-

proofs must be nested, one entirely within the other. At no time should the scope

marker lines cross. If you find patterns like the ones below, you know you have

done something wrong.Unit 9 Conditional Proof and Indirect Proof 187

This is one reason it is so important to use the scope markers; they will tell you

if you have your assumptions crossed. The following proof will illustrate what hap-

pens in these more complex cases, where you have several assumptions, one inside

the other. Here we first assume (A - B), since this is the antecedent of what we want

to prove, and then we try to derive (A ::J (F ::J ~ E)), the consequent. This is itself a

conditional, with A as the antecedent, so at step 5 we assume A and try to derive

(F ::J ~ E). To get (F ::J ~ E), we assume F (for c.P.) and then try to derive ~ E.

For this we will use I.P., so at step 7 we assume E and try to derive a contradiction.

Once all the assumptions have been made, the rest of the proof goes smoothly.

1. I. A ::J (B ::J (C -D)) Pro

2. C ::J (E ::J (H - I)) Pro

3. F::J~I Pro J ". (A - B) ::J (A ::J (F ::J ~ E))

4. A-B Assp. (C.P.)

5. A Assp. (C.P.)

6. F Assp. (C.P.)

7. E Assp. (I.P.)

8. B ::J (C - D) M.P. 1,5

9. B Simp. 4

10. CoD M.P. 8,9

II. C Simp. 10

12. E ::J (H-J) M.P. 2,11

13. H-I M.P. 7,12

14. I Simp. 13

15. ~I M.P. 3,6

16. I-~I Conj. 14,15

17. ~E I.P.7-16

18. F::J ~E C.P.6-17

19. A::J(F::J~E) C.P.5-18

20. (A - B) ::J (A ::J (F ::J ~ E)) C.P.4-19

The proof above may look somewhat complicated, but without the use of

c.P. and I.P., it would probably be twice as long and would require more complex

rules, such as Distribution. In general, C.P. and I.P. will greatly simplify your

work, not only shortening proofs but also eliminating most applications of the

more difficult rules. Another advantage of c.P. and I.P. is that they make it easy to

plan your proof strategy, since you should always be making assumptions with a

particular aim in mind and know exactly what you are looking for. You may also

work from the bottom up; the strategy of working backward is particularly effective188 Unit 9 Conditional Proof and Indirect Proof

once you have C.P. and LP. The arrows and vertical lines-scope markers-help

to keep straight which assumptions go with which conclusions and allow us to see

exactly where we are going at each stage of the proof. Using c.P. and LP. clarifies

the proof and makes it much easier to find an effective strategy for solving prob-

lems. Now that you have these rules you should, in general, have much less trou-

ble figuring out how to "get started" on a proof; to further assist you, some

strategy hints are given below.

In some cases the direct method, working from the top down, will work, but

with more complex problems your best bet will usually be the method of working

backward. That is, think about the structure of the conclusion and what you need

to do to derive a conclusion of that form. For conditionals, most often the best ap-

proach is to use Conditional Proof; it will generally clarify and simplify your proof

structure. For biconditionals, the best method is often to use two applications of

C.P., derive the two conditionals, conjoin them, and then use the rule of Bicondi-

tional Exchange. For conjunctions, in general, you will just get each conjunct sep-

arately, by whatever method works best in that particular case, and then conjoin

them. For disjunctions, you may use Addition or Dilemma, and now that you have

c.P. you can often use this in conjunction with the C.E. rule. If you want to derive

a formula A v B, for instance, you can assume the negation of one disjunct, ~ A,

derive B, infer ~ A :J B by C.P., use c.E. to get ~ ~ A v B, and then use D.N. to

get A v B. To derive a negation or a single letter, if there is no obvious direct

method available, the best approach is to use Indirect Proof: assume the opposite

of what you want to prove and derive a contradiction from it. This is an extremely

powerful rule and can, in fact, be used to derive any formula. It is usually helpful

if you get stuck on a proof; if you just can't see what to do or how to get started,

try LP. In the following problem, for instance, it is not obvious how the direct ap-

proach would work. If we use LP., however, the solution is almost immediate.

J. 1. SvT Pro

2. S:JT Pro / :. T

3.

Assp. (LP.)

4. M.T.2,3

5.

D.S.l,3

6. Conj.4,5

~.~S

~

7. ~~T LP.3-6

8. T D.N.7

These are the last rules you will be given for sentential logic; together with

the other rules they form a very powerful deductive system-powerful enough, as

we shall see in Section 7, that we can derive any truth functionally valid argument

and any tautology by using just these rules. At this point your job is to learn to use

these rules effectively, and this requires doing as many problems as possible.Unit 9 Conditional Proof and Indirect Proof 189

There are a great many exercises at the end of the unit, and you should do all the

preliminary questions and as many of the proofs as you can. A summary of the

rules of C.P. and I.P. is also given at the end of the unit for handy reference.

5. Proofs of Theorems

There are certain formulas, "obvious truths," such as «p 0 q) ::J p), which can

be proved without any initially given premises. These formulas are called theorems,

and they play a very important role in logic because they are formulas that are ab-

solutely reliable: they are always derivable, and they are always true, no matter what.

We may define a theorem as a statement form that can be proved without any

given premises. This means that the proof contains only assumptions and steps de-

rived from previous steps. It is interesting that the set of theorems is exactly the

same as the set of tautologies; that is, every theorem is a tautology, and every tau-

tology is a theorem and so can be proved without premises.

In proving theorems we use exactly the same methods and rules as in the

other proofs; the only difference is that here we have no premises to begin with.

Thus, in order to get started, we need to use one of the rules in which we can make

assumptions, C.P. or I.P. The proof of a theorem will always require the use of c.P.

or J.P., since, without premises, this is the only way we can begin the proof. The

first step of a prooffor a theorem will always be an assumption. You may use the

same kind of proof strategy you used before; if the theorem is a conditional, for in-

stance, the best method is to use C.P. The proof of the theorem below is extremely

simple, requiring only three steps. We simply assume the antecedent of the formula,

derive its consequent in one step by Simp., and then apply c.P.:

k. 1. r poq

2.~

3. (p 0 q) ::J P

Assp. (c.P.)

Simp. 1

C.P.l,2

Other theorems require more extensive proofs, but there is nothing different,

in principle, from the kinds of proofs we use for theorems and the ones we use in

arguments. We simply have to start off with assumptions in the proofs of theo-

rems. This is illustrated below in the proof of (p ::J (q ::J r)) ::J (q ::J (p ::J r)).

1. 1. p ::J (q ::J r) Assp. (C.P.)

2.

3. 4. 5. 6. 7. 8. Assp. (C.P.)

Assp. (C.P.)

M.P. 1,3

M.P. 2,4

p::Jr C.P.3-5

q ::J (p ::J r) C.P.2-6

(p ::J (q ::J r)) ::J (q ::J (p ::J r)) C.P.I-7

~~r190 Unit 9 Conditional Proof and Indirect Proof

Another example is given below, in which we make use of both C.P. and I.P.

to prove «p v q) ::J ~ r) ::J ~ (r' p). There are alternative ways, in which only

one assumption is made, to do both these problems. You might try to work out the

proofs in that way.

m. l. (p v q) ::J ~ r Assp. (c.P.)

2. r' p Assp. (I.P.)

3. p Simp. 2

4. pvq Add. 3

5. ~r M.P. 1,4

6. r Simp. 2

7. r' ~r Conj.6,5

8. ~ (r' p) I.P.2-7

9. «p v q)::J ~r)::J ~(r' p) C.P.1-8

An example of a theorem in which the best approach is to use the rule of I.P. is

the following: ~ «p == q)' (p' ~ q». Here we will assume the opposite, the

unnegated formula, and derive a contradiction. At that point we will be entitled to

infer, by I.P., the negation of the formula that we assumed, that is, the theorem itself.

n. l. (p == q)' (p' ~ q) Assp. (I.P.)

2. 3.

4. 5. 6. 7. 8. 9. 10.

(p == q) Simp. 1

P'~q Simp. 1

p Simp. 3

~q Simp. 3

(p ::J q)' (q ::J p) RE.2

p::Jq Simp. 6

q M.P. 4,7

q' ~ q Conj.5,8

~ «p == q)' (p' ~ q» I.P. 1-9

We have done problems in which the conclusions are conditionals and nega-

tions; the obvious strategy in these cases is to use c.P. or I.P. If the conclusion is a

biconditional, (p == q), the best method is probably to use two applications of C.P.

to get (p ::J q) and (q ::J p) and then conjoin them and use B .E. If the conclusion is

a conjunction, you must derive each conjunct separately and then use Conj. (A

conjunction will be a theorem only if each of its conjuncts alone is a theorem.) If

you want to prove a disjunction, (p ::J q) v (q ::J p), for instance, there are two

possibilities: you can simply assume its negation, ~ «p ::J q) v (q ::J p», and try

to derive a contradiction, that is, use I.P.; or you can assume the negation of the left

disjunct, ~ (p ::J q), and try to derive the other. This will yield, in this case,

~(p ::J q) ::J (q ::J p), which, by an application ofC.E. and D.N., will give you the


o. I. ~ ((p :J q) v (q :J p)) Assp. (LP.)


2. 

~ (p :J q). ~ (q :J p) 

DeM.l

3. 

~ (p :J q) 

Simp. 2

4. 

~ (q :J p) 

Simp. 2

5. 

~ (~ p v q) 

C.E.3

6. 

~ ~ p. ~ q 

DeM.5

7. 

~(~qvp) 

C.E.4

8. 

~~q.~p 

DeM.7

9. 

~ ~ q 

Simp. 8

10. 

~q 

Simp. 6


~ q. ~ ~ q 

Conj.9,10

12. 

~ ~ ((p :J q) v (q :J p» 

I.P. 1-11

13. 

(p :J q) v (q :J p) 

D.N.12

I. 

~ (p :J q) 

Assp. (C.P.)

2. 

~ (~ p v q) 

C.E.l

3. 

~~p.~q 

DeM.2

4. 

~q 

Simp. 3

5. 

~qvp 

Add. 4

6. 

q:Jp 

C.E.5

7. 

~ (p :J q) :J (q :J p) 

C.P.I-6

8. 

~ ~ (p :J q) v (q :J p) 

C.E.7


9. (p :J q) v (q :J p) 

D.N.8


Unit 9 Conditional Proof and Indirect Proof 191

desired result. We will work the problem both ways below, to illustrate both meth-

ods for proving disjunctions.

II. 6. Invalidity

We must also say something at this point about invalidity. So far we have

only used the proof method to show that an argument is valid: that the conclusion

does follow from the premises. As it turns out, this is all we can do with proofs; the

method of proofs is good only for demonstrating positive results, for concluding

that the argument is valid. It can never be used to show that an argument is invalid.

You can never conclude that an argument is invalid, for instance, just because you

are unable to find a proof for it, as you no doubt have discovered. There can be all

sorts of reasons why you are unable to find a proof-too much noise in the dorms,

too much pasta and beer for supper, or just trying to work with the TV blaring. And

this is true not just for beginning logic students; there have been many cases in the

history of logic and mathematics in which tlreorems were conjectured-were

thought to be true-but for which no proof was found for centuries. Even the best

logicians and mathematicians are, on occasion, unable to find proofs for valid ar-

guments. Thus, no matter who you are, failure to find a proof does not mean that

no proof exists; it may just be very well hidden.192 Unit 9 Conditional Proof and Indirect Proof

How, then, do we show that an argument is invalid? One proposal that

sounds reasonable, which may have occurred to you, is to try to derive the

negation of the conclusion. Surely if you could do that, the argument would be in-

valid; that is, you would be unable to derive the conclusion. Right? Unfortunately,

wrong. Deriving the negation of the conclusion does not mean that you cannot de-

rive the conclusion itself. Ifthe premises tum out to be inconsistent (contradictory),

you will be able to derive both the conclusion and its negation (and anything else

you want, for that matter)! So this method won't work either.

To show that an argument is invalid, you cannot use the proof method at all; you

must revert to the method of counterexample. The only way to demonstrate that an

argument is invalid is to show that its form is invalid, which means we must construct

a counterexample, that is, an instance with true premises and a false conclusion. At

this point, since our arguments are rather complex, this generally means using the

short truth table method. You have already gone over this in Unit 5, but to refresh

your memory, one example is given here and there are a few exercises at the end of

the unit. We can show that the argument below is invalid in the following way:

A ::) (B ::) ~ C), B • (D ::) ~ E), (E v F) ::) (C v H) / ... A ::) H.

The form of the argument is

(p ::) (q ::) ~ r)), (q' (s ::) ~ t)), ((t v w) ::) (r v u)) / ... p ::) u

To make the conclusion false, we must make p true and u false. For the second

premise to be true, we know that q must be true. If both p and q are true, then for

the first premise to be true, r must be false. But if rand u are both false, the only

way for the third premise to be true is to make both t and w false. We now have the

conclusion false with the first and third premises true. All we need for a coun-

terexample is to make the second premise true, which means making the second

conjunct of that premise true. But this is already done: we had to make t false, so

~t is true, so (s ::) ~t) is true. Therefore, all the premises are true and the conclu-

sion is false, which means that there is a counterexample; thus the argument form

and the argument are invalid.

7. Truth and Proof

Finally, our last word on the topic of proofs, and in fact on sentential logic in

general, concerns the relationship between the two methods you have learned for

testing arguments for validity: the truth table method and the method of proofs. As

we found in Unit 7, the two methods are theoretically independent of each other.

However, there are some very interesting relationships between them that should

be mentioned to round out your understanding of sentential logic.Unit 9 Conditional Proof and Indirect Proof 193

The most important fact about the two methods-truth tables and proofs-is

that for classical logic they are exactly equivalent, which means that they give ex-

actly the same results. If an argument is valid according to the truth table

method-sometimes called the semantic method-then it is possible to construct a

proof for it; this means that the system is complete. Also, whatever argument we

can prove will also be semantically valid, which means that the system is

consistent. And as noted in Section 5, every theorem is a tautology and every tau-

tology is a theorem. This equivalence between the two methods holds for all classical,

two-valued logic through relational predicate logic with identity. (In predicate

logic we can't use truth tables per se, but there is an analogous semantic procedure

using the notion of possible truth-value assignments.)

Interestingly, this equivalence between truth and proof, the consistency and

completeness of the system, does not hold even in simple arithmetic. In 1931, Kurt

GOdel, possibly the greatest logician ever, showed that the proof method falls short

of the semantic method, which means that for any proof system for arithmetic

there will be true arithmetical statements that cannot be proved in that system.

Arithmetic is irredeemably incomplete. Even worse, perhaps, GOdel proved that it

is impossible ever to show that all the statements provable in arithmetical systems

are true. In other words, we can never show that our arithmetical system is consis-

tent. We may assume that arithmetic contains no false statements, but we will

never be able to demonstrate this fact.

These results, which would be more fully explored in an advanced course in

logic, have been the source of a great deal of philosophical controversy about the

nature of mathematics and mathematical truth. If mathematics is not certain, not

provably consistent, then is it just another empirical science? And if being true in

mathematics does not mean the same as being provable, as many had thought, then

what could it possibly mean? This issue is still being debated, and the implications

of GOdel's results for the concepts of certainty and truth in mathematics are still

not clear.

SUMMARY OF RULES OF CONDITIONAL PROOF AND INDIRECT PROOF

A. CONDITIONAL PROOF (c.P.)

p

If, given the assumption p, we are able to derive q, then we are

allowed to infer (p :::J q), citing all the steps from p to q inclusive.

q

/ .". p:::J q194 • INDIRECT PROOF (I.P.)

P

Unit 9 Conditional Proof and Indirect Proof

If, given an assumption p, we are able to derive a contradiction

(q. ~ q), then we may infer the negation of our assumption, ~ p,

citing all the steps from p to (q. ~ q), inclusive .

• RESTRICTIONS ON THE USE OF c.P. AND I.P.

1. 2. 3. Every assumption made in a proof must eventually be discharged.

Once an assumption has been discharged, neither it nor any step that falls within

its scope may be used in the proof again.

Assumptions inside the scope of other assumptions must be discharged in the

reverse order in which they were made; that is, no two scope markers may

cross.

'. GENERAL INSTRUCTIONS FOR USING c.P. AND loP.

1. 2. 3. 4. 5. 6. For both c.P. and I.P., an assumption may be introduced at any point in the proof,

provided it is justified as such, that is, provided we label it as an assumption.

In using C.P., we assume the antecedent of the conditional to be proved and then

derive the consequent. In using I.P., we assume the opposite of what we want to

prove and then derive a contradiction. All the steps from the assumption to the

consequent (for c.P.) or the contradiction (for I.P.) are said to be within the scope

of the assumption.

The sequence of steps within the scope of an assumption is called a subprooJ

We indicate the scope of an assumption and set off the subproof by an arrow

(pointing to the assumption) and a vertical line that runs to the left of the sub-

proof and includes every step in the subproof. This arrow and vertical line are

called the scope marker for the assumption. We also set in or indent every step in

the subproof.

There is no limit to the number of assumptions we may introduce in a given

proof, and we may make one assumption inside the scope of another.

The scope of the assumption ends immediately prior to the step in which we

infer the conditional or negation. We say that the assumption is discharged at

the point at which we apply the c.P. or I.P. rule. Thus neither the conditional nor

the negation, the result of applying C.P. or I.P., falls within the scope of the as-

sumption. We indicate that the assumption has been discharged by cutting off the

vertical line (the scope marker) at this point.Unit 9 Conditional Proof and Indirect Proof 195

DEFINITIONS

1. 2. 3. A theorem is a statement form that can be proved without any given premises.

A justified step is either a premise, or an assumption, or a step that follows from

previous steps according to one of the given rules of inference.

A proof is a sequence of justified steps in which the last step is the desired con-

clusion; that is, it is a sequence of steps, each of which is either a premise, or an

assumption, or a step that follows from previous steps according to one of the

given rules of inference and in which the last step is the desired conclusion.