disjunction that has P as one of its disjuncts. After all, if P is true, so is any

such disjunction.

What strikes newcomers to logic as peculiar about such a step is that using

it amounts to throwing away information. Why in the world would you want

to conclude P ∨ Q when you already know the more informative claim P? But

as we will see, this step is actually quite useful when combined with some

of the methods of proof to be discussed later. Still, in mathematical proofs,

it generally goes by unnoticed. In formal systems, it is dubbed disjunction

introduction, or (rather unfortunately) addition.

Matters of style

Informal proofs serve two purposes. On the one hand, they are a method of

discovery; they allow us to extract new information from information already

obtained. On the other hand, they are a method of communication; they allow

us to convey our discoveries to others. As with all forms of communication,

this can be done well or done poorly.

When we learn to write, we learn certain basic rules of punctuation, capi-

talization, paragraph structure and so forth. But beyond the basic rules, there

are also matters of style. Di¬erent writers have di¬erent styles. And it is a

Section 5.1

130 / Methods of Proof for Boolean Logic

good thing, since we would get pretty tired of reading if everyone wrote with

the very same style. So too in giving proofs. If you go on to study mathemat-

ics, you will read lots of proofs, and you will ¬nd that every writer has his or

her own style. You will even develop a style of your own.

Every step in a “good” proof, besides being correct, should have two prop-

erties. It should be easily understood and signi¬cant. By “easily understood”

we mean that other people should be able to follow the step without undue

di¬culty: they should be able to see that the step is valid without having to

engage in a piece of complex reasoning of their own. By “signi¬cant” we mean

that the step should be informative, not a waste of the reader™s time.

These two criteria pull in opposite directions. Typically, the more signif-

icant the step, the harder it is to follow. Good style requires a reasonable

balance between the two. And that in turn requires some sense of who your

knowing your audience

audience is. For example, if you and your audience have been working with

logic for a while, you will recognize a number of equivalences that you will

want to use without further proof. But if you or your audience are beginners,

the same inference may require several steps.

Remember

1. In giving an informal proof from some premises, if Q is already

known to be a logical consequence of sentences P1 , . . . , Pn and each of

P1 , . . . , Pn has been proven from the premises, then you may assert Q

in your proof.

2. Each step in an informal proof should be signi¬cant but easily under-

stood.

3. Whether a step is signi¬cant or easily understood depends on the

audience to whom it is addressed.

4. The following are valid patterns of inference that generally go unmen-

tioned in informal proofs:

—¦ From P § Q, infer P.

—¦ From P and Q, infer P § Q.

—¦ From P, infer P ∨ Q.

Chapter 5

Proof by cases / 131

Exercises

In the following exercises we list a number of patterns of inference, only some of which are valid. For

each pattern, determine whether it is valid. If it is, explain why it is valid, appealing to the truth tables

for the connectives involved. If it is not, give a speci¬c example of how the step could be used to get from

true premises to a false conclusion.

5.1 5.2

From P ∨ Q and ¬P, infer Q. From P ∨ Q and Q, infer ¬P.

5.3 5.4

From ¬(P ∨ Q), infer ¬P. From ¬(P § Q) and P, infer ¬Q.

5.5 5.6

From ¬(P § Q), infer ¬P. From P § Q and ¬P, infer Q.

Section 5.2

Proof by cases

The simple forms of inference discussed in the last section are all instances of

the principle that you can use already established cases of logical consequence

in informal proofs. But the Boolean connectives also give rise to two entirely

new methods of proof, methods that are explicitly applied in all types of

rigorous reasoning. The ¬rst of these is the method of proof by cases. In our

formal system F , this method will be called disjunction elimination, but don™t

be misled by the ordinary sounding name: it is far more signi¬cant than, say,

disjunction introduction or conjunction elimination.

We begin by illustrating proof by cases with a well-known piece of math-

ematical reasoning. The reasoning proves that there are irrational numbers b

and c such that bc is rational. First, let™s review what this means. A number

is said to be rational if it can be expressed as a fraction n/m, for integers

n and m. If it √ can™t be so expressed, then it is irrational. Thus 2 is rational

(2 = 2/1), but 2 is irrational. (We will prove this latter fact in the next sec-

tion, to illustrate proof by contradiction; for now, just take it as a well-known

truth.) Here now is our proof:

Proof: To show that there are irrational numbers b and c such that

√ √2

c is rational, we will consider the number

b 2 . We note that this

number is either rational or irrational.

Section 5.2

132 / Methods of Proof for Boolean Logic

√ √2

If 2 √ rational, then we have found our b and c; namely, we take

is

b = c = 2.

√ √2

Suppose, on the other hand, that 2 is irrational. Then we take

√ √2 √

b = 2 and c = 2 and compute bc :

√ √2 √2

c

b = ( 2√ )

