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