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

1

0
𝒫1
PR

0

k

0
𝒫k
PR

0

n

0
𝒜

0

m

0

m+1

0
𝒜
I n, m

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 m, n 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

n

open subproof, 1
𝒜

1

m

1

m+1

close subproof, 0
𝒜
I nm

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

n

open subproof, 1
𝒜

1

m

1

m+1

close subproof, 0
¬𝒜
¬I nm

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

n

0
𝒜

n+1

0
𝒜
I n

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

n

0

n+1

0
𝒜
I n

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

n

0
𝒜

n+1

0
𝒜
E n

n+2

0
E n

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 𝒜B to work with. (That 𝒜B 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

n

0
𝒜

n+1

open subproof, 1
𝒜

1

m

1
𝒞

m+1

close subproof, open subproof, 1

1

k

1
𝒞

k+1

close subproof, 0
𝒞
E n, (n+1)–m, (m+1)–k

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

n

0
𝒜

0

m

0
𝒜

m+1

0
E n, m

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

n

0
¬𝒜

0

m

0
𝒜

m+1

0
¬E n, m

18.3 Strategies at work

Suppose we want to show that the argument (AB)(AC)A(BC) 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

1

0
(AB)(AC)
PR

0

n

0
A(BC)

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 1, and set up the subproofs we need for E. The disjunction on line 1 has two disjuncts, AB and AC. The goal sentence you want to prove is A(BC). So in this case you have to set up two subproofs, one with assumption AB and last line A(BC), the other with assumption AC and last line A(BC). The justification for the conclusion on line n will be E, citing the disjunction on line 1 and the two subproofs. So your proof now looks like this:

Line number

Subproof level

Formula

Justification

1

0
(AB)(AC)
PR

2

open subproof, 1
AB
AS

1

n

1
A(BC)

n+1

close subproof, open subproof, 1
AC
AS

1

m

1
A(BC)

m+1

close subproof, 0
A(BC)
E 1, 2n, (n+1)–m

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 A(BC). That is a conjunction, so inside the first subproof, you will have two separate subgoals: proving A, and proving BC. These subgoals will let you justify line n using I. Your proof now looks like this:

Line number

Subproof level

Formula

Justification

1

0
(AB)(AC)
PR

2

open subproof, 1
AB
AS

1

i

1
A

1

n1

1
BC

n

1
A(BC)
I i, n1

n+1

close subproof, open subproof, 1
AC
AS

1

m

1
A(BC)

m+1

close subproof, 0
A(BC)
E 1, 2n, (n+1)–m

We immediately see that we can get line i from line 2 by E. So line i is actually line 3, and can be justified with E from line 2. The other subgoal BC is a disjunction. We’ll apply the strategy for working backward from a disjunctions to line n1. We have a choice of which disjunct to pick as a subgoal, B or C. Picking C wouldn’t work and we’d end up having to backtrack. And you can already see that if you pick B as a subgoal, you could get that by working forward again from the conjunction AB on line 2. So we can complete the first subproof as follows:

Line number

Subproof level

Formula

Justification

1

0
(AB)(AC)
PR

2

open subproof, 1
AB
AS

3

1
A
E 2

4

1
B
E 2

5

1
BC
I 4

6

1
A(BC)
I 3, 5

7

close subproof, open subproof, 1
AC
AS

1

m

1
A(BC)

m+1

close subproof, 0
A(BC)
E 1, 26, 7m

Like line 3, we get line 4 from 2 by E. Line 5 is justified by I from line 4, 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, A and BC, and then work forward from the premise to prove them, e.g.,

Line number

Subproof level

Formula

Justification

1

0
(AB)(AC)
PR

2

open subproof, 1
AB
AS

1

k

1
A

k+1

close subproof, open subproof, 1
AC
AS

1

n1

1
A

n

close subproof, 0
A
E 1, 2k, (k+1)–(n1)

n+1

open subproof, 1
AB
AS

1

l

1
BC

l+1

close subproof, open subproof, 1
AC
AS

1

m1

1
BC

m

close subproof, 0
BC
E 1, (n+1)–l, (l+1)–(m1)

m+1

0
A(BC)
I n, m

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 (AB)(¬B¬A) 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, (AB)(¬B¬A), using I. Its assumption must be the antecedent of the conditional we want to prove, i.e., AB, and its last line the consequent, ¬B¬A.

Line number

Subproof level

Formula

Justification

1

open subproof, 1
AB
AS

1

n

1
¬B¬A

n+1

close subproof, 0
(AB)(¬B¬A)
I 1n

The new goal, ¬B¬A is itself a conditional, so working backward we set up another subproof:

Line number

Subproof level

Formula

Justification

1

open subproof, 1
AB
AS

2

open subproof, 2
¬B
AS

2

n1

2
¬A

n

close subproof, 1
¬B¬A
I 2–(n1)

n+1

close subproof, 0
(AB)(¬B¬A)
I 1n

From ¬A we again work backward. To do this, look at the ¬I rule. It requires a subproof with A as assumption, and as its last line. So the proof is now:

Line number

Subproof level

Formula

Justification

1

open subproof, 1
AB
AS

2

open subproof, 2
¬B
AS

3

open subproof, 3
A

3

n2

3

n1

close subproof, 2
¬A
¬I 3–(n2)

n

close subproof, 1
¬B¬A
I 2–(n1)

n+1

close subproof, 0
(AB)(¬B¬A)
I 1n

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 ¬B on line 2. That means we have to derive B inside the subproof, since ¬E requires not just ¬B (which we have already), but also B. And B, in turn, we get by working forward from AB, since E will allow us to justify the consequent of that conditional, B, by E. The rule E also requires the antecedent A of the conditional, but that is also already available (on line 3). So we finish with:

Line number

Subproof level

Formula

Justification

1

open subproof, 1
AB
AS

2

open subproof, 2
¬B
AS

3

open subproof, 3
A

4

3
B
E 1, 3

5

3
¬E 2, 4

6

close subproof, 2
¬A
¬I 35

7

close subproof, 1
¬B¬A
I 26

8

close subproof, 0
(AB)(¬B¬A)
I 17

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 AB,¬AB. You set up your proof, writing the premises AB and ¬A at the top on lines 1 and 2, and the conclusion B at the bottom of the page. B has no main connective, so you can’t work backward from it. Instead, you must work forward from AB: That requires two subproofs, like so:

Line number

Subproof level

Formula

Justification

1

0
AB
PR

2

0
¬A
PR

3

open subproof, 1
A
AS

1

m

1
B

m+1

close subproof, open subproof, 1
B
AS

1

k

1
B

k+1

close subproof, 0
B
E 1, 3m, (m+1)–k

Notice that you have ¬A on line 2 and A as the assumption of your first subproof. That gives you using ¬E, and from you get the conclusion B 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

1

0
AB
PR

2

0
¬A
PR

3

open subproof, 1
A
AS

4

1
¬E 2, 3

5

1
B
X 4

6

close subproof, open subproof, 1
B
AS

7

1
B
R 6

8

close subproof, 0
B
E 1, 35, 67

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

n

open subproof, 1
¬𝒜
AS

1

m

1

m+1

close subproof, 0
𝒜
IP nm

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 n) 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

