Maggie Johnson                                                                                                Handout #13

                                                                                                            CS103A

Proof Strategies

 

Key Topics

 

            * Where To Start?

            * A Common Methodology: Working Backwards

            * How to End

            * Examples

                                                                                                                                               

 

Where To Start?

 

·        Convince yourself that the conclusion is indeed true by studying the premises and understanding their meaning:

 

§         Make sure you understand all the terms used in the premises and conclusion - get your definitions ready.

 

§         We typically prove general conclusions about a set of objects.   One way to understand what is to be proven is by proving the conclusion for a particular element of the set.  Convince yourself that the conclusion is true for this element (and if you find that it is not, you have just disproven the conclusion).  This will also give you insight into how to do the general proof.

 

§         Try giving an informal proof of the conclusion - explain it to a friend.

 

 

A Common Methodology: Working Backwards

 

Once you have convinced yourself that the conclusion is valid, there are two possible ways to proceed:

 

1.      If the process you went through in understanding the premises and conclusion (working through an example or defining an informal proof) gave you all the details you need, write up a formal (or informal depending on the requirements) proof following the same sequence of steps.  In writing an informal proof, you may leave out obvious steps if you know your audience can fill in those gaps.

 

2.      If you are convinced of the conclusion's validity but are having trouble formalizing it, try working backwards from the conclusion, rather than forward from the premises.  But always be careful that any intermediate goals you define are consequences of the available information.  Think carefully about each step, whether working forwards or backwards.

 

 

How To End

 

Check your work:  Remember that each line in a proof (whether formal or informal) is either a premise, intermediate goal or final goal.  Any goal, intermediate or final, must be justified.  Make certain that the justifications are valid and lead step-by-step to the conclusion.

 

If you are writing a formal proof, the justifications must be explicitly stated.  If you are writing an informal proof, certain obvious justifications can be left out assuming that your audience can still follow the proof.

 

If any line in your proof is not a premise, intermediate goal or final goal (or perhaps a clarifying remark), it probably does not belong in your proof.

 

A well-written proof flows.  The reader should feel as though they are being taken on a ride that takes them directly and inevitably to the desired conclusion without any distractions or irrelevant details.

 

 

Examples

 

1)         Given:   Any integer n

Prove: If n2 is even, then n is even.

 

Convince ourselves it is true: 64 and 8; 16 and 4.

 

Get the definitions ready: the definition of even: 2k for some integer k; the definition of odd: 2k+1 for some integer k.

 

Construct an informal proof: It's easier to work with n than n2, so perhaps a proof by contradiction...

 

Proof:  Suppose there exists an integer n such that n2 is even, but n is not even, that is, n is odd.  Since n is odd, we know that n = 2k+1 for some integer k.  If we square n, we get (2k+1) 2 = 4k2 + 4k + 1 = 2(2k2 + 2k) + 1.  Since k is an integer, 2k2 + 2k is also an integer and can be represented by some integer m.  Therefore, n2 = 2m + 1 which is odd.  This contradicts our premise that n2 is even.  Hence, our original conclusion is true.

 

 

2)         Prove: Ö2 is irrational.

 

Definitions: a real number r is rational if r = a/b for some integers a and b with

b ¹ 0.  A real number that is not rational is irrational.

 

Rational numbers are easier to work than with than irrational because of our definition so this leads to a proof by contradiction.

 

Proof:  Suppose Ö2 is rational.  Then:

 

            Ö2 = a/b for some integers a and b.

 

Without loss of generality, we may assume that a and b have no common divisors, i.e., the fraction is in lowest terms.  We begin by squaring both sides of the above equation:

 

            2 = a2 / b2

 

or equivalently,

 

            a2 =  2b2

 

This implies that a2 is even.  It follows that a is also even, i.e., a = 2k for some integer k.  Substituting this value for a into the above equation, we get:

 

            a2 = (2k) 2 = 4k 2 =  2b2

 

Dividing 4k 2 =  2b2 by 2, we get 2k 2 =  b2  and we see that b2 is also even, and so is b.  Therefore, a and b have a common divisor of 2.  This contradicts the supposition that a and b have no common divisors. Hence, our original conclusion is true.

 

3)                  Given: (A v B) ^ (A v C)

Prove: A

 

4)                  Given: (A v B) ^ (A ^ C)

Prove: A

 

5)                  Given: (A ^ B) v (A ^ C)

Prove: A ^ (B v C)

 

6)                  Given: A v B, C v D, ~C ^ ~B

Prove: A ^ D

 

7)                  Given: (A ^ B) ^ C, ~A

Prove: C