信息安全专业参考书籍：《Mathematics for Computer Science》计算机科学数学（revised Monday 5th June, 2017，Eric Lehman、F Thomson Leighton、Albert R Meyer）.pdf_P11-P15

“mcs”-2017/6/5一19：42一page6一#14 6 Chapter I What is a Proof? nonnegative numbers into prime numbers,unless it's a constant(see Problem 1.26). But this example highlights the point that,in general,you can't check a claim about an infinite set by checking a finite sample of its elements,no matter how large the sample. By the way,propositions like this about all numbers or all items of some kind are so common that there is a special notation for them.With this notation,Claim 1.1.3 would be Vn∈N.p(n)is prime. (1.2) Here the symbol V is read"for all."The symbol N stands for the set of nonnegative integers:0,1,2,3,...(ask your instructor for the complete list).The symbol "e" is read as“is a member of,”or“belongs to,.”or simply as“isin”The period after the N is just a separator between phrases. Here are two even more extreme examples: Conjecture.[Euler]The equation a4+b4+c4=d4 has no solution when a,b,c.d are positive integers. Euler (pronounced "oiler")conjectured this in 1769.But the conjecture was proved false 218 years later by Noam Elkies at a liberal arts school up Mass Ave. The solution he found was a 95800,b=217519,c =414560,d 422481. In logical notation,Euler's Conjecture could be written, va∈z+vbez+c∈z+Vd∈z+.a4+b4+c4≠d4 Here,Z is a symbol for the positive integers.Strings of V's like this are usually abbreviated for easier reading: a,b,c,d∈Z+.a4+b4+c4≠d4. Here's another claim which would be hard to falsify by sampling:the smallest possible x.y,z that satisfy the equality each have more than 1000 digits! False Claim.313(x3 +y3)=z3 has no solution when x,y,z Z. It's worth mentioning a couple of further famous propositions whose proofs were sought for centuries before finally being discovered: Proposition 1.1.4 (Four Color Theorem).Every map can be colored with 4 colors so that adjacent regions have different colors. 2Two regions are adjacent only when they share a boundary segment of positive length.They are not considered to be adjacent if their boundaries meet only at a few points

“mcs” — 2017/6/5 — 19:42 — page 6 — #14 Chapter 1 What is a Proof?6 nonnegative numbers into prime numbers, unless it’s a constant (see Problem 1.26). But this example highlights the point that, in general, you can’t check a claim about an infinite set by checking a finite sample of its elements, no matter how large the sample. By the way, propositions like this about all numbers or all items of some kind are so common that there is a special notation for them. With this notation, Claim 1.1.3 would be 8n 2 N: p.n/ is prime: (1.2) Here the symbol 8 is read “for all.” The symbol N stands for the set of nonnegative integers: 0, 1, 2, 3, . . . (ask your instructor for the complete list). The symbol “2” is read as “is a member of,” or “belongs to,” or simply as “is in.” The period after the N is just a separator between phrases. Here are two even more extreme examples: Conjecture. [Euler] The equation a 4 C b 4 C c 4 D d 4 has no solution when a; b; c; d are positive integers. Euler (pronounced “oiler”) conjectured this in 1769. But the conjecture was proved false 218 years later by Noam Elkies at a liberal arts school up Mass Ave. The solution he found was a D 95800; b D 217519; c D 414560; d D 422481. In logical notation, Euler’s Conjecture could be written, 8a 2 Z C 8b 2 Z C 8c 2 Z C 8d 2 Z C: a4 C b 4 C c 4 ¤ d 4 : Here, Z C is a symbol for the positive integers. Strings of 8’s like this are usually abbreviated for easier reading: 8a; b; c; d 2 Z C: a4 C b 4 C c 4 ¤ d 4 : Here’s another claim which would be hard to falsify by sampling: the smallest possible x; y; z that satisfy the equality each have more than 1000 digits! False Claim. 313.x3 C y 3 / D z 3 has no solution when x; y; z 2 Z C. It’s worth mentioning a couple of further famous propositions whose proofs were sought for centuries before finally being discovered: Proposition 1.1.4 (Four Color Theorem). Every map can be colored with 4 colors so that adjacent2 regions have different colors. 2Two regions are adjacent only when they share a boundary segment of positive length. They are not considered to be adjacent if their boundaries meet only at a few points

