“mcs” — 2015/5/18 — 1:43 — page i — #1
Mathematics for Computer Science
revised Monday 18th May, 2015, 01: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 Electrica Engineering and Computer Science
F
and the Computer Science and AI Laboratory,
Massachussetts Institute of Technology
, “mcs” — 2015/5/18 — 1: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 Wel Ordering Principle
F 27
2.1 Wel Ordering Proofs
F 27
2.2 Template for Wel Ordering Proofs
F 28
2.3 Factoring into Primes 30
2.4 Wel Ordered Sets
F 31
3 Logica Formulas
F 41
3.1 Propositions from Propositions 42
3.2 Propositiona Logic in Computer Programs
F 45
3.3 Equivalence and Validity 48
3.4 The Algebra of Propositions 50
3.5 The SAT Problem 55
3.6 Predicate Formulas 56
3.7 References 61
4 Mathematica Data Types F 81
4.1 Sets 81
4.2 Sequences 86
4.3 Functions 87
4.4 Binary Relations 89
4.5 Finite Cardinality 93
, “mcs” — 2015/5/18 — 1:43 — page iv — #4
iv Contents
5 Induction 115
5.1 Ordinary Induction 115
5.2 Strong Induction 124
5.3 Strong Induction vs. Induction vs. Wel Ordering
F 129
5.4 State Machines 130
6 Recursive Data Types 173
6.1 Recursive Definitions and Structura Induction
F 173
6.2 Strings of Matched Brackets 177
6.3 Recursive Functions on Nonnegative Integers 180
6.4 Arithmetic Expressions 183
6.5 Induction in Computer Science 188
7 Infinite Sets 205
7.1 Infinite Cardinality 206
7.2 The Halting Problem 215
7.3 The Logic of Sets 219
7.4 Does Al This Really Work?
F 222
II Structures
Introduction 241
8 Number Theory 243
8.1 Divisibility 243
8.2 The Greatest Common Divisor 248
8.3 Prime Mysteries 254
8.4 The Fundamenta Theorem of Arithmetic 257
F
8.5 Alan Turing 259
8.6 Modular Arithmetic 263
8.7 Remainder Arithmetic 265
8.8 Turing’s Code (Version 2.0) 268
8.9 Multiplicative Inverses and Cancelling 270
8.10 Euler’s Theorem 274
8.11 RSA Public Key Encryption 279
8.12 What has SAT got to do with it? 281
8.13 References 282
9 Directed graphs & Partia Orders F 317
9.1 Vertex Degrees 319
9.2 Walks and Paths 320
, “mcs” — 2015/5/18 — 1:43 — page v — #5
v Contents
9.3 Adjacency Matrices 323
9.4 Walk Relations 326
9.5 Directed Acyclic Graphs & Scheduling 327
9.6 Partia Orders 335
F
9.7 Representing Partia Orders by Set Containment
F 339
9.8 Linear Orders 340
9.9 Product Orders 340
9.10 Equivalence Relations 341
9.11 Summary of Relationa Properties 343
F
10 Communication Networks 373
10.1 Complete Binary Tree 373
10.2 Routing Problems 373
10.3 Network Diameter 374
10.4 Switch Count 375
10.5 Network Latency 376
10.6 Congestion 376
10.7 2-D Array 377
10.8 Butterfly 379
10.9 Benesˇ Network 381
11 Simple Graphs 393
11.1 Vertex Adjacency and Degrees 393
11.2 Sexua Demographics in America 395
F
11.3 Some Common Graphs 397
11.4 Isomorphism 399
11.5 Bipartite Graphs & Matchings 401
11.6 The Stable Marriage Problem 406
11.7 Coloring 413
11.8 Simple Walks 417
11.9 Connectivity 419
11.10 Forests & Trees 424
11.11 References 433
12 Planar Graphs 473
12.1 Drawing Graphs in the Plane 473
12.2 Definitions of Planar Graphs 473
12.3 Euler’s Formula 484
12.4 Bounding the Number of Edges in a Planar Graph 485
12.5 Returning to k5 and k3,3 486
12.6 Coloring Planar Graphs 487
Mathematics for Computer Science
revised Monday 18th May, 2015, 01: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 Electrica Engineering and Computer Science
F
and the Computer Science and AI Laboratory,
Massachussetts Institute of Technology
, “mcs” — 2015/5/18 — 1: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 Wel Ordering Principle
F 27
2.1 Wel Ordering Proofs
F 27
2.2 Template for Wel Ordering Proofs
F 28
2.3 Factoring into Primes 30
2.4 Wel Ordered Sets
F 31
3 Logica Formulas
F 41
3.1 Propositions from Propositions 42
3.2 Propositiona Logic in Computer Programs
F 45
3.3 Equivalence and Validity 48
3.4 The Algebra of Propositions 50
3.5 The SAT Problem 55
3.6 Predicate Formulas 56
3.7 References 61
4 Mathematica Data Types F 81
4.1 Sets 81
4.2 Sequences 86
4.3 Functions 87
4.4 Binary Relations 89
4.5 Finite Cardinality 93
, “mcs” — 2015/5/18 — 1:43 — page iv — #4
iv Contents
5 Induction 115
5.1 Ordinary Induction 115
5.2 Strong Induction 124
5.3 Strong Induction vs. Induction vs. Wel Ordering
F 129
5.4 State Machines 130
6 Recursive Data Types 173
6.1 Recursive Definitions and Structura Induction
F 173
6.2 Strings of Matched Brackets 177
6.3 Recursive Functions on Nonnegative Integers 180
6.4 Arithmetic Expressions 183
6.5 Induction in Computer Science 188
7 Infinite Sets 205
7.1 Infinite Cardinality 206
7.2 The Halting Problem 215
7.3 The Logic of Sets 219
7.4 Does Al This Really Work?
F 222
II Structures
Introduction 241
8 Number Theory 243
8.1 Divisibility 243
8.2 The Greatest Common Divisor 248
8.3 Prime Mysteries 254
8.4 The Fundamenta Theorem of Arithmetic 257
F
8.5 Alan Turing 259
8.6 Modular Arithmetic 263
8.7 Remainder Arithmetic 265
8.8 Turing’s Code (Version 2.0) 268
8.9 Multiplicative Inverses and Cancelling 270
8.10 Euler’s Theorem 274
8.11 RSA Public Key Encryption 279
8.12 What has SAT got to do with it? 281
8.13 References 282
9 Directed graphs & Partia Orders F 317
9.1 Vertex Degrees 319
9.2 Walks and Paths 320
, “mcs” — 2015/5/18 — 1:43 — page v — #5
v Contents
9.3 Adjacency Matrices 323
9.4 Walk Relations 326
9.5 Directed Acyclic Graphs & Scheduling 327
9.6 Partia Orders 335
F
9.7 Representing Partia Orders by Set Containment
F 339
9.8 Linear Orders 340
9.9 Product Orders 340
9.10 Equivalence Relations 341
9.11 Summary of Relationa Properties 343
F
10 Communication Networks 373
10.1 Complete Binary Tree 373
10.2 Routing Problems 373
10.3 Network Diameter 374
10.4 Switch Count 375
10.5 Network Latency 376
10.6 Congestion 376
10.7 2-D Array 377
10.8 Butterfly 379
10.9 Benesˇ Network 381
11 Simple Graphs 393
11.1 Vertex Adjacency and Degrees 393
11.2 Sexua Demographics in America 395
F
11.3 Some Common Graphs 397
11.4 Isomorphism 399
11.5 Bipartite Graphs & Matchings 401
11.6 The Stable Marriage Problem 406
11.7 Coloring 413
11.8 Simple Walks 417
11.9 Connectivity 419
11.10 Forests & Trees 424
11.11 References 433
12 Planar Graphs 473
12.1 Drawing Graphs in the Plane 473
12.2 Definitions of Planar Graphs 473
12.3 Euler’s Formula 484
12.4 Bounding the Number of Edges in a Planar Graph 485
12.5 Returning to k5 and k3,3 486
12.6 Coloring Planar Graphs 487
