<<

. 25
( 107 .)



>>

More generally, if you have proven some sentence P then you can infer any
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

<<

. 25
( 107 .)



>>