5.3: The Complete Rules of Inference

We now have in place all the basic ideas of natural deduction. We need I only to complete the rules. So &at you will have them all in one place for easy reference, I will simply state them all in abbreviated form and then comment on the new ones. Also, I will now state all of the rules using the same format. For each rule I will show a schematic derivation with one part in a box and another part in a circle. In the box you will find, depending on the rule, either one or two sentence forms or a subderivation form. In the circle you will find a sentence form. To apply a given rule in an actual derivation, you proceed as follows: You look to see whether the derivation has something with the same form as what's in the box. If so, the rule licenses you to write down, as a new conclusion, a sentence with the form of what's in the circle.  Reiterntion: If a sentence occurs, either as a premise or as a conclusion in a derivation, that sentence may be copied (reiterated) in any of that derivation's lower subderivations, or lower down in the same derivation.

In interpreting these schematic statements of the rules, you must remember the following: When a rule applies to two sentences, as in the case of conjunction introduction, the two sentences can occur in either order, and they may be separated by other sentences. The sentences to which a rule applies may be premises, an assumption, or prior conclusions, always of the same derivation, that is, lying along the same scope line. Also, the sentence which a rule licenses you to draw may be written anywhere below the licensing sentences or derivation, but as part of the same derivation, again, along the same scope line.

Conjunction introduction and elimination are so simple we rarely bother to mention them when we argue informally. But to be rigorous and complete, our system must state and use them explicitly. Conjunction introduction states that when two sentences, X and Y, appear in a derivation, in either order and whether or not separated by other sentences, we may conclude their conjunction, X&Y, anywhere below the two conjunct~. Conjunction elimination just tells us that if a conjunction of the form X&Y appears on a derivation, we may write either conjunct (or both, on different lines) anywhere lower down on the derivation. We have already discussed the rules for disjunction and the conditional. Here we need only add that in the elimination rules, the sentences to which the rules apply may occur in either order and may be separated by other sentences. For example, when applying disjunction elimination, the rule applies to sentences of the form XvY and ~X, in whatever order those sentences occur and whether or not other sentences appear between them.

Biconditional introduction and elimination really just express the fact that a biconditional of the form X≡Y is logically equivalent to the conjunction of sentences of the form X⊃Y and Y⊃X. If the two conditionals appear on a derivation, whatever the order, and whether or not separated by other sentences, we may write the biconditional lower down as a conclusion. Conversely, if a biconditional of the form X≡Y appears, one may write lower down, as a conclusion, X⊃Y, Y⊃X, or both (on separate lines).

Note that negation elimination licenses dropping a double negation, and is justified by the fact that X is always logically equivalent to ~~X. Negation introduction requires some comment. Once again, natural deduction seeks to capture and make precise conventional forms of informal argument. This time we express what traditionally goes under the name of "reductio ad absurdum," or "reduction to the absurd." Here the idea is that if we begin with an assumption from which we can deduce a contradiction, the original assumption must be false. Natural deduction employs this strategy as follows: Begin a subderivation with an assumption, X. If one succeeds in deriving both a sentence of the form Y and its negation, ~Y, write the sentence of the form ~X as a conclusion of the outer derivation anywhere below the subderivation.

As with the other rules, you should be sure you understand why this rule works. Suppose in a subderivation we have drawn the conclusions Y and ~Y from the assumption X. This is (by the rules for conjunction) equivalent to deriving the contradiction Y&~Y from X. Now, X must be either true or false. If it is true, and we have drawn from it the conclusion that Y&~Y, we have a valid argument from a true premise to a false conclusion. But that can't happen--our rules for derivations won't let that happen. So X must have been false, in which case ~X must be true and can be entered as a conclusion in the outer derivation. Finally, if the subderivation has used premises or conclusions of the outer derivation, we can reason in exactly the same way, but subject to the restriction that we consider only cases in which the original premises were true.

In annotating negation introduction, keep in mind the same consideration which applied in annotating conditional introduction. The new line is justified by appeal, not to any one or two lines, but to a whole argument, represented by a subderivation. Consequently, the justification for the new line appeals to the whole subderivation. Indicate this fact by writing down the inclusive line numbers of the subderivation (the first and last of its line numbers separated by a dash).

In applying these rules, be sure to keep the following in mind: To apply the rules for conditional and negation introduction, you must always have a completed subderivation of the form shown. It's the presence of the subderivation of the right form which licenses the introduction of a conditional or a negated sentence. To apply any of the other rules, you must have the input sentence or sentences (the sentence or sentences in the box in the rule's schematic statement) to be licensed to write the output sentence of the rule (the sentence in the circle in the schematic presentation). But an input sentence can itself be either a prior conclusion in the derivation or an original premise or assumption.

