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.