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 ...... degree rotation of these shapes would not count as a tiling at all.) (a) There are ...... assertion that a predicate is always true is called a universal quantification, and an.
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 ii — #2
“mcs” — 2017/6/5 — 19:42 — page iii — #3
Contents I
Proofs Introduction 3 0.1
1
Well Ordering Proofs 29 Template for WOP Proofs 30 Factoring into Primes 32 Well Ordered Sets 33
Logical Formulas 47 3.1 3.2 3.3 3.4 3.5 3.6 3.7
4
Propositions 5 Predicates 8 The Axiomatic Method 8 Our Axioms 9 Proving an Implication 11 Proving an “If and Only If” 13 Proof by Cases 15 Proof by Contradiction 16 Good Proofs in Practice 17 References 19
The Well Ordering Principle 29 2.1 2.2 2.3 2.4
3
4
What is a Proof? 5 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 1.10
2
References
Propositions from Propositions 48 Propositional Logic in Computer Programs Equivalence and Validity 54 The Algebra of Propositions 57 The SAT Problem 62 Predicate Formulas 63 References 68
States and Transitions 167 The Invariant Principle 168 Partial Correctness & Termination 176 The Stable Marriage Problem 181
Recursive Data Types 211 7.1 7.2 7.3 7.4 7.5 7.6
8
Recursive Definitions and Structural Induction 211 Strings of Matched Brackets 215 Recursive Functions on Nonnegative Integers 219 Arithmetic Expressions 221 Games as a Recursive Data Type 226 Induction in Computer Science 230
Infinite Sets 257 8.1 8.2 8.3 8.4
Infinite Cardinality 258 The Halting Problem 267 The Logic of Sets 271 Does All This Really Work?
275
II Structures Introduction 299 9
147
State Machines 167 6.1 6.2 6.3 6.4
7
Ordinary Induction 131 Strong Induction 140 Strong Induction vs. Induction vs. Well Ordering
Number Theory 301 9.1 9.2 9.3 9.4 9.5 9.6 9.7 9.8 9.9 9.10 9.11
Divisibility 301 The Greatest Common Divisor 306 Prime Mysteries 313 The Fundamental Theorem of Arithmetic 315 Alan Turing 318 Modular Arithmetic 322 Remainder Arithmetic 324 Turing’s Code (Version 2.0) 327 Multiplicative Inverses and Cancelling 329 Euler’s Theorem 333 RSA Public Key Encryption 338
“mcs” — 2017/6/5 — 19:42 — page v — #5
v
Contents
9.12 What has SAT got to do with it? 9.13 References 341
ciplines including programming, algebra, finance, and political theory. ... sages would also become an easy task, so online financial transactions would be.
Sep 7, 2013 - 6.3 Communication Networks 196. 7 Relations ...... weeks of an introductory course like Mathematics for Computer Science would be regarded ...... ing an optimization problem, or designing a network, you will be dealing with.
3. antisymmetric: for all x and y in X it follows that if xRy and yRx then ... A relation which is reflexive, symmetric and transitive is called an equivalence ... What is the cardinalty of {{1, 2},{3},1}. 6. Give the domain and the range of each of
The widespread availability of two key technologies ... familiarity with HTML editors, and transmission is .... Figure 2 shows an example HTML page with image.
The mechanization of mathematics refers to the use of computers to find, or to help ...... Notes in Computer Science 475 101-156, Springer-Verlag (1991). 10.