Incidentally, you might have been puzzled by the rule for negation introduction. The rule for negation elimination has the form "~~X. Therefore X". Why not, you might wonder, use the rule "X. Therefore ~~X for negation introduction? That's a good question. The rule "X. Therefore ~~X" is a correct rule in the sense that it is truth preserving. It will never get you a false sentence out of true ones. But the rule is not strong enough. For example, given the other rules, if you restrict yourself to the rule "X. Therefore ~~X for negation introduction, you will never be able to construct a derivation that shows the argument

~A
~(A&B)

to be valid. We want our system of natural deduction not only to be Sound, which means that every derivation represents a valid argument. We also want it to be Complete, which means that every valid argument is represented by a derivation. If we use the rule "X. Therefore ~~X" for negation introduction, our system of natural deduction will not be complete. The rules will not be strong enough to provide a correct derivation for every valid argument.

Exercise

5-3. Below you find some correct derivations without the annotations which tell you, for each line, which rule was used in writing the line and to which previous line or lines the rule appeals. Copy the derivations and add the annotations. That is, for each line, write the line number of the previous line or lines and the rule which, applying to those previous lines, justifies the line you are annotating.

a) 1 | B&(B⊃~A) P c) 1 | A⊃~B P
2 | B 2 | BvC P
3 | B⊃~A 3 | |
4 | ~A | | A
b) 1 | ~C≡(AvB) P 4 | | A⊃~B
2 | A P 5 | | ~B
3 | (AvB) ⊃ ~C 6 | | BvC
4 | AvB 7 | | C
5 | ~C 8 | A ⊃ C

d) 1 | D P e) 1 | AvB P
2 | (D&A)⊃C P 2 | | ~A&~B
3 | | A 3 | | ~A
4 | | D 4 | | ~B
5 | | D&A 5 | | AvB
6 | | (D&A)⊃C 6 | | B
7 | | C 7 | ~(~A&~B)
8 | A⊃C

f) 1 | A&B P g) 1 | ~A⊃B P
2 | | A 2 | ~A⊃~B P
3 | | A&B 3 | | ~A
4 | | B 4 | | ~A⊃B
5 | A⊃B 5 | | B
6 | | B 6 | | ~A⊃~B
7 | | A&B 7 | | ~B
8 | | A 8 | ~~A
9 | B⊃A 9 | A
10 | A≡B

5-4. For each of the following arguments, provide a derivation which shows the argument to be valid. Follow the same directions as you did for exercises 5-1 and 5-2.

a) C&~H b) JvD c) A&B d) A⊃~D
~H ~~~D B&A ~~A
J ~D
e) G⊃D f) A≡~B g) M h) A&(B&C)
G⊃~D ~B⊃A Rv~H (A&B)&C
~G M&(Rv~H)
i) ~C⊃D j) A≡~B k) ~C⊃~~~A l) K⊃~B
D⊃~C ~B ~C B&F
D≡~C A ~A ~K
m) ~P n) (N⊃K)&(N⊃L) o) D⊃(AvF) p) H≡J
~Q N⊃(K&L) D⊃~F H≡K
~(PvQ) ~A J≡K
~D&~A

5-5. In chapter 3 we defined triple conjunctions and disjunctions, that is, sentences of the form X&Y&Z and XvYvZ. Write introduction and elimination rules for such triple conjunctions and disjunctions.

5-6. Suppose we have a valid argument and an assignment of truth values to sentence letters which makes one or more of the premises false. What, then, can we say about the truth value of the conclusions which follow validly from the premises? Do they have to be false? Can they be true? Prove what you say by providing illustrations of your answers.

chapter summary Exercise

Give brief explanations for each of the following, referring back to the text to make sure your explanations are correct and saving your answers in your notebook for reference and review.

a) Derivation

b) Subderivation

c) Outer Derivation

d) Scope Line

e) Premise

f) Assumption

g) Rule of Inference

h) License (to draw a conclusion)

i) Truth Reserving Rule

j) Discharging an Assumption

k) Conjunction Introduction

l) Conjunction Elimination

m) Disjunction Introduction

n) Disjunction Elimination

o) Conditional Introduction

p) Conditional Elimination

q) Biconditional Introduction

r) Biconditional Elimination

s) Negation Introduction

t) Negation Elimination

u) Reiteration