Mathematics for Computer Science - Computer Science and Engineering

1

Mathematics for Computer Science

revised May 9, 2010, 770 minutes

Prof. Albert R Meyer

Massachusets Institute of Technology

Creative Commons

2010, Prof. Albert R. Meyer.

2

Contents

1 What is a Proof?

13

1.1 Mathematical Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.1.1 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.2 Propositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.3 Predicates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

1.4 The Axiomatic Method . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

1.5 Our Axioms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

1.5.1 Logical Deductions . . . . . . . . . . . . . . . . . . . . . . . . 19

1.5.2 Patterns of Proof . . . . . . . . . . . . . . . . . . . . . . . . . . 20

1.6 Proving an Implication . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

1.6.1 Method #1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

1.6.2 Method #2 - Prove the Contrapositive . . . . . . . . . . . . . . 22

1.6.3 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

1.7 Proving an "If and Only If" . . . . . . . . . . . . . . . . . . . . . . . . 23

1.7.1 Method #1: Prove Each Statement Implies the Other . . . . . . 23

1.7.2 Method #2: Construct a Chain of Iffs . . . . . . . . . . . . . . . 23

1.8 Proof by Cases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

1.8.1 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

1.9 Proof by Contradiction . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

1.9.1 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

1.10 Good Proofs in Practice . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

2 The Well Ordering Principle

31

2.1 Well Ordering Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.2 Template for Well Ordering Proofs . . . . . . . . . . . . . . . . . . . . 32

2.2.1 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

2.3 Summing the Integers . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

2.3.1 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

2.4 Factoring into Primes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

3 Propositional Formulas

37

3.1 Propositions from Propositions . . . . . . . . . . . . . . . . . . . . . . 38

3.1.1 "Not", "And", and "Or" . . . . . . . . . . . . . . . . . . . . . . 38

3

4

CONTENTS

3.1.2 "Implies" . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

3.1.3 "If and Only If" . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

3.1.4 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

3.2 Propositional Logic in Computer Programs . . . . . . . . . . . . . . . 41

3.2.1 Cryptic Notation . . . . . . . . . . . . . . . . . . . . . . . . . . 42

3.2.2 Logically Equivalent Implications . . . . . . . . . . . . . . . . 43

3.2.3 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

4 Mathematical Data Types

51

4.1 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

4.1.1 Some Popular Sets . . . . . . . . . . . . . . . . . . . . . . . . . 52

4.1.2 Comparing and Combining Sets . . . . . . . . . . . . . . . . . 52

4.1.3 Complement of a Set . . . . . . . . . . . . . . . . . . . . . . . . 52

4.1.4 Power Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

4.1.5 Set Builder Notation . . . . . . . . . . . . . . . . . . . . . . . . 53

4.1.6 Proving Set Equalities . . . . . . . . . . . . . . . . . . . . . . . 54

4.1.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

4.2 Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

4.3 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

4.3.1 Function Composition . . . . . . . . . . . . . . . . . . . . . . . 57

4.4 Binary Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

4.5 Binary Relations and Functions . . . . . . . . . . . . . . . . . . . . . . 58

4.6 Images and Inverse Images . . . . . . . . . . . . . . . . . . . . . . . . 59

4.7 Surjective and Injective Relations . . . . . . . . . . . . . . . . . . . . . 60

4.7.1 Relation Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . 60

4.8 The Mapping Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

4.9 The sizes of infinite sets . . . . . . . . . . . . . . . . . . . . . . . . . . 62

4.9.1 Infinities in Computer Science . . . . . . . . . . . . . . . . . . 65

4.9.2 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

4.10 Glossary of Symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

5 First-Order Logic

73

5.1 Quantifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

5.1.1 More Cryptic Notation . . . . . . . . . . . . . . . . . . . . . . . 74

5.1.2 Mixing Quantifiers . . . . . . . . . . . . . . . . . . . . . . . . . 75

5.1.3 Order of Quantifiers . . . . . . . . . . . . . . . . . . . . . . . . 75

5.1.4 Negating Quantifiers . . . . . . . . . . . . . . . . . . . . . . . . 76

5.1.5 Validity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

5.1.6 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

5.2 The Logic of Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

5.2.1 Russell's Paradox . . . . . . . . . . . . . . . . . . . . . . . . . . 81

5.2.2 The ZFC Axioms for Sets . . . . . . . . . . . . . . . . . . . . . 81

5.2.3 Avoiding Russell's Paradox . . . . . . . . . . . . . . . . . . . . 83

5.2.4 Power sets are strictly bigger . . . . . . . . . . . . . . . . . . . 83

5.2.5 Does All This Really Work? . . . . . . . . . . . . . . . . . . . . 84

CONTENTS

5

5.2.6 Large Infinities in Computer Science . . . . . . . . . . . . . . . 85

5.2.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

5.3 Glossary of Symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

6 Induction

91

6.1 Ordinary Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

6.1.1 Using Ordinary Induction . . . . . . . . . . . . . . . . . . . . . 92

6.1.2 A Template for Induction Proofs . . . . . . . . . . . . . . . . . 93

6.1.3 A Clean Writeup . . . . . . . . . . . . . . . . . . . . . . . . . . 94

6.1.4 Courtyard Tiling . . . . . . . . . . . . . . . . . . . . . . . . . . 94

6.1.5 A Faulty Induction Proof . . . . . . . . . . . . . . . . . . . . . 97

6.1.6 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

6.2 Strong Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

6.2.1 Products of Primes . . . . . . . . . . . . . . . . . . . . . . . . . 103

6.2.2 Making Change . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

6.2.3 The Stacking Game . . . . . . . . . . . . . . . . . . . . . . . . . 104

6.2.4 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

6.3 Induction versus Well Ordering . . . . . . . . . . . . . . . . . . . . . . 107

7 Partial Orders

109

7.1 Axioms for Partial Orders . . . . . . . . . . . . . . . . . . . . . . . . . 109

7.2 Representing Partial Orders by Set Containment . . . . . . . . . . . . 111

7.2.1 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

7.3 Total Orders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

7.3.1 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

7.4 Product Orders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

7.4.1 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

7.5 Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

7.5.1 Parallel Task Scheduling . . . . . . . . . . . . . . . . . . . . . . 119

7.6 Dilworth's Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

7.6.1 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122

8 Directed graphs

129

8.1 Digraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129

8.1.1 Paths in Digraphs . . . . . . . . . . . . . . . . . . . . . . . . . . 130

8.2 Picturing Relational Properties . . . . . . . . . . . . . . . . . . . . . . 130

8.3 Composition of Relations . . . . . . . . . . . . . . . . . . . . . . . . . 131

8.4 Directed Acyclic Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 131

8.4.1 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132

9 State Machines

135

9.1 State machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135

9.1.1 Basic definitions . . . . . . . . . . . . . . . . . . . . . . . . . . 135

9.1.2 Reachability and Preserved Invariants . . . . . . . . . . . . . . 137

9.1.3 Sequential algorithm examples . . . . . . . . . . . . . . . . . . 140

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download