]> No Title

""mcs“ —2015/5/18 —1:43 — page 11 —#19

1.5. Proving an Implication 11

1.4.2 Patterns of Proof

In principle, a proof can be any sequence of logical deductions from axioms and previously proved statements that concludes with the proposition in question. This freedom in constructing a proof can seem overwhelming at first. How do you even start a proof?

Here's the good news: many proofs follow one of a handful of standard tem‐ plates. Each proof has it own details, of course, but these templates at least provide you with an outline to fill in. We'll go through several of these standard patterns, pointing out the basic idea and common pitfalls and giving some examples. Many of these templates fit together; one may give you a top‐level outline while others help you at the next level of detail. And we'll show you other, more sophisticated proof techniques later on.

The recipes below are very specific at times, telling you exactly which words to write down on your piece of paper. You're certainly free to say things your own way instead; we're just giving you something you could say so that you're never at a complete loss.

1.5 Proving an Implication

Propositions of the form ""If P, then Q“ are called implications. This implication is often rephrased as P IMPLIES Q

Here are some examples:

(Quadratic Formula) If ax2+bx+c=0 and a0, then


(Goldbach's Conjecture rephrased) If n is an even integer greater than 2, then n is asum of two primes.

If 0<x<2, then -x3+4x+1>0.

There are a couple of standard methods for proving an implication.

1.5.1 Method#1

In order to prove that P IMPLIES Q: 1. Write, ""Assume P

2. Show that Q logically follows.