# 6.3: Derivations: Overview, Definitions, and Points to Watch out for

This chapter and chapter 5 have described, explained, and illustrated derivations. Let's pull these thoughts together with some explicit definitions and further terminology.

A Rule of Inference tells when you are allowed, or Licensed, to draw a conclusion from one or more sentences or from a whole argument (as represented by a subderivation).

A Derivation is a list of which each member is either a sentence or another derivation. If a first derivation has a second derivation as one of the first derivation's parts, the second derivation is called a Subderivation of the first and the first is called the Outer Derivation, of the second. Each sentence in a derivation is a premise or assumption, or a reiteration of a previous sentence from the same derivation or an outer derivation, or a sentence which follows by one of the rules of inference from previous sentences or subderivations of the derivation.

In practice, we always list the premises or assumptions of a derivation at its beginning, and use a horizontal line to separate them from the further sentences which follow as conclusions. What's the difference between premises and assumptions? From a formal point of view, there is no difference at all, in the sense that the rules of inference treat premises and assumptions in exactly the same way. In practice, when an unargued sentence is assumed at the beginning of the outermost deduction, we call it a premise. When an unargued sentence is assumed at the beginning of a subderivation, we call it an assumption. The point is that we always terminate subderivations before the end of a main derivation, and when we terminate a subderivation, in some sense we have gotten rid of, or Discharged, the subderivation's assumptions.

To make these ideas clearer and more precise, we have to think through what the vertical lines, or Scope Lines, are doing for us?

A Scope Line tells us what sentences and subderivations hang together as a single derivation. Given a vertical scope line, the derivation it marks begins where the line begins and ends where the line ends. The derivation marked by a scope tine includes all and only the sentences and subderivations immediately to the right of the scope tine.

To help sort out these definitions, here is a schematic example:

| Q
| R
| S
| .
| .
| .
| | T
| | .
| | .
| | .
| 2| U
| .
| .
| .
| | V
| | .
| | .
| | .
| | | W
| | | .
| | | .
| | | .
| | 4| X
| 3 | Y
| .
| .
| .
1 | Z

Notice that at the bottom of each scope line I have written a number to help us in talking about the different component derivations. Consider first the main derivation, derivation 1, marked with the leftmost scope line numbered '1' at its bottom. Derivation 1 includes premises Q and R and has a first conclusion S, other conclusions not explicitly shown, indicated by . . . , and the final conclusion Z. Derivation 1 also includes two subderivations, derivations 2 and 3. Derivation 2 has assumption T, various conclusions not explicitly indicated (again signaled by . . .), and final conclusion U. Derivation 3 starts with assumption V, has final conclusion Y, and includes a subderivation of its own, derivation 4.

This organization serves the purpose of keeping track of what follows from what. In the outermost derivation 1, all the conclusions of the derivation (S . . . Z) follow from the derivation's premises, Q and R. This means that every assignment of truth values to sentence letters which makes the premises Q and R true will make all the conclusions of derivation 1 true. But the conclusions of a subderivation hold only under the subderivation's additional assumption. For example, the conclusion U of subderivation 2 is subject to the assumption T as well as the premises Q and R. This means that we are only guaranteed that any assignment of truth values to sentence letters which makes Q, R, and T all true will make U true also. In other words, when we start a subderivation, we add an additional assumption which is assumed in effect just in the subderivation. Any premises or assumptions from outer derivations also apply in the subderivation, since they and their consequences can be reiterated into the subderivation.

You should particularly notice that when a subderivation has ended, its special assumption is no longer assumed. It is not assumed in any conclusions drawn as part of the outer derivation, nor is it assumed as part of a new subderivation which starts with a different assumption. Thus the truth of T is not being assumed anywhere in derivation 1, 3, or 4. This is what we mean by saying that the assumption of a subderivation has been discharged when the subderivation is terminated.

These facts are encoded in the reiteration rule which we can now spell out more clearly than before. The reiteration rule spells out the fact that a subderivation assumes the truth, not only of its own assumption, but of the prior assumptions, premises, and conclusions of any outer derivation. Thus, in subderivation 2, reiteration permits us to write, as part of 2, Q, R, S, or any other conclusion of 1 which appears before 2 starts. This is because inside 2, we assume that the premises of outer derivation 1 are true. Andrbecause whenever the premises are true, conclusions which follow from them are true, we may also use the truth of any such conclusions which have already followed from these premises.

But we cannot reiterate a sentence of 2 in, for example, 1. This is because when we end subderivation 2 we have discharged its premise. That is, we are no longer arguing under the assumption that the assumption of 2 is true. So, for example, it would be a mistake to reiterate U as part of 1. U has been proved only subject to the additional assumption T. In 1, T is not being assumed. In the same way, we cannot reiterate U as part of 3 or 4. When we get to 3, subderivation 2 has been ended. Its special assumption, T, has been discharged, which is to say that we no longer are arguing under the assumption of T.

Students very commonly make the mistake of copying a conclusion of a subderivation, such as U, as a conclusion of an outer derivation-' m our schematic example, listing U as a conclusion in derivation 1 as well as in subderivation 2. I'll call this mistake the mistake of hopping scope lines. Don't hop scope lines!

We can, however, reiterate Q, R, S, or any prior conclusion in 1 within sub-sub-derivation 4. Why? Because 4 is operating under its special assumption, W, as well as all the assumptions and premises of all derivations which are outer to 4. Inside 4 we are operating under all the assumptions which are operative in 3, which include not only the assumption of 3 but all the premises of the derivation of which 3 is a part, namely, 1. All this can be expressed formally with the reiteration rule, as follows: To get a premise or prior conclusion of 1 into 4, first reiterate the sentence in question as part of 3. Now that sentence, officially part of 3, can be reiterated again in 4. But we can dispense with the intermediate step.