“mcs”-2017/6/5一19：42一page7-#15 1.1.Propositions 1 Several incorrect proofs of this theorem have been published,including one that stood for 10 years in the late 19th century before its mistake was found.A laborious proof was finally found in 1976 by mathematicians Appel and Haken,who used a complex computer program to categorize the four-colorable maps.The program left a few thousand maps uncategorized,which were checked by hand by Haken and his assistants-among them his 15-year-old daughter. There was reason to doubt whether this was a legitimate proof-the proof was too big to be checked without a computer.No one could guarantee that the com- puter calculated correctly,nor was anyone enthusiastic about exerting the effort to recheck the four-colorings of thousands of maps that were done by hand.Two decades later a mostly intelligible proof of the Four Color Theorem was found, though a computer is still needed to check four-colorability of several hundred spe- cial maps.3 Proposition 1.1.5 (Fermat's Last Theorem).There are no positive integers x,y and z such that x”+yn=zm for some integer n >2. In a book he was reading around 1630,Fermat claimed to have a proof for this proposition,but not enough space in the margin to write it down.Over the years, the Theorem was proved to hold for all n up to 4,000,000,but we've seen that this shouldn't necessarily inspire confidence that it holds for all n.There is,after all, a clear resemblance between Fermat's Last Theorem and Euler's false Conjecture. Finally,in 1994,British mathematician Andrew Wiles gave a proof,after seven years of working in secrecy and isolation in his attic.His proof did not fit in any margin.4 Finally,let's mention another simply stated proposition whose truth remains un- known. Conjecture 1.1.6 (Goldbach).Every even integer greater than 2 is the sum of two primes. Goldbach's Conjecture dates back to 1742.It is known to hold for all numbers up to 1018,but to this day,no one knows whether it's true or false. 3The story of the proof of the Four Color Theorem is told in a well-reviewed popular(non- technical)book:"Four Colors Suffice.How the Map Problem was Solved."Robin Wilson.Princeton Univ.Press,2003,276pp.ISBN0-691-11533-8. 4In fact,Wiles'original proof was wrong.but he and several collaborators used his ideas to arrive at a correct proof a year later.This story is the subject of the popular book,Fermat's Enigma by Simon Singh,Walker Company.November,1997

“mcs” — 2017/6/5 — 19:42 — page 7 — #15 1.1. Propositions 7 Several incorrect proofs of this theorem have been published, including one that stood for 10 years in the late 19th century before its mistake was found. A laborious proof was finally found in 1976 by mathematicians Appel and Haken, who used a complex computer program to categorize the four-colorable maps. The program left a few thousand maps uncategorized, which were checked by hand by Haken and his assistants—among them his 15-year-old daughter. There was reason to doubt whether this was a legitimate proof—the proof was too big to be checked without a computer. No one could guarantee that the computer calculated correctly, nor was anyone enthusiastic about exerting the effort to recheck the four-colorings of thousands of maps that were done by hand. Two decades later a mostly intelligible proof of the Four Color Theorem was found, though a computer is still needed to check four-colorability of several hundred special maps.3 Proposition 1.1.5 (Fermat’s Last Theorem). There are no positive integers x, y and z such that x n C y n D z n for some integer n > 2. In a book he was reading around 1630, Fermat claimed to have a proof for this proposition, but not enough space in the margin to write it down. Over the years, the Theorem was proved to hold for all n up to 4,000,000, but we’ve seen that this shouldn’t necessarily inspire confidence that it holds for all n. There is, after all, a clear resemblance between Fermat’s Last Theorem and Euler’s false Conjecture. Finally, in 1994, British mathematician Andrew Wiles gave a proof, after seven years of working in secrecy and isolation in his attic. His proof did not fit in any margin.4 Finally, let’s mention another simply stated proposition whose truth remains unknown. Conjecture 1.1.6 (Goldbach). Every even integer greater than 2 is the sum of two primes. Goldbach’s Conjecture dates back to 1742. It is known to hold for all numbers up to 1018, but to this day, no one knows whether it’s true or false. 3The story of the proof of the Four Color Theorem is told in a well-reviewed popular (nontechnical) book: “Four Colors Suffice. How the Map Problem was Solved.” Robin Wilson. Princeton Univ. Press, 2003, 276pp. ISBN 0-691-11533-8. 4 In fact, Wiles’ original proof was wrong, but he and several collaborators used his ideas to arrive at a correct proof a year later. This story is the subject of the popular book, Fermat’s Enigma by Simon Singh, Walker & Company, November, 1997

