<<

. 26
( 107 .)



>>

as convenient, much in the style we have used above. Whenever you use proof by cases, say so. You don™t
have to be explicit about the use of simple proof steps like conjunction elimination. By the way, there is
typically more than one way to prove a given result.




Chapter 5
Proof by cases / 135



5.7 5.8
Home(max) ∨ Home(claire) LeftOf(a, b) ∨ RightOf(a, b)
 
¬Home(max) ∨ Happy(carl) BackOf(a, b) ∨ ¬LeftOf(a, b)
¬Home(claire) ∨ Happy(carl) FrontOf(b, a) ∨ ¬RightOf(a, b)
SameCol(c, a) § SameRow(c, b)
Happy(carl)
BackOf(a, b)

5.9 Assume the same four premises as in Exercise 5.8. Is LeftOf(b, c) a logical consequence of
‚| these premises? If so, turn in an informal proof of the argument™s validity. If not, submit a
counterexample world.

5.10 Suppose Max™s favorite basketball team is the Chicago Bulls and favorite football team is the
 Denver Broncos. Max™s father John is returning from Indianapolis to San Francisco on United
Airlines, and promises that he will buy Max a souvenir from one of his favorite teams on the
way. Explain John™s reasoning, appealing to the annoying fact that all United ¬‚ights between
Indianapolis and San Francisco stop in either Denver or Chicago. Make explicit the role proof
by cases plays in this reasoning.

5.11 Suppose the police are investigating a burglary and discover the following facts. All the doors
 to the house were bolted from the inside and show no sign of forced entry. In fact, the only
possible ways in and out of the house were a small bathroom window on the ¬rst ¬‚oor that
was left open and an unlocked bedroom window on the second ¬‚oor. On the basis of this, the
detectives rule out a well-known burglar, Julius, who weighs two hundred and ¬fty pounds and
is arthritic. Explain their reasoning.

In our proof that there are irrational numbers b and c where bc is rational, one of our steps
5.12
√ √2
 was to assert that 2 is either rational or irrational. What justi¬es the introduction of this
claim into our proof ?

5.13 Describe an everyday example of reasoning by cases that you have performed in the last few
 days.

5.14 Give an informal proof that if S is a tautological consequence of P and a tautological conse-
 quence of Q, then S is a tautological consequence of P ∨ Q. Remember that the joint truth
table for P ∨ Q and S may have more rows than either the joint truth table for P and S, or the
joint truth table for Q and S. [Hint: Assume you are looking at a single row of the joint truth
table for P ∨ Q and S in which P ∨ Q is true. Break into cases based on whether P is true or Q
is true and prove that S must be true in either case.]




Section 5.2
136 / Methods of Proof for Boolean Logic


Section 5.3
Indirect proof: proof by contradiction
One of the most important methods of proof is known as proof by contradic-
tion. It is also called indirect proof or reductio ad absurdum. Its counterpart
in F is called negation introduction.
The basic idea is this. Suppose you want to prove a negative sentence, say
¬S, from some premises, say P1 , . . . , Pn . One way to do this is by temporarily
indirect proof or proof
by contradiction assuming S and showing that a contradiction follows from this assumption. If
you can show this, then you are entitled to conclude that ¬S is a logical conse-
quence of the original premises. Why? Because your proof of the contradiction
shows that S, P1, . . . , Pn cannot all be true simultaneously. (If they were, the
contradiction would have to be true, and it can™t be.) Hence if P1 , . . . , Pn are
true in any set of circumstances, then S must be false in those circumstances.
Which is to say, if P1 , . . . , Pn are all true, then ¬S must be true as well.
Let™s look at a simple indirect proof. Assume Cube(c) ∨ Dodec(c) and
Tet(b). Let us prove ¬(b = c).

Proof: In order to prove ¬(b = c), we assume b = c and attempt
to get a contradiction. From our ¬rst premise we know that either
Cube(c) or Dodec(c). If the ¬rst is the case, then we conclude Cube(b)
by the indiscernibility of identicals, which contradicts Tet(b). But
similarly, if the second is the case, we get Dodec(b) which contra-
dicts Tet(b). So neither case is possible, and we have a contradiction.
Thus our initial assumption that b = c must be wrong. So proof by
contradiction gives us our desired conclusion, ¬(b = c). (Notice that
this argument also uses the method of proof by cases.)

