Chapter 18 Constructing proofs
There is no simple recipe for finding proofs, and there is no substitute for practice. Here, though, are some rules of thumb and strategies to keep in mind.
18.1 Working backward from what we want
So you’re trying to find a proof of some conclusion , which will be the last line of your proof. The first thing you do is look at and ask what the introduction rule is for its main logical operator. This gives you an idea of what should happen before the last line of the proof. The justifications for the introduction rule require one or two other sentences above the last line, or one or two subproofs. Moreover, you can tell from what those sentences are, or what the assumptions and conclusions of the subproof(s) are. Then you can write down those sentence or outline the subproof(s) above the last line, and treat those as your new goals.
For example: If your conclusion is a conditional , plan to use the I rule. This requires starting a subproof in which you assume . The subproof ought to end with . Then, continue by thinking about what you should do to get inside that subproof, and how you can use the assumption .
If your goal is a conjunction, conditional, or negated sentence, you should start by working backward in this way. We’ll describe what you have to do in each of these cases in detail.
Working backward from a conjunction
If we want to prove , working backward means we should write at the bottom of our proof, and try to prove it using I. At the top, we’ll write out the premises of the proof, if there are any. Then, at the bottom, we write the sentence we want to prove. If it is a conjunction, we’ll prove it using I.
Line number |
Subproof level |
Formula |
Justification |
---|---|---|---|
|
0
|
|
PR
|
|
0
|
|
|
|
0
|
|
PR
|
|
0
|
|
|
|
0
|
|
|
|
0
|
|
|
|
0
|
|
|
|
0
|
|
I ,
|
For I, we need to prove first, then prove . For the last line, we have to cite the lines where we (will have) proved and , and use I. The parts of the proof labelled by the vertical have to still be filled in. We’ll mark the line numbers , for now. When the proof is complete, these placeholders can be replaced by actual numbers.
Working backward from a conditional
If our goal is to prove a conditional , we’ll have to use I. This requires a subproof starting with and ending with . We’ll set up our proof as follows:
Line number |
Subproof level |
Formula |
Justification |
---|---|---|---|
|
open subproof,
1
|
|
|
|
1
|
|
|
|
1
|
|
|
|
close subproof,
0
|
|
I –
|
Again we’ll leave placeholders in the line number slots. We’ll record the last inference as I, citing the subproof.
Working backward from a negated sentence
If we want to prove , we’ll have to use I.
Line number |
Subproof level |
Formula |
Justification |
---|---|---|---|
|
open subproof,
1
|
|
|
|
1
|
|
|
|
1
|
|
|
|
close subproof,
0
|
|
I –
|
For I, we have to start a subproof with assumption ; the last line of the subproof has to be . We’ll cite the subproof, and use I as the rule.
When working backward, continue to do so as long as you can. So if you’re working backward to prove and have set up a subproof in which you want to prove . Now look at . If, say, it is a conjunction, work backward from it, and write down the two conjuncts inside your subproof. Etc.
Working backward from a disjunction
Of course, you can also work backward from a disjunction , if that is your goal. The I rule requires that you have one of the disjuncts in order to infer . So to work backward, you pick a disjunct, infer from it, and then continue to look for a proof of the disjunct you picked:
Line number |
Subproof level |
Formula |
Justification |
---|---|---|---|
|
0
|
|
|
|
0
|
|
|
|
0
|
|
I
|
However, you may not be able to prove the disjunct you picked. In that case you have to backtrack. When you can’t fill in the part labelled by the vertical , delete everything, and try with the other disjunct:
Line number |
Subproof level |
Formula |
Justification |
---|---|---|---|
|
0
|
|
|
|
0
|
|
|
|
0
|
|
I
|
Obviously, deleting everything and starting over is frustrating, so you should avoid it. If your goal is a disjunction, therefore, you should not start by working backward: try working forward first, and apply the I strategy only when working forward (and working backward using I, I, and I) no longer work.
18.2 Work forward from what you have
Your proof may have premises. And if you’ve worked backward in order to prove a conditional or a negated sentence, you will have set up subproofs with an assumption, and be looking to prove a final sentence in the subproof. These premises and assumptions are sentences you can work forward from in order to fill in the missing steps in your proof. That means applying elimination rules for the main operators of these sentences. The form of the rules will tell you what you’ll have to do.
Working forward from a conjunction
To work forward from a sentence of the form , we use E. That rule allows us to do two things: infer , and infer . So in a proof where we have , we can work forward by writing and/or immediately below the conjunction:
Line number |
Subproof level |
Formula |
Justification |
---|---|---|---|
|
0
|
|
|
|
0
|
|
E
|
|
0
|
|
E
|
Usually it will be clear in the particular situation you’re in which one of or you’ll need. It doesn’t hurt, however, to write them both down.
Working forward from a disjunction
Working forward from a disjunction works a bit differently. To use a disjunction, we use the E rule. In order to apply that rule, it is not enough to know what the disjuncts of the disjunction are that we want to use. We must also keep in mind what we want to prove. Suppose we want to prove , and we have to work with. (That may be a premise of the proof, an assumption of a subproof, or something already proved.) In order to be able to apply the E rule, we’ll have to set up two subproofs:
Line number |
Subproof level |
Formula |
Justification |
---|---|---|---|
|
0
|
|
|
|
open subproof,
1
|
|
|
|
1
|
|
|
|
1
|
|
|
|
close subproof,
open subproof,
1
|
|
|
|
1
|
|
|
|
1
|
|
|
|
close subproof,
0
|
|
E , ()–, ()–
|
The first subproof starts with the first disjunct, , and ends with the sentence we’re looking for, . The second subproof starts with the other disjunct, , and also ends with the goal sentence . Each of these subproofs have to be filled in further. We can then justify the goal sentence by using E, citing the line with and the two subproofs.
Working forward from a conditional
In order to use a conditional , you also need the antecedent in order to apply E. So to work forward from a conditional, you will derive , justify it by E, and set up as a new subgoal.
Line number |
Subproof level |
Formula |
Justification |
---|---|---|---|
|
0
|
|
|
|
0
|
|
|
|
0
|
|
|
|
0
|
|
E ,
|
Working forward from a negated sentence
Finally, to use a negated sentence , you would apply E. It requires, in addition to , also the corresponding sentence without the negation. The sentence you’ll get is always the same: . So working forward from a negated sentence works especially well inside a subproof that you’ll want to use for I (or IP). You work forward from if you already have and you want to prove . To do it, you set up as a new subgoal.
Line number |
Subproof level |
Formula |
Justification |
---|---|---|---|
|
0
|
|
|
|
0
|
|
|
|
0
|
|
|
|
0
|
|
E ,
|
18.3 Strategies at work
Suppose we want to show that the argument is valid. We start the proof by writing the premise and conclusion down. (On a piece of paper, you would want as much space as possible between them, so write the premises at the top of the sheet and the conclusion at the bottom.)
Line number |
Subproof level |
Formula |
Justification |
---|---|---|---|
|
0
|
|
PR
|
|
0
|
|
|
|
0
|
|
|
We now have two options: either work backward from the conclusion, or work forward from the premise. We’ll pick the second strategy: we use the disjunction on line , and set up the subproofs we need for E. The disjunction on line has two disjuncts, and . The goal sentence you want to prove is . So in this case you have to set up two subproofs, one with assumption and last line , the other with assumption and last line . The justification for the conclusion on line will be E, citing the disjunction on line and the two subproofs. So your proof now looks like this:
Line number |
Subproof level |
Formula |
Justification |
---|---|---|---|
|
0
|
|
PR
|
|
open subproof,
1
|
|
AS
|
|
1
|
|
|
|
1
|
|
|
|
close subproof,
open subproof,
1
|
|
AS
|
|
1
|
|
|
|
1
|
|
|
|
close subproof,
0
|
|
E , –, ()–
|
You now have two separate tasks, namely to fill in each of the two subproofs. In the first subproof, we now work backward from the conclusion . That is a conjunction, so inside the first subproof, you will have two separate subgoals: proving , and proving . These subgoals will let you justify line using I. Your proof now looks like this:
Line number |
Subproof level |
Formula |
Justification |
---|---|---|---|
|
0
|
|
PR
|
|
open subproof,
1
|
|
AS
|
|
1
|
|
|
|
1
|
|
|
|
1
|
|
|
|
1
|
|
|
|
1
|
|
I ,
|
|
close subproof,
open subproof,
1
|
|
AS
|
|
1
|
|
|
|
1
|
|
|
|
close subproof,
0
|
|
E , –, ()–
|
We immediately see that we can get line from line by E. So line is actually line , and can be justified with E from line . The other subgoal is a disjunction. We’ll apply the strategy for working backward from a disjunctions to line . We have a choice of which disjunct to pick as a subgoal, or . Picking wouldn’t work and we’d end up having to backtrack. And you can already see that if you pick as a subgoal, you could get that by working forward again from the conjunction on line . So we can complete the first subproof as follows:
Line number |
Subproof level |
Formula |
Justification |
---|---|---|---|
|
0
|
|
PR
|
|
open subproof,
1
|
|
AS
|
|
1
|
|
E
|
|
1
|
|
E
|
|
1
|
|
I
|
|
1
|
|
I ,
|
|
close subproof,
open subproof,
1
|
|
AS
|
|
1
|
|
|
|
1
|
|
|
|
close subproof,
0
|
|
E , –, –
|
Like line , we get line from by E. Line is justified by I from line , since we were working backward from a disjunction there.
That’s it for the first subproof. The second subproof is almost exactly the same. We’ll leave it as an exercise.
Remember that when we started, we had the option of working forward from the premise, or working backward from the conclusion, and we picked the first option. The second option also leads to a proof, but it will look different. The first steps would be to work backward from the conclusion and set up two subgoals, and , and then work forward from the premise to prove them, e.g.,
Line number |
Subproof level |
Formula |
Justification |
---|---|---|---|
|
0
|
|
PR
|
|
open subproof,
1
|
|
AS
|
|
1
|
|
|
|
1
|
|
|
|
close subproof,
open subproof,
1
|
|
AS
|
|
1
|
|
|
|
1
|
|
|
|
close subproof,
0
|
|
E , –, ()–()
|
|
open subproof,
1
|
|
AS
|
|
1
|
|
|
|
1
|
|
|
|
close subproof,
open subproof,
1
|
|
AS
|
|
1
|
|
|
|
1
|
|
|
|
close subproof,
0
|
|
E , ()–, ()–()
|
|
0
|
|
I ,
|
We’ll leave you to fill in the missing pieces indicated by .
Let’s give another example to illustrate how to apply the strategies to deal with conditionals and negation. The sentence is a tautology. Let’s see if we can find a proof of it, from no premises, using the strategies. We first write the sentence at the bottom of a sheet of paper. Since working forward is not an option (there is nothing to work forward from), we work backward, and set up a subproof to establish the sentence we want, , using I. Its assumption must be the antecedent of the conditional we want to prove, i.e., , and its last line the consequent, .
Line number |
Subproof level |
Formula |
Justification |
---|---|---|---|
|
open subproof,
1
|
|
AS
|
|
1
|
|
|
|
1
|
|
|
|
close subproof,
0
|
|
I –
|
The new goal, is itself a conditional, so working backward we set up another subproof:
Line number |
Subproof level |
Formula |
Justification |
---|---|---|---|
|
open subproof,
1
|
|
AS
|
|
open subproof,
2
|
|
AS
|
|
2
|
|
|
|
2
|
|
|
|
close subproof,
1
|
|
I –()
|
|
close subproof,
0
|
|
I –
|
From we again work backward. To do this, look at the I rule. It requires a subproof with as assumption, and as its last line. So the proof is now:
Line number |
Subproof level |
Formula |
Justification |
---|---|---|---|
|
open subproof,
1
|
|
AS
|
|
open subproof,
2
|
|
AS
|
|
open subproof,
3
|
|
|
|
3
|
|
|
|
3
|
|
|
|
close subproof,
2
|
|
I –()
|
|
close subproof,
1
|
|
I –()
|
|
close subproof,
0
|
|
I –
|
Now our goal is to prove . We said above, when discussing how to work forward from a negated sentence, that the E rule allows you to prove , which is our goal in the innermost subproof. So we look for a negated sentence which we can work forward from: that would be on line . That means we have to derive inside the subproof, since E requires not just (which we have already), but also . And , in turn, we get by working forward from , since E will allow us to justify the consequent of that conditional, , by E. The rule E also requires the antecedent of the conditional, but that is also already available (on line ). So we finish with:
Line number |
Subproof level |
Formula |
Justification |
---|---|---|---|
|
open subproof,
1
|
|
AS
|
|
open subproof,
2
|
|
AS
|
|
open subproof,
3
|
|
|
|
3
|
|
E ,
|
|
3
|
|
E ,
|
|
close subproof,
2
|
|
I –
|
|
close subproof,
1
|
|
I –
|
|
close subproof,
0
|
|
I –
|
18.4 Working forward from
When applying the strategies, you will sometimes find yourself in a situation where you can justify . Using the explosion rule, this would allow you to justify anything. So works like a wildcard in proofs. For instance, suppose you want to give a proof of the argument . You set up your proof, writing the premises and at the top on lines and , and the conclusion at the bottom of the page. has no main connective, so you can’t work backward from it. Instead, you must work forward from : That requires two subproofs, like so:
Line number |
Subproof level |
Formula |
Justification |
---|---|---|---|
|
0
|
|
PR
|
|
0
|
|
PR
|
|
open subproof,
1
|
|
AS
|
|
1
|
|
|
|
1
|
|
|
|
close subproof,
open subproof,
1
|
|
AS
|
|
1
|
|
|
|
1
|
|
|
|
close subproof,
0
|
|
E , –, ()–
|
Notice that you have on line and as the assumption of your first subproof. That gives you using E, and from you get the conclusion of the first subproof using X. Recall that you can repeat a sentence you already have by using the reiteration rule R. So our proof would be:
Line number |
Subproof level |
Formula |
Justification |
---|---|---|---|
|
0
|
|
PR
|
|
0
|
|
PR
|
|
open subproof,
1
|
|
AS
|
|
1
|
|
E ,
|
|
1
|
|
X
|
|
close subproof,
open subproof,
1
|
|
AS
|
|
1
|
|
R
|
|
close subproof,
0
|
|
E , –, –
|
18.5 Proceed indirectly
In very many cases, the strategies of working forward and backward will eventually pan out. But there are cases where they do not work. If you cannot find a way to show directly using those, use IP instead. To do this, set up a subproof in which you assume and look for a proof of inside that subproof.
Line number |
Subproof level |
Formula |
Justification |
---|---|---|---|
|
open subproof,
1
|
|
AS
|
|
1
|
|
|
|
1
|
|
|
|
close subproof,
0
|
|
IP –
|
Here, we have to start a subproof with assumption ; the last line of the subproof has to be . We’ll cite the subproof, and use IP as the rule. In the subproof, we now have an additional assumption (on line ) to work with.
Suppose we used the indirect proof strategy, or we’re in some other situation where we’re looking for a proof of . What’s a good candidate? Of course the obvious candidate would be to use a negated sentence, since (as we saw above) E always yields . If you set up a proof as above, trying to prove using IP, you will have as the assumption of your subproof—so working forward from it to justify inside your subproof, you would next set up as a goal inside your subproof. If you are using this IP strategy, you will find yourself in the following situation:
Line number |
Subproof level |
Formula |
Justification |
---|---|---|---|
|
open subproof,
1
|
|
AS
|
|
1
|
|
|
|
1
|
|
|
|
1
|
|
E ,
|
|
close subproof,
0
|
|
IP –
|
This looks weird: We wanted to prove and the strategies failed us; so we used IP as a last resort. And now we find ourselves in the same situation: we are again looking for a proof of . But notice that we are now inside a subproof, and in that subproof we have an additional assumption () to work with which we didn’t have before. Let’s look at an example.
18.6 Indirect proof of excluded middle
The sentence is a tautology, and so should have a proof even without any premises. But working backward fails us: to get using I we would have to prove either or —again, from no premises. Neither of these is a tautology, so we won’t be able to prove either. Working forward doesn’t work either, since there is nothing to work forward from. So, the only option is indirect proof.
Line number |
Subproof level |
Formula |
Justification |
---|---|---|---|
|
open subproof,
1
|
|
AS
|
|
1
|
|
|
|
1
|
|
|
|
close subproof,
0
|
|
IP –
|
Now we do have something to work forward from: the assumption . To use it, we justify by E, citing the assumption on line , and also the corresponding unnegated sentence , yet to be proved.
Line number |
Subproof level |
Formula |
Justification |
---|---|---|---|
|
open subproof,
1
|
|
AS
|
|
1
|
|
|
|
1
|
|
|
|
1
|
|
E ,
|
|
close subproof,
0
|
|
IP –
|
At the outset, working backward to prove by I did not work. But we are now in a different situation: we want to prove inside a subproof. In general, when dealing with new goals we should go back and start with the basic strategies. In this case, we should first try to work backward from the disjunction , i.e., we have to pick a disjunct and try to prove it. Let’s pick . This would let us justify on line using I. Then working backward from , we start another subproof in order to justify using I. That subproof must have as the assumption and as its last line.
Line number |
Subproof level |
Formula |
Justification |
---|---|---|---|
|
open subproof,
1
|
|
AS
|
|
open subproof,
2
|
|
AS
|
|
2
|
|
|
|
2
|
|
|
|
close subproof,
1
|
|
I –()
|
|
1
|
|
I
|
|
1
|
|
E ,
|
|
close subproof,
0
|
|
IP –
|
Inside this new subproof, we again need to justify . The best way to do this is to work forward from a negated sentence; on line is the only negated sentence we can use. The corresponding unnegated sentence, , however, directly follows from (which we have on line ) by I. Our complete proof is:
Line number |
Subproof level |
Formula |
Justification |
---|---|---|---|
|
open subproof,
1
|
|
AS
|
|
open subproof,
2
|
|
AS
|
|
2
|
|
I
|
|
2
|
|
E ,
|
|
close subproof,
1
|
|
I –
|
|
1
|
|
I
|
|
1
|
|
E ,
|
|
close subproof,
0
|
|
IP –
|
Practice exercises
A. Use the strategies to find proofs for each of the following arguments:
-
1.
-
2.
-
3.
-
4.
-
5.
-
6.
-
7.
-
8.
B. Formulate strategies for working backward and forward from .
C. Use the strategies to find proofs for each of the following sentences:
-
1.
-
2.
-
3.
-
4.
-
5.
Since these should be proofs of sentences from no premises, you will start with the respective sentence at the bottom of the proof, which will have no premises.
D. Use the strategies to find proofs for each one of the following arguments and sentences:
-
1.
-
2.
-
3.
-
4.
-
5.
-
6.
-
7.
These all will require the IP strategy. The last three especially are quite hard!