Subsection 3.5.6 Disjunctive Syllogism Proof Example: Who Drives Me? - Continued
How shall we start? We notice that the only one of our premises that mentions W is [6]. In order to use it (with Modus Ponens), we’ll have to know Y. We could derive Y using [5] if we knew G. We could derive G from [4] if we knew M. How can we prove M? The only premise that mentions M is [1], so somehow we’re going to have to use it. In order to use it to produce M by itself, we could use Disjunctive Syllogism. But to do that, we’d have to know J. Can we prove that? Sure. We can apply Modus Tollens to [2] and [3]. Okay, so we’ve got a plan. To come up with it, we reasoned backward from what we wanted to prove.
But this is important: While we walked backward to figure out what to do, the actual proof must proceed forward from the premises to the conclusions. Let’s do the first step:
J M Premise
J L Premise
L Premise
M G Premise
G Y Premise
Y W Premise
J Modus Tollens [2], [3]
M Disjunctive Syllogism [7], [1]
G Modus Ponens [4], [8]
Y Modus Ponens [5], [9]
W Modus Ponens [6], [10]
Notice that this example is a poster child for natural deduction as an alternative to proof by truth table, at least when the proofs have to be constructed by people. It uses six variables. So the truth table that we’d have to build for it would have 2 6 = 64 rows and 13 columns, for a total of 832 entries. While automatic proving systems can easily handle truth tables that are orders of magnitude bigger than that, we sure don’t want to have to write them out by hand.
