Chapter 18 Constructing proofs

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

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

We immediately see that we can get line $i$ from line $2$ by $\wedge$E. So line $i$ is actually line $3$, and can be justified with $\wedge$E from line $2$. The other subgoal $B\vee C$ is a disjunction. We’ll apply the strategy for working backward from a disjunctions to line $n-1$. 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 $A\wedge B$ on line $2$. So we can complete the first subproof as follows:

Like line $3$, we get line $4$ from $2$ by $\wedge$E. Line $5$ is justified by $\vee$I from line $4$, since we were working backward from a disjunction there.

We’ll leave you to fill in the missing pieces indicated by $\mathrm{⋮}$.

The new goal, $\mathrm{\neg }B\to \mathrm{\neg }A$ is itself a conditional, so working backward we set up another subproof:

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

Now our goal is to prove $\perp$. We said above, when discussing how to work forward from a negated sentence, that the $\mathrm{\neg }$E rule allows you to prove $\perp$, which is our goal in the innermost subproof. So we look for a negated sentence which we can work forward from: that would be $\mathrm{\neg }B$ on line $2$. That means we have to derive $B$ inside the subproof, since $\mathrm{\neg }$E requires not just $\mathrm{\neg }B$ (which we have already), but also $B$. And $B$, in turn, we get by working forward from $A\to B$, since $\to$E will allow us to justify the consequent of that conditional, $B$, by $\to$E. The rule $\to$E also requires the antecedent $A$ of the conditional, but that is also already available (on line $3$). So we finish with:

Notice that you have $\mathrm{\neg }A$ on line $2$ and $A$ as the assumption of your first subproof. That gives you $\perp$ using $\mathrm{\neg }$E, and from $\perp$ 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:

Here, we have to start a subproof with assumption $\mathrm{\neg }𝒜$; the last line of the subproof has to be $\perp$. 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.

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 ($\mathrm{\neg }𝒜$) to work with which we didn’t have before. Let’s look at an example.

Now we do have something to work forward from: the assumption $\mathrm{\neg }(A\vee \mathrm{\neg }A)$. To use it, we justify $\perp$ by $\mathrm{\neg }$E, citing the assumption on line $1$, and also the corresponding unnegated sentence $A\vee \mathrm{\neg }A$, yet to be proved.

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

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

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

1. 1.
   ​

   $A\to B,A\to C\therefore A\to (B\wedge C)$

2. 2.
   ​

   $(A\wedge B)\to C\therefore A\to (B\to C)$

3. 3.
   ​

   $A\to (B\to C)\therefore (A\to B)\to (A\to C)$

4. 4.
   ​

   $A\vee (B\wedge C)\therefore (A\vee B)\wedge (A\vee C)$

5. 5.
   ​

   $(A\wedge B)\vee (A\wedge C)\therefore A\wedge (B\vee C)$

6. 6.
   ​

   $A\vee B,A\to C,B\to D\therefore C\vee D$

7. 7.
   ​

   $\mathrm{\neg }A\vee \mathrm{\neg }B\therefore \mathrm{\neg }(A\wedge B)$

8. 8.
   ​

   $A\wedge \mathrm{\neg }B\therefore \mathrm{\neg }(A\to B)$

B. Formulate strategies for working backward and forward from $𝒜\leftrightarrow ℬ$.

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

1. 1.
   ​

   $\mathrm{\neg }A\to (A\to \perp )$

2. 2.
   ​

   $\mathrm{\neg }(A\wedge \mathrm{\neg }A)$

3. 3.
   ​

   $[(A\to C)\wedge (B\to C)]\to [(A\vee B)\to C]$

4. 4.
   ​

   $\mathrm{\neg }(A\to B)\to (A\wedge \mathrm{\neg }B)$

5. 5.
   ​

   $(\mathrm{\neg }A\vee B)\to (A\to B)$

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

   $\mathrm{\neg }\mathrm{\neg }A\to A$

2. 2.
   ​

   $\mathrm{\neg }A\to \mathrm{\neg }B\therefore B\to A$

3. 3.
   ​

   $A\to B\therefore \mathrm{\neg }A\vee B$

4. 4.
   ​

   $\mathrm{\neg }(A\wedge B)\to (\mathrm{\neg }A\vee \mathrm{\neg }B)$

5. 5.
   ​

   $A\to (B\vee C)\therefore (A\to B)\vee (A\to C)$

6. 6.
   ​

   $(A\to B)\vee (B\to A)$

7. 7.
   ​

   $((A\to B)\to A)\to A$

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