UNIT 7: The Proof Method: Eight Basic

Inference Rules

A. INTRODUCTION

In this unit you will begin to learn an entirely different method for demonstrat-

ing the validity of deductive arguments: the method of proofs. With this proce-

dure, instead of testing the premises and conclusion simultaneously, "in one fell

swoop," to see whether there is a counterexample, you will proceed step by step

through a series of relatively simple intermediate inferences until you arrive at

the conclusion. This procedure is much closer to the way we reason in everyday

life; you probably quite often work out step by step the implications of certain

hypotheses, but it is a good bet that you never made up a truth table before you

picked up this book. The proof method is historically prior as well; 2,300 years

ago Aristotle developed the first system of proofs, and Euclid developed the

proof method for geometry at about the same time. The truth table method, by

contrast (although not the general method of refutation by counterexample), is

an invention of the twentieth century. The two methods are obviously indepen-

dent of each other: you were able to learn the truth table method without re-

course to proofs, and the method of proofs was clearly possible without the

truth table method. It is interesting that there are two such different methods for

doing the same thing-testing validity. As we shall see, however, there is a very

important connection between them: the truth table method, in a way, serves to

validate the rules we will be using in constructing proofs. Fortunately, the two

methods yield the same results, at least in logic. (In mathematics, as it turns out,

the results of the two methods are somewhat different-one of the most excit-

ing discoveries of the twentieth century.)

113114 Unit 7 The Proof Method: Eight Basic Inference Rules

In using the proof method, proceeding step by step from premises to con-

clusion, you will not, of course, be permitted to make whatever inferences you

wish. (You will not, for instance, be allowed to infer ~ B from (A :::J B) and ~ A.)

You will be given a certain set of inference rules and will be permitted to use

those and only those rules in your proofs. The reason for this constraint will be

explained in Section 3.c. In this unit you will be given eight very basic inference

rules consisting of a premise or set of premises and a conclusion. In the next two

units you will be given additional rules of a slightly different form.

It cannot be emphasized enough that it is absolutely essential that you

learn these rules thoroughly. You must memorize them, or you will simply not be

able to do the proofs. You should be able to reel off the rules as easily as you can

(I hope) reel off your multiplication tables. You will not be able to master this unit,

or the next few units, unless you first learn the rules. To assist you in this process,

the rules will always be carefully explained in the text; understanding what the

rules mean will help you memorize them.

You will probably find the proof method more interesting and challenging

than the use of truth tables and will very possibly find it quite frustrating initially

as well. This is because, unlike the truth table method, there are no set procedures

to follow. I cannot give you a prescription for constructing proofs that is guaran-

teed to work; there is no algorithm, no mechanical procedure, for the proof

method. You will have to use your imagination and ingenuity; this is the source of

both the challenge and the frustration. On the other hand, when you do solve a

problem, you will feel that you have really accomplished something. You may

consider these problems as puzzles, like chess problems or crossword puzzles;

your goal will be to get to the conclusion from the premises by using only the rules

of inference given you.

Although there are no set procedures for reaching your goal (the conclusion),

you willieam certain "rules of thumb," certain "tricks of the trade," and methods,

such as "working backward," that will help you plan your strategy. The more ex-

ercises you do, of course, the more adept you will become, and by the end of the

unit you should be fairly proficient in planning strategies and figuring out how to

reach your goal. But, again, it must be emphasized that unless you thoroughly

learn the rules you will be able to go nowhere. You cannot hope even to begin to

construct proofs without knowing the means of construction! For convenient ref-

erence, the rules are all given at the end of the unit and are also given on the inside

front cover of the book.

To fully understand the application of rules of inference, it will be important

to master the distinction between a statement form and the particular statement,

the substitution instance. Section 1 is thus devoted to this topic, before we proceed

to the discussion of rules and proofs in the succeeding sections.Unit 7 The Proof Method: Eight Basic Inference Rules 115

B. UNIT 7 OBJECTIVES

• Learn the difference between forms and substitution instances, and learn

the definitions of these and related terms given at the end of the unit.

• Be able to determine whether a statement is or is not a substitution in-

stance of a given form.

• Be able to write out the symbolic forms of the inference rules and to un-

derstand their verbal explanations.

• Be able to identify correct applications (substitution instances) of the

rules and to spot incorrect applications.

• Given a derivation, be able to supply the justification for each step.

• Be able to state and apply the following definitions: (a) justified step,

(b) derivation, (c) proof.

• Be able to construct derivations.

• Given a set of premises and a conclusion, be able to construct a short

proof (up to five intermediate steps).

• Learn to plot proof strategies, such as the method of "working backward."

• Given a set of premises and a conclusion, be able to construct longer

proofs (up to 25 or 30 intermediate steps).

C. UNIT 7 TOPICS

1. Form and Substitution Instance

In Unit 1 we introduced the distinction betweenform and substitution instance,

and we have used these terms already in defining validity and in discussing truth ta-

bles. So far, however, we have been relying on a rather informal understanding of

these concepts; in Unit 1, for example, the form was said to be the general pattern, or

structure, of the sentence or argument, with no particular meaning or truth value,

while the instance was the particular, meaningful sentence or argument. The time

has now come to make these concepts more precise.

The basic distinction is that between constant and variable. A constant is sim-

ply a term that has a definite, particular value, while a variable, as the name indi-

cates, may stand for any value. In algebra, for example, quantities such as

2,6, 101 1 / 2, (8 + 7), even 7T are constants, since their value always remains the

same. (Lowercase letters such as a and b are sometimes used to represent arbitrary

constants.) By contrast, the letters x, y, and z are used as variables, which means

that they may take any value or stand for any number. Constants may be substituted

for variables; that is, we may replace a variable with a constant. The result of such116 Unit 7 The Proof Method: Eight Basic Inference Rules

a substitution may be called a substitution instance, or just an instance, of the vari-

able or formula that contains the variable. In the formula x + y = Y + x, for in-

stance, we may substitute 3 for x (consistently) and 5 for y to get the substitution

instance 3 + 5 = 5 + 3.

In sentential logic we are using sentential variables rather than numerical

variables and sentential constants rather than particular numbers, but the idea is

the same. A sentential variable, or statement variable, as we will call it, is simply a

letter (we use lowercase letters from the middle of the alphabet, p, q, r, s, ... ) that

in itself has no meaning or truth value, but that is used to stand generally for, and

that may take as a substitution instance, any particular statement, simple or com-

plex. Our sentential constants, on the other hand, which we will call statement

constants, are simple capital letters that stand for definite, particular, meaningful

instances. They are just the letters, such as A and N, that we have been using as ab-

breviations for truth functionally simple English sentences. Sentential constants,

unlike variables, have definite truth values.

Statement variables and statement constants, then, are the simple compo-

nents of our formulas. Statement forms and statements, on the other hand, may be

either simple or complex, and the difference between them is that the forms are

built up out of variables, whereas the statements are built up out of the capital let-

ters, or constants. More precisely, a statement form is a formula (simple or com-

pound) that has as its smallest units statement variables, whereas a statement is a

formula (simple or compound) that has as its smallest units statement constants.

Some examples of statement forms would be p, (p v q), and «p' q) :J ~ (r v s».

