“mcs”一2017/6/5一19：42一page10一#18 10 Chapter I What is a Proof? 1.4.1 Logical Deductions Logical deductions,or inference rules,are used to prove new propositions using previously proved ones. A fundamental inference rule is modus ponens.This rule says that a proof of P together with a proof that P IMPLIES O is a proof of O. Inference rules are sometimes written in a funny notation.For example,modus ponens is written: Rule. P,P IMPLIES O 0 When the statements above the line,called the antecedents,are proved,then we can consider the statement below the line,called the conclusion or consequent,to also be proved. A key requirement of an inference rule is that it must be sound:an assignment of truth values to the letters P,,...that makes all the antecedents true must also make the consequent true.So if we start off with true axioms and apply sound inference rules,everything we prove will also be true. There are many other natural,sound inference rules,for example: Rule. P IMPLIES O,O IMPLIES R P IMPLIES R Rule. NOT(P)IMPLIES NOT(O) O IMPLIES P On the other hand, Non-Rule. NOT(P)IMPLIES NOT(O) P IMPLIES O is not sound:if P is assigned T and O is assigned F,then the antecedent is true and the consequent is not. As with axioms,we will not be too formal about the set of legal inference rules. Each step in a proof should be clear and"logical";in particular,you should state what previously proved facts are used to derive each new conclusion
“mcs” — 2017/6/5 — 19:42 — page 10 — #18 Chapter 1 What is a Proof?10 1.4.1 Logical Deductions Logical deductions, or inference rules, are used to prove new propositions using previously proved ones. A fundamental inference rule is modus ponens. This rule says that a proof of P together with a proof that P IMPLIES Q is a proof of Q. Inference rules are sometimes written in a funny notation. For example, modus ponens is written: Rule. P; P IMPLIES Q Q When the statements above the line, called the antecedents, are proved, then we can consider the statement below the line, called the conclusion or consequent, to also be proved. A key requirement of an inference rule is that it must be sound: an assignment of truth values to the letters P, Q, . . . , that makes all the antecedents true must also make the consequent true. So if we start off with true axioms and apply sound inference rules, everything we prove will also be true. There are many other natural, sound inference rules, for example: Rule. P IMPLIES Q; Q IMPLIES R P IMPLIES R Rule. NOT.P / IMPLIES NOT.Q/ Q IMPLIES P On the other hand, Non-Rule. NOT.P / IMPLIES NOT.Q/ P IMPLIES Q is not sound: if P is assigned T and Q is assigned F, then the antecedent is true and the consequent is not. As with axioms, we will not be too formal about the set of legal inference rules. Each step in a proof should be clear and “logical”; in particular, you should state what previously proved facts are used to derive each new conclusion
“mcs”一2017/6/5一19：42一page11一#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 O"are called implications.This implication is often rephrased as“P IMPLIES O.” Here are some examples: ·(Quadratic Formula)Ifax2+bx+c=0anda≠0，then x=（-b±vb2-4ac/2a. .(Goldbach's Conjecture 1.1.6 rephrased)If n is an even integer greater than 2,then n is a sum of two primes. ·f0≤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 O: l.Write,“Assume P” 2.Show that O logically follows
“mcs” — 2017/6/5 — 19:42 — 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 templates. 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 C bx C c D 0 and a ¤ 0, then x D b ˙ p b 2 4ac =2a: (Goldbach’s Conjecture 1.1.6 rephrased) If n is an even integer greater than 2, then n is a sum of two primes. If 0 x 2, then x 3 C 4x C 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
“mcs”一2017/6/5一19：42一page12一#20 12 Chapter I What is a Proof? Example Theorem1.5.l.If0≤x≤2，then-x3+4x+1>0. Before we write a proof of this theorem,we have to do some scratchwork to figure out why it is true. The inequality certainly holds forx =0;then the left side is equal to 1 and 1>0.As x grows,the 4x term(which is positive)initially seems to have greater magnitude than-x3(which is negative).For example,when x=1,we have 4x =4,but-x3 =-1 only.In fact,it looks like-x3 doesn't begin to dominate until x>2.So it seems the-x3+4x part should be nonnegative for all x between 0 and 2,which would imply thatx3+4x+1 is positive. So far,so good.But we still have to replace all those "seems like"phrases with solid,logical arguments.We can get a better handle on the critical-x3+4x part by factoring it,which is not too hard: -x3+4x=x(2-x)(2+x) Aha!For x between 0 and 2,all of the terms on the right side are nonnegative.And a product of nonnegative terms is also nonnegative.Let's organize this blizzard of observations into a clean proof. Proof.Assume 0<x<2.Then x,2-x and 2+x are all nonnegative.Therefore, the product of these terms is also nonnegative.Adding 1 to this product gives a positive number,so: x(2-x)(2+x)+1>0 Multiplying out on the left side proves that -x3+4x+1>0 as claimed. There are a couple points here that apply to all proofs: You'll often need to do some scratchwork while you're trying to figure out the logical steps of a proof.Your scratchwork can be as disorganized as you like-full of dead-ends,strange diagrams,obscene words,whatever.But keep your scratchwork separate from your final proof,which should be clear and concise Proofs typically begin with the word"Proof"and end with some sort of de- limiter like or"QED."The only purpose for these conventions is to clarify where proofs begin and end
“mcs” — 2017/6/5 — 19:42 — page 12 — #20 Chapter 1 What is a Proof?12 Example Theorem 1.5.1. If 0 x 2, then x 3 C 4x C 1 > 0. Before we write a proof of this theorem, we have to do some scratchwork to figure out why it is true. The inequality certainly holds for x D 0; then the left side is equal to 1 and 1 > 0. As x grows, the 4x term (which is positive) initially seems to have greater magnitude than x 3 (which is negative). For example, when x D 1, we have 4x D 4, but x 3 D 1 only. In fact, it looks like x 3 doesn’t begin to dominate until x > 2. So it seems the x 3 C4x part should be nonnegative for all x between 0 and 2, which would imply that x 3 C 4x C 1 is positive. So far, so good. But we still have to replace all those “seems like” phrases with solid, logical arguments. We can get a better handle on the critical x 3 C 4x part by factoring it, which is not too hard: x 3 C 4x D x.2 x/.2 C x/ Aha! For x between 0 and 2, all of the terms on the right side are nonnegative. And a product of nonnegative terms is also nonnegative. Let’s organize this blizzard of observations into a clean proof. Proof. Assume 0 x 2. Then x, 2x and 2Cx are all nonnegative. Therefore, the product of these terms is also nonnegative. Adding 1 to this product gives a positive number, so: x.2 x/.2 C x/ C 1 > 0 Multiplying out on the left side proves that x 3 C 4x C 1 > 0 as claimed. There are a couple points here that apply to all proofs: You’ll often need to do some scratchwork while you’re trying to figure out the logical steps of a proof. Your scratchwork can be as disorganized as you like—full of dead-ends, strange diagrams, obscene words, whatever. But keep your scratchwork separate from your final proof, which should be clear and concise. Proofs typically begin with the word “Proof” and end with some sort of delimiter like or “QED.” The only purpose for these conventions is to clarify where proofs begin and end.
“mcs”一2017/6/5一19：42一page13一#21 1.6.Proving an "If and Only If" 13 1.5.2 Method #2-Prove the Contrapositive An implication ("P IMPLIES O")is logically equivalent to its contrapositive NOT(O)IMPLIES NOT(P). Proving one is as good as proving the other,and proving the contrapositive is some- times easier than proving the original statement.If so,then you can proceed as follows: 1.Write,"We prove the contrapositive:"and then state the contrapositive. 2.Proceed as in Method #1. Example Theorem 1.5.2.If r is irrational,then r is also irrational. A number is rational when it equals a quotient of integers-that is,if it equals m/n for some integers m and n.If it's not rational,then it's called irrational.So we must show that if r is not a ratio of integers,then r is also not a ratio of integers.That's pretty convoluted!We can eliminate both not's and simplify the proof by using the contrapositive instead. Proof.We prove the contrapositive:if r is rational,then r is rational. Assume that r is rational.Then there exist integers m and n such that: VF=m n Squaring both sides gives: m2 r= n2 Since m2 and n2 are integers,r is also rational. 1.6 Proving an "If and Only If" Many mathematical theorems assert that two statements are logically equivalent; that is,one holds if and only if the other does.Here is an example that has been known for several thousand years: Two triangles have the same side lengths if and only if two side lengths and the angle between those sides are the same. The phrase"if and only if"comes up so often that it is often abbreviated "iff
“mcs” — 2017/6/5 — 19:42 — page 13 — #21 1.6. Proving an “If and Only If” 13 1.5.2 Method #2 - Prove the Contrapositive An implication (“P IMPLIES Q”) is logically equivalent to its contrapositive NOT.Q/ IMPLIES NOT.P / : Proving one is as good as proving the other, and proving the contrapositive is sometimes easier than proving the original statement. If so, then you can proceed as follows: 1. Write, “We prove the contrapositive:” and then state the contrapositive. 2. Proceed as in Method #1. Example Theorem 1.5.2. If r is irrational, then p r is also irrational. A number is rational when it equals a quotient of integers —that is, if it equals m=n for some integers m and n. If it’s not rational, then it’s called irrational. So we must show that if r is not a ratio of integers, then p r is also not a ratio of integers. That’s pretty convoluted! We can eliminate both not’s and simplify the proof by using the contrapositive instead. Proof. We prove the contrapositive: if p r is rational, then r is rational. Assume that p r is rational. Then there exist integers m and n such that: p r D m n Squaring both sides gives: r D m2 n 2 Since m2 and n 2 are integers, r is also rational. 1.6 Proving an “If and Only If” Many mathematical theorems assert that two statements are logically equivalent; that is, one holds if and only if the other does. Here is an example that has been known for several thousand years: Two triangles have the same side lengths if and only if two side lengths and the angle between those sides are the same. The phrase “if and only if” comes up so often that it is often abbreviated “iff
“mcs”一2017/6/5一19：42一page14一#22 14 Chapter I What is a Proof? 1.6.1 Method #1:Prove Each Statement Implies the Other The statement“P IFF O”is equivalent to the two statements“P IMPLIES O”and “O IMPLIES P.”So you can prove an“iff"by proving two implications: 1.Write,"We prove P implies O and vice-versa." 2.Write,"First,we show P implies O."Do this by one of the methods in Section 1.5. 3.Write,"Now,we show o implies P"Again,do this by one of the methods in Section 1.5. 1.6.2 Method #2:Construct a Chain of Iffs In order to prove that P is true iff O is true: 1.Write,"We construct a chain of if-and-only-if implications." 2.Prove p is equivalent to a second statement which is equivalent to a third statement and so forth until you reach O. This method sometimes requires more ingenuity than the first,but the result can be a short,elegant proof. Example The standard deviation of a sequence of values x1,x2.....xn is defined to be: (x1-)2+(x2-0)2+…+(xn-4)2 (1.3) where u is the average or mean of the values: u=1+2十…+xn 之 Theorem 1.6.1.The standard deviation of a sequence of values x1,...,xn is zero iff all the values are equal to the mean. For example,the standard deviation of test scores is zero if and only if everyone scored exactly the class average. Proof.We construct a chain of"iff"implications,starting with the statement that the standard deviation(1.3)is zero: (x1-0)2+(x2-4)2+…+(m-0)2 三0. (1.4)
“mcs” — 2017/6/5 — 19:42 — page 14 — #22 Chapter 1 What is a Proof?14 1.6.1 Method #1: Prove Each Statement Implies the Other The statement “P IFF Q” is equivalent to the two statements “P IMPLIES Q” and “Q IMPLIES P.” So you can prove an “iff” by proving two implications: 1. Write, “We prove P implies Q and vice-versa.” 2. Write, “First, we show P implies Q.” Do this by one of the methods in Section 1.5. 3. Write, “Now, we show Q implies P.” Again, do this by one of the methods in Section 1.5. 1.6.2 Method #2: Construct a Chain of Iffs In order to prove that P is true iff Q is true: 1. Write, “We construct a chain of if-and-only-if implications.” 2. Prove P is equivalent to a second statement which is equivalent to a third statement and so forth until you reach Q. This method sometimes requires more ingenuity than the first, but the result can be a short, elegant proof. Example The standard deviation of a sequence of values x1; x2; : : : ; xn is defined to be: s .x1 /2 C .x2 /2 C C .xn /2 n (1.3) where is the average or mean of the values: WWD x1 C x2 C C xn n Theorem 1.6.1. The standard deviation of a sequence of values x1; : : : ; xn is zero iff all the values are equal to the mean. For example, the standard deviation of test scores is zero if and only if everyone scored exactly the class average. Proof. We construct a chain of “iff” implications, starting with the statement that the standard deviation (1.3) is zero: s .x1 /2 C .x2 /2 C C .xn /2 n D 0: (1.4)