Page
1
(This page has no text content)
Page
2
“mcs” — 2012/6/4 — 15:49 — page i — #1 Eric Lehman Google Inc. F Thomson Leighton Department of Mathematics and the Computer Science and AI Laboratory, Massachussetts Institute of Technology; Akamai Technologies Albert R Meyer Department of Electrical Engineering and Computer Science and the Computer Science and AI Laboratory, Massachussetts Institute of Technology Mathematics for Computer Science revised Monday 4th June, 2012, 15:49 Copyright © , Eric Lehman, F Tom Leighton, Albert R Meyer . All rights reserved.2012
Page
3
“mcs” — 2012/6/4 — 15:49 — page ii — #2
Page
4
“mcs” — 2012/6/4 — 15:49 — page iii — #3 Contents I Proofs 1 What is a Proof? 5 1.1 Propositions 5 1.2 Predicates 8 1.3 The Axiomatic Method 8 1.4 Our Axioms 9 1.5 Proving an Implication 11 1.6 Proving an “If and Only If” 13 1.7 Proof by Cases 15 1.8 Proof by Contradiction 16 1.9 Good Proofs in Practice 17 2 The Well Ordering Principle 25 2.1 Well Ordering Proofs 25 2.2 Template for Well Ordering Proofs 26 2.3 Factoring into Primes 28 2.4 Well Ordered Sets 29 3 Logical Formulas 37 3.1 Propositions from Propositions 38 3.2 Propositional Logic in Computer Programs 41 3.3 Equivalence and Validity 44 3.4 The Algebra of Propositions 46 3.5 The SAT Problem 51 3.6 Predicate Formulas 52 4 Mathematical Data Types 73 4.1 Sets 73 4.2 Sequences 77 4.3 Functions 77 4.4 Binary Relations 80 4.5 Finite Cardinality 84 5 Induction 99 5.1 Ordinary Induction 99 5.2 Strong Induction 108 5.3 Strong Induction vs. Induction vs. Well Ordering 113
Page
5
“mcs” — 2012/6/4 — 15:49 — page iv — #4 Contentsiv 5.4 State Machines 114 6 Recursive Data Types 151 6.1 Recursive Definitions and Structural Induction 151 6.2 Strings of Matched Brackets 155 6.3 Recursive Functions on Nonnegative Integers 158 6.4 Arithmetic Expressions 161 6.5 Induction in Computer Science 166 7 Infinite Sets 179 7.1 Infinite Cardinality 180 7.2 The Halting Problem 184 7.3 The Logic of Sets 188 7.4 Does All This Really Work? 191 8 Number Theory 203 8.1 Divisibility 203 8.2 The Greatest Common Divisor 208 8.3 Prime Mysteries 214 8.4 The Fundamental Theorem of Arithmetic 217 8.5 Alan Turing 219 8.6 Modular Arithmetic 223 8.7 Remainder Arithmetic 225 8.8 Turing’s Code (Version 2.0) 228 8.9 Multiplicative Inverses and Cancelling 230 8.10 Euler’s Theorem 234 8.11 RSA Public Key Encryption 241 8.12 What has SAT got to do with it? 244 II Structures 9 Directed graphs & Partial Orders 273 9.1 Digraphs & Vertex Degrees 275 9.2 Adjacency Matrices 279 9.3 Walk Relations 282 9.4 Directed Acyclic Graphs & Partial Orders 283 9.5 Weak Partial Orders 286 9.6 Representing Partial Orders by Set Containment 288 9.7 Path-Total Orders 289 9.8 Product Orders 290
Page
6
“mcs” — 2012/6/4 — 15:49 — page v — #5 Contentsv 9.9 Scheduling 291 9.10 Equivalence Relations 297 9.11 Summary of Relational Properties 299 10 Communication Networks 325 10.1 Complete Binary Tree 325 10.2 Routing Problems 325 10.3 Network Diameter 326 10.4 Switch Count 327 10.5 Network Latency 328 10.6 Congestion 328 10.7 2-D Array 329 10.8 Butterfly 331 10.9 Beneš Network 333 11 Simple Graphs 345 11.1 Vertex Adjacency and Degrees 345 11.2 Sexual Demographics in America 347 11.3 Some Common Graphs 349 11.4 Isomorphism 351 11.5 Bipartite Graphs & Matchings 353 11.6 The Stable Marriage Problem 358 11.7 Coloring 365 11.8 Getting from u to v in a Graph 370 11.9 Connectivity 371 11.10 Odd Cycles and 2-Colorability 375 11.11 Forests & Trees 376 12 Planar Graphs 413 12.1 Drawing Graphs in the Plane 413 12.2 Definitions of Planar Graphs 413 12.3 Euler’s Formula 424 12.4 Bounding the Number of Edges in a Planar Graph 425 12.5 Returning to K5 and K3;3 426 12.6 Coloring Planar Graphs 427 12.7 Classifying Polyhedra 429 12.8 Another Characterization for Planar Graphs 432
Page
7
“mcs” — 2012/6/4 — 15:49 — page vi — #6 Contentsvi III Counting 13 Sums and Asymptotics 443 13.1 The Value of an Annuity 444 13.2 Sums of Powers 450 13.3 Approximating Sums 452 13.4 Hanging Out Over the Edge 456 13.5 Products 463 13.6 Double Trouble 465 13.7 Asymptotic Notation 468 14 Cardinality Rules 487 14.1 Counting One Thing by Counting Another 487 14.2 Counting Sequences 488 14.3 The Generalized Product Rule 491 14.4 The Division Rule 495 14.5 Counting Subsets 498 14.6 Sequences with Repetitions 500 14.7 Counting Practice: Poker Hands 503 14.8 The Pigeonhole Principle 508 14.9 Inclusion-Exclusion 518 14.10 Combinatorial Proofs 524 15 Generating Functions 559 15.1 Infinite Series 559 15.2 Counting with Generating Functions 560 15.3 Partial Fractions 567 15.4 Solving Linear Recurrences 569 15.5 Formal Power Series 575 IV Probability 16 Events and Probability Spaces 591 16.1 Let’s Make a Deal 591 16.2 The Four Step Method 592 16.3 Strange Dice 601 16.4 Set Theory and Probability 608 16.5 Conditional Probability 614 16.6 Independence 626
Page
8
“mcs” — 2012/6/4 — 15:49 — page vii — #7 Contentsvii 17 Random Variables 659 17.1 Random Variable Examples 659 17.2 Independence 661 17.3 Distribution Functions 662 17.4 Great Expectations 670 17.5 Linearity of Expectation 682 18 Deviation from the Mean 707 18.1 Why the Mean? 707 18.2 Markov’s Theorem 708 18.3 Chebyshev’s Theorem 710 18.4 Properties of Variance 714 18.5 Estimation by Random Sampling 719 18.6 Confidence versus Probability 724 18.7 Sums of Random Variables 725 18.8 Really Great Expectations 735 19 Random Processes 755 19.1 Gamblers’ Ruin 755 19.2 Random Walks on Graphs 764 V Recurrences 20 Recurrences 783 20.1 The Towers of Hanoi 783 20.2 Merge Sort 786 20.3 Linear Recurrences 790 20.4 Divide-and-Conquer Recurrences 797 20.5 A Feel for Recurrences 804 Bibliography 806 Index 808
Page
9
“mcs” — 2012/6/4 — 15:49 — page viii — #8
Page
10
“mcs” — 2012/6/4 — 15:49 — page 1 — #9 I Proofs
Page
11
“mcs” — 2012/6/4 — 15:49 — page 2 — #10
Page
12
“mcs” — 2012/6/4 — 15:49 — page 3 — #11 Introduction This text explains how to use mathematical models and methods to analyze prob- lems that arise in computer science. Proofs play a central role in this work because the authors share a belief with most mathematicians that proofs are essential for genuine understanding. Proofs also play a growing role in computer science; they are used to certify that software and hardware will always behave correctly, some- thing that no amount of testing can do. Simply put, a proof is a method of establishing truth. Like beauty, “truth” some- times depends on the eye of the beholder, and it should not be surprising that what constitutes a proof differs among fields. For example, in the judicial system, legal truth is decided by a jury based on the allowable evidence presented at trial. In the business world, authoritative truth is specified by a trusted person or organization, or maybe just your boss. In fields such as physics or biology, scientific truth1 is confirmed by experiment. In statistics, probable truth is established by statistical analysis of sample data. Philosophical proof involves careful exposition and persuasion typically based on a series of small, plausible arguments. The best example begins with “Cogito ergo sum,” a Latin sentence that translates as “I think, therefore I am.” This phrase comes from the beginning of a 17th century essay by the mathematician/philosopher, René Descartes, and it is one of the most famous quotes in the world: do a web search for it, and you will be flooded with hits. 1Actually, only scientific falsehood can be demonstrated by an experiment—when the experiment fails to behave as predicted. But no amount of experiment can confirm that the next experiment won’t fail. For this reason, scientists rarely speak of truth, but rather of theories that accurately predict past, and anticipated future, experiments.
Page
13
“mcs” — 2012/6/4 — 15:49 — page 4 — #12 Part I Proofs4 Deducing your existence from the fact that you’re thinking about your existence is a pretty cool and persuasive-sounding idea. However, with just a few more lines of argument in this vein, Descartes goes on to conclude that there is an infinitely beneficent God. Whether or not you believe in an infinitely beneficent God, you’ll probably agree that any very short “proof” of God’s infinite beneficence is bound to be far-fetched. So even in masterful hands, this approach is not reliable. Mathematics has its own specific notion of “proof.” Definition. A mathematical proof of a proposition is a chain of logical deductions leading to the proposition from a base set of axioms. The three key ideas in this definition are highlighted: proposition, logical deduc- tion, and axiom. Chapter 1 examines these three ideas along with some basic ways of organizing proofs. Chapter 2 introduces the Well Ordering Principle, a basic method of proof; later, Chapter 5 introduces the closely related proof method of Induction. If you’re going to prove a proposition, you’d better have a precise understand- ing of what the proposition means. To avoid ambiguity and uncertain definitions in ordinary language, mathematicians use language very precisely, and they often express propositions using logical formulas; these are the subject of Chapter 3. The first three Chapters assume the reader is familiar with a few mathematical concepts like sets and functions. Chapters 4 and 7 offer a more careful look at such mathematical data types, examining in particular properties and methods for proving things about infinite sets. Chapter 6 goes on to examine recursively defined data types. Number theory is the study of properties of the integers. This part of the text ends with Chapter 8 on Number theory because there are lots of easy-to-state and interesting-to-prove properties of numbers. This subject was once thought to have few, if any, practical applications, but it has turned out to have multiple applications in Computer Science. For example, most modern data encryption methods are based on Number theory.
Page
14
“mcs” — 2012/6/4 — 15:49 — page 5 — #13 1 What is a Proof? 1.1 Propositions Definition. A proposition is a statement that is either true or false. For example, both of the following statements are propositions. The first is true, and the second is false. Proposition 1.1.1. 2 + 3 = 5. Proposition 1.1.2. 1 + 1 = 3. Being true or false doesn’t sound like much of a limitation, but it does exclude statements such as, “Wherefore art thou Romeo?” and “Give me an A!” It also ex- cludes statements whose truth varies with circumstance such as, “It’s five o’clock,” or “the stock market will rise tomorrow.” Unfortunately it is not always easy to decide if a proposition is true or false: Proposition 1.1.3. For every nonnegative integer, n, the value of n2 C n C 41 is prime. (A prime is an integer greater than 1 that is not divisible by any other integer greater than 1. For example, 2, 3, 5, 7, 11, are the first five primes.) Let’s try some numerical experimentation to check this proposition. Let 1 p.n/ WWD n2 C nC 41: (1.1) We begin with p.0/ D 41 which is prime; then p.1/ D 43; p.2/ D 47; p.3/ D 53; : : : ; p.20/ D 461 are each prime. Hmmm, starts to look like a plausible claim. In fact we can keep checking through n D 39 and confirm that p.39/ D 1601 is prime. But p.40/ D 402 C 40C 41 D 41 41, which is not prime. So it’s not true that the expression is prime for all nonnegative integers. In fact, it’s not hard to show that no polynomial with integer coefficients can map all nonnegative numbers into prime numbers, unless it’s a constant (see Problem 1.6). The point is that in general 1The symbol WWD means “equal by definition.” It’s always ok simply to write “=” instead of WWD, but reminding the reader that an equality holds by definition can be helpful.
Page
15
“mcs” — 2012/6/4 — 15:49 — page 6 — #14 Chapter 1 What is a Proof?6 you can’t check a claim about an infinite set by checking a finite set of its elements, no matter how large the finite set. 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, Propo- sition 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, namely, 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: Proposition 1.1.4. [Euler’s Conjecture] The equation a4 C b4 C c4 D d4 has no solution when a; b; c; d are positive integers. Euler (pronounced “oiler”) conjectured this in 1769. But the proposition 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 ZC 8b 2 ZC 8c 2 ZC 8d 2 ZC: a4 C b4 C c4 ¤ d4: Here, ZC is a symbol for the positive integers. Strings of 8’s like this are usually abbreviated for easier reading: 8a; b; c; d 2 ZC: a4 C b4 C c4 ¤ d4: Proposition 1.1.5. 313.x3 C y3/ D z3 has no solution when x; y; z 2 ZC. This proposition is also false, but the smallest counterexample has more than 1000 digits! It’s worth mentioning a couple of further famous propositions whose proofs were sought for centuries before finally being discovered: Proposition 1.1.6 (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.
Page
16
“mcs” — 2012/6/4 — 15:49 — 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, and these were checked by hand by Haken and his assistants —including 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, and 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.7 (Fermat’s Last Theorem). There are no positive integers x, y, and z such that xn C yn D zn for some integer n > 2. In a book he was reading around 1630, Fermat claimed to have a proof but not enough space in the margin to write it down. Over the years it 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, 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. Proposition 1.1.8 (Goldbach’s Conjecture). 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 1016, but to this day, no one knows whether it’s true or false. 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 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. ISBN 0-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.
Page
17
“mcs” — 2012/6/4 — 15:49 — page 8 — #16 Chapter 1 What is a Proof?8 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 mistakes like the notorious Intel division bug in the 1990’s. 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 is a proposition whose truth depends on the value of one or more vari- ables. Most of the propositions above were defined in terms of predicates. For example, “n is a perfect square” is a predicate whose truth depends on the value of n. The predicate is true for n D 4 since four is a perfect square, but false for n D 5 since five is not 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 name our earlier predicate P : P.n/ WWD “n is a perfect square”: So 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 n2C1, 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 pair of points.) Propositions like these that are simply accepted as true are called axioms.
Page
18
“mcs” — 2012/6/4 — 15:49 — page 9 — #17 1.4. Our Axioms 9 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 axioms Zermelo-Frankel with Choice (ZFC), together with a few logical deduction rules, appear to be sufficient to derive essentially all of mathematics. We’ll examine these in Chapter 7. 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 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.
Page
19
“mcs” — 2012/6/4 — 15:49 — 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. Note that a propositional inference rule is sound precisely when the conjunction (AND) of all its antecedents implies its consequent. 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.
Page
20
“mcs” — 2012/6/4 — 15:49 — 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 C bx C c D 0 and a ¤ 0, then x D b ˙ p b2 4ac =2a: (Goldbach’s Conjecture 1.1.8 rephrased) If n is an even integer greater than 2, then n is a sum of two primes. If 0 x 2, then x3 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.