Examples of statements would be A, (A v B), and (~ (C, D) • (A :J ~ B». Again,

forms have variables and statements have constants as their smallest units.

The following table classifies and illustrates the various sentential elements

we have described above.

FORMS

INSTANCES

Simple

Simple or

Complex

Statement variables

p, q, r, ...

Statement forms

p, (q v r), «p :J q)' ~ r)

Statement constants

A, B, N, ...

Statements

N, (A :J ~ N), «A v B) == ~ C)

As noted, statements will be the substitution instances of statement forms.

We will get a substitution instance of a form by (uniformly) substituting some state-

ment, simple or complex, for each variable in the form. Thus, from the form

«p v q) :J r), we could obtain the following: (1) «A v B) :J ~ C), where A, B, and

~ C have been substituted, respectively, for p, q, and r; and (2) «B' C) v

(C :J ~ D» :J ~ (A v (B • ~ C», where (B' C) has been substituted for p,

(C :J ~ D) has been substituted for q, and ~ (A v (B' ~ C» has been substitutedUnit 7 The Proof Method: Eight Basic Inference Rules 117

for r. There are unlimited numbers of substitution instances for each form. It is ex-

tremely important to keep in mind that each simple variable p, q, r, and so on, may

take as substitution instances complexformulas as well as simple ones. In general,

in fact, the substitution instance will be more complex than the form itself, since

in most cases we will substitute complex statements for at least some of the

variables. Some instances of the form (p ~ q) are (1) (A ~ B),

(2) «A v B) ~ (G v H», and (3) «F == G) ~ «A v B) v (C' D»). Any state-

ment, in fact, whose major operator is a conditional would be a substitution in-

stance of (p ~ q), since we just put in the antecedent for p and the consequent for

q. By contrast, «A ~ B) v C) is not a substitution instance of (p ~ q) since, al-

though it does contain a conditional, the conditional is not the major operator, and

there is no way we can substitute formulas for p and q to come out with the state-

ment. The best we could do would be to substitute A for p and B ) v C for q, but

this would not do, since B ) v C is not a formula. «A ~ B) v C) would be a sub-

stitution instance of (p v q).

Note that according to the definition we may substitute the same statement

for different variables, so that (A v A) is a substitution instance of (p v q). But we

must not put in different statements for repeated occurrences of the same variable.

We must be consistent in our substitution; that is, whatever we put in for p at one

place, we must put in for p at all other places. Thus «A v B) ~ C) is not a substi-

tution instance of «p v p) ~ q), but «A v A) ~ B) would be a substitution in-

stance, as well as «A v A) ~ A).

Note that the requirement of consistent substitution and the possibility of

putting in the same statement for different variables are exactly analogous to the

use of variables in mathematics. If we have the formula x + y = Y + x, a correct

substitution instance would be 3 + 4 = 4 + 3, but 2 + 3 = 4 + 5 would not be

an instance, since whatever we put in for x at one place we must also put in for any

other occurrence of x. On the other hand, 3 + 3 = 3 + 3 is a perfectly good in-

stance, since we can substitute 3 for both x and y if we wish.

Some examples are given below to help you see what kinds of statements

do or do not count as substitution instances of forms. To help you figure out in

each case why a formula is an instance, the statements that were substituted for

each variable to get the substitution instance have been outlined. For those for-

mulas that are not instances, you should try to see why it is not possible to sub-

stitute statements for the variables in a way that would yield the formulas as

instances. Exercise 1, at the end of the unit, will also contribute to your under-

standing of these very important concepts of form and substitution instance,

and it is important that you do these exercises before you go on to the sections

on proofs.118 FORM

INSTANCES

Unit 7 The Proof Method: Eight Basic Inference Rules

2. ~ (p' q)

~ (lA}~)