n

open subproof, 1
¬𝒜
AS

1

m1

1
𝒜

m

1
¬E n, m1

m+1

close subproof, 0
𝒜
IP nm

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 A¬A is a tautology, and so should have a proof even without any premises. But working backward fails us: to get A¬A using I we would have to prove either A or ¬A—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

1

open subproof, 1
¬(A¬A)
AS

1

m

1

m+1

close subproof, 0
A¬A
IP 1m

Now we do have something to work forward from: the assumption ¬(A¬A). To use it, we justify by ¬E, citing the assumption on line 1, and also the corresponding unnegated sentence A¬A, yet to be proved.

Line number

Subproof level

Formula

Justification

1

open subproof, 1
¬(A¬A)
AS

1

m1

1
A¬A

m

1
¬E 1, m1

m+1

close subproof, 0
A¬A
IP 1m

At the outset, working backward to prove A¬A by I did not work. But we are now in a different situation: we want to prove A¬A 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 A¬A, i.e., we have to pick a disjunct and try to prove it. Let’s pick ¬A. This would let us justify A¬A on line m1 using I. Then working backward from ¬A, we start another subproof in order to justify ¬A using ¬I. That subproof must have A as the assumption and  as its last line.

Line number

Subproof level

Formula

Justification

1

open subproof, 1
¬(A¬A)
AS

2

open subproof, 2
A
AS

2

m3

2

m2

close subproof, 1
¬A
¬I 2–(m3)

m1

1
A¬A
I m2

m

1
¬E 1, m1

m+1

close subproof, 0
A¬A
IP 1m

Inside this new subproof, we again need to justify . The best way to do this is to work forward from a negated sentence; ¬(A¬A) on line 1 is the only negated sentence we can use. The corresponding unnegated sentence, A¬A, however, directly follows from A (which we have on line 2) by I. Our complete proof is:

Line number

Subproof level

Formula

Justification

1

open subproof, 1
¬(A¬A)
AS

2

open subproof, 2
A
AS

3

2
A¬A
I 2

4

2
¬E 1, 3

5

close subproof, 1
¬A
¬I 24

6

1
A¬A
I 5

7

1
¬E 1, 6

8

close subproof, 0
A¬A
IP 17

Practice exercises

A. Use the strategies to find proofs for each of the following arguments:

  1. 1.

    AB,ACA(BC)

  2. 2.

    (AB)CA(BC)

  3. 3.

    A(BC)(AB)(AC)

  4. 4.

    A(BC)(AB)(AC)

  5. 5.

    (AB)(AC)A(BC)

  6. 6.

    AB,AC,BDCD

  7. 7.

    ¬A¬B¬(AB)

  8. 8.

    A¬B¬(AB)

B. Formulate strategies for working backward and forward from 𝒜.

C. Use the strategies to find proofs for each of the following sentences:

  1. 1.

    ¬A(A)

  2. 2.

    ¬(A¬A)

  3. 3.

    [(AC)(BC)][(AB)C]

  4. 4.

    ¬(AB)(A¬B)

  5. 5.

    (¬AB)(AB)

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. 1.

    ¬¬AA

  2. 2.

    ¬A¬BBA

  3. 3.

    AB¬AB

  4. 4.

    ¬(AB)(¬A¬B)

  5. 5.

    A(BC)(AB)(AC)

  6. 6.

    (AB)(BA)

  7. 7.

    ((AB)A)A

These all will require the IP strategy. The last three especially are quite hard!