“mcs”-2017/6/5一19：42一page8一#16 Chapter I What is a Proof? For a computer scientist,some of the most important things to prove are the correctness of programs and systems-whether a program or system does what it's supposed to.Programs are notoriously buggy,and there's a growing community of researchers and practitioners trying to find ways to prove program correctness. These efforts have been successful enough in the case of CPU chips that they are now routinely used by leading chip manufacturers to prove chip correctness and avoid some notorious past mistakes. Developing mathematical methods to verify programs and systems remains an active research area.We'll illustrate some of these methods in Chapter 5. 1.2 Predicates A predicate can be understood as a proposition whose truth depends on the value of one or more variables.So"n is a perfect square"describes a predicate,since you can't say if it's true or false until you know what the value of the variable n happens to be.Once you know,for example,that n equals 4,the predicate becomes the true proposition"4 is a perfect square".Remember,nothing says that the proposition has to be true:if the value of n were 5,you would get the false proposition"5 is a perfect square.” Like other propositions,predicates are often named with a letter.Furthermore,a function-like notation is used to denote a predicate supplied with specific variable values.For example,we might use the name"P"for predicate above: P(n):=“n is a perfect square”, and repeat the remarks above by asserting that P(4)is true,and P(5)is false. This notation for predicates is confusingly similar to ordinary function notation. If P is a predicate,then P(n)is either true or false,depending on the value of n. On the other hand,if p is an ordinary function,like n2+1,then p(n)is a numerical quantity.Don't confuse these two! 1.3 The Axiomatic Method The standard procedure for establishing truth in mathematics was invented by Eu- clid,a mathematician working in Alexandria,Egypt around 300 BC.His idea was to begin with five assumptions about geometry,which seemed undeniable based on direct experience.(For example,"There is a straight line segment between every

“mcs” — 2017/6/5 — 19:42 — page 8 — #16 Chapter 1 What is a Proof?8 For a computer scientist, some of the most important things to prove are the correctness of programs and systems—whether a program or system does what it’s supposed to. Programs are notoriously buggy, and there’s a growing community of researchers and practitioners trying to find ways to prove program correctness. These efforts have been successful enough in the case of CPU chips that they are now routinely used by leading chip manufacturers to prove chip correctness and avoid some notorious past mistakes. Developing mathematical methods to verify programs and systems remains an active research area. We’ll illustrate some of these methods in Chapter 5. 1.2 Predicates A predicate can be understood as a proposition whose truth depends on the value of one or more variables. So “n is a perfect square” describes a predicate, since you can’t say if it’s true or false until you know what the value of the variable n happens to be. Once you know, for example, that n equals 4, the predicate becomes the true proposition “4 is a perfect square”. Remember, nothing says that the proposition has to be true: if the value of n were 5, you would get the false proposition “5 is a perfect square.” Like other propositions, predicates are often named with a letter. Furthermore, a function-like notation is used to denote a predicate supplied with specific variable values. For example, we might use the name “P” for predicate above: P .n/ WWD “n is a perfect square”; and repeat the remarks above by asserting that P .4/ is true, and P .5/ is false. This notation for predicates is confusingly similar to ordinary function notation. If P is a predicate, then P .n/ is either true or false, depending on the value of n. On the other hand, if p is an ordinary function, like n 2C1, then p.n/ is a numerical quantity. Don’t confuse these two! 1.3 The Axiomatic Method The standard procedure for establishing truth in mathematics was invented by Euclid, a mathematician working in Alexandria, Egypt around 300 BC. His idea was to begin with five assumptions about geometry, which seemed undeniable based on direct experience. (For example, “There is a straight line segment between every

