Subsection 3.5.4 Creating Natural Deduction Proofs
We’re going to walk through the process of constructing natural deduction proofs for a collection of representative examples.
For each of these problems, we suggest that you first try to do the proof yourself. You can do this with StepWise, our interactive proof checker.
You can also watch a video in which we walk through the construction of a proof.
Forward Reasoning – Modus Ponens Proof Example: Relaxing
Relaxing:
We’ll start with a simple example. We’ll do this one with just symbols (p, q, r, and s) so that we’re not distracted by a particular real world problem. At the end, we’ll suggest such a problem that could correspond to this generic proof.
Prove:
\(p \)
\( q \)
\((q s) r\)
\( r \)
You should try to do this proof yourself:
You can also watch our video, which will outline a strategy for creating a proof.
On the next page, you’ll find a summary of the approach that is described in the video.
We are given three hypotheses and, although we do not know if we will use them all, let’s include them all in the proof – if we notice some are superfluous, we can delete them later. So we can write the first three lines of our proof of r:
[1] p Premise
[2] p q Premise
[3] (q s) r Premise
Now let’s do some strategizing. The first thing to notice is that (on the basis of what our premises tell us) the only way to conclude r is first to derive q s. The role of s is perplexing – it appears nowhere else. It’s one of those “out of thin air” sorts of statements. Two of our inference rules allow for statements to be introduced out of thin air: Addition and Contradictory Premises. Using Contradictory Premises is fairly rare since it requires a contradiction – and a glance at the premises doesn’t suggest any contradiction. Thus it appears that the use of Addition is going to be one key to this proof.
We need to obtain q somehow before we can use addition to get q s. But that’s easy from the premises, by using Modus Ponens. Thus the next line of the proof is:
[4] q Modus Ponens [1], [2]
Remember that [1], [2] indicates that we have used lines 1 and 2.
Now it is easy to get q s using Addition:
[5] q s Addition [4]
Finally, another use of Modus Ponens gets our conclusion:
[6] r Modus Ponens [3], [5]
Notice, by the way, that we did use all of the hypotheses. We could check by seeing if each of the premise line numbers [1], [2], and [3] in this case, appears someplace in the rightmost column. Here’s our complete proof:
[1] p Premise
[2] p q Premise
[3] (q s) r Premise
[4] q Modus Ponens [1], [2]
[5] q s Addition [4]
[6] r Modus Ponens [3], [5]
By the way, this example could have come from a more real world seeming problem: Suppose we are given that Peter is home, the home will be Quiet when Peter is home, and if the home is Quiet or it is TueSday it’s easy to Relax. We prove that it’s easy to Relax.