~ (~'I~ AI)

~ (I(B V C)I'I~ D )1

~~ vl(B ~ C)I

~I(B ~ C)lvEA]

~1«Av~B)~(CvD»lv 1m ~(I~ (B V C) I· r-I~----;-«C;-:-A--=~----;;B=-) -V-';;;CC71»I

~ (Em'~)

3.p ~ ~ q

~~ ~[g

EAl ~ ~I(B V cj

I~ (B V C) I ~ ~ ~

I ((A V B) ~ C)I ~ ~E]J

I(((A ~ (B V C» D) F)I ~ ~I(A V B)I

~~~

1. ~pvq 2. ~ (p. q)

3. P ~ ~q

Av~B ~A·B

~A~B

~ (AvB) ~A·~B

~(AvB) ~ C ~(A·B)vC

(A ~ ~B)vC

~(A ~ ~B)

(~AvB)v(CvD) ~~(A·B)

A ~ (B ~ ~C)

1.~pvq

~G1Jvlm

~1~AlvEAI

FORM

INSTANCES

FORM

NONINSTANCES

2. The Proof Process

In the proof method for demonstrating validity, we start with the premises

and then deduce from the premises a series of intermediate steps that finally results

in the desired conclusion. What we do is to construct a chain of reasoning in which

each new step follows from the previous steps. Suppose, for instance, that we have

the following argument: John is weak and has a stomach ache. If he is weak and

has a stomach ache and has either a rash or a fever, then he either has food poison-

ing or mononucleosis. He would have food poisoning only if he ate bean sand-

wiches at Joe's Bar and Grill last night. But he didn't have bean sandwiches at

Joe's last night; instead, he had lobster at Maxmillian's. He doesn't have a rash,

but he does have a fever. Therefore, he must have mononucleosis. We can symbol-

ize this argument as follows, numbering the premises:

1. (W·S)

2. «W· S)· (Rv F» ~ (Pv M)

3. (P~B)

4. ~B·L

5. ~R·F/".MUnit 7 The Proof Method: Eight Basic Inference Rules 119

Given these five premises, we could deduce that John has mono in the fol-

lowing way (we will number and symbolize every step):

6. F

7. (R v F)

8. (W' S)· (R v F)

9. (Pv M)

10. ~ B

11. ~ P

12. M

John does have a fever (from step 5)

John has a rash or a fever (from step 6)

John is weak and has a stomach ache and has either a

rash or a fever (by combining steps 1 and 7)

John either has food poisoning or mono (from steps 2

and 8)

John didn't eat bean sandwiches last night (from step 4)

John does not have food poisoning (from steps 3 and 10)

John has mono (from steps 9 and 11)

Some of these steps, such as step 6, may seem obvious and trivial, and you

may wonder why we even bother to list them. It is essential to a proof, however,

that every single move be recorded; the whole point of a proof (as opposed to an

intuitive leap to the conclusion) is to be absolutely certain that the conclusion fol-

lows, and the only way we can obtain this certainty is by being very precise and

very thorough. This means taking nothing for granted, but actually writing down

every inference we make, no matter how trivial. Too often, people (including logi-

cians) take things for granted and then discover that they have omitted something,

or that there is some premise they need that they don't have, so the argument is not

valid after all. To avoid this kind of mistake, it is necessary that you write down

every step. Notice also that we have provided a justification for every step by in-

dicating what previous steps it was derived from; this is an important part of the

proof process. It should be obvious by now why we number the steps: since each

later step is justified in terms of previous steps, we need a simple way of referring

back to the previous steps; numbering them is the easiest way to do this.

In constructing proofs, not any old inference will do; you cannot deduce

just anything that strikes your fancy. In a proof, every step must logically follow

from previous steps; each individual inference must be valid. The way we guar-

antee this is to require that each step in a proof follow from the previous steps

according to certain specified rules of inference. These inference rules are pat-

terns, or forms (they will be given in terms of variables), that are "tried and

true," certifiably correct, guaranteed never to result in true premises but a false

conclusion. They are all truth functionally valid argument forms, a fact you may

want to verify for yourself by using the truth table method on them. If you use

just these rules (and use them correctly), you can be sure that your arguments

will be valid. No one is claiming that these are the only possible correct rules;

there are, in fact, an infinite number of rules that we might use. The rules you

will be given in the next three units, however, are very basic, common, and com-

pletely sufficient for sentential logic. There is no valid sentential argument that120 Unit 7 The Proof Method: Eight Basic Inference Rules

cannot be proved using just these rules. The first eight of these rules, the basic

inference rules, will be introduced in the next section.

3. Eight Basic Inference Rules

a. Rules for "if-then," "and," and ~~or." An inference rule is a basic pat-

tern of reasoning, according to which a conclusion of a certain form may be in-

ferred from premises of a certain form. It is not the sort of rule that tells you

that you must do something, such as limiting your speed to 65 mph when driving;

you will never be required to use any given rule. Rather, it is a rule telling you

that you may make a certain inference, that given premises of a certain form,

you are permitted to draw a conclusion of a certain form. The rule of Disjunc-

tive Syllogism, for instance, will tell you that given a disjunction and the nega-

tion of one of the disjuncts, you are permitted to infer the other disjunct. In this

unit you will be given eight very basic inference rules, all in the following

form: there will be one or more statement forms given as premises and a single

statement form given as the conclusion, which can be derived from those

premises. A summary of these eight rules will be provided at the end of the unit

for easy reference. Remember that you will be required to memorize the sym-

bolic forms of the inference rules; otherwise, you will simply not be able to do

the work in these units. You should also become familiar with and be able to

paraphrase the informal explanations of the rules, such as the one just given for

Disjunctive Syllogism.

It will be easier to learn these rules if you think of them in terms of the oper-

ators they contain. Our first three rules, for example, are horseshoe rules, because

they tell us how we may make inferences with formulas that have horseshoes as

their major operators. The next two are conjunction rules, and the two after that are

disjunction rules. Dilemma, which is presented in subsection b, combines the con-

ditional and disjunction operators.

Probably the most fundamental rule in all of logic is the rule of Modus Po-

nendo Ponens (its complete and proper name), more familiarly known as Modus

Ponens; other rules may come and go, but most systems retain the rule of M.P. (as

we will abbreviate it). This rule tells you that if you have a conditional and also the

antecedent of the conditional (the "if' part), then you are permitted to infer the

consequent (the "then" part). It really just reflects the meaning of "if-then." Sym-

bolically, it is stated thus:

MODUS PONENS (M.P.)

p~q

P

/ ... q

Given a conditional and the antecedent of that conditional, you

are permitted to infer the consequent of the conditional.Unit 7 The Proof Method: Eight Basic Inference Rules 121

It is essential to be aware at the outset that the rules are given in terms of

variables; that is, they are rule forms. You will be applying these to particular

instances, and an instance of a rule will be correct if its premises are a substitution

instance of the premises of the rule form and the conclusion is the corresponding instance

of the conclusion of the rule form. The following, for instance, would be a correct

application of the rule of M.P.: «A v B) ::J ~ C), (A v B) / ... ~ C. The following

would not be a correct application, because the second premise is not the an-

tecedent of the conditional: «A· B) ::J ~ C), A / ... ~ C. The following is also not

a correct instance, because neither of the premises is in the form of a conditional:

«A::J B) v (C ::J B», A / ... B.] The rule of Modus Ponens can only be applied in

cases where one of the formulas has, as its major operator, a conditional. (The

other premise must be the antecedent of the conditional.) A correct application of

M.P. occurs in the problem in the preceding section, where step 9, (P v M), was

inferred from steps 2 and 8, «W· S)· (R v F» ::J (Pv M) and «W· S)· (R v F».

As this example illustrates, the applications of the rules-the instances-may be

considerably more complex than the rules themselves, which use variables, since

a variable may take as a substitution instance any formula, no matter how com-

plex. You will need to have a sharp eye for the relationship between a form and

its instances, and the second set of exercises at the end of the unit is designed to

give you practice in recognizing instances and noninstances of the rules.

Another very basic rule, which also contains a conditional as a premise, is

the rule of Modus Tollendo Tollens, more commonly known as Modus Tollens.

This rule tells us that given a conditional as one premise and the negation of the

consequent of that conditional as the second premise, we may infer the negation of

the antecedent of the conditional. In symbolic form it looks like this:

MODUS TOLLENS (M.T.)

p::Jq

~q

/ .". ~p

Given a conditional and the negation of the consequent of the

conditional, you are permitted to infer the negation of the an-

tecedent of that conditional.

An instance of the rule of M.T. (as we will abbreviate it) would be the following:

«A v B) ::J C), ~ C / .". ~ (A v B). This is a very common inference pattern, and

now that you are aware of it, you will probably notice instances of it being used con-

tinually. An example in English would be "If John broke up with his girlfriend, he is

depressed. He isn't depressed. Therefore, he didn't break up with his girlfriend." It is

INot only are these incorrect applications of the rules, they are also truth functionally invalid. You

should use the short truth table method on these and the other instances of incorrect applications

given in this unit, constructing counterexamples to convince yourself that they are wrong.122 Unit 7 The Proof Method: Eight Basic Inference Rules

important to remember with this rule that the second premise must always be the

negation of the consequent. Thus the following would not be a correct application of

the rule of M.T.: (~(A· B) :J ~ (Cv D)), ~ (Cv D) / :. ~ (A· B). The second

premise is a negation, but it is not the negation of the consequent, and this is what is

required. Another error here is that the conclusion, although it is also a negation, is not

the negation of the antecedent. In order to use this conditional in the rule of M. T., we

would have to have, as the second premise, the double negation ~ ~ (C v D), and the

correct conclusion would be the double negation ~ ~ (A· B). Notice that the rule of

M.T. was used to infer step 11 in the example in the preceding section.

A third rule that uses the conditional is the rule of Hypothetical Syllogism,

which we will abbreviate as H.S. In this rule there are two overlapping condition-

als as premises, and the conclusion is the conditional with the middle term elimi-

nated. Its symbolic form is given below (notice how much easier it is to say it in

symbols than to try to describe it in English):

HYPOTHETICAL SYLLOGISM (H.S.)

P ::J q q ::J r / '""""\ .. p -' r

Given two conditionals in which the consequent of the first

is identical to the antecedent of the second, you may infer

the conditional whose antecedent is the antecedent of the

first and whose consequent is the consequent of the second.

What this rule tells us is that the conditional is transitive: if the first state-

ment implies the second and the second implies the third, then the first implies the

third. An instance of this would be

(A v B) ::J (C· D), (C, D) ::J (~ E· F) / ... (A v B) ::J (~E· F).

It is crucial in the application of this rule that the overlapping terms be exactly

identical. The following would not be an instance of Hypothetical Syllogism, be-

cause it violates this condition: (A v B) :J (C :J D), (C· D) :J (F· G) / .'.

(A v B) :J (F· G). Clearly, (C :J D) is not the same as (C· D), so the inference is

