The Logic Café
Reference

Chapter Five — Derivations in SL

 

Contents: Section 1: The Derivation System SD; Section 2: Subderivations; Section 3: The SD Tests for Basic Deductive Concepts; Section 4: SD Strategy; Section 5: SD+; Section 6: SD+ Strategy

It is recommended that you PRINT this reference. Click on "File" in the top left, then on "Print". (To print just this frame, you may have to click on the Logic Cafe Reference to select it before trying to print. This depends on your browser.)

 

In this chapter we define derivations for sentence logic. A derivation is simply a sequence of valid inferences. The end product is a numbered and vertical list of steps from premises through intermediate conclusions to a final conclusion.

As we extend our system from a basic system (SD) to fuller ones (later in this chapter and in chapters eight and nine), derivations will begin to model natural language deduction in important ways.

1. The Derivation System SD

We define two systems of rules for derivations in sentence logic. The first is called SD and involves only rules of inference , rules which allow one to draw a conclusion (the "output") from specified "input". For example, the rule "ampersand elimination" is written this way:

&E
input:

output:		 P&Q

P		 or P&Q
Q

and means that one can infer either P or Q from P&Q. Notice that this, and all rules of inference correspond to valid arguments. Think of the input sentence(s) as premise(s) and the output sentence as the argument's conclusion.

On the basis of a well defined collection of rules of inference (of SD or any other derivation system) one defines derivations.

A derivation is a numbered and vertical list of steps (called "lines") each containing a single sentence. It must start with a premise or assumption on line 1. After that, each line must contain either a premise, an assumption, or a sentence derived using one of the SD derivation rules citing lines with lesser number.* The lines to cite are the inputs given by the rule. (For instance &E requires that one cite the line number of the conjunction 'P&Q'.)

This idea of a derivation is easier to understand in practice than in abstract description. So, consider the easiest sort of example one might give:

Justification:       Sentence:

1.
2.

That's all there really is to &E. At line 2, one simply cites a conjunction from a line above, in this case line 1, and writes down the rule name and then a conjunct (here it's 'A').

The Rules of Inference

Next we give the SD rules. The rule name is given at top. The -symbol means "from the input above infer the output below". Three of these rules involve subderivations, an aspect of derivations described later. The symbol for a subderivation is: The assumption is at the top of this symbol, the required end of the subderivation is at its bottom. So, for instance this:

P


Q
P>Q

means that from a subderivation assuming P and terminating in Q one can infer P>Q.

SD: Derivation Rules for Sentence Logic
R
input:

output: 		P

P
&E
input:

output:		 P&Q

P		 or P&Q
Q
&I
input 1:
input 2:

output: 		P
Q

P&Q
>E
input 1:
input 2:

output: 		P>Q
P

Q
>I

input:



output:
P


Q
P>Q
vE
input 1:
input 2:
input 3:

output: 		PvQ
P>R
Q>R

R
vI
input:

output:		 P

PvQ		 or Q
PvQ
=E
input 1:
input 2:

output: 		P=Q
P

Q		 or P=Q
Q

P
=I
input 1:
input 2:

output: 		P>Q
Q>P

P=Q
~E

input:



output:
~P

Q
~Q
P
~I

input:



output:
P

Q
~Q
~P

Notice that there are two rules for each connective, one introduction rule and one elimination. This fact makes derivation strategy much easier: we have one rule to prove a sentence with a given connective and one to break such a sentence down into it's component parts.

2. Subderivations

Our rules for conditional introduction, negation introduction and negation elimination require a subderivation. In the statements of the rules just above, a subderivation is indicated by sentences appearing to the right of a vertical bar. Similarly, when derivations are written, the subderivation lines are written in a column to the right of the main derivation. Consider an example.

In this derivation, the subderivation occurs on lines 3 - 6. Together these lines tell us what follows if 'A' is supposed true: a contradiction.

So, because the premises together with line 3's assumption of 'A' lead to a contradiction, we know the premises entail that the assumption is false.
Premise 1. A>(B&C)  
Premise 2. ~B&~X  
Assumption 3. what if ...............  A
1,3 >E 4. then .................. B&C
4 &E 5. then ..................  B
2 &E 6. then .................. ~B
3-6 ~I 7. ~A  

Intuitively, we need to separate our premises — the claims made by the arguer — from our assumptions and their consequences — which are just hypothetical, assumed for the sake of argument. When an assumption is made, one is asking "what if".

That's the motivating idea. Let's now look at the rules governing subderivations.

Subderivation Rules

First, at any time one may make an assumption: write "Assumption" in the justification field then write the assumed sentence. No line number is cited. In this way, assumptions are like premises. One just makes them. However, unlike a premise, an assumption is placed one column to the right of the current column.

