5.1: The Idea of Natural Deduction

In chapter 4 you learned that saying an argument is valid means that any case which makes all of the argument's premises true also makes its conclusion true. And you learned how to test for validity by using truth tables, by exhaustively checking all the relevant cases, that is, all the lines of the truth table. But truth tables are horribly awkward. It would be nice to have a way to check validity which looked more like the forms of argument we know from everyday life.

Natural deduction does just that. When we speak informally, we use many kinds of valid arguments. (I'll give some examples in a moment.) Natural deduction makes these familiar forms of argument exact. It also organizes them in a system of valid arguments in which we can represent absolutely any valid argument.

Let's look at some simple and, I hope, familiar forms of argument. Suppose I know (say, because I know Adam's character) that if Adam loves Eve, then he will ask Eve to many him. I then find out from Adam's best friend that Adam does indeed love Eve. Being a bright fellow, I immediately conclude that a proposal is in the offing. In so doing I have used the form of argument traditionally called 'modus ponens', but which I am going to call Conditional Elimination.

Conditional Elimination

X⊃Y
X ⊃E
Y

Logicians call such an argument form a Rule of Inference. If, in the course of an argument, you are given as premises (or you have already concluded) a sentence of the form X⊃Y and the sentence X, you may draw as a conclusion the sentence Y. This is because, as you can check with a truth table, in any case in which sentences of the form X⊃Y and X are both true, the sentence Y will be true also. You may notice that I have stated these facts, not for some particular sentences 'A⊃B', 'A', and 'B', but for sentence forms expressed with boldfaced 'X' and 'Y'. This is to emphasize the fact that this form of argument is valid no matter what specific sentences might occur in the place of 'X' and 'Y'.
Here is another example of a very simple and common argument form, or rule of inference:

Disjunction Elimination

XvY
~X vE
Y

If I know that either Eve will marry Adam or she will marry no one, and I then somehow establish that she will not marry Adam (perhaps Adam has promised himself to another), I can conclude that Eve will marry no one. (Sorry, even in a logic text not all love stories end happily!) Once again, as a truth table will show, this form of argument is valid no matter what sentences occur in the place of 'X' and in the place of 'Y'.

Though you may never have stopped explicitly to formulate such rules of argument, all of us use rules like these. When we argue we also do more complicated things. We often give longer chains of argument which start from some premises and then repeatedly use rules in a series of steps. We apply a rule to premises to get an intermediate conclusion. And then, having established the intermediate conclusion, we can use it (often together with some of the other original premises) to draw further conclusions.

Let's look at an example to illustrate how this process works. Suppose you are given the sentences 'A⊃B', 'B⊃C', and 'A' as premises. You are asked to show that from these premises the conclusion 'C' follows. How can you do this?

It's not too hard. From the premises 'A⊃B' and 'A', the rule of conditional elimination immediately allows you to infer 'B':

A⊃B
A ⊃E
C

But now you have 'B' available in addition to the original premise 'B⊃C'. From these two sentences, the rule of conditional elimination allows you to infer the desired conclusion 'C':

B⊃C
B ⊃E
C

I hope this example is easy to follow. But if I tried to write out an example with seven steps in this format, things would get impossibly confusing. We need a streamlined way of writing chains of argument.

The basic idea is very simple. We begin by writing all our premises and then drawing a line to separate them from the conclusions which follow. But now we allow ourselves to write any number of conclusions below the line, as long as the conclusions follow from the premises. With some further details, which I'll explain in a minute, the last example looks like this:

1 | A⊃B P
2 | B⊃C P
3 | A P
4 | B 1,3,⊃E
5 | C 2,4,⊃E

Lines 1 through 5 constitute a Derivation of conclusions 4 and 5 from premises 1, 2, and 3. In thinking about such a derivation, you should keep most clearly in mind the idea that the conclusions are supposed to follow from the premises, in the following sense: Any assignment of truth values to sentence letters which makes the premises all true will also make all of the conclusions true.