Incidentally, once you clearly understand the reiteration rule, you may find it very tiresome always to have to explicitly copy the reiterated sentences you need in subderivations. Why, you may wonder, should you not be allowed, when you apply other rules, simply to appeal to prior sentences in outer derivations, that is, to the sentences which the reiteration rule allows you to reiterate? If you fully understand the reiteration rule, you will do no harm in thus streamlining your derivations. I will not use this abbreviation, because I want to be sure that all of my readers understand as clearly as possible how reiteration works. You also should not abbreviate your derivations in this way unless your instructor gives you explicit permission to do so.

Scope lines also indicate the sentences to which we can apply a rule in deriving a conclusion in a derivation or subderivation. Let us first focus on rules which apply only to sentences, that is, rules such as vE or ⊃E, which have nothing to do with subderivations. The crucial feature of such a rule is that, if the sentences to which we apply it are true, the conclusion will be true also. Suppose, now, we apply such a rule to the premises Q and R of derivation 1. Then, if the premises are true, so will the rule's conclusion, so that we can write any such conclusion as part of derivation 1. In further application of such rules in reaching conclusions of derivation 1, we may appeal to 1's prior conclusions as well as its premises, since if the premises are true, so will the prior conclusions. In this way we are still guaranteed that if the premises are true, so will the new conclusion.

But we can't apply such a rule to assumptions or conclusions of a subderivation in drawing conclusions to be made part of derivation 1. For example, we can't apply a rule to sentences S and U in drawing a conclusion which will be entered as a part of derivation 1. Why not? Because we want all the conclusions of 1 to be guaranteed to be true if 1's premises are true. But assumptions or conclusions of a subderivation, say, 2, are only sure to be true if 1's premises and 2's special assumption are true.

In sum, when applying a rule of inference which provides a conclusion when applied to sentences ("input sentences"), the input sentences must already appear before the rule is applied, and all input sentences as well as the conclusion must appear in the same derivation. Violating this instruction constitutes a second form of the mistake of hopping scope lines.

What about ⊃I and ~I, which don't have sentences as input? Both these rules have the form: If a subderivation of such and such a form appears in a derivation, you may conclude so and so. It is important to appreciate that these two rules do not appeal to the sentences which appear in the subderivation. They appeal to the subderivation as a whole. They appeal not to any particular sentences, but to the fact that from one sentence we have derived certain other sentences. That is why when we annotate these rules we cite the whole subderivation to which the rule applies, by indicating the inclusive line numbers of the subderivation.

Consider ⊃I. Suppose that from T we have derived U, perhaps using the premises and prior conclusions of our outer derivation. Given this fact, any assignment of truth values to sentence letters which makes the outer derivation's premises true will also make the conditional T⊃U true. (1 explained why in the last chapter.) Thus, given a subderivation like 2 from T to U, we can write the conclusion T⊃U as part of the outer derivation 1. If 1's premises are true, T⊃U will surely be true also.

The key point to remember here is that when ⊃I and ~I apply to a subderivation, the conclusion licensed appears in the same derivation in which the input subderivation appeared as a part. Subderivation 2 licenses the conclusion T⊃Y as a conclusion of 1, by ⊃I; and ⊃I, similarly applied to derivation 4, licenses concluding W⊃X as part of 3, but not as part of 1.

By this time you may be feeling buried under a pile of details and mistakes to watch out for. Natural deduction may not yet seem all that natural. But, as you practice, you will find that the bits come to hang together in a very natural way. With experience, all these details will become second nature so that you can focus on the challenging task of devising a good way of squeezing a given conclusion out of the premises you are allowed to use.

Exercise $$\PageIndex{1}$$

For each of the following arguments, provide a derivation which shows the argument to be valid. If you get stuck on one problem, try another. If you get good and stuck, read over the examples , in this chapter, and then try again.

a) R b) (~A&B)vC c) ~(Hv~D) d) F⊃(O⊃M)
(RvD)&(RvK) AvD F⊃H (F&O)⊃M
~C⊃D ~F

e) P&~Q f) (K&G)⊃S g) ~(A&~F) h) ~(N⊃I)
~R⊃~[P⊃(RvQ)] K⊃(G⊃S) D⊃A ~I⊃C
D⊃F C

i) ~M~L j) QvF k) ~(S&T) l) ~C⊃(AvB)
~L⊃~K Q⊃A SvT ~D⊃(Cv~B)
K⊃M F⊃A ~S≡T ~(cvD)
A (AvB)&(Cv~B)

m) G≡~H n) P≡Q o) (N⊃S)&(G⊃D)
~GH ~(P≡~Q) (SvD)⊃{[F⊃(FvK)]⊃(N&G)}
N≡G
p) (S&B)⊃K q) CvB r) H⊃(D⊃K)
(G⊃P))&(GvP) ~(C&~B) (K&M)⊃P
~B≡(~P&G) ~(~C&B) J⊃~(M⊃P)
S⊃K C&(Bv~C) H⊃(D⊃~I)

6-4. Write a rule of inference for the Sheffer stroke, defined in section 3-5.

chapter summary Exercise

This chapter has focused on improving your understanding of material introduced in chapter 5, so there are only a few new ideas. Complete short explanations in your notebook for the following terms. But also go back to your explanations for the terms in the chapter summary exercises for chapter 5 and see if you can now explain any of these terms more accurately and clearly.