Most importantly, the statements after the assumption are placed under it in the same column. That column indicates the subderivation. The only way to move back out of this subderivation, back into the column under the premises, is to use a rule (>I, ~I, or ~E) which sanctions the termination of the subderivation. It is important to terminate all subderivations; then the concluding sentence is based solely on the premises.

If a statement is derived outside all subderivations, then it follows in a valid way from the premises. This statement of the correctness of derivations needs proof — a proof about the reliability of our derivation scheme. It is important to know that logic is sophisticated enough to be able to provide such a proof about derivations: One reasons in English about the logic of SL. But this theorizing about SL, called "metatheory", will need to await an advanced level logic class.

Once a subderivation is terminated, nothing within it may be cited to justify further derivation. We say in such a case that the assumption made by the subderivation is discharged. In this case we are no longer relying on that assumption for what we derive.

Though one may not cite any line or lines within a terminated subderivation, one may site the whole subderivation.*

3. The SD Tests for Basic Deductive Concepts

Chapter one introduced a group of concepts of deductive logic: valid, logically equivalent, logically true, etc. Chapter three provided precise definitions of these concepts for the language SL and provided straightforward truth table tests determining just when each concept applied. But these tests are not a good model of natural, real world reasoning.

In this chapter we introduce derivations which are much more "natural". We need to be able to use them to test deductive reasoning. The following tests are the means.

To give an SD derivation showing an SL argument is valid, simply take that argument's premises as the premises of a derivation and derive the conclusion using only the rules of SD.

To show in SD that P and Q are logically equivalent, do two derivations one with premise P from which you derive Q and the second with premise Q from which you derive P.

To give an SD derivation showing that a sentence P of SL is a logical truth, derive P from no premises.

To give an SD derivation showing that a sentence P of SL is a logical falsehood, take P as the one premise and deduce Q and ~Q, a contradiction (where Q is any sentence of SL).

To show in SD that a set of sentences \ is logically inconsistent, do a derivation taking the members of \ as premises and, for any sentence P of SL, derive both P and ~P.

In addition to the concepts defined above, it is worth having a generic concept of derivability:

To show that a sentence P is derivable from set \ of sentences, simply take the members of \ as the premises of a derivation and derive P using only the rules of SD.

It is worth noticing that we do not have tests for the concepts of invalidity, consistency, and logically indeterminateness. In each case, the concept holds just in case there is no derivation of the appropriate sort.

For example, consider invalidity. An argument is invalid just in case there is no derivation of its conclusion from its premises. But we have no SD procedure to show that there isn't a derivation of a conclusion. We can only use SD to show that there are derivations. So, for the concepts of invalidity, consistency, and logically indeterminateness, we need be content with our truth table tests.

Another matter of metatheory: The above paragraph stated "an argument is invalid just in case there is no derivation of its conclusion from its premises". This is true, but how do we know it? The concepts of validity and invalidity for SL sentences are defined in terms of truth value assignments not derivations! It takes a fairly difficult "metatheoretical" proof to show that the quoted claim is correct. That is left for a second logic course.

4. SD Strategy

So far we know what counts as a good step in a derivation. But putting together a long string of steps leading to what one is asked to derive, your goal, can seem very difficult at first. But a little strategic planning — i.e., thinking about how the derivation should end — will make derivations much easier.

One should always begin a derivation with goal analysis. First, ask "what is the main connective of the goal?" and then "how might I derive a sentence with this main connective?" It may be that there is some obvious way which will help toward this goal.

Next, if a procedure is not obvious to you then consider (a) the introduction rule appropriate for your goal and/or (b) the elimination rules appropriate for accessible lines. (For example, if one is working on a certain line of a proof, then one considers the introduction rules for any goal sentence to follow it and the elimination rules for any accessible lines above. If one is working with a line with sentence P&Q, then one might use &E to derive P if that seems to be helpful in moving toward a goal.)

The following capsule formulation of strategy analysis should help:

SD Strategy
  1. Consider goals that may plausibly allow you to complete your derivation.
    • Usually you will be given an ultimate goal: what you are asked to derive.
    • Often during the course of a derivation, strategy will require intermediate goals — other sentences required to complete the derivation.
  2. Do what is obvious to you if that will clearly help you toward your goal(s).
  3. Use introduction and elimination rules:
    • Consider the I-rules appropriate for the main connective of your goal sentence.
    • Consider the E-rules appropriate for the main connectives of any accessible sentence you may have already derived (this includes assumptions).

Now Recycle: After you have applied a rule go back to 1 and start the goal analysis anew. Continue the process until you are finished.

