This reference provides some of the basic points made in Chapter Two. But it doesn't include everything of importance! Please spend the time working through all the tutorials! Often details for working homework problems -- the only good preparation for exams! -- is available in the tutorials. Even if you can do this weeks homework without doing them all, there may be material in later units that will be very hard without a clear understanding of all that going on in the tutorials.

Contents: Section 1: Basic Derivations; Section 2: RD and subderivations; Section 3: The SD Tests for Basic Deductive Concepts; Section 4: Derived Rules ; Section 5 : SD Strategy

 

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 gradually extend our system in this chapter and again in chapter 7, derivations will begin to model natural language deduction in important ways.

Here's the idea by example.

We take certain premises -- think of these as input -- and derive a conclusion, the ultimate output: here this is 'D'. But there are steps along the way so that one conclusion is used as "input" for another step which has it's own conclusion.


Each step is valid, so the whole derivation corresponds to this valid argument:

Av(B&C)
  ~A   
    D

That's the basic idea. Let's look more closely at the rules and the system.

 

1. The Derivation System SD

We first define the rules for each line of a derivation and then define how to use the rules in derivation.

Rules

We define two groups of rules for derivations in sentence logic, SD. Rules of the first sort are called rules of inference. These are rules which allow one to draw a conclusion (the "output") from specified "input".

Our first example is a familiar one.

MP
input 1: input 2: output:	P>Q P Q

If you prefer, you may write this, or anyone with more obvious placeholders:

Remember that P and Q are metavariables. You may prefer to think about this in terms of our bigger metavariables.

MP
input 1: input 2: output:	>

 

This helps make it clear that our metavariables are just placeholders. You need to fit the form...just like back in chapter one!

 

Most important:

For any three sentences fitting this form, we have a valid argument with output as the conclusion from the input as premises.

Put another way, there is no truth value assignment (i.e., no row) making the input true and the output false.

 

Another rule, "ampersand elimination", is written with two forms and has only one input:

&E
input: output:	P&Q P	or	P&Q Q

This should make sense; it 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 as premise and the output sentence as the argument's conclusion.

There is another type of rule called a rule of replacement. These are double arrow rules like

DN (Double Negation)
P ~~P

The double arrow means that one can make an inference in either direction.

Also, with rules of replacement and only with rules of replacement, one can work on the components of larger sentences. For example:

Here the first premise is not yet in the right from for DM. So, we massage it a bit without changing its meaning: Notice that 1's second disjunct 'B' is replaced by '~~B' in line 2. This helps by allowing DM at line 3.

 

We have a fairly long list of basic rules through 5.3.

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	MP (Modus Ponens) input 1: input 2: output: P>Q P Q
&E input: output: P&Q P or P&Q Q		&I input 1: input 2: output: P Q P&Q
RD input: output: P Q ~Q ~P or input: output: ~P Q ~Q P		R input: output: P P
Rules of Replacement
EQ (Equivalence) P=Q(P&Q)v(~P&~Q) or P=Q(P>Q)&(Q>P)		IM (Implication) P>Q  ~PvQ
DM (De Morgan's) ~(P&Q)~Pv~Q or ~(PvQ)~P&~Q		DN (Double Negation)   P ~~P

 

Derivations

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').

2. Subderivations for the Indirect Proofs of RD

RD
input: output:	P Q ~Q ~P	or	input: output:	~P Q ~Q P

Our rule RD 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 MP 4. then .................. B&C 4 &E 5. then ..................  B 2 &E 6. then .................. ~B 3-6 RD 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 RD 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 self-contradiction, derive a contradiction from P utilizing no premises.

---

---

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. Derived Rules

In an advanced logic class, one might prove that the rules we've already given are quite sufficient to prove any valid argument as valid by derivation. (The derivations are enough, you don't need truth tables any longer; hooray!)

So, not only are our rules all trustworthy -- none will go from true input to false output -- but they are also complete enough that you don't need any more to prove a valid argument valid.

Still, you may still think of further rules you might want to have, rules that are trustworthy, and will allow you to short-cut derivations.

CM (Commutation) P&Q  Q&P or PvQ  QvP or P=Q  Q=P	=E input 1: input 2: output: P=Q P Q or P=Q Q P
vE input 1: input 2: input 3: output: PvQ P>R Q>R R	vI input: output: P PvQ or Q PvQ

A little less useful but still of value:

=I input 1: input 2: output: P>Q Q>P P=Q	AS (Association) P&(Q&R)(P&Q)&R or Pv(QvR)(PvQ)vR
TR (Transposition) P>Q  ~Q>~P	DI (Distribution) P&(QvR)(P&Q)v(P&R) or Pv(Q&R)(PvQ)&(PvR)
HS (Hypothetical Syllogism) input 1: input 2: output: P>Q Q>R P>R

Some like these rules too. You may use them, but I seldom find them of much use:

ID (Idempotence) P&PP or PvPP

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

 

 

 

5. 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. You may have an ultimate goal given to you and you may need to figure out some preliminary goals. Either way, make sure you have a goal in mind. Then, 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.

The following capsule formulation of strategy analysis should help:

SD Strategy

Goal analysis: Make sure you have a goal at all times during a derivation. Sometimes a goal is a given (e.g., something you are asked to derive). Sometimes you need to figure one out preliminary goals to help prove the ultimate goal. Output for the Goal: Think about rules that output a sentence with the form of the goal. Pattern Matching: Think about rules that will fit the accessible lines on your derivation. RD, when all else fails: Just assume the "opposite" of the goal and show this leads to a contradiction within the subderivation.

We can be a bit more specific about 2 and 3.

• For 2, if your goal's main connective is '&' you would naturally think about '&I'. If it is triple-bar, you might think of =I or EQ. For the other connectives there are lots of possibilities. (E.g., you can frequently prove a conditional by HS or EQ or EX. However, I usually recommend IM or RD.) The methods just described are appropriate for building up a goal sentence.
• But one can also break down premises and other statements derived along the way to the goal. For example, if a sentence on a derivation has main connective '&', then &I is a good way to go. MP is the first thing to keep in mind when a sentence has '>' as main connective. BUT MP requires two inputs, so be careful that you have more than conditional to work with! If there is a disjunction on a line, think vE. A triple-bar? Use =E, or at least, that is a good bet.