“mcs”一2017/6/5一19：42一page i一#1 Mathematics for Computer Science revised Monday 5th June,2017,19:42 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 2017.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” — 2017/6/5 — 19:42 — page i — #1 Mathematics for Computer Science revised Monday 5th June, 2017, 19:42 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 2017, 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”一2017/6/5一19：42一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 97 4.1 Sets 97 4.2 Sequences 102 4.3 Functions 103 4.4 Binary Relations 105 4.5 Finite Cardinality 109
“mcs” — 2017/6/5 — 19:42 — 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 97 4.1 Sets 97 4.2 Sequences 102 4.3 Functions 103 4.4 Binary Relations 105 4.5 Finite Cardinality 109
“mcs”一2017/6/5一19：42一page iv一#4 公 Contents 5 Induction 131 5.1 Ordinary Induction 131 5.2 Strong Induction 140 5.3 Strong Induction vs.Induction vs.Well Ordering 147 6 State Machines 167 6.1 States and Transitions 167 6.2 The Invariant Principle 168 6.3 Partial Correctness Termination 176 6.4 The Stable Marriage Problem 181 7 Recursive Data Types 211 7.1 Recursive Definitions and Structural Induction 211 7.2 Strings of Matched Brackets 215 7.3 Recursive Functions on Nonnegative Integers 219 7.4 Arithmetic Expressions 221 7.5 Games as a Recursive Data Type 226 7.6 Induction in Computer Science 230 8 Infinite Sets 257 8.1 Infinite Cardinality 258 8.2 The Halting Problem 267 8.3 The Logic of Sets 271 8.4 Does All This Really Work?275 II Structures Introduction 299 9 Number Theory 301 9.1 Divisibility 301 9.2 The Greatest Common Divisor 306 9.3 Prime Mysteries 313 9.4 The Fundamental Theorem of Arithmetic 315 9.5 Alan Turing 318 9.6 Modular Arithmetic 322 9.7 Remainder Arithmetic 324 9.8 Turing's Code (Version 2.0)327 9.9 Multiplicative Inverses and Cancelling 329 9.10 Euler's Theorem 333 9.11 RSA Public Key Encryption 338
“mcs” — 2017/6/5 — 19:42 — page iv — #4 Contentsiv 5 Induction 131 5.1 Ordinary Induction 131 5.2 Strong Induction 140 5.3 Strong Induction vs. Induction vs. Well Ordering 147 6 State Machines 167 6.1 States and Transitions 167 6.2 The Invariant Principle 168 6.3 Partial Correctness & Termination 176 6.4 The Stable Marriage Problem 181 7 Recursive Data Types 211 7.1 Recursive Definitions and Structural Induction 211 7.2 Strings of Matched Brackets 215 7.3 Recursive Functions on Nonnegative Integers 219 7.4 Arithmetic Expressions 221 7.5 Games as a Recursive Data Type 226 7.6 Induction in Computer Science 230 8 Infinite Sets 257 8.1 Infinite Cardinality 258 8.2 The Halting Problem 267 8.3 The Logic of Sets 271 8.4 Does All This Really Work? 275 II Structures Introduction 299 9 Number Theory 301 9.1 Divisibility 301 9.2 The Greatest Common Divisor 306 9.3 Prime Mysteries 313 9.4 The Fundamental Theorem of Arithmetic 315 9.5 Alan Turing 318 9.6 Modular Arithmetic 322 9.7 Remainder Arithmetic 324 9.8 Turing’s Code (Version 2.0) 327 9.9 Multiplicative Inverses and Cancelling 329 9.10 Euler’s Theorem 333 9.11 RSA Public Key Encryption 338
“mcs”一2017/6/5一19：42-page v一#5 Contents 9.12 What has SAT got to do with it?340 9.13 References 341 10 Directed graphs Partial Orders 381 10.1 Vertex Degrees 383 10.2 Walks and Paths 384 10.3 Adjacency Matrices 387 10.4 Walk Relations 390 10.5 Directed Acyclic Graphs Scheduling 391 10.6 Partial Orders 399 10.7 Representing Partial Orders by Set Containment 403 10.8 Linear Orders 404 10.9 Product Orders 404 10.10 Equivalence Relations 405 10.11 Summary of Relational Properties 407 10.12 References 409 11 Communication Networks 441 11.1 Routing 441 11.2 Routing Measures 442 11.3 Network Designs 445 12 Simple Graphs 461 12.1 Vertex Adjacency and Degrees 461 12.2 Sexual Demographics in America 463 12.3 Some Common Graphs 465 12.4 Isomorphism 466 12.5 Bipartite Graphs Matchings 469 12.6 Coloring 474 12.7 Walks in Simple Graphs 478 12.8 Connectivity 480 12.9 Special Walks and Tours 483 12.10 k-connected Graphs 485 12.11 Forests Trees 487 12.12 References 494 13 Planar Graphs 533 13.1 Drawing Graphs in the Plane 533 13.2 Definitions of Planar Graphs 533 13.3 Euler's Formula 544 13.4 Bounding the Number of Edges in a Planar Graph 545 13.5 Returning to K's and K3,3 546
“mcs” — 2017/6/5 — 19:42 — page v — #5 Contentsv 9.12 What has SAT got to do with it? 340 9.13 References 341 10 Directed graphs & Partial Orders 381 10.1 Vertex Degrees 383 10.2 Walks and Paths 384 10.3 Adjacency Matrices 387 10.4 Walk Relations 390 10.5 Directed Acyclic Graphs & Scheduling 391 10.6 Partial Orders 399 10.7 Representing Partial Orders by Set Containment 403 10.8 Linear Orders 404 10.9 Product Orders 404 10.10 Equivalence Relations 405 10.11 Summary of Relational Properties 407 10.12 References 409 11 Communication Networks 441 11.1 Routing 441 11.2 Routing Measures 442 11.3 Network Designs 445 12 Simple Graphs 461 12.1 Vertex Adjacency and Degrees 461 12.2 Sexual Demographics in America 463 12.3 Some Common Graphs 465 12.4 Isomorphism 466 12.5 Bipartite Graphs & Matchings 469 12.6 Coloring 474 12.7 Walks in Simple Graphs 478 12.8 Connectivity 480 12.9 Special Walks and Tours 483 12.10 k-connected Graphs 485 12.11 Forests & Trees 487 12.12 References 494 13 Planar Graphs 533 13.1 Drawing Graphs in the Plane 533 13.2 Definitions of Planar Graphs 533 13.3 Euler’s Formula 544 13.4 Bounding the Number of Edges in a Planar Graph 545 13.5 Returning to K5 and K3;3 546
“mcs”一2017/6/5一19：42一page vi-#6 vi Contents 13.6 Coloring Planar Graphs 547 13.7 Classifying Polyhedra 549 13.8 Another Characterization for Planar Graphs 552 III Counting Introduction 561 14 Sums and Asymptotics 563 14.1 The Value of an Annuity 564 14.2 Sums of Powers 570 14.3 Approximating Sums 572 14.4 Hanging Out Over the Edge 576 14.5 Products 582 14.6 Double Trouble 585 14.7 Asymptotic Notation 588 15 Cardinality Rules 613 15.1 Counting One Thing by Counting Another 613 15.2 Counting Sequences 614 15.3 The Generalized Product Rule 617 15.4 The Division Rule 621 15.5 Counting Subsets 623 15.6 Sequences with Repetitions 625 15.7 Counting Practice:Poker Hands 629 15.8 The Pigeonhole Principle 634 15.9 Inclusion-Exclusion 643 15.10 Combinatorial Proofs 649 15.11 References 653 16 Generating Functions 693 16.1 Infinite Series 693 16.2 Counting with Generating Functions 695 16.3 Partial Fractions 701 16.4 Solving Linear Recurrences 704 16.5 Formal Power Series 709 16.6 References 712
“mcs” — 2017/6/5 — 19:42 — page vi — #6 Contentsvi 13.6 Coloring Planar Graphs 547 13.7 Classifying Polyhedra 549 13.8 Another Characterization for Planar Graphs 552 III Counting Introduction 561 14 Sums and Asymptotics 563 14.1 The Value of an Annuity 564 14.2 Sums of Powers 570 14.3 Approximating Sums 572 14.4 Hanging Out Over the Edge 576 14.5 Products 582 14.6 Double Trouble 585 14.7 Asymptotic Notation 588 15 Cardinality Rules 613 15.1 Counting One Thing by Counting Another 613 15.2 Counting Sequences 614 15.3 The Generalized Product Rule 617 15.4 The Division Rule 621 15.5 Counting Subsets 623 15.6 Sequences with Repetitions 625 15.7 Counting Practice: Poker Hands 629 15.8 The Pigeonhole Principle 634 15.9 Inclusion-Exclusion 643 15.10 Combinatorial Proofs 649 15.11 References 653 16 Generating Functions 693 16.1 Infinite Series 693 16.2 Counting with Generating Functions 695 16.3 Partial Fractions 701 16.4 Solving Linear Recurrences 704 16.5 Formal Power Series 709 16.6 References 712