After you get used to the three step version above, it may be helpful to add a fourth step to the strategy for help with some of the harder derivations:

  1. It is often best to wait to apply ~E until other means are attempted. Then you may best think as follows:
    • When an accessible line has main connective tilde, you may have to reiterate that statement within a subderivation to provide a contradiction.
    • When all else fails or when you begin to feel desperate, you may have to assume the negation of your goal and work toward a contradiction.

Keeping goals in mind and working with the strategy aids just mentioned is important. Otherwise it can be too easy to randomly apply rules or make assumptions up from thin air! In logic class like in life, strategic thinking is rewarded.

 

5. SD+

We now present an extended set of rules SD+. It is important to emphasize that the current section adds to the rules of SD.

SD+  =  all the old rules of SD  +  new rules.

We will continue to use all the old rules but will gain new ones to make our derivations faster and easier to write and (most importantly!) easier to follow and understand.

All the new rules to be introduced here are dispensable — any derivation done with the the rules of SD+ could be done with only the rules of SD. But it may take many more steps to do in SD alone.

In this sense, all the new rules defined in SD+ are "shortcut rules".

SD+ Rules of Inference
DS
(Disjunctive Syllogism)
input 1:
input 2:

output: 		PvQ
~P

Q 		or PvQ
~Q

P
MT
(Modus
Tolens )
input 1:
input 2:

output: 		P>Q
~Q

~P
HS
(Hypothetical Syllogism)
input 1:
input 2:

output: 		P>Q
Q>R

P>R

DS, MT, and HS are rules of inference just like those of SD. But these rules will save you time by removing the need for doing messy subderivations. You should be able to see that each of these rules corresponds to valid thinking and you should be able to convince yourself that each new rule of inference is dispensable.

The most powerful new rules in SD+ are "rules of replacement". These rules involve pairs of logically equivalent sentence forms.

For example, 'P&Q' and 'Q&P' form such a pair. We will write this as...

P&Q  Q&P    

(This rule is called "CM" for "commutation".)

Our rules of replacement allow us to replace one member of the pair with the other as one step in any derivation. For example, if line 1 (say) of a derivation is '(A>B)&(C&~D)' then line 2 can switch first and second disjunct: '(C&~D)&(A>B)'.

Justification:       Sentence:

1.
2.

We cite the line number of the sentence from which the replacement is made. (For rules of replacement, it is always one line number to be cited.)

Now, rules of replacement are even more powerful than the example suggests because...

  1. as the double arrow indicates, replacement can go in either direction.
  2. replacement can work on the sentential components of any line of a derivation. So, line 2 from the above example could be '(A>B)&(~D&C)' where commutation takes place only within the second conjunct:
    Justification:       Sentence:

    1.
    2.
    here the switch has been make around the second ampersand — one that is not the main connective.

Now, look to the other rules of replacement and notice that the sentences flanking the arrow are logically equivalent.

SD+ Rules of Replacement
CM
(Commutation)
P&Q  Q&P
or
PvQ  QvP
or
P=Q  Q=P

DN
(Double Negation)
  P ~~P

IM
(Implication)
P>Q  ~PvQ

TR
(Transposition)
P>Q  ~Q>~P

ID
(Idempotence)
P&PP
or
PvPP

DM
(De Morgan's)
~(P&Q)~Pv~Q
or
~(PvQ)~P&~Q

AS
(Association)
P&(Q&R)(P&Q)&R
or
Pv(QvR)(PvQ)vR

DI
(Distribution)
P&(QvR)(P&Q)v(P&R)
or
Pv(Q&R)(PvQ)&(PvR)

EQ
(Equivalence)
P=Q(P&Q)v(~P&~Q)
or
P=Q(P>Q)&(Q>P)

EX
(Exportation)
  P>(Q>R)(P&Q)>R

 

6. SD+ Strategy

Strategy in SD+ is very similar to that in SD. Just a couple of minor amendments:

  1. Once you get used to the new rules, they will sometimes allow you to quickly see how to move toward a goal in just one or two steps. Thus, their use will be obvious and comes in at step 2 of the strategy guidelines.
  2. These rules allow one to analyze complex negations. For example, consider a premise '~(P>Q)'.
    • In SD one must usually reiterate this premise for contradiction; there is no way in SD to break this sentence into parts. (For example, think about how you would use SD to derive '~Q' from this single premise.)
    • But in SD+ one may first apply IM inside the parentheses (to derive '~(~PvQ)') and then DM (to derive '~~P&~Q'). This then can be further simplified with &E or DN.
  3. Finally, don't get lost! There are now so many rules that one can spend all day (literally!) going around in circles, getting no nearer one's goal sentence. Remember, that "obvious" in step two of the strategy means "obviously helps move toward your goal". Do not apply the rules at random!

 

 

back to chapter five
on to the next chapter
continue with this reference