Let us now give a more interesting and famous example of this method of
proof. The Greeks were shocked to discover that the square root of 2 could
not be expressed as a fraction, or, as we would put it, is irrational. The proof
of this fact proceeds via contradiction. Before we go through the proof, let™s
review some simple numerical facts that were well known to the Greeks. The
¬rst is that any rational number can be expressed as a fraction p/q where at
least one of p and q is odd. (If not, keep dividing both the numerator and
denominator by 2 until one of them is odd.) The other fact follows from the
observation that when you square an odd number, you always get an odd
number. So if n2 is an even number, then so is n. And from this, we see that
if n2 is even, it must be divisible by 4. √
Now we™re ready for the proof that 2 is irrational.




Chapter 5
Indirect proof: proof by contradiction / 137



Proof: With an eye toward getting a contradiction, we will assume
√ √
that 2 is rational. Thus, on this assumption, 2 can be expressed √
in the form p/q, where at least one of p and q is odd. Since p/q = 2
we can square both sides to get:
p2
=2
q2
Multiplying both sides by q 2 , we get p2 = 2q 2 . But this shows that
p2 is an even number. As we noted before, this allows us to conclude
that p is even and that p2 is divisible by 4. Looking again at the
equation p2 = 2q 2 , we see that if p2 is divisible by 4, then 2q 2 is
divisible by 4 and hence q 2 must be divisible by 2. In which case, q is
even as well. So both p and q are even, contradicting the fact that at

least one of them is odd. Thus, our assumption that 2 is rational
led us to a contradiction, and so we conclude that it is irrational.

In both of these examples, we used the method of indirect proof to prove a
sentence that begins with a negation. (Remember, “irrational” simply means
not rational.) You can also use this method to prove a sentence S that does not
begin with a negation. In this case, you would begin by assuming ¬S, obtain
a contradiction, and then conclude that ¬¬S is the case, which of course is
equivalent to S.
In order to apply the method of proof by contradiction, it is important
that you understand what a contradiction is, since that is what you need
to prove from your temporary assumption. Intuitively, a contradiction is any contradiction
claim that cannot possibly be true, or any set of claims which cannot all
be true simultaneously. Examples are a sentence Q and its negation ¬Q, a
pair of inconsistent claims like Cube(c) and Tet(c) or x < y and y < x, or a
single sentence of the form a = a. We can take the notion of a contradictory
or inconsistent set of sentences to be any set of sentences that could not all
be true in any single situation.
The symbol ⊥ is often used as a short-hand way of saying that a contra- contradiction
symbol (⊥)
diction has been obtained. Di¬erent people read ⊥ as “contradiction,” “the
absurd,” and “the false,” but what it means is that a conclusion has been
reached which is logically impossible, or that several conclusions have been
derived which, taken together, are impossible.
Notice that a sentence S is a logical impossibility if and only if its negation
¬S is logically necessary. This means that any method we have of demonstrat-
ing that a sentence is logically necessary also demonstrates that its negation
is logically impossible, that is, a contradiction. For example, if a truth table
shows that ¬S is a tautology, then we know that S is a contradiction.



Section 5.3
138 / Methods of Proof for Boolean Logic


