MIT教材--计算机科学的数学基础

MIT（麻省理工学院）的教材--计算机科学的数学基础。主要设计离散数学和组合数学的内容，广泛用于排序，图论等。非扫描版，可搜索可打印，共520页。Contents1 What is a Proof?131.1 Mathematical Proofs131.1.1 Problems.141.2 Propositions1.3 Predicate181.4 The Axiomatic Method181.5 Our Axioms191.5.1 Logical Deductions191.5.2 Patterns of Proof201.6 Proving an Implication201.6.1 Method #1211.6.2 Method #2-Prove the Contrapositive221.6.3 Problems231.7 Proving an"If and Only If1.7.1 Method #1: Prove Each Statement Implies the other1.7.2 Method #2: Construct a Chain of iffs231.8 Proof by cases241.8.1 Prob1.9 Proof by Contradiction番垂261.9.1 Problems271.10 Good Proofs in practice292 The Well Ordering Principle312.1 Well Ordering Proofs312.2 Template for Well Ordering proofs322.2.1 Problems2.3 Summing the Integers.342.3.1 Problems2.4 Factoring into Primes3 Propositional Formulas3.1 Propositions from Propositions3.1.1“Not"’,“And",and“Or″...38CONTENTS312“ plies"393.1.3 If and Only If3.1.4 Problems3.2 Propositional logic in Computer programs413.2.1 Cryptic Notation423.2.2 Logically equivalent Implications3.2.3 Problems4 Mathematical Data Typees514.1 Sets514.1.1 Some Popular Sets4.1.2 Comparing and Combining Sets524.1.3 Complement of a Set524.1.4 Power Set534.1.5 Set Builder notation534.1.6 Proving set equalities4.1.7 Problems4.2 Sequences554.3 Functions4.3.1 Function Composition574.4 Binary relations574.5 Binary Relations and Functions4.6 Images and Inverse Images594.7 Surjective and Injective Relations4.7.1 Relation Diagrams4.8 The Mapping rule614.9 The sizes of infinite sets4.9.1 Infinities in Computer Science654.9.2 Problems4.10 Glossary of Symbols715 First-Order Logic5.1 Quantifiers5.1. 1 More Cryptic notation5.1.2 Mixing Quantifiers755.1.3 Order of Quantifiers5.1.4 Negating Quantifiers765.1.5 Validity765.1.6 Problems785.2 The Logic of sets815.2.1 Russells Paradox815.2.2 The ZFC Axioms for Sets815.2.3 Avoiding russells Paradox5.2.4 Power sets are strictly bigger5.2.5 Does all This really work?84CONTENTS5.2.6 Large Infinities in Computer Science5.2.7 Problems5.3 Glossary of Symbols896 Induction916.1 Ordinary Induction926.1.1 Using Ordinary Induction6.1.2 A Template for Induction Proofs36.1.3 A Clean Writeup946.1.4 Courtyard Tiling946.1.5 A Faulty Induction Proof6.1.6 Problems986.2 Strong Induction1026.2.1 Products of Primes1036.2.2 Making Change1046.2.3 The Stacking game1046.2.4 Problems1066.3 Induction versus Well ordering..1077 Partial Orders1097. 1 Axioms for Partial Orders1097. 2 Representing Partial Orders by Set Containment1117.2.1 Problems1127.3 Total Orders7.3.1 Problems1147.4 Product Orders7.4.1 Proble7.5 Scheduling1177.5.1 Parallel Task scheduling.1197.6 Dilworth's Lemma1217.6.1 Problems1228 Directed graphs1298.1 Digraphs1298.1.1 Paths in Digraphs1308.2 Picturing Relational Properties1308. 3 Composition of relations1318.4 Directed Acyclic Graphs1318.4.1 Problems1329 State machines1359.1 State machines1359.1.1 Basic definitions9.1.2 Reachability and Preserved Invariants1351379.1.3 Sequential algorithm examples140CONTENTS9.1.4 Derived variables.1449. 1.5 Problems9.2 The Stable marriage Problem...1569.2.1 The Problem9.2.2 The Mating Ritual1589.2.3 A State Machine model1589.2.4 There is a Marriage day1599.2.5 They All Live Happily Every After1599.2.6 .. Especially the boys1609.2.7 Applications1629.2. 8 Problems16310 SirImple Grap16710.1 Degrees &z Isomorphism16810.1.1 Definition of Simple Graph..16810.1.2 Sex in America16910.1.3 Handshaking lemma17110.1.4 Some Common graphs..17110.1.5 Isomorphism17210.1.6 Problems..17410.2 Connectedness17810.2.1 Paths and Simple cycles17810.2.2 Connected Components.18010.2.3 How Well Connected?18110.2.5 The Minimum Number of Edges in a Connected Grap...18110.2.4 Connection by simple Path18210.2.6 Problems18310.3 Trees..18710.3.1 Tree Properties18810.3.2 Spanning trees..18910.3. 3 Problems番垂19010.4 Coloring graphs19210.5 Modelling Scheduling Conflicts.19210.5.1 Degree-bounded Coloring19310.5.2 Why coloring?.19410.5.3 Problems19510.6 Bipartite Matchings19810.6.1 Bipartite graphs..19810.6.2 Bipartite matchings19910.6.3 The Matching Condition20010.6.4 A Formal statement20210.6.5 Problems20311 Recursive Data Types20711.1 Strings of Brackets207CONTENTS11.2 Arithmetic Expressions..21011.3 Structural Induction on Recursive Data Types21011.3.1 Functions on Recursively-defined Data Types21111.3.2 Recursive Functions on Nonnegative Integers21211.3.3 Evaluation and Substitution with Aexp's21411.3.4 Problems21811.4 Games as a recursive data Type22311.4.1 Tic-Tac-Toe22411.4.2 Infinite Tic-Tac-Toe games22711.4.3 Two Person Terminating Games.22711.4.4 Game Strategies22911.4.5 Problems23011.5 Induction in Computer Science番垂23112 Planar graphs233124 What outer face?常司12. 1 Drawing Graphs in the Plane23312.2 Continuous discre23512.3 Planar Embeddin23712.5 Eulers formula24012.6 Number of edges versus Vertices24112.7 Planar Subgraphs.24212.8 Planar 5-Colorability24312.9 Classifying polyhedra24512.9.1 Problems24713 Communication Networks25313.1 Communication Networks25313.2 Complete Binary Tree25313.3 Routing Problems25413.4 Network Diameter25513.4.1 Switch Size25513.5 Switch Count25513.6 Network latency25613.7 Congestion25613.8 2-D Array25713.9 Butterfl2513.10 Benes Network26113.10.1 Problems26614 Number Theory27314.1 Divisibility27314.1.1 Facts About Divisibility27414.1.2 When Divisibility Goes bad27614.1.3 Die hard..276CONTENTS14.2 The Greatest Common divisor27814.2.1 Linear combinations and the gcd27814.2.2 Properties of the greatest Common Divisor.27914.2.3 One Solution for All Water Jug Problems28014.2.4 The pulverizer28214.2.5 Problems..28314.3 The Fundamental Theorem of Arithmetic28314.3.1 Problems.28614.4 Alan Turing14.4.1 Turing's Code(Version1028628714.4.2 Breaking Turings Code..28914.5 Modular arithmetic28914.5.1 Turings Code(version 2.0)29114.5.2 Problems29214.6 Arithmetic with a Prime modulus29314.6.1 Multiplicative Inverses214.6.2 Cancellation29414.6.3 Fermat's Little Theorem29514.6. 4 Breaking turings code -Again29614.6.5 Turing Postscript29714.6.6 Problems29914.7 Arithmetic with an Arbitrary modulus29914.7.1 Relative Primality and phi30014.7.2 Generalizing to an Arbitrary Modulus30114.7.3 Euler's theorem30114.7.4 RSA30314.7.5 Problems30315 Sums &c Asymptotics30715.1 The value of an annuity30715.1.1 The Future value of money30815.1.2 Closed Form for the annuity value.30915.1.3 Infinite Geometric series30915.1.4 Problems31015.2 Book Stacki831115.2.1 Formalizing the problem3115.2.2 Evaluating the Sum--The Integral Meth31315.2.3 More about harmonic numbers31515.2.4 Problems31615. 3 Finding Summation Formulas.31715.3.1 Double sums31915.4 Stirlings Approximation..32015.4.1 Products to sums32115.5 Asymptotic notation32215.5.1 Little oh322CONTENTS15.5.2 Big Oh..32415.5.3 Theta32515.5. 4 Pitfalls with big Oh..32615.5.5 Problems32716 Counting33116.1 Why Count33116.2 Counting One Thing by Counting Another33316.2. 1 The Bijection rule33316.2.2 Counting Sequences33416.2. 3 The Sum rule33516.2. 4 The Product rule33516.2.5 Putting Rules Together33616.2.6 Problems33716.3 The Pigeonhole Principle34116.3.1 Hairs on heads..34216.3.2 Subsets with the Same Sum34216.3. 3 Problems34316.4 The Generalized product Rule34416.4.1 Defective dollars34616.4.2 A Chess problem.34616.4.3 Permutations34716.5 The Division rule34716.5.1 Another Chess problem34816.5.2 Knights of the Round Table34916.5. 3 Problems35016.6 Counting Subsets35216.6.1 The Subset rule35216.6.2 Bit Sequences35316.7 Sequences with repetitions35316.7.1 Sequences of Subsets35316. 2 The Bookkeeper rule35416.7.3 A Word about Words35516.7.4 Problems35516.8 Magic Trick35616.8.1 The Secret35716.8.2 The Real secret.35916.8.3 Same Trick with Four cards?36016.8.4 Problems36116.9 Counting Practice: Poker Hands..36216.9.1 Hands with a Four-of-a-Kind36216.9.2 Hands with a full house.36316.9. 3 Hands with Two Pairs36416.9.4 Hands with Every suit3616.9.5 Problems..36610CONTENTS16.10Inclusion-Exclusion..36816.10.1 Union of Two Sets36816.10.2 Union of Three Sets..36916.10. 3 Union of n Sets37116. 10.4 Computing Euler's Function37216.10.5 Problems37316.11 Binomial Theorem37616.11.1 Problems37716.12 Combinatorial Proof38016.12. 1 Boxing38016.12.2 Finding a Combinatorial Proof38116.12. 3 Problems38217 Generating Functions38517.1 Operations on Generating Functions..38617.1.1 Scaling38617.1.2 Addition38717. 1.3 Right Shifting38817.1.4 Differentiation38817.1.5 Produc...39017.2 The Fibonacci Sequence39017. 2.1 Finding a Generating Function39117.2.2 Finding a Closed Form39217.2.3 Problems39317.3 Counting with Generating Functions..39817.3.1 Choosing Distinct Items from a Set39817.3.2 Building Generating Functions that Count39817.3.3 Choosing Items with Repetition.40017.3.4 Problems40117.4 An"Impossible"Counting problem.40317.4.1 Problems番垂40518 Introduction to Probability40918.1 Monty hall4018.1.1 The Four Step Method41018.1.2 Clarifying the Problem18.1.3 Step 1. Find the sample space41041118.1. 4 Step 2: Define Events of Interest41318.1.5 Step 3 Determine Outcome probabilities41418.1.6 Step 4: Compute Event Probabilities41618.1.7 An Alternative Interpretation of the Monty Hall Problem... 41718.1. 8 Problems.,41718.2 Set Theory and probability41918.2.1 Probability spaces42018.2.2 An Infinite Sample space.421