Did you get lost? This proof has a pretty complicated structure, since we

¬rst assumed Even(n2 ) for the purpose of conditional proof, but then immedi-

ately assumed ¬Even(n) to get an indirect proof of Even(n). The contradiction

that we arrived at was ¬Even(n2 ), which contradicted our ¬rst assumption.

Proofs of this sort are fairly common, and this is why it is often easier to

prove the contrapositive of a conditional. The contrapositive of our original

claim is this:

¬Even(n) ’ ¬Even(n2 )

Let™s look at the proof of this contrapositive.

Proof: To prove ¬Even(n) ’ ¬Even(n2 ), we begin by assuming ¬Even(n),

i.e., that n is odd. Then we can express n as 2m + 1, for some m.

But then we see that:

n2 (2m + 1)2

=

4m2 + 4m + 1

=

2(2m2 + 2m) + 1

=

But this shows that n2 is also odd, hence ¬Even(n2 ). Thus, by con-

ditional proof, we have established ¬Even(n) ’ ¬Even(n2 ).

By proving the contrapositive, we avoided the need for an indirect proof

inside the conditional proof. This makes the proof easier to understand, and

since the contrapositive is logically equivalent to our original claim, our second

proof could serve as a proof of the original claim as well.

The method of conditional proof is used extensively in everyday reason-

ing. Some years ago Bill was trying to decide whether to take English 301,

Postmodernism. His friend Sarah claimed that if Bill takes Postmodernism,

he will not get into medical school. Sarah™s argument, when challenged by Bill,

took the form of a conditional proof, combined with a proof by cases.

Suppose you take Postmodernism. Then either you will adopt the

postmodern disdain for rationality or you won™t. If you don™t, you will

fail the class, which will lower your GPA so much that you will not get

into medical school. But if you do adopt the postmodern contempt

toward rationality, you won™t be able to pass organic chemistry, and

so will not get into medical school. So in either case, you will not get

into medical school. Hence, if you take Postmodernism, you won™t

get into medical school.

Unfortunately for Bill, he had already succumbed to postmodernism, and

so rejected Sarah™s argument. He went ahead and took the course, failed chem-

istry, and did not get into medical school. He™s now a wealthy lobbyist in

Washington. Sarah is an executive in the computer industry in California.

Section 8.1

202 / The Logic of Conditionals

Proving biconditionals

Not surprisingly, we can also use conditional proof to prove biconditionals,

though we have to work twice as hard. To prove P ” Q by conditional proof,

you need to do two things: assume P and prove Q; then assume Q and prove

P. This gives us both P ’ Q and Q ’ P, whose conjunction is equivalent to

P ” Q.

There is another form of proof involving ” that is common in math-

ematics. Mathematicians are quite fond of ¬nding results which show that

several di¬erent conditions are equivalent. Thus you will ¬nd theorems that

make claims like this: “The following conditions are all equivalent: Q1 , Q2 , Q3 .”

What they mean by this is that all of the following biconditionals hold:

Q1 ” Q2

Q2 ” Q3

Q1 ” Q3

To prove these three biconditionals in the standard way, you would have

to give six conditional proofs, two for each biconditional. But we can cut our

proving a cycle of

conditionals work in half by noting that it su¬ces to prove some cycle of results like the

following:

Q1 ’ Q2

Q2 ’ Q3

Q3 ’ Q1

These would be shown by three conditional proofs, rather than the six that

would otherwise be required. Once we have these, there is no need to prove the

reverse directions, since they follow from the transitivity of ’. For example,

we don™t need to explicitly prove Q2 ’ Q1, the reverse of the ¬rst conditional,

since this follows from Q2 ’ Q3 and Q3 ’ Q1 , our other two conditionals.

When we apply this technique, we don™t have to arrange the cycle in

exactly the order in which the conditions are given. But we do have to make

sure we have a genuine cycle, one that allows us to get from any one of our

conditions to any other.

Let™s give a very simple example. We will prove that the following condi-

tions on a natural number n are all equivalent:

1. n is even

2. n2 is even

3. n2 is divisible by 4.

Proof: Rather than prove all six biconditionals, we prove that (3) ’

(2) ’ (1) ’ (3). Assume (3). Now clearly, if n2 is divisible by 4, then

Chapter 8

Informal methods of proof / 203

it is divisible by 2, so we have (3) ’ (2). Next, we prove (2) ’ (1)

by proving its contrapositive. Thus, assume n is odd and prove n2

is odd. Since n is odd, we can write it in the form 2m + 1. But then

(as we™ve already shown) n2 = 2(2m2 + 2m) + 1 which is also odd.

Finally, let us prove (1) ’ (3). If n is even, it can be expressed as 2m.

Thus, n2 = (2m)2 = 4m2 , which is divisible by 4. This completes

the cycle, showing that the three conditions are indeed equivalent.

When you apply this method, you should look for simple or obvious impli-

cations, like (1) ’ (3) above, or implications that you™ve already established,

like (2) ’ (1) above, and try to build them into your cycle of conditionals.

Remember

1. The method of conditional proof: To prove P ’ Q, assume P and prove

Q.

2. To prove a number of biconditionals, try to arrange them into a cycle

of conditionals.

Exercises

8.1 In the following list we give a number of inference patterns, some of which are valid, some

invalid. For each pattern, decide whether you think it is valid and say so. Later, we will return

to these patterns and ask you to give formal proofs for the valid ones and counterexamples for

the invalid ones. But for now, just assess their validity.