“mcs”-2017/6/5一19：42一page9-#17 1.4.Our Axioms 9 pair of points".)Propositions like these that are simply accepted as true are called axioms. Starting from these axioms,Euclid established the truth of many additional propo- sitions by providing"proofs."A proof is a sequence of logical deductions from axioms and previously proved statements that concludes with the proposition in question.You probably wrote many proofs in high school geometry class,and you'll see a lot more in this text. There are several common terms for a proposition that has been proved.The different terms hint at the role of the proposition within a larger body of work. .Important true propositions are called theorems. .A lemma is a preliminary proposition useful for proving later propositions. .A corollary is a proposition that follows in just a few logical steps from a theorem. These definitions are not precise.In fact,sometimes a good lemma turns out to be far more important than the theorem it was originally used to prove. Euclid's axiom-and-proof approach,now called the axiomatic method,remains the foundation for mathematics today.In fact,just a handful of axioms,called the Zermelo-Fraenkel with Choice axioms(ZFC),together with a few logical deduction rules,appear to be sufficient to derive essentially all of mathematics.We'll examine these in Chapter 8. 1.4 Our Axioms The ZFC axioms are important in studying and justifying the foundations of math- ematics,but for practical purposes,they are much too primitive.Proving theorems in ZFC is a little like writing programs in byte code instead of a full-fledged pro- gramming language-by one reckoning,a formal proof in ZFC that 2+2 =4 requires more than 20,000 steps!So instead of starting with ZFC,we're going to take a huge set of axioms as our foundation:we'll accept all familiar facts from high school math. This will give us a quick launch,but you may find this imprecise specification of the axioms troubling at times.For example,in the midst of a proof,you may start to wonder,"Must I prove this little fact or can I take it as an axiom?"There really is no absolute answer,since what's reasonable to assume and what requires proof depends on the circumstances and the audience.A good general guideline is simply to be up front about what you're assuming

“mcs” — 2017/6/5 — 19:42 — page 9 — #17 1.4. Our Axioms 9 pair of points”.) Propositions like these that are simply accepted as true are called axioms. Starting from these axioms, Euclid established the truth of many additional propositions by providing “proofs.” A proof is a sequence of logical deductions from axioms and previously proved statements that concludes with the proposition in question. You probably wrote many proofs in high school geometry class, and you’ll see a lot more in this text. There are several common terms for a proposition that has been proved. The different terms hint at the role of the proposition within a larger body of work. Important true propositions are called theorems. A lemma is a preliminary proposition useful for proving later propositions. A corollary is a proposition that follows in just a few logical steps from a theorem. These definitions are not precise. In fact, sometimes a good lemma turns out to be far more important than the theorem it was originally used to prove. Euclid’s axiom-and-proof approach, now called the axiomatic method, remains the foundation for mathematics today. In fact, just a handful of axioms, called the Zermelo-Fraenkel with Choice axioms (ZFC), together with a few logical deduction rules, appear to be sufficient to derive essentially all of mathematics. We’ll examine these in Chapter 8. 1.4 Our Axioms The ZFC axioms are important in studying and justifying the foundations of mathematics, but for practical purposes, they are much too primitive. Proving theorems in ZFC is a little like writing programs in byte code instead of a full-fledged programming language—by one reckoning, a formal proof in ZFC that 2 C 2 D 4 requires more than 20,000 steps! So instead of starting with ZFC, we’re going to take a huge set of axioms as our foundation: we’ll accept all familiar facts from high school math. This will give us a quick launch, but you may find this imprecise specification of the axioms troubling at times. For example, in the midst of a proof, you may start to wonder, “Must I prove this little fact or can I take it as an axiom?” There really is no absolute answer, since what’s reasonable to assume and what requires proof depends on the circumstances and the audience. A good general guideline is simply to be up front about what you’re assuming