2.6.1: Constructing Correct Derivations

Knowing the rules for constructing derivations is one thing. Being able to apply the rules successfully is another. There are no simple mechanical guidelines to tell you which rule to apply next, so constructing derivations is a matter of skill and ingenuity. Long derivations can be extremely difficult. (It's not hard to come up with problems which will stump your instructorl) At first, most students feel they don't even know how to get started. But with a bit of practice and experience, you will begin to develop some intuitive skill in knowing how to organize a derivation. To get you started, here are some examples and practical strategies.

Usually you will be setting a problem in the following form: You will be given some premises and a conclusion. You will be told to prove that the conclusion follows validly from the premises by constructing a derivation which begins with the given premises and which terminates with the given conclusion. So you already know how your derivation will begin and end.

Your job is to fill in the intermediate steps so that each line follows from previous lines by one of the rules. In filling in, you should look at both the beginning and the end of the derivation.

Let's illustrate this kind of thinking with a simple example. Suppose you are asked to derive 'B&C' from the premises 'A⊃B', 'A⊃C', and 'A'. Right off, you know that the derivation will take the form

1 | A⊃B P
2 | A⊃C P
3 | A P
| ?
| ?
| ?
| B&C

where you still have to figure out what replaces the question marks.

First, look at the conclusion. It is a conjunction, which can most straightforwardly be introduced with the rule for &I. (From now on, I'm going to use the shorthand names of the rules.) What do you need to apply that rule? You need 'B' and you need 'C'. So if you can derive 'B' and 'C', you can apply &I to get 'B&C'. Can you derive 'B' and 'C'? Look at the premises. Can you get 'B' out of them? Yes, by applying ⊃E to lines 1 and 3. Similarly, you can derive 'C' from lines 2 and 3. Altogether, the derivation will look like this:

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

Let's try a slightly harder example. Suppose you are asked to derive 'C~A' from the premises 'AvB' and 'C⊃~B'. Your target conclusion is a conditional. Well, what rule allows you to conclude a conditional? ⊃1. So you will try to set things up so that you can apply ⊃I. This will involve starting a subderivation with 'C' as its assumption, in which you will try to perive 'A'. In outline, the derivation you are hoping to construct can be expected to look like this:

1 | A⊃B P
2 | C⊃~B P
3 | | C A
| | ?
| | ?
| | A
| C⊃A

(Your derivation won't have to look like this. In every case there is more than one correct derivation of a conclusion which follows from a given set of premises. But in this case, this is the obvious thing to try, and it provides the simplest correct derivation.)

To complete the derivation, you must fill in the steps in the subderivation to show that (given the premises of the outer derivation) 'A' follows from 'C'.

How will you do this? Let's study what you have available to use. In the subderivation you are allowed to use the subderivation's assumption and also any previous premise or conclusion in the outer derivation. Notice that from 'C' and the premise 'C⊃~B' you can get '~B' by ⊃E. Is that going to do any good? Yes, for you can then apply vE to '~B' and the premise 'AvB' to get the desired 'A'. All this is going to take place in the subderivation, so you will have to reiterate the premises. The completed derivation looks like this:

1 | AvB P
2 | C⊃~B P
3 | | C A
4 | | C⊃~B 2, R
5 | | ~B 3, 4, ⊃E
6 | | AvB 1, R
7 | | A 5, 6, vE
8 | C⊃A 3-7, ⊃l

If you are still feeling a little lost and bewildered, reread the text from the beginning of this section.

When you have understood the examples given so far, you are ready for something new. Let's try to derive 'A⊃~B' from 'B⊃~A'. As in the second example, our first effort to derive a conditional should be by using ⊃I. So we want a subderivation with 'A' as assumption and '~B' as final conclusion:

1 | B⊃~A P
2 | | A A
| | ?
| | ?
| | ~B
| A⊃~B ⊃l

But how can we get '~B' from the assumption of 'A', using the premise of the outer derivation?

'~B' is the negation of the sentence 'B'. Unless there is some really obvious simple alternative, one naturally tries to use ~I. ~I works by starting a subderivation with the sentence to be negated as assumption and then deriving some sentence and its negation. In the present situation this involves something that might not have occurred to you, namely, creating a subderivation of a subderivation. But that's fine. All the rules for working on a derivation apply to subderivations also, including the creation of subderivations. The only difference between a subderivation and a derivation is that a subderivation ends when we discharge its assumption, returning to its outer derivation; and that in a subderivation we may reiterate prior premises or conclusions from an outer derivation (or from any outer-outer derivation, as you will see in a moment). This is because in a subderivation we are working under the assumption that all outer assumptions and premises are true.

Will this strategy work? Before writing anything down, let me illustrate the informal thinking you should go through to see whether a strategy promises to be successful. Look back at the outline we have already written of how we hope the derivation will look. We are proposing to start a sub-sub-derivation with the new assumption 'B'. That sub-sub-derivation can use the original premise 'B⊃~A', which, together with the assumption 'B', will give '~A' by ⊃E. But the sub-sub-derivation is also within its outer derivation beginning with the assumption of 'A'. So 'A' is also being assumed in the sub-sub-derivation, which we express by reiterating 'A' in the sub-sub-derivation. The sub-sub-derivation now has both 'A' and '~A', which constitutes the contradiction we needed:

1 | B⊃~A P
2 | |A A
3 | | | B A
4 | | | B⊃~A 1, R
5 | | | ~A 3, 4, ⊃E
6 | | | A 2, R
7 | | ~B 3-6, ~I
8 | A⊃~B 2-7, ⊃I

How are you doing? If you have had trouble following, rest for a moment, review to be sure you have gotten everything up to this point, and then we'll try something one step more involved.

Let's try deriving 'A≡~B' from 'AvB' and '~(A&B)'. The conclusion is a biconditional, and one derives a biconditional most easily by using ≡I. Think of a biconditional as the conjunction of two conditionals, the two conditionals we need to derive the biconditional using ≡I. So you should aim to develop a derivation along these lines:

1 | AvB P
2 | ~(AvB) P
3 | ?
4 | ?
5 | ~B⊃A
6 | ?
7 | ?
8 | A⊃~B
9 | A≡~B ≡I

We have reduced the complicated problem of deducing 'A≡~B' to the simpler problems of deducing '~B⊃A' and 'A⊃~B'.

In constructing derivations, you should learn to think in this kind of pattern. Try to resolve the problem of deriving the final conclusion (your target conclusion) by breaking it down into simpler problems of deriving . simpler sentences (your new target conclusions). You may actually need to resolve your simpler problems intostill more simple problems. You continue working backward toward the middle until you can see how to derive your simple sentences from the premises. At this point you start working from the premises forward and fill everything in.

How, in this example, can we derive our simplified new target conclusions? They are both conditionals, and as we saw in the second example, the straightforward way to derive conditionals uses ⊃I. This involves starting one subderivation for each of the conditionals to be derived:

1 | AvB P
2 | ~(AvB) P
| |~B A
| | ?
| | ?
| | A
| ~B⊃A ⊃I
| | A A
| | ?
| | ?
| | ~B
| A⊃~B ⊃I
| A≡~B ≡I

We have now resolved our task into the problem of filling in the two subderivations.

Can you see how to complete the subderivations by working with the premises of the outer derivation? The first subderivation is easy: '~B' and 'AvB' give 'A' by vE. The second subderivation presents more of a challenge. But we can complete it by using the same tactics illustrated in the previous example. We've assumed 'A' and want to get '~B'. To get '~B', we can try ~I (unless a really simple alternative suggests itself). ~I will require us to start a subsub-derivation with 'B' as assumption. In this sub subderivation we can reiterate anything which is above in an outer derivation of the derivation on which we are working. So we can reiterate 'A', which, with 'B' , will give us 'A&B'; and we can reiterate the original premise '~(A&B)', thus giving us our contradiction. (Note that the contradiction can be in the form of any sentence and its negation. Neither sentence has to be atomic.) Since from 'B' we have derived a sentence and its negation, we can use ~I to discharge the assumption 'B', giving the conclusion '~B' at the end of the subderivation which began with 'A'. This is just what we needed.

If you find this tangle of thinking hard to unravel, read it over again, following each step in the completed derivation below to see how it all fits together.

1 | AvB P
2 | ~(AvB) P
3 | | ~B A
4 | | AvB 1, R
5 | | A 3, 4, vE
6 | ~B⊃A 3-5, ⊃I
7 | | A A
8 | | | B A
9 | | | A 7, R
10 | | | A&B 8, 9, &I
11 | | | ~(A&B) 2, R
12 | | ~B 8-11, ~I
13 | A⊃~B 7-12, ⊃I
14 | A≡~B 6, 13, ≡I

Now let's tackle something different. You are asked to derive 'C' from 'A&B' and '~C⊃~B'. What can you do? If you are stuck, you can at least write down the premises and conclusion so that you can start to see how the derivation will look:

1 | A&B P
2 | ~C⊃~B P
| ?
| ?
| C

No rule applies immediately to the premises to give 'C'. Because 'C' is atomic, no introduction rule for a connective will give 'C'. What on earth can you do?

Sometimes when you are stuck, you can succeed by arranging to use ~-I in what I am going to call the Reductio Ad Absurdum strategy. This strategy proceeds by assuming the negation of what you want and then from this assumption (and prior premises and conclusions) deriving a contradiction. As you will see in the example, you will then be able to apply ~I to derive the double negation of what you want, followed by ~E to get rid of the double negation. In outline, the reductio absurdum strategy, applied to this problem, will look like this:

1 | A&B P
2 | ~C⊃~B P
3 | | ~C A
| | X ('X' here stands for some specific sentence, but I don't yet know what it will be.)
| | ~X
| ~~C ~I
| C ~E

Will this strategy work in this case? If you assume '~C', you will be able to use that assumption with the premise '~C⊃~B' to get '~B'. But '~B' will contradict the 'B' in the premise 'A&B', and you can dig 'B' out of 'A&B' with &E. In sum, from '~C' and the premises you will be able to derive both 'B' and '~B'. ~I then allows you to conclude '~~C' (the negation of the assumption which led to the contradiction). ~E finally gives 'C':

1 | AvB P
2 | ~C⊃~B P
3 | | ~C A
4 | | ~C⊃~B 2, R
5 | | ~B 3, 4, ⊃E
6 | | A&B 1, R
7 | | B 6, &E
8 | ~~C 3-7, ~I
9 | C 9, ~E

The first time you see an example like this it may seem tricky. But you will soon get the hang of it.

You do need to be a little cautious in grasping at the reductio strategy when you are stuck. Often, when students have no idea what to do, they assume the opposite of what they want to conclude and then start blindly applying rules. This almost never works. To use the reductio strategy successfully, you need to have a more specific plan. Ask yourself: "Can I, by assuming the opposite of what I want to derive, get a contradiction (a sentence and its negation) out of the assumption?" If you can see how to do this, you are all set, and you can start writing down your derivation. If you think you see a way which might work, it may be worth starting to write to clarify your ideas. But if you have no idea of how you are going to get a contradiction out of your assumption, go slow. Spend a little time brainstorming about how to get a contradiction. Then, if you find you are getting nowhere, you may well need to try an entirely different approach to the problem.

I should also comment on the connection between what I have called the reductio ad absurdum strategy and the rule for ~I. They really come to pretty much the same thing. If you need to derive a sentence of the form ~X, consider assuming X, trying to derive a contradiction, and applying ~I to get ~X. To derive a sentence of the form X, assume ~X, and derive ~~X by ~I. Then eliminate the double negation with ~E.

Exercise 6-1.

For each of the following arguments, provide a derivation, complete with annotations, which shows the argument to be valid. If you find you are having difficulty with these problems, go over the examples earlier in this chapter and then try again.

a) Kv~I b) ~C⊃A c) ~D⊃~K d) ~F⊃G
~(~K&I) B⊃~A K G⊃~E
B ~KvH E⊃F
C D&H

e) A≡~B f) AvB
~A⊃B B⊃C
~CvD
~D⊃A