In a derivation, every sentence below the horizontal line follows from the premises above the line. But sentences below the line may follow directly or indirectly. A sentence follows directly from the premises if a rule of inference applies directly to premises to allow you to draw the sentence as a conclusion. This is the way I obtained line 4. A sentence follows indirectly from the premises if a rule of inference applies to some conclusion already obtained (and possibly also to an original premise) to allow you to draw the sentence as a conclusion. The notation on the right tells you that the first three sentences are premises. It tells you that line 4 is Licensed (i.e., permitted) by applying the rule of conditional elimination to the sentence of lines 1 and 3. And the notation for line 5 tells you that line 5 is licensed by applying the rule of conditional elimination to the sentences of lines 2 and 4.

For the moment don't worry too much about the vertical line on the left. It's called a Scope Line. Roughly speaking, the scope line shows what hangs together as one extended chain of argument. You will see why scope lines are useful when we introduce a new idea in the next section. You should be sure you understand why it is legitimate to draw conclusions indirectly from premises, by appealing to previous conclusions. Again, what we want to guarantee is that any case (i.e., any assignment of truth values to sentence letters) which makes the premises true will also make each of the conclusions true. We design the rules of inference so that whenever they apply to sentences and these sentences happen to be true, then the conclusion licensed by the rule will be true also. For short, we say that the rules are Truth Preserving.

Suppose we have a case in which all of the premises are true. We apply a rule to some of the premises, and because the rule is truth preserving, the conclusion it licenses will, in our present case, also be true. (Line 4 in the last example illustrates this.) But if we again apply a rule, this time to our first conclusion (and possibly some premise), we are again applying a rule to sentences which are, in the present case, all true. So the further conclusion licensed by the rule will be true too. (As an illustration, look at line 5 in the last example.) In this way, we see that if we start with a case in which all the premises are true and use only truth preserving rules, all the sentences which follow in this manner will be true also.
To practice, let's try another example. We'll need a new rule:

Disjunction Introduction -

X vl
XvY

which says that if X is true, then so is XvY. If you recall the truth table definition of 'v', you will see that disjunction introduction is a correct, truth preserving rule of inference. The truth of even one of the disjuncts in a disjunction is enough to make the whole disjunction true. So if X is true, then so is XvY, whatever the truth value of Y.

Let's apply this new rule, together with our two previous rules, to show that from the premises 'A⊃~B', 'BvC', and 'A', we can draw the conclusion 'CvD'. But first close the book and see if you can do it for yourself.

The derivation looks like this:

1 | A⊃~B P
2 | B⊃C P
3 | A P
4 | ~B 1, 3, ⊃E
5 | C 2, 4, vE
6 | CvD 5, vl

The sentence of line 4 (I'll just say "line 4" for short) is licensed by applying conditional elimination to lines 1 and 3. Line 5 is licensed by applying disjunction elimination to lines 2 and 4. Finally, I license line 6 by applying disjunction introduction to line 5.

Exercise

5-1. For each of the following arguments, provide a derivation which shows the argument to be valid. That is, for each argument construct a derivation which uses as premises the argument's premises and which has as final conclusion the conclusion of the argument. Be sure to number and annotate each step as I have done with the examples in the text. That is, for each conclusion, list the rule which licenses drawing the conclusion and the line numbers of the sentences to which the rule applies.

a) ~P⊃~D b) ~C⊃~D c) Fv~G d) A⊃B e) Lv~M
~D⊃~F ~C ~F A ~L
~P ~DvE GvK B⊃~C MvD
~F K CvD D⊃H
DvE H

f) C g) (Kv~D)⊃F h) D
C⊃(HvA) K (DvB)⊃~G
~H FvD (~Gv~H)⊃(GvQ)
Av~K Qv~A

i) (Mv~T)⊃(AvJ)
~A
BvM
~A⊃~B
JvD