Similarly, the truth table method gives us a way of showing that a col-
lection of sentences are mutually contradictory. Construct a joint truth table
for P1 , . . . , Pn . These sentences are tt-contradictory if every row has an F as-
tt-contradictory
signed to at least one of the sentences. If the sentences are tt-contradictory,
we know they cannot all be true at once, simply in virtue of the meanings
of the truth functional connectives out of which they are built. We have al-
ready mentioned one such example: any pair of sentences, one of which is the
negation of the other.
The method of proof by contradiction, like proof by cases, is often encoun-
tered in everyday reasoning, though the derived contradiction is sometimes
left implicit. People will often assume a claim for the sake of argument and
then show that the assumption leads to something else that is known to be
false. They then conclude the negation of the original claim. This sort of rea-
soning is in fact an indirect proof: the inconsistency becomes explicit if we
add the known fact to our set of premises.
Let™s look at an example of this kind of reasoning. Imagine a defense
attorney presenting the following summary to the jury:
The prosecution claims that my client killed the owner of the KitKat
Club. Assume that they are correct. You™ve heard their own experts
testify that the murder took place at 5:15 in the afternoon. We also
know the defendant was still at work at City Hall at 4:45, according
to the testimony of ¬ve co-workers. It follows that my client had to
get from City Hall to the KitKat Club in 30 minutes or less. But
to make that trip takes 35 minutes under the best of circumstances,
and police records show that there was a massive tra¬c jam the day
of the murder. I submit that my client is innocent.
Clearly, reasoning like this is used all the time: whenever we assume some-
thing and then rule out the assumption on the basis of its consequences.
Sometimes these consequences are not contradictions, or even things that we
know to be false, but rather future consequences that we consider unaccept-
able. You might for example assume that you will go to Hawaii for spring
break, calculate the impact on your ¬nances and ability to ¬nish the term
papers coming due, and reluctantly conclude that you can™t make the trip.
When you reason like this, you are using the method of indirect proof.

Remember

Proof by contradiction: To prove ¬S using this method, assume S and
prove a contradiction ⊥.




Chapter 5
Indirect proof: proof by contradiction / 139



Exercises

In the following exercises, decide whether the displayed argument is valid. If it is, turn in an infor-
mal proof, phrased in complete, well-formed English sentences, making use of ¬rst-order sentences as
convenient. Whenever you use proof by cases or proof by contradiction, say so. You don™t have to be
explicit about the use of simple proof steps like conjunction elimination. If the argument is invalid, con-
struct a counterexample world in Tarski™s World. (Argument 5.16 is valid, and so will not require a
counterexample.)

5.15 5.16
b is a tetrahedron. Max or Claire is at home but either
‚| 
c is a cube. Scru¬y or Carl is unhappy.
Either c is larger than b or else they Either Max is not home or Carl is
are identical. happy.
Either Claire is not home or Scru¬y is
b is smaller than c.
unhappy.
Scru¬y is unhappy.

5.17 5.18
Cube(a) ∨ Tet(a) ∨ Large(a) Cube(a) ∨ Tet(a) ∨ Large(a)
‚| ‚|
¬Cube(a) ∨ a = b ∨ Large(a) ¬Cube(a) ∨ a = b ∨ Large(a)
¬Large(a) ∨ a = c ¬Large(a) ∨ a = c
¬(c = c § Tet(a)) ¬(c = c § Tet(a))
a= b∨a= c ¬(Large(a) ∨ Tet(a))

5.19 Consider the following sentences.
 1. Folly was Claire™s pet at 2 pm or at 2:05 pm.
2. Folly was Max™s pet at 2 pm.
3. Folly was Claire™s pet at 2:05 pm.

Does (3) follow from (1) and (2)? Does (2) follow from (1) and (3)? Does (1) follow from (2)
and (3)? In each case, give either a proof of consequence, or describe a situation that makes the
premises true and the conclusion false. You may assume that Folly can only be one person™s
pet at any given time.

5.20 Suppose it is Friday night and you are going out with your boyfriend. He wants to see a romantic
 comedy, while you want to see the latest Wes Craven slasher movie. He points out that if he
watches the Wes Craven movie, he will not be able to sleep because he can™t stand the sight of
blood, and he has to take the MCAT test tomorrow. If he does not do well on the MCAT, he
won™t get into medical school. Analyze your boyfriend™s argument, pointing out where indirect
proof is being used. How would you rebut his argument?




Section 5.3
140 / Methods of Proof for Boolean Logic


5.21 Describe an everyday example of an indirect proof that you have used in the last few days.

5.22 Prove that indirect proof is a tautologically valid method of proof. That is, show that if
 P1 , . . . , Pn , S is tt-contradictory, then ¬S is a tautological consequence of P1 , . . . , Pn .

In the next three exercises we ask you to prove simple facts about the natural numbers. We do not expect
you to phrase the proofs in fol. You will have to appeal to basic facts of arithmetic plus the de¬nitions

<<

. 26
( 107 .)



>>