not correct. Not any two conditionals, in other words, can serve as the premises of

Hypothetical Syllogism; they must have the very special relationship of sharing a

common term. The antecedent of one must be exactly the same as the consequent

of the other. An example in English of this rule would be the following: "If either

inflation remains high or unemployment increases, Jones will be defeated. If

Jones is defeated, either Smith or Andrews will be governor. Therefore, if either

inflation remains high or unemployment increases, then either Smith or An-

drews will be governor." ("Jones" has been eliminated.)

As noted, it is useful to learn the rules in groups, according to the major

operators involved. What you have just learned are three rules that tell us whatUnit 7 The Proof Method: Eight Basic Inference Rules 123

we can infer from conditionals. When you begin to construct proofs, Exercise 6

at the end ofthe unit will give you practice in using these three rules. The next two

rules, which are extremely simple, are rules that tell us how to operate with con-

junctions. The first tells us how to use a conjunction as a premise, that is, what we

can derive from it, and the second tells us how to derive it as a conclusion. The rule

of Simplification, abbreviated as Simp., tells us that if we have a conjunction as a

premise, we may infer either one of its conjuncts as a conclusion. (Thus the rule

has two forms.) This is exactly what you would expect from a rule for conjunction;

since the conjunction asserts that both of the conjuncts are true, we should be able

to infer either one separately.

SIMPLIFICATION (SIMP.)

P'q p.q

-- --

I.'.p I.'.q

From a conjunction as premise, we may infer either of

the conjuncts separately as a conclusion.

Again, it will be very important to remember that the rule of Simplification

applies only when the major operator of the premise is a conjunction; in other

words, you may not apply Simp., to just a subformula. The following would not be

a correct application of the rule and is, in fact, invalid: (A· B) :J C / .'. (A :J C).

(Again, use the short truth table method to construct a counterexample to verify

that this instance is invalid.) The following, however, is a correct application of the

rule: «A· B) :J ~ (Cv D»· (Fv ~ H) / ... (F v ~ H). Notice that the rule of

Simp. was used in inferring steps 6 and 10 in the example given in Section 2.

The rule of Conjunction, which will be abbreviated as Conj., is also a very

easy rule. This rule tells us, as we would expect, that if we have two separate state-

ments then we may infer their conjunction. The rule is stated as follows:

CONJUNCTION (CONJ.)

P Given any two statements, we may infer their conjunction.

q

I.'. p. q

This rule should give you little difficulty, except that you must remember that to

infer the conjunction, you must have both components separately first. An example of

this rule would be the following: (A v B), ~ (C :J D) / .'. (A v B) • ~ (C :J D). The

rule of Conj. was also used to infer step 8 in the example in the preceding section. Ex-

ercise 7 at the end of the unit will give you practice in constructing proofs using only

the rules for conjunctions and those for conditionals.

The rules for disjunction are slightly more complex than those for conjunction,

but are still quite simple. Again, one rule, Disjunctive Syllogism, tells us how to use a

disjunction in a premise, while the other, Addition (a confusing name, but standard

for this rule), tells us how to derive a disjunction as a conclusion. The rule of124 Unit 7 The Proof Method: Eight Basic Inference Rules

Disjunctive Syllogism, abbreviated as D.S., says that if you are given a disjunction as

a premise and the negation of one of the disjuncts as a second premise, you may infer

the other disjunct. In this rule, either disjunct may be negated as the second premise,

so, like the rule of Simplification, it will have two forms. They are given below:

DISJUNCTIVE SYLLOGISM (D.S.)

pvq

pvq

~p

Given a disjunction and the negation of one of the

disjuncts, you may infer the other disjunct.

/ ... q / ... p

This rule is very common in ordinary usage; an example employing the sec-

ond form of the rule might be: "This tree is either a walnut and will bear nuts in the

fall, or it is a cherry tree. It is not a cherry tree. Therefore, it is a walnut and will

bear nuts in the fall." D.S. was also used to infer the conclusion that John has

mono in our example in Section 2 of this unit.

In using this rule, you must be sure that the second premise is the negation of

one of the disjuncts, and not just any old negation. The following, for example,

would not be an instance of Disjunctive Syllogism, because the second premise is

not the negation of the second disjunct (or, of course, of the first).

(A v~ (B· C)), ~ (B· C) / .'. A. To infer A from the first premise, we would need

the double negation ~ ~ (B· C). The following, however, would be a correct ap-

plication of the rule:

( ~ A v (B :J C)) v ~ D, ~ ( ~ A v (B :J C)) / ... ~ D.

The rule of Addition, abbreviated as Add., aside from its rather inapt name, is

sometimes confusing to students for several reasons: in the first place, it is not of

much use in ordinary discourse, since in using the rule we are going from some-

thing more definite to something less definite, which we rarely need to do. In the

second place, it looks as if we are just pulling a formula out of thin air, and stu-

dents often wonder how it is possible to do this. To clarify these comments, we

need to look at the rule. The rule will tell us that given any statement whatever, we

may infer any disjunction with that statement as one of its disjuncts. Since the

statement used as a premise may appear as either disjunct in the conclusion, the

rule again has two forms. The rule is stated symbolically below:

ADDITION (ADD.)

P q

I,'.pvq I,'.pvq

Given any statement, you may infer any dis-

junction that includes that statement as one of

the disjuncts.

~qUnit 7 The Proof Method: Eight Basic Inference Rules 125

What is odd about this rule is that we are going from something stronger to

something weaker. From "Tod stole John's wallet," for instance, we can infer that

"Either Bill or Tod stole John's wallet," which seems grossly unfair to Bill since

we already know that Tod is the culprit! It is true, however, that if Tod stole it

then either Bill or Tod stole it, unfortunate as this may be for Bill. Although we

have little use for this rule in ordinary language, it is extremely helpful in formal

inferences, in actually constructing proofs. We often need to derive C, for in-

stance, from previous steps of the form (A v B) ::J C and A. But we cannot directly

infer C from these two steps by M.P., since A is not the antecedent of the condi-

tional. From A, however, we can infer (A v B), and since this is the antecedent, we

are then entitled to infer C. We used the rule of Addition in this way, to infer part

of a more complex antecedent, in step 7 of the proof in Section 2.

Another rather disconcerting thing about this rule is that we may add on as a

disjunct any formula, whether it has previously appeared in our proof or not and no

matter how complex it is. From ~ A, we may infer by Add. ~ A v [( Z v

(X ::J Y)) • [~ B ::J (C • ~ (Dv F))]]! This rather odd-looking rule is justified, how-

ever, simply by noting that if a given formula is true, then (because of the truth table

for disjunction) any formula containing it as a disjunct must be true.

The rule of Addition may be used on any formula; in other words, the

premise may be of any form. The conclusion of the rule, however, must always be

in the form of a disjunction; that is, it must always have a disjunction as its major

operator, with the premise as one disjunct. This means you may not apply Addition

to just a part of a formula. It would thus not be correct to infer «A v B) ::J C) from

(A ::J C) because the major operator of the conclusion is not a disjunction, al-

though the formula contains a disjunction as a subformula.

One final reminder: do not confuse the Addition rule, which has a disjunction

as a conclusion, with the Conjunction rule, which has a conjunction as a conclu-