1. A¬rming the Consequent: From A ’ B and B, infer A.

2. Modus Tollens: From A ’ B and ¬B, infer ¬A.

3. Strengthening the Antecedent: From B ’ C, infer (A § B) ’ C.

4. Weakening the Antecedent: From B ’ C, infer (A ∨ B) ’ C.

5. Strengthening the Consequent: From A ’ B, infer A ’ (B § C).

6. Weakening the Consequent: From A ’ B, infer A ’ (B ∨ C).

7. Constructive Dilemma: From A ∨ B, A ’ C, and B ’ D, infer C ∨ D.

8. Transitivity of the Biconditional: From A ” B and B ” C, infer A ” C.

8.2 Open Conditional Sentences. Suppose that the sentences in this ¬le are your premises. Now

‚| consider the ¬ve sentences listed below. Some of these sentences are consequences of these

premises, some are not. For those that are consequences, give informal proofs and turn them

Section 8.1

204 / The Logic of Conditionals

in to your instructor. For those that are not consequences, submit counterexample worlds in

which the premises are true but the conclusion false. Name the counterexamples World 8.2.x,

where x is the number of the sentence.

1. Tet(e)

2. Tet(c) ’ Tet(e)

3. Tet(c) ’ Larger(f, e)

4. Tet(c) ’ LeftOf(c, f)

5. Dodec(e) ’ Smaller(e, f)

The following arguments are all valid. Turn in informal proofs of their validity. You may ¬nd it helpful

to translate the arguments into fol before trying to give proofs, though that™s not required. Explicitly

note any inferences using modus ponens, biconditional elimination, or conditional proof.

8.3 8.4

The unicorn, if it is not mythical, is The unicorn, if horned, is elusive and

a mammal, but if it is mythical, it is dangerous.

immortal. If elusive or mythical, the unicorn is

If the unicorn is either immortal or a rare.

mammal, it is horned. If a mammal, the unicorn is not rare.

The unicorn, if horned, is magical.

The unicorn, if horned, is not a

The unicorn is magical. mammal.

8.5 8.6

The unicorn, if horned, is elusive a is a large tetrahedron or a small

and magical, but if not horned, it is cube.

neither. b is not small.

If the unicorn is not horned, it is not If a is a tetrahedron or a cube, then b

mythical. is large or small.

a is a tetrahedron only if b is medium.

The unicorn is horned if and only if

magical or mythical. a is small and b is large.

8.7 8.8

b is small unless it™s a cube. d is in the same row as a, b or c.

If c is small, then either d or e is too. If d is in the same row as b, then it is

If d is small, then c is not. in the same row as a only if it™s not in

If b is a cube, then e is not small. the same row as c.

d is in the same row as a if and only

If c is small, then so is b.

if it is in the same row as c.

d is in the same row as a if and only

if it is not in the same row as b.

Chapter 8

Informal methods of proof / 205

8.9 a is either a cube, a dodecahedron, or a tetrahedron.

a is small, medium, or large.

a is medium if and only if it™s a dodecahedron.

a is a tetrahedron if and only if it is large.

a is a cube if and only if it™s small.

8.10 Open Between Sentences. Determine whether this set of sentences is satis¬able or not. If it

‚| is, submit a world in which all the sentences are true. If not, give an informal proof that the

sentences are inconsistent. That is, assume all of them and derive a contradiction.

8.11 Analyze the structure of the informal proof in support of the following claim: If the U.S. does

not cut back on its use of oil soon, parts of California will be ¬‚ooded within 50 years. Are there

weak points in the argument? What premises are implicitly assumed in the proof? Are they

plausible?

Proof: Suppose the U.S. does not cut back on its oil use soon. Then it will be unable

to reduce its carbon dioxide emissions substantially in the next few years. But then

the countries of China, India and Brazil will refuse to join in e¬orts to curb carbon

dioxide emissions. As these countries develop without such e¬orts, the emission of

carbon dioxide will get much worse, and so the greenhouse e¬ect will accelerate. As a

result the sea will get warmer, ice will melt, and the sea level will rise. In which case,

low lying coastal areas in California will be subject to ¬‚ooding within 50 years. So if

we do not cut back on our oil use, parts of California will be ¬‚ooded within 50 years.

8.12 Describe an everyday example of reasoning that uses the method of conditional proof.

√

8.13 8.14

Prove: Odd(n + m) ’ Even(n — m). Prove: Irrational(x) ’ Irrational( x).

[Hint: Compare this with Exercise 5.24 [Hint: It is easier to prove the contra-

on page 140.] positive.]

8.15 Prove that the following conditions on the natural number n are all equivalent. Use as few

conditional proofs as possible.

1. n is divisible by 3

2. n2 is divisible by 3

3. n2 is divisible by 9

4. n3 is divisible by 3

5. n3 is divisible by 9

6. n3 is divisible by 27

8.16 Give an informal proof that if R is a tautological consequence of P1 , . . . , Pn and Q, then Q ’ R

is a tautological consequence of P1, . . . , Pn .

Section 8.1

206 / The Logic of Conditionals

Section 8.2

Formal rules of proof for ’ and ”

We now turn to the formal analogues of the methods of proof involving the

conditional and biconditional. Again, we incorporate an introduction and elim-

ination rule for each connective into F.

Rules for the conditional

The rule of modus ponens or conditional elimination is easily formalized. If you

have proven both P ’ Q and P then you can assert Q, citing as justi¬cation

these two earlier steps. Schematically:

Conditional Elimination (’ Elim):

P’Q

.