√ ( 2·√2)

= 2

√2

= 2

= 2

Thus, we see that in this case, too, bc is rational.

√ √2

Consequently, whether 2 is rational or irrational, we know that

there are irrational numbers b and c such that bc is rational.

What interests us here is not the result itself but the general structure of

the argument. We begin with a desired goal that we want to prove, say S, and

a disjunction we already know, say P ∨ Q. We then show two things: that S

proof by cases

follows if we assume that P is the case, and that S follows if we assume that

Q is the case. Since we know that one of these must hold, we then conclude

that S must be the case. This is the pattern of reasoning known as proof by

cases.

In proof by cases, we aren™t limited to breaking into just two cases, as we

did in the example. If at any stage in a proof we have a disjunction containing

n disjuncts, say P1 ∨ . . . ∨ Pn , then we can break into n cases. In the ¬rst we

assume P1 , in the second P2 , and so forth for each disjunct. If we are able to

prove our desired result S in each of these cases, we are justi¬ed in concluding

that S holds.

Let™s look at an even simpler example of proof by cases. Suppose we want

to prove that Small(c) is a logical consequence of

(Cube(c) § Small(c)) ∨ (Tet(c) § Small(c))

This is pretty obvious, but the proof involves breaking into cases, as you will

notice if you think carefully about how you recognize this. For the record,

here is how we would write out the proof.

Proof: We are given

(Cube(c) § Small(c)) ∨ (Tet(c) § Small(c))

as a premise. We will break into two cases, corresponding to the two

disjuncts. First, assume that Cube(c) § Small(c) holds. But then (by

Chapter 5

Proof by cases / 133

conjunction elimination, which we really shouldn™t even mention) we

have Small(c). But likewise, if we assume Tet(c) § Small(c), then it

follows that Small(c). So, in either case, we have Small(c), as desired.

Our next example shows how the odd step of disjunction introduction

(from P infer P ∨ Q) can be used fruitfully with proof by cases. Suppose we

know that either Max is home and Carl is happy, or Claire is home and Scru¬y

is happy, i.e.,

(Home(max) § Happy(carl)) ∨ (Home(claire) § Happy(scru¬y))

We want to prove that either Carl or Scru¬y is happy, that is,

Happy(carl) ∨ Happy(scru¬y)

A rather pedantic, step-by-step proof would look like this:

Proof: Assume the disjunction:

(Home(max) § Happy(carl)) ∨ (Home(claire) § Happy(scru¬y))

Then either:

Home(max) § Happy(carl)

or:

Home(claire) § Happy(scru¬y).

If the ¬rst alternative holds, then Happy(carl), and so we have

Happy(carl) ∨ Happy(scru¬y)

by disjunction introduction. Similarly, if the second alternative holds,

we have Happy(scru¬y), and so

Happy(carl) ∨ Happy(scru¬y)

So, in either case, we have our desired conclusion. Thus our conclu-

sion follows by proof by cases.

Arguing by cases is extremely useful in everyday reasoning. For example,

one of the authors (call him J) and his wife recently realized that their parking

meter had expired several hours earlier. J argued in the following way that

there was no point in rushing back to the car (logicians argue this way; don™t

marry one):

Section 5.2

134 / Methods of Proof for Boolean Logic

Proof: At this point, either we™ve already gotten a ticket or we

haven™t. If we™ve gotten a ticket, we won™t get another one in the

time it takes us to get to the car, so rushing would serve no purpose.

If we haven™t gotten a ticket in the past several hours, it is extremely

unlikely that we will get one in the next few minutes, so again,

rushing would be pointless. In either event, there™s no need to rush.

J™s wife responded with the following counterargument (showing that many

years of marriage to a logician has an impact):

Proof: Either we are going to get a ticket in the next few minutes or

we aren™t. If we are, then rushing might prevent it, which would be

a good thing. If we aren™t, then it will still be good exercise and will

also show our respect for the law, both of which are good things. So

in either event, rushing back to the car is a good thing to do.

J™s wife won the argument.

The validity of proof by cases cannot be demonstrated by the simple truth

table method introduced in Chapter 4. The reason is that we infer the con-

clusion S from the fact that S is provable from each of the disjuncts P and

Q. It relies on the principle that if S is a logical consequence of P, and also a

logical consequence of Q, then it is a logical consequence of P ∨ Q. This holds

because any circumstance that makes P ∨ Q true must make at least one of P

or Q true, and hence S as well, by the fact that S is a consequence of both.

Remember

Proof by cases: To prove S from P1 ∨ . . . ∨ Pn using this method, prove

S from each of P1 , . . . , Pn .

Exercises

The next two exercises present valid arguments. Turn in informal proofs of the arguments™ validity. Your

proofs should be phrased in complete, well-formed English sentences, making use of ¬rst-order sentences