“mcs”一2018/6/6一13：43一page i一#1 Mathematics for Computer Science revised Wednesday 6th June,2018,13:43 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 2018.Eric Lehman,F Tom Leighton.Albert R Meyer.This work is available under the terms of the Creative Commons Attribution-ShareAlike 3.0 license
“mcs” — 2018/6/6 — 13:43 — page i — #1 Mathematics for Computer Science revised Wednesday 6th June, 2018, 13:43 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 2018, Eric Lehman, F Tom Leighton, Albert R Meyer. This work is available under the terms of the Creative Commons Attribution-ShareAlike 3.0 license
“mcs”一2018/6/6一13：43一page ifⅲi一#3 Contents Proofs Introduction 3 0.1 References 4 1 What is a Proof?5 1.1 Propositions 5 P 1.2 Predicates 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'”l3 1.7 Proof by Cases 15 1.8 Proof by Contradiction 16 1.9 Good Proofs in Practice 17 1.10 References 19 2 The Well Ordering Principle 29 2.1 Well Ordering Proofs 29 2.2 Template for WOP Proofs 30 2.3 Factoring into Primes 32 2.4 Well Ordered Sets 33 3 Logical Formulas 47 3.1 Propositions from Propositions 48 3.2 Propositional Logic in Computer Programs 52 3.3 Equivalence and Validity 54 3.4 The Algebra of Propositions 57 3.5 The SAT Problem 62 3.6 Predicate Formulas 63 3.7 References 68 4 Mathematical Data Types 103 4.1Sets103 4.2 Sequences 108 4.3 Functions 109 4.4 Binary Relations 111 4.5 Finite Cardinality 115
“mcs” — 2018/6/6 — 13:43 — page iii — #3 Contents I Proofs Introduction 3 0.1 References 4 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 1.10 References 19 2 The Well Ordering Principle 29 2.1 Well Ordering Proofs 29 2.2 Template for WOP Proofs 30 2.3 Factoring into Primes 32 2.4 Well Ordered Sets 33 3 Logical Formulas 47 3.1 Propositions from Propositions 48 3.2 Propositional Logic in Computer Programs 52 3.3 Equivalence and Validity 54 3.4 The Algebra of Propositions 57 3.5 The SAT Problem 62 3.6 Predicate Formulas 63 3.7 References 68 4 Mathematical Data Types 103 4.1 Sets 103 4.2 Sequences 108 4.3 Functions 109 4.4 Binary Relations 111 4.5 Finite Cardinality 115
“mcs”一2018/6/6一13：43一page iv一#4 公 Contents 5 Induction 137 5.1 Ordinary Induction 137 5.2 Strong Induction 146 5.3 Strong Induction vs.Induction vs.Well Ordering 153 6 State Machines 173 6.1 States and Transitions 173 6.2 The Invariant Principle 174 6.3 Partial Correctness Termination 182 6.4 The Stable Marriage Problem 187 7 Recursive Data Types 217 7.1 Recursive Definitions and Structural Induction 217 7.2 Strings of Matched Brackets 221 7.3 Recursive Functions on Nonnegative Integers 225 7.4 Arithmetic Expressions 227 7.5 Games as a Recursive Data Type 232 7.6 Search Trees 238 7.7 Induction in Computer Science 257 8 Infinite Sets 295 8.1 Infinite Cardinality 296 8.2 The Halting Problem 305 8.3 The Logic of Sets 309 8.4 Does All This Really Work?314 II Structures Introduction 339 9 Number Theory 341 9.1 Divisibility 341 9.2 The Greatest Common Divisor 346 9.3 Prime Mysteries 353 9.4 The Fundamental Theorem of Arithmetic 356 9.5 Alan Turing 358 9.6 Modular Arithmetic 362 9.7 Remainder Arithmetic 364 9.8 Turing's Code (Version 2.0)367 9.9 Multiplicative Inverses and Cancelling 369 9.10 Euler's Theorem 373
“mcs” — 2018/6/6 — 13:43 — page iv — #4 Contentsiv 5 Induction 137 5.1 Ordinary Induction 137 5.2 Strong Induction 146 5.3 Strong Induction vs. Induction vs. Well Ordering 153 6 State Machines 173 6.1 States and Transitions 173 6.2 The Invariant Principle 174 6.3 Partial Correctness & Termination 182 6.4 The Stable Marriage Problem 187 7 Recursive Data Types 217 7.1 Recursive Definitions and Structural Induction 217 7.2 Strings of Matched Brackets 221 7.3 Recursive Functions on Nonnegative Integers 225 7.4 Arithmetic Expressions 227 7.5 Games as a Recursive Data Type 232 7.6 Search Trees 238 7.7 Induction in Computer Science 257 8 Infinite Sets 295 8.1 Infinite Cardinality 296 8.2 The Halting Problem 305 8.3 The Logic of Sets 309 8.4 Does All This Really Work? 314 II Structures Introduction 339 9 Number Theory 341 9.1 Divisibility 341 9.2 The Greatest Common Divisor 346 9.3 Prime Mysteries 353 9.4 The Fundamental Theorem of Arithmetic 356 9.5 Alan Turing 358 9.6 Modular Arithmetic 362 9.7 Remainder Arithmetic 364 9.8 Turing’s Code (Version 2.0) 367 9.9 Multiplicative Inverses and Cancelling 369 9.10 Euler’s Theorem 373
“mcs”一2018/6/6一13：43-page v一#5 Contents 9.11 RSA Public Key Encryption 378 9.12 What has SAT got to do with it?381 9.13 References 382 10 Directed graphs Partial Orders 421 10.1 Vertex Degrees 423 10.2 Walks and Paths 424 10.3 Adjacency Matrices 427 10.4 Walk Relations 430 10.5 Directed Acyclic Graphs Scheduling 431 10.6 Partial Orders 439 10.7 Representing Partial Orders by Set Containment 442 10.8 Linear Orders 444 10.9 Product Orders 444 10.10 Equivalence Relations 445 10.11 Summary of Relational Properties 447 10.12 References 449 11 Communication Networks 481 11.1 Routing 481 11.2 Routing Measures 482 11.3 Network Designs 485 12 Simple Graphs 501 12.1 Vertex Adjacency and Degrees 501 12.2 Sexual Demographics in America 503 12.3 Some Common Graphs 505 12.4 Isomorphism 507 12.5 Bipartite Graphs Matchings 509 12.6 Coloring 514 12.7 Walks in Simple Graphs 519 12.8 Connectivity 521 12.9 Special Walks and Tours 523 12.10 k-connected Graphs 525 12.11 Forests Trees 527 12.12 References 535 13 Planar Graphs 575 13.1 Drawing Graphs in the Plane 575 13.2 Definitions of Planar Graphs 575 13.3 Euler's Formula 586 13.4 Bounding the Number of Edges in a Planar Graph 587
“mcs” — 2018/6/6 — 13:43 — page v — #5 Contentsv 9.11 RSA Public Key Encryption 378 9.12 What has SAT got to do with it? 381 9.13 References 382 10 Directed graphs & Partial Orders 421 10.1 Vertex Degrees 423 10.2 Walks and Paths 424 10.3 Adjacency Matrices 427 10.4 Walk Relations 430 10.5 Directed Acyclic Graphs & Scheduling 431 10.6 Partial Orders 439 10.7 Representing Partial Orders by Set Containment 442 10.8 Linear Orders 444 10.9 Product Orders 444 10.10 Equivalence Relations 445 10.11 Summary of Relational Properties 447 10.12 References 449 11 Communication Networks 481 11.1 Routing 481 11.2 Routing Measures 482 11.3 Network Designs 485 12 Simple Graphs 501 12.1 Vertex Adjacency and Degrees 501 12.2 Sexual Demographics in America 503 12.3 Some Common Graphs 505 12.4 Isomorphism 507 12.5 Bipartite Graphs & Matchings 509 12.6 Coloring 514 12.7 Walks in Simple Graphs 519 12.8 Connectivity 521 12.9 Special Walks and Tours 523 12.10 k-connected Graphs 525 12.11 Forests & Trees 527 12.12 References 535 13 Planar Graphs 575 13.1 Drawing Graphs in the Plane 575 13.2 Definitions of Planar Graphs 575 13.3 Euler’s Formula 586 13.4 Bounding the Number of Edges in a Planar Graph 587
“mcs”一2018/6/6一13：43一page vi-#6 公 Contents 13.5 Returning to Ks and K3.3 588 13.6 Coloring Planar Graphs 589 13.7 Classifying Polyhedra 591 13.8 Another Characterization for Planar Graphs 594 III Counting Introduction 603 14 Sums and Asymptotics 605 14.1 The Value of an Annuity 606 14.2 Sums of Powers 612 14.3 Approximating Sums 614 14.4 Hanging Out Over the Edge 618 14.5 Products 624 14.6 Double Trouble 627 14.7 Asymptotic Notation 630 15 Cardinality Rules 655 15.1 Counting One Thing by Counting Another 655 15.2 Counting Sequences 656 15.3 The Generalized Product Rule 659 15.4 The Division Rule 663 15.5 Counting Subsets 665 15.6 Sequences with Repetitions 667 15.7 Counting Practice:Poker Hands 671 15.8 The Pigeonhole Principle 676 15.9 Inclusion-Exclusion 685 15.10 Combinatorial Proofs 690 15.11 References 694 16 Generating Functions 735 16.1 Infinite Series 735 16.2 Counting with Generating Functions 737 16.3 Partial Fractions 743 16.4 Solving Linear Recurrences 746 16.5 Formal Power Series 751 16.6 References 754
“mcs” — 2018/6/6 — 13:43 — page vi — #6 Contentsvi 13.5 Returning to K5 and K3;3 588 13.6 Coloring Planar Graphs 589 13.7 Classifying Polyhedra 591 13.8 Another Characterization for Planar Graphs 594 III Counting Introduction 603 14 Sums and Asymptotics 605 14.1 The Value of an Annuity 606 14.2 Sums of Powers 612 14.3 Approximating Sums 614 14.4 Hanging Out Over the Edge 618 14.5 Products 624 14.6 Double Trouble 627 14.7 Asymptotic Notation 630 15 Cardinality Rules 655 15.1 Counting One Thing by Counting Another 655 15.2 Counting Sequences 656 15.3 The Generalized Product Rule 659 15.4 The Division Rule 663 15.5 Counting Subsets 665 15.6 Sequences with Repetitions 667 15.7 Counting Practice: Poker Hands 671 15.8 The Pigeonhole Principle 676 15.9 Inclusion-Exclusion 685 15.10 Combinatorial Proofs 690 15.11 References 694 16 Generating Functions 735 16.1 Infinite Series 735 16.2 Counting with Generating Functions 737 16.3 Partial Fractions 743 16.4 Solving Linear Recurrences 746 16.5 Formal Power Series 751 16.6 References 754
“mcs”-2018/6/6一13：43一page vii一#7 vii Contents IV Probability Introduction 771 17 Events and Probability Spaces 773 17.1 Let's Make a Deal 773 17.2 The Four Step Method 774 17.3 Strange Dice 783 17.4 The Birthday Principle 790 17.5 Set Theory and Probability 792 17.6 References 796 18 Conditional Probability 805 18.1 Monty Hall Confusion 805 18.2 Definition and Notation 806 18.3 The Four-Step Method for Conditional Probability 808 18.4 Why Tree Diagrams Work 810 18.5 The Law of Total Probability 818 18.6 Simpson's Paradox 820 18.7 Independence 822 18.8 Mutual Independence 824 18.9 Probability versus Confidence 828 19 Random Variables 857 19.1 Random Variable Examples 857 19.2 Independence 859 19.3 Distribution Functions 861 19.4 Great Expectations 869 19.5 Linearity of Expectation 881 19.6 Really Great Expectations 890 20 Deviation from the Mean 915 20.1 Markov's Theorem 915 20.2 Chebyshev's Theorem 918 20.3 Properties of Variance 922 20.4 Estimation by Random Sampling 928 20.5 Sums of Random Variables 933 21 Random Walks 965 21.1 Gambler's Ruin 965 21.2 Random Walks on Graphs 975
“mcs” — 2018/6/6 — 13:43 — page vii — #7 Contentsvii IV Probability Introduction 771 17 Events and Probability Spaces 773 17.1 Let’s Make a Deal 773 17.2 The Four Step Method 774 17.3 Strange Dice 783 17.4 The Birthday Principle 790 17.5 Set Theory and Probability 792 17.6 References 796 18 Conditional Probability 805 18.1 Monty Hall Confusion 805 18.2 Definition and Notation 806 18.3 The Four-Step Method for Conditional Probability 808 18.4 Why Tree Diagrams Work 810 18.5 The Law of Total Probability 818 18.6 Simpson’s Paradox 820 18.7 Independence 822 18.8 Mutual Independence 824 18.9 Probability versus Confidence 828 19 Random Variables 857 19.1 Random Variable Examples 857 19.2 Independence 859 19.3 Distribution Functions 861 19.4 Great Expectations 869 19.5 Linearity of Expectation 881 19.6 Really Great Expectations 890 20 Deviation from the Mean 915 20.1 Markov’s Theorem 915 20.2 Chebyshev’s Theorem 918 20.3 Properties of Variance 922 20.4 Estimation by Random Sampling 928 20.5 Sums of Random Variables 933 21 Random Walks 965 21.1 Gambler’s Ruin 965 21.2 Random Walks on Graphs 975
“mcs”一2018/6/6一13：43一page viii一#8 vii Contents V Recurrences Introduction 993 22 Recurrences 995 22.1 The Towers of Hanoi 995 22.2 Merge Sort 998 22.3 Linear Recurrences 1002 22.4 Divide-and-Conquer Recurrences 1009 22.5 A Feel for Recurrences 1016 Bibliography 1023 Glossary of Symbols 1027 Index 1031
“mcs” — 2018/6/6 — 13:43 — page viii — #8 Contentsviii V Recurrences Introduction 993 22 Recurrences 995 22.1 The Towers of Hanoi 995 22.2 Merge Sort 998 22.3 Linear Recurrences 1002 22.4 Divide-and-Conquer Recurrences 1009 22.5 A Feel for Recurrences 1016 Bibliography 1023 Glossary of Symbols 1027 Index 1031
“mcs”一2018/6/6一13：43一page1一#9 I Proofs
“mcs” — 2018/6/6 — 13:43 — page 1 — #9 I Proofs
“mcs”-2018/6/6一13：43一page3一#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 truth 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, Rene 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. 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 IActually,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
“mcs” — 2018/6/6 — 13:43 — page 3 — #11 Introduction This text explains how to use mathematical models and methods to analyze problems 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, something that no amount of testing can do. Simply put, a proof is a method of establishing truth. Like beauty, “truth” sometimes 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 truth is confirmed by experiment.1 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, Rene 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. 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 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
“mcs”-2018/6/6一13：43一page4一#12 0.1.References 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 8 offer a more careful look at such mathematical data types,examining in particular properties and methods for proving things about infinite sets.Chapter 7 goes on to examine recursively defined data types. 0.1 References [141,[49],[1]
“mcs” — 2018/6/6 — 13:43 — page 4 — #12 0.1. References4 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 deduction, 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 understanding 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 8 offer a more careful look at such mathematical data types, examining in particular properties and methods for proving things about infinite sets. Chapter 7 goes on to examine recursively defined data types. 0.1 References [14], [49], [1]