<<

. 38
( 107 .)



>>

Informal methods of proof / 201



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
.

<<

. 38
( 107 .)



>>