sion. The disjunctive conclusion, by Addition, requires only a single formula as a

premise, whereas the conjunctive conclusion of Conjunction requires two premises.

We will not, in this unit, introduce a rule for the biconditional. In the next

unit we will have a rule that will allow us to replace a biconditional (p == q) with

the conjunction of two conditionals, (p ::J q). (q ::J p), and this is the only bicon-

ditional rule we will need.

h. The Rule of Dilemma. Our last rule in this unit is one that combines sev-

eral operators and so falls into no particular category; this is the Dilemma rule,

abbreviated Dil. The Dilemma rule tells us that given two conditionals and the

disjunction of their antecedents, we may infer the disjunction of their conse-

quents. This is the only rule that requires more than two premises. The symbolic

form is stated below:126 DILEMMA (OIL.)

Unit 7 The Proof Method: Eight Basic Inference Rules

p~q

Given two conditionals and the disjunction of the antecedents

of those conditionals, we may infer the disjunction of the con-

sequences of the conditionals.

r~s

pvr

/ :. qvs

Notice that this rule is very much like Modus Ponens; it is just a kind of

"double-barreled" or "souped-up" version of M.P. Instead of one conditional and its

antecedent as premises, we have two conditionals and the disjunction of the an-

tecedents as premises, and instead of inferring the single consequent, we infer the

disjunction of the consequents. It is essential to remember that in this rule, the

premises must consist of two conditionals and one disjunction and that the conclu-

sion will be a disjunction.

The name of this rule was, no doubt, inspired by instances like the follow-

ing: "If the United States relies primarily on nuclear power, then waste dis-

posal will be a serious problem and there will someday be a major accident. If

the United States relies primarily on coal, then many miners will be killed and

air pollution will increase significantly. The United States will rely primarily

either on nuclear power or on coal. Therefore, either waste disposal will be a

serious problem and there will someday be a major accident, or many miners

will be killed and air pollution will increase significantly." Of course, we might

look on the bright side of things with the following instance of Dilemma: "If

the United States relies primarily on nuclear power, then there will not be an

enormous increase in air pollution. If it relies primarily on coal, then there will

not be a severe nuclear waste disposal problem. The United States will rely pri-

marily either on nuclear power or on coal. Therefore, either there will not be an

enormous increase in air pollution or there will not be a severe nuclear waste

disposal problem!"

Since this is our most complicated rule so far, it will be harder to keep straight

the premises and conclusion and easier to fall into error. The following, for instance,

would not be a correct application of the rule: ((A v B) :::J C), ((D· E) :::J F),

(A v D) / ... C y F. Here the problem is that the disjunction, the third premise, is

not the disjunction of the antecedents. The following would also be incorrect:

(A yC), (By D), (A :::J B) / ... C :::J D. Here the major operators are reversed.

These examples are not only not instances of the rule, they are also invalid; you

should construct counterexamples to demonstrate this fact. Correct uses of the rule

may be rather complex, but just keep in mind that as long as there are two condi-

tionals and the disjunction of their antecedents in the premises and the disjunction of

their consequents in the conclusion, the instance is correct. The following would be

a correct application of the rule:Unit 7 The Proof Method: Eight Basic Inference Rules 127

[«A v B) :J C) :J (D v F)], «F G) :J (A :J F)), [«A v B) :J C) v (F G)]

/:. (DvF)v(A:JF).

c. About the Rules. You now have all the rules for this unit; if you did not

memorize them as you went along, you should sit down and do so now. Learn the

rules and their names well enough so that you can take out a blank sheet of paper

and write them down with little or no hesitation. Learn the verbal descriptions of

the rules as well, so that you have a very clear understanding of what each rule can

do for you. This will be important when it comes to actually constructing proofs,

planning strategies, and thinking up plans of attack. Keep in mind also that the

rules you have been given areforms. They contain variables that can take as sub-

stitution instances any statement, simple or complex. You have already seen some

examples of fairly complex substitution instances of the rules. Exercises 2 through

5 at the end of the unit will give you further practice in recognizing complex in-

stances ofthe rules. It is very important that you complete all of them. Do not take

shortcuts. Again, it will help to think of the rules in terms of their major operators:

M.P., M.T., and H.S. are horseshoe rules; Simp. and Conj. are dot rules; Add. and

D.S. are wedge rules. Dilemma combines the horseshoe and the wedge.

You may wonder how we can be so certain that these results are correct and

that we will not get into trouble in applying them. The reason is that each of these

rules can easily be shown to be a truth functionally valid argument form. This

means that there can be no instance of any of these rules that has true premises and

a false conclusion. Our rules are all truth preserving. Thus, if our premises are all

true, even if we have a very long chain of intermediate steps, we can be sure that

in the end our conclusion will be true as well. If you are in doubt about any of

these rules, just construct a little truth table to test them out.

You may well wonder why you are allowed just these rules and no others.

You will not have a rule, for instance, that will permit you to infer ~ q directly

from (p == q) and ~ p, although it seems intuitively to be (and is) a perfectly valid

inference. Isn't this an arbitrary restriction on your creative powers? Well, yes and

no. It is a restriction, certainly, and in some ways it is arbitrary, since we could just

as well have included this rule in our system. But, on the other hand, there are an

infinite number of possible rules we could have included, which would have made

the system a bit difficult to learn. (You will gripe enough initially about the few

rules you do have to learn.) We need to include enough rules to do the job, but not

so many that the system becomes unwieldy. What we have here is a reasonable

compromise, and these particular rules are included because they are quite power-

ful and because they are rules that are commonly used.

But then, you may ask, why do we need any fixed system of rules at all? Why

can't we just make those inferences that seem reasonable, like the one mentioned

above, and not worry about memorizing a particular list? Well, to take nothing128 Unit 7 The Proof Method: Eight Basic Inference Rules

away from your undoubtedly fine reasoning powers, it is quite possible that you

might, at some point, be mistaken in what follows from what. You might be

tempted, for instance, to infer ~ A from ~ (A • B), which would be incorrect, or to

infer ~ B from (A v B) and A, which would be just as bad. There is an interesting

history of logical mistakes made by some of the best logicians of the twentieth

century, and this is, in fact, why there has come to be such an emphasis onjormal

logic, on using only those rules that are tried and true. You can be certain that if

you use only the rules given here (and use them correctly), you will never arrive

at an erroneous conclusion. If you try to make up your own rules, chances are that

sooner or later (and most probably sooner) your intuitions will lead you astray.

Finally, it must be emphasized that you must do the exercises as well as learn

the rules. In learning proofs, as in many other endeavors, practice, although it may

not make perfect, is absolutely essential; and lack of practice will virtually guar-

antee failure. At this point, you should complete Exercises 2 and 3 at the end of the

unit; do not even attempt to construct proofs until you can easily do the pre-

liminary exercises. You can't run before you walk, and you can't construct proofs

before you can recognize correct and incorrect applications of the rules.

4. Derivations and Proofs

The proof method for determining validity consists, as we have seen, in start-

ing with the premises and deriving a series of intermediate steps until we reach the

conclusion. What we do is to construct a chain of reasoning, each step a conse-

quence of previous steps, which shows that the conclusion does follow from the

premises. But, as noted above, not any old step will do; we are permitted to make

an inference only if it follows from previous steps according to one of the given

rules. We want to be sure that there are no "logical gaps" in our proof construction,

