Mathematics for Computer Science.pdf

(5287 KB) Pobierz
1114488125.001.png
Mathematics for Computer Science
revised May 9, 2010,
Prof. Albert R Meyer
Massachusets Institute of Technology
©
2010, Prof. Albert R. Meyer
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

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin