The Logic Café

&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:
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  

















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

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.*
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.
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 

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:

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.
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, 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)'.
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...
Now, look to the other rules of replacement and notice that the sentences flanking the arrow are logically equivalent.
SD+ Rules of Replacement  



Strategy in SD+ is very similar to that in SD. Just a couple of minor amendments:
back to chapter five
on to the next chapter
continue with this reference