no weak links in our chain of reasoning; our sequence of steps must be "logically

tight." If an attempted proof contains even one incorrect step, then the chain of

reasoning has been broken, so the proof is a failure; we have not shown that the

conclusion follows from the premises. To guarantee that the proof sequence is log-

ically tight, each step in the proof that is not a premise must be justified, by noting

that it follows from previous steps (premises or other, intermediate steps) accord-

ing to one of the given rules of inference. Premises will be justified simply by not-

ing that they are premises, steps given initially from which the others are to follow.

We will require in a proof, then, that every single step be justified, either as

being a premise or as following from previous steps according to one of the given

rules of inference. We will justify a step by writing to the right of it whether it is a

premise or, if it is not, what rule it was derived from and what steps served as

premises for the application of that rule. Fully justified, the proof from Section 2

would look like the following (we will abbreviate "Premise" as "Pr."):

Unit 7 The Proof Method: Eight Basic Inference Rules 129

Supplying the justification for each step will be considered essential to the

proof, and if the justification is missing, the proof will be considered defective.

You should never write down a step in the first place unless you know exactly

where it comes from and by what rule; if you do know, then it is a simple matter to

jot down to the right of the step the information that justifies it.

We need now to be a little more precise in our definitions. In particular, we

have been rather taking for granted what it means for a step to follow from previ-

ous steps. We can now give the following definition: A step S follows from previ-

ous steps Pl ... P n according to a given rule of inference R if and only if S is a

substitution instance of the conclusion of the rule Rand Pl . .. P n are the corre-

sponding substitution instances of the premises of the rule R. Given the definition

of "following from," we can now say precisely what it means for a step to be jus-

tified: A justified step is either a premise, or else a step that follows from previous

steps according to one of the given rules of inference. This definition will be ex-

panded slightly in Unit 9, but for this unit and the next it is adequate.

So far we have been talking about arguments in which the desired conclusion is

given, where the problem is to arrive at the stated conclusion by constructing a series

of intermediate justified steps. In some cases, however, we do not know what the con-

clusion is supposed to be. Often we just want to derive the consequences of certain

hypotheses, see what follows from them, without any preconceived notions of what

the result will be. Such a deduction of consequences, which does not necessarily lead

to a particular conclusion, will be called a derivation. Any sequence of steps will be a

derivation so long as every step is justified. This gives us the following short and sim-

ple definition of a derivation: a derivation is a sequence ofjustified steps. All sorts of

funny things will count as derivations, including just a set of premises (since each

step will be justified as being a premise).The following sequence, which doesn't seem

to be going anywhere useful, is also a derivation:

I.A

2. AvB

3. (A vB) vC

4. ((AvB)vC)vD

5. (((A v B) vC) v D) v E

Pro

Add. 1

Add. 2

Add. 3

Add. 4130 Unit 7 The Proof Method: Eight Basic Inference Rules

6. ««AvB)vC)vD)vE)vF

7. ««(AvB)vC) vD)vE)vF)vG)

Add. 5

Add. 6

In contrast to a derivation, a proof is a sequence of steps that is going some-

where, in which we arrive at a definite conclusion that we were aiming at ahead of

time. The only difference between a derivation and a proof is that in a proof we

know where we are going (and get there), while in a derivation we simply deduce

whatever we can, whatever "falls out" of the premises. It should be noted that the

concepts of derivation and proof are not mutually exclusive. In fact, every proof is

also a derivation, since each step must be justified. A proof just has something

extra-a conclusion toward which the derivation is headed and with which it must

conclude. We can thus define proof very simply: a proof is a derivation in which

the last step is the desired conclusion.

In the next section we will begin to construct proofs, which lead to a definite

conclusion, but before you go on, you should do Exercises 4 and 5 at the end of the

unit. In Exercise 4 you will be given derivations, sequences of justified steps, and

it will be up to you to supply the justifications. You must find out what steps were

used in deriving each line and what rule was applied. In Exercise 5 you will first

be given premises and a rule and will be asked to draw the appropriate conclusion;

you will also be asked to supply the missing premise used in drawing a particular

conclusion from a particular rule; and in some cases you will be asked simply to

draw a conclusion, and you will have to figure out yourself what rule is applicable.

These exercises will prepare you for the task of constructing proofs yourself.

5. Constructing Simple Proofs

It is at this point in the course, where you begin to construct your own proofs,

that you may begin to feel some frustration. Learning the rules may be tedious, but

at least it requires nothing more than perseverance, and supplying the justification

for derivations that are already worked out is a purely mechanical procedure, requir-

ing nothing more than a thorough knowledge of the rules and an understanding of

the concept of a substitution instance. Constructing proofs from scratch, how-

ever, is not a mechanical procedure; there is no precise method, no set of instruc-

tions, for coming up with a series of steps that leads to the desired conclusion.

Constructing proofs often requires insight and ingenuity, and even if you know the

rules well, you may often find that you simply don't know how to get started or, once

started, you may not be able to see how to continue. This is a very common experi-

ence with beginning logic students and should be no cause for alarm, at least initial-

ly. What we will do in this section is to give you some idea of how to attack proof

problems and some practical hints for learning the process of constructing proofs.

What is absolutely essential, of course, is to know the rules thoroughly; you

should have them all clearly in your head so that you can look at a pair of formulasUnit 7 The Proof Method: Eight Basic Inference Rules 131

such as (A ::J (B· C)), ~ (B • C), and see immediately that it is an instance in which

you can apply the rule of Modus Tollens. You should also be sure you have done all

the preliminary exercises (l through 5) at the end of the unit; these will help make

the rules second nature to you and will help you get started in applying them. Finally,

you should make it a habit to start with the easiest problems first and gradually work

your way up to the more difficult ones. And do persevere; even though it may seem

that you are making no progress, if you follow the instructions, you will eventually

come to the point where what once seemed impossible now looks rather trivial. It

often takes a couple of weeks to catch on to the method, but sooner or later the light

will dawn. Once it does, you will have a real sense of accomplishment and may very

well find that this is the most enjoyable part of the course. Constructing proofs is like

doing puzzles, a challenging intellectual exercise, and if you take it in this spirit, you

should find it much easier and more enjoyable. Don't expect miracles the first time

you sit down to work; it sometimes takes time for everything to sink in, but your pa-

tience will eventually be rewarded.

Now that the sermon is finished, let us look at a very simple example: sup-

pose we have as premises (A . B) • ~ e and D ::J e, and we want to prove B • ~ D.

Whether we list the premises vertically or horizontally, we will generally write the

conclusion, for reference, to the right of the last premise, preceded by our "there-

fore" sign / .' .. We might, then, set up our problem as follows: (1) (A· B)· ~ e,

(2) D ::J e, / .'. B· ~ D. We will also "number" our problems in this unit with

small letters (this one is a). Try to do the proof yourself before you go on. One

method you can use, which will not always work but does work here, is to treat the

problem like a derivation and simply try to deduce whatever can be derived from

the premises. We will call this the method of working from the "top down" (as op-

posed to the "bottom-up" method, which will be applied in more complicated

problems). Let us see, then, what can be deduced from these premises. When you

have a conjunction in the premises, you can always apply the rule of Simplifica-

tion, and we can here apply it to premise 1. This would give us two intermediate

steps, from the two forms of the rule:

