http://online-learning.harvard.edu/course/discrete-mathematics-computer-science
--------------------------------------------------------------------------------------------------------
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 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.” It 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
on the phrase 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
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 proofs using the Well Ordering
Principle; later Chapter 6 introduces the closely related proof method of Induction.
If you’re going to prove a proposition, you 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 5 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 recursive 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
Author(s): Eric Lehman, Thomson Leighton, Albert Meyer
Edition: revised
Year: 2012
Language: English
Pages: 800
I Proofs
1 What is a Proof? 5
1.1 Propositions 5
1.2 Predicates 7
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
3 Logical Formulas 35
3.1 Propositions from Propositions 36
3.2 Propositional Logic in Computer Programs 39
3.3 Equivalence and Validity 41
3.4 The Algebra of Propositions 44
3.5 The SAT Problem 49
3.6 Predicate Formulas 50
4 Mathematical Data Types 69
4.1 Sets 69
4.2 Sequences 72
4.3 Functions 73
4.4 Binary Relations 75
5 Infinite Sets 89
5.1 Finite Cardinality 90
5.2 Infinite Cardinality 92
5.3 The Halting Problem 97
5.4 The Logic of Sets 101
5.5 Does All This Really Work? 104
6 Induction 115
6.1 Ordinary Induction 115
6.2 Strong Induction 124
6.3 Strong Induction vs. Induction vs. Well Ordering 128
6.4 State Machines 129
7 Recursive Data Types 161
7.1 Recursive Definitions and Structural Induction 161
7.2 Strings of Matched Brackets 165
7.3 Recursive Functions on Nonnegative Integers 168
7.4 Arithmetic Expressions 171
7.5 Induction in Computer Science 176
8 Number Theory 187
8.1 Divisibility 187
8.2 The Greatest Common Divisor 193
8.3 The Fundamental Theorem of Arithmetic 199
8.4 Alan Turing 202
8.5 Modular Arithmetic 205
8.6 Arithmetic with a Prime Modulus 208
8.7 Arithmetic with an Arbitrary Modulus 213
8.8 The RSA Algorithm 219
8.9 What has SAT got to do with it? 221
II Structures
9 Directed graphs & Partial Orders 245
9.1 Digraphs & Vertex Degrees 247
9.2 Digraph Walks and Paths 248
9.3 Adjacency Matrices 251
9.4 Walk Relations 254
9.5 Directed Acyclic Graphs & Partial Orders 255
9.6 Weak Partial Orders 258
9.7 Representing Partial Orders by Set Containment 260
9.8 Path-Total Orders 261
9.9 Product Orders 262
9.10 Scheduling 263
9.11 Equivalence Relations 269
9.12 Summary of Relational Properties 270
10 Communication Networks 295
10.1 Complete Binary Tree 295
10.2 Routing Problems 295
10.3 Network Diameter 296
10.4 Switch Count 297
10.5 Network Latency 298
10.6 Congestion 298
10.7 2-D Array 299
10.8 Butterfly 301
10.9 Benes Network ˘ 303
11 Simple Graphs 315
11.1 Vertex Adjacency and Degrees 315
11.2 Sexual Demographics in America 317
11.3 Some Common Graphs 319
11.4 Isomorphism 321
11.5 Bipartite Graphs & Matchings 323
11.6 The Stable Marriage Problem 328
11.7 Coloring 335
11.8 Getting from u to v in a Graph 339
11.9 Connectivity 341
11.10 Odd Cycles and 2-Colorability 345
11.11 Forests & Trees 346
12 Planar Graphs 381
12.1 Drawing Graphs in the Plane 381
12.2 Definitions of Planar Graphs 381
12.3 Euler’s Formula 392
12.4 Bounding the Number of Edges in a Planar Graph 393
12.5 Returning to K5 and K3;3 394
12.6 Coloring Planar Graphs 395
12.7 Classifying Polyhedra 397
12.8 Another Characterization for Planar Graphs 400
13 State Machines 407
13.1 The Alternating Bit Protocol 407
13.2 Reasoning About While Programs 410
III Counting
14 Sums and Asymptotics 421
14.1 The Value of an Annuity 422
14.2 Sums of Powers 428
14.3 Approximating Sums 430
14.4 Hanging Out Over the Edge 434
14.5 Products 446
14.6 Double Trouble 448
14.7 Asymptotic Notation 451
15 Cardinality Rules 471
15.1 Counting One Thing by Counting Another 471
15.2 Counting Sequences 472
15.3 The Generalized Product Rule 475
15.4 The Division Rule 479
15.5 Counting Subsets 482
15.6 Sequences with Repetitions 483
15.7 The Binomial Theorem 485
15.8 A Word about Words 487
15.9 Counting Practice: Poker Hands 487
15.10 The Pigeonhole Principle 492
15.11 A Magic Trick 496
15.12 Inclusion-Exclusion 501
15.13 Combinatorial Proofs 507
16 Generating Functions 541
16.1 Operations on Generating Functions 542
16.2 The Fibonacci Sequence 547
16.3 Counting with Generating Functions 550
16.4 An “Impossible” Counting Problem 554
IV Probability
17 Events and Probability Spaces 571
17.1 Let’s Make a Deal 571
17.2 The Four Step Method 572
17.3 Strange Dice 581
17.4 Set Theory and Probability 589
17.5 Conditional Probability 593
17.6 Independence 605
18 Random Variables 635
18.1 Random Variable Examples 635
18.2 Independence 637
18.3 Distribution Functions 638
18.4 Great Expectations 646
18.5 Linearity of Expectation 658
19 Deviation from the Mean 679
19.1 Why the Mean? 679
19.2 Markov’s Theorem 680
19.3 Chebyshev’s Theorem 682
19.4 Properties of Variance 686
19.5 Estimation by Random Sampling 690
19.6 Confidence versus Probability 695
19.7 Sums of Random Variables 696
19.8 Really Great Expectations 706
20 Random Processes 725
20.1 Gamblers’ Ruin 725
20.2 Random Walks on Graphs 734
V Recurrences
21 Recurrences 753
21.1 The Towers of Hanoi 753
21.2 Merge Sort 760
21.3 Linear Recurrences 764
21.4 Divide-and-Conquer Recurrences 771
21.5 A Feel for Recurrences 778
Index 780
