Lesson 10

Propositional Logic: Derivation Rules

Truth tables are necessary to define valid argument forms. But once we have identified a limited number of forms, we do not need them to show validity. There are a variety of methods that can be used to handle complex arguments. One such method is derivation. Although it is easily deployed and seems to match more nearly our reasoning processes, it does have a drawback. By its very nature as a method to derive true conclusions from true premises, it cannot be relied on to show us when an argument is invalid. Thus, for the time being, we will still need short-cut truth tables to show invalidity. Moreover, a derivation system often has twenty or so rules. (The one we will use has eight rules of inference and eleven rules of replacement.) Thus, a certain amount of memorization is involved.

In this lesson we will present and explain the rules of inference and then use them to derive a conclusion. In the next lesson we will consider the rules of replacement.


Rules of Inference

These rules of inference constitute some of the basic, valid argument forms, many of which can be found not only in propositional logic, but in other logics as well, logics such as the predicate calculus and modal logic. (These latter logics are important systems which would be mastered by the complete logician, but we not cover them in this course.) Because the eight rules presented here are fundamental, you are expected to memorize them.

1. Modus Ponens (MP): from p É q and p to infer q.

This is one of the classic, hence the Latin name, argument forms. It is also known as "affirming the antecedent". An example of this sort of argument form is:

If the sun is shining, then Mary is at the beach.
The sun is shining.
Therefore Mary is at the beach.

2. Modus Tollens (MT): from p É q and ~q to infer ~p.

Another classic argument form, known also as "denying the consequent":

If the sun is shining, then Mary is at the beach.
Mary is not at the beach.

3. Hypothetical Syllogism (HS): from p É q and q É r to infer p É r.

Also known as "chain reasoning", a hypothetical syllogism is not limited to two premises. Any number of premises can be used, provided that each one preserves the chain: the consequent of one premise must be the antecedent of the succeeding premise.

If the sun is shining, then Mary is at the beach.
If Mary is at the beach, then she is swimming.
If she is swimming, then she will be tired tonight.
Therefore, if the sun is shining, Mary will be tired tonight.

4. Disjunctive Syllogism (DS): from p Úq and ~p to infer q.

Either the sun is shining or it is raining.
The sun is not shining.
Therefore it is raining.

Despite the trivial example, this is a very useful argument form. But some students confuse it with Modus Tollens. In both argument forms one proposition in the first premise is denied and the other is detached. But in a disjunctive syllogism the detached proposition is not denied, as in Modus Tollens.

5. Conjunction (Conj): from p and q to infer p & q.

This rule will be familiar by now, because it is implicit in the logical operation of joining two true atomic statements and writing them as a compound statement, linked by the "&-sign". All it is saying is that if two independent statements are true, then the conjoined statement is true.

6. Simplification (Simpl): from p & q to infer p.

This is the reverse of conjunction. If a conjoined statement is true, then each of its atomic statements are true. But this rule as stated (from p & q to infer p) permits only the left conjunct to be inferred.

7. Addition (Add): from p to infer p Ú q.

This is a neat rule even though it may appear to be a trick. If a proposition is true, then a disjunctive statement involving that proposition is true--regardless of the truth-value of the added statement. Remember, for a disjunction to be true, only one of the disjuncts must be true. So, if you know that p is true, you can add any other statement whatsoever to it by means of the disjunctive logical operator and the resulting compound statement will also be true.

8. Constructive Dilemma (CD): from (p É q) & (r É s) and p Ú r to infer q Ú s.

Another classic:

If John moves to Alaska, then he will freeze this winter;
but if he moves to Miami, then he will burn up next summer.
Either he will move to Alaska or Miami.
Therefore, he will either freeze this winter or burn up next summer.


A Derivation

A ÉB

B É C

~C

A Ú D

D

We then rewrite the argument, numbering each premise and setting the conclusion over to the side, separating it from the premises by means of a slash and a three dot triangle:

  1. A É B

  2. B É C

  3. ~C

  4. A Ú D      /\ D

Now we assume that the premises are true and then use the premises and any of the eight inferences we need to derive the conclusion:

  1. A É B

  2. B É C

  3. ~C

  4. A Ú D   /\   D

  5. A É C    Lines 1,2; Rule HS

  6. ~A         Lines 5,3; Rule MT

  7. D           Lines 4,6; Rule DS

Note: Each step must be justified (by a rule), and every move must be made explicit.

Full truth tables are mechanical. One simply does the operations according to the rules and one gets the correct result. Derivations require both rule following and problem solving. In fact, for many arguments there are often multiple ways to derive the conclusion from the premises. Logicians prefer simpler proofs, ones with less rather than more lines. But for beginning proof constructors, longer lined derivations are acceptable.

But before you do problem-solving, you will only have to justify the steps in a successful derivation. Here is a proof in which each step is worked out, but the lines and rules are unspecified. Your task is to identify the lines and rules which justify each step.

1. F Ú G

2. D É E

3. E É ~F

4. D / \ G

                                    Lines     Rule

5. D É ~F

6. ~F

7. G

Actually, each step is a single argument, in which the lines cited serve as premises and the first expression listed to the left is the conclusion. The particular argument form used is the rule that is cited.

For instance, step 5 is a hypothetical syllogism, in which lines 2 and 3 serve as the premises. Write out this argument:

 

 

 

 

Now do the same for steps 6 and 7:

 

 

 

 

 

 

Exercise 10 provides practice opportunities.

Back to Logic home page

Copyright 1999, Michael Eldridge