3. A· B Simp. 1

4. ~ e Simp. I

Now, given the conjunction in step 3, we could apply the Simp. rule once

again to get two more intermediate steps:

5. A Simp. 3

6. B Simp. 3

At this point we can check out our other premise and see what can be de-

duced from it. This premise is a conditional, D ::J e, and we note that in step 4, we132 Unit 7 The Proof Method: Eight Basic Inference Rules

have the negation of its consequent. This allows us to derive the negation of the

antecedent, according to the rule of Modus Tollens. Thus our next step in the

deduction would be

7. ~ D M.T.2,4

This seems to exhaust the resources of our premises, but it is all we need for

the conclusion. The conclusion, if you remember, was simply the conjunction

B· ~ D. We now have both of the conjuncts separately, so we are entitled to join

them together with the Conjunction rule, and the last step in our derivation will be

the desired conclusion.

8. B'~D Conj.6,7

You may have noticed here that we could just as well have applied the rule of

M.T. to get ~ D at step 5; there was no need to do the other Simplification step

first. In general, there will be many different ways in which a proof can be con-

structed; the order makes no difference except that, of course, every step must be

validly derived from previous steps, so you must first have the steps you need to

apply the rules. We could not have derived ~ D immediately after step 3, for in-

stance, because we did not yet have ~ C. Another thing that needs to be men-

tioned, although it does not come up in this problem, is that the order of the

premises in the application of a rule is irrelevant. If we first had ~ C and only then

derived D :J C, we could still have applied the M.T. rule.

Let us take a slightly more complicated example, but one in which we can

still work from the top down. Our premises will be the following, numbered I

through 4, and the conclusion will be listed following the "therefore" sign to the

right of the last premise:

b. 1. (A v B) :J (Cv D) Pro

2. (CvF):J H

3. E'~D

Pro

Pro

4. E:J A

Pro 1.".HvI

(Hint: When you have a letter in the conclusion that appears nowhere in the

premises, such as the I in this proof, it will have to be "imported" by the use of Ad-

dition. Here we will need to get H first, and then H v I by Add.) Again we have a

conjunction in the premises, at step 3, so we may as well begin there by applying

the Simplification rule. This gives us

5. E

6. ~D

Simp. 3

Simp. 3Unit 7 The Proof Method: Eight Basic Inference Rules 133

Now, if you know your rules well, the next step should be obvious: the rule

of Modus Ponens will give us

7. A M.P. 4,5

Now what? Here you should notice that we could apply the rule of Modus

Ponens to step 1 if we had A v B (this is, again, a matter of knowing your rules

well). We do have A, and if you think for a minute, you will realize that you can

derive A v B from A by Addition. This gives

8. AvB Add. 7

At this point we can apply M.P., as we saw earlier.

9. CvD M.P. 1,8

We now have quite a few steps, and you may need to pause to look them over

to see what else you can do. As we scan the list, we see that we have a disjunction

and the negation of one of the disjuncts in steps 9 and 6; thus, we can apply the

rule of Disjunctive Syllogism. (Notice here that the order of the premises is re-

versed.) This gives us

10. C D.S.9,6

We can now apply our Addition trick again to get

11. CvF Add. 10

This we need in order to apply M.P. to step 2, which will yield

12. H M.P. 2,11

Now what? We seem to have used up all our ammunition. Fortunately, the

conclusion is only a short hop away: from H we can derive H v I by Addition, and

this is the end of the proof.

13. Hv I Add. 12

At this point, it would be a good idea to take a fresh sheet of paper, write

down the last two problems, close your book, and try to reconstruct the proofs. If

you get stuck, go back and reread the explanation and then try to do the proofs

again. Keep trying and rereading until you can do them.134 Unit 7 The Proof Method: Eight Basic Inference Rules

Although there are many things you cannot do in a proof, such as make up your

own rules, a number of things are permitted that make no difference to the proof. You

may use premises more than once, or you may not use some of them at all. Nothing in

the definition of "proof' says that each premise must be used once and only once. It

has already been noted that the premises may be in any order. Perhaps surprisingly, it

also does not matter if you have extra, unneeded steps. If in doing a proof you go

down the wrong road and reach a dead end, it is not necessary to erase all the useless

steps and start over. Once you discover the correct route, you can simply write down

those useful steps immediately following the useless steps. There is nothing in the de-

finition of a proof that says it must be optimally short, so it is not necessary to "purge"

a proof of unnecessary steps. A proof may contain all sorts of useless garbage as long

as the two essential conditions are met: (1) the conclusion is eventually reached, and

(2) every step in the proof sequence, whether useful or not, is justified. You should

keep these things in mind as you attempt to do the following proof:

c. 1. ~ A Pro

2. D::J A Pro

3. B::J A Pro

4. A::J C Pro

5. C::J (D v E) Pro

6. BvF Pro

7. DvG Pro / ... F' G

Suppose you were given the following problem; would you consider it a

misprint?

d. 1. AvB

2. B::J C

3. ~A' ~ C

Pro

Pro

Pro / ... F ::J G

It certainly looks as if there is no possible way to derive the conclusion; F and G

don't appear anywhere in the premises. But being a conscientious student, you

would no doubt give it a try anyway, perhaps in the following manner:

4. ~A

5. ~C

6. B

7. ~B

Simp. 3

Simp. 3

D.S.l,4

M.T.2,5

At this point you need to know that given a contradiction, you may derive

anything, including the desired conclusion (or its negation!). Simply use Addition

on B to get B v (F ::J G), and then D.S., with ~ B, to get the conclusion.Unit 7 The Proof Method: Eight Basic Inference Rules 135

8. B v (F => G)

9. F => G

Add. 6

D.S.7,8

In general, if you have a contradiction (p and also ~ p), you can derive any

formula q at all by getting p v q by Addition from p, and then q by the application

of Disjunctive Syllogism to p v q and ~ p. Some of the proof problems at the end

of the unit may require this little trick.

Having seen several examples, and assuming that you know your rules, you

should now be in a position to try Exercises 6, 7, and 8 at the end ofthe unit. These

exercises are graduated, starting with some fairly trivial problems and then moving

on to more complex ones. They should all be solvable by the application of the top-

down method, in which you simply try to deduce whatever you can until you reach

the conclusion. More complex problems, which will require a little more planning

and strategy, will be given in Exercise 9. For these you will sometimes need to use

the method of "working backward," or "from the bottom up." This method and other

strategy hints for more complex problems will be developed in the next section.

6. Constructing More Complex Proofs

In some proofs, even relatively easy ones on occasion, you may simply not

see how to get started; you may not be able to use the top-down method because

you don't see what things can be deduced from the premises to begin with. In such

cases it may be helpful to use the bottom-up method, or the method of working

backward. What this entails is looking first at the conclusion, then checking the

premises to see how the conclusion could "come out" of them, and then working

out step by step, from the bottom up, what will be needed to obtain the conclusion.

To use this method, you have to not only know your rules by heart, but also know

what they can do for you. If your conclusion, for instance, is B, and you have a for-

mula (C => (A vB)), you must know your rules well enough to reason in the fol-

lowing way: "If I had A v B and ~ A, I could derive B. I could get A v B by the rule

of Modus Ponens from (C => (A v B)), provided I had the antecedent c." This bit of

reasoning would have told you that you need C and ~ A in order to derive B from

(C => (A vB)). This kind of reasoning will be used constantly in the bottom-up

method, because you will be asking, "What do I need to get the conclusion?" And,

having discovered that you need a certain intermediate formula to get it, you will

then have to ask, "How can I get that intermediate formula?" and so on, until you

reach back into the premises. We will take a relatively simple problem (which actu-

ally could be solved by the direct top-down method) to illustrate this procedure.

e. 1. (AvB) => (Cv(F => H))

2. A'~C

3. H => C

Pro

Pro

Pro / ". ~ F136 Unit 7 The Proof Method: Eight Basic Inference Rules

Since our conclusion is ~ F, we look into the premises to see where it might

come from. F occurs in the rather complex first premise, and what we must do is

figure out how to pull ~ F out of that formula. For this you need to know, again,

what each rule can do for you. F appears as a subformula of the consequent of a

conditional; thus you must first get that consequent, (C v (F :J H)). You should

know that you can derive the consequent of a conditional by M.P., provided you can

get its antecedent. Thus you will need (A v B). Once you get (C v (F :J H)), you

should note that you need (F :J H) and that this could be derived by D.S. if you

could get ~ C. ~ C, then, is another formula you will need. Once you have F :J H

by this process, clearly you will need ~ H to get ~ F by M.T. Thus you will need

the three formulas (A v B), ~ C, and ~ H to get ~ F from the first premise. Having

figured this out, the obvious next move is to try to figure out how to get these three

formulas. You look back into the premises and note that one is immediate: ~ C oc-

curs as a part of a conjunction in step 2 and so can be derived just by Simp. We

might as well do A at the same time, for the following two steps:

4. ~C

5. A

Simp. 2

Simp. 2

At this point it's no mystery how to get A v B, since we already have A.

6. AvB Add. 5

The only thing left is to get ~ H. By this time that is no trick either, since we

have H :J C as premise 3, and we already have ~ C at step 4. Thus we get

7. ~H M.T.3,4

We now have the steps we said we needed in order to pull ~ F out of the first

premise, so let us apply them as needed:

8. C v (F:J H)

9. F:J H

10. ~F

M.P. 1,6

D.S.8,4

M.T.7,9

In the bottom-up or working-backward method, as the names imply, you start

out by considering the conclusion in your reasoning process, rather than the

premises. Instead of asking, "What can be derived from these premises?" as in the

last section, you ask, "Given that this is the conclusion I want, how can I get it;

that is, what formulas do I need to derive it, and what rules will be applied?" If

your conclusion is a conjunction, for instance, in general the thing to do will be to

get both conjuncts separately, and if the conclusion is a disjunction, it can be de-

rived either by Addition or Dilemma.Unit 7 The Proof Method: Eight Basic Inference Rules 137

Let us take a slightly more complex problem that requires more steps and a

more extended use of the working-backward method:

f. 1. A::J (B v C)

2. B::J F

3. A'~F

4. (A v H) ::J D

Pro

Pro

Pro

Pr./".C·D

Here our conclusion is a conjunction, so the thing to do is work on each conjunct

separately and then put them together with the rule of Conjunction. D should not

be hard to derive, since it occurs as the consequent of a conditional in Premise 4

and thus can be derived by M.P., provided we have the antecedent. The antecedent

is A v H, and to get this, we will probably use either Add. or Dil. Checking out the

premises, we see that we have A in Premise 3, which occurs as a part of a con-

junction. Thus we can get A by Simp., A v H by Add., and D by M.P. This is

one-half of our conclusion.

5. A

6. AvH

7. D

Simp. 3

Add. 5

M.P. 4,6

The other half is C, and this will be a little more involved. C occurs in

Premise 1 in the consequent of a conditional, as one disjunct. Thus we could de-

rive C from Premise 1 if we could get A, the antecedent of the conditional, and

~ B, the negation of the other disjunct. But we already have A, so we can use

M.P. to get

8. BvC M.P. 1,5

Now we need ~ B, and at this point it is easy to get. Since B appears in

Premise 2 as the antecedent of a conditional, we could derive ~ B by M.T. provided

we could get the negation of the consequent, ~ F. But we have this ready and

waiting in Premise 3, so we are almost there.

9. ~F

10. ~B

Simp. 3

M.T. 2,9

We can now apply D.S. to steps 8 and 10 to get our other conjunct, and we

can then conjoin the two conjuncts to get our conclusion.

II. C

12. C'D

D.S.8,1O

Conj.7,11138 Unit 7 The Proof Method: Eight Basic Inference Rules

You should read through these problems until you fully understand every

step; keep in mind, however, that there may be other ways of doing the proofs.

Especially with complex problems, there are usually a number of different and

equally correct ways to derive the conclusions. As long as every step is justified

and you eventually get to the conclusion, it doesn't really matter how you got

there, even if your route is rather circuitous. In doing your problems, start with

the easiest ones first and gradually work your way up to the more difficult ones.

Take your time and don't get discouraged if you don't immediately succeed. If

you know your rules well, apply them correctly, study the previous examples,

and persevere, you should eventually be able to complete most of the proofs.

And, again, think of them as puzzles, as intellectual challenges; proofs are

rather like mazes, where you have to reach the conclusion by working through

to the right path. If you take it in this spirit, the process of learning to construct

proofs should prove to be intellectually rewarding.

SUMMARY OF RULES OF INFERENCE

MODUS PONENS (M.P.)

MODUS TOLLENS (M.T.)

p-:Jq

P

I .'. q

p'-:Jq

~q

I :. ~p

HYPOTHETICAL

SYLLOGISM (H.S.)

p-:Jq

q-:Jr

I:.p-:Jr

SIMPLIFICATION (SIMP.)

p'q P'q

I :. p I :. q

CONJUNCTION (CONj.)

P

q

DILEMMA (DIL.)

I:.p·q pvr

p-:Jq

r-:Js

I :. q v s

DISJUNCTIVE SYLLOGISM (D.S.) ADDITION (ADD.)

pvq

p vq

p

q

~p

~q

I:. p v q

I:. p v q

I :. q

I :. p

1. 2. DEFINITIONS

A constant is a term that has a definite, particular value.

A variable is a term that may represent any value.3. 4. 5. 6. 7. 8. 9. 10. Unit 7 The Proof Method: Eight Basic Inference Rules 139

A statement variable is a letter that can take as substitution instances any par-

ticular statement, simple or complex. (We will use lowercase letters from the

middle of the alphabet, p, q, r, ... , as our statement variables.)

A statement constant is a capital letter that is used as an abbreviation for a par-

ticular truth functionally simple English sentence.

A statement is a formula (simple or complex) that has statement constants as its

smallest components.

A statement form is a formula (simple or complex) that has statement variables

as its smallest components.

A substitution instance (s.i.) of a statement form is a statement obtained by

substituting (uniformly) some statement for each variable in the statement

form. (We must substitute the same statement for repeated occurrences of the

same variable, and we may substitute the same statement for different vari-

ables. Thus both A v B and A v A are s. i. 's of p v q, but A v B is not an s.i. of

p vp.)

A justified step is either a premise, or else a step that follows from previous

steps according to one of the given rules of inference.

A derivation is a sequence of justified steps.

A proof is a derivation (sequence of justified steps) in which the last step is the

desired conclusion.