《Discrete mathematics using a Computer (2nd Edition)》

【实例截图】

【核心代码】

Contents
I Programming and Reasoning with Equations 1
1 Introduction to Haskell . . . . . . . . . . . . . . . . . . . . . . . 3
1.1 Obtaining and Running Haskell . . . . . . . . . . . . . . . . . 4
1.2 Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.1 Integer and Int . . . . . . . . . . . . . . . . . . . . . 6
1.2.2 Rational and Floating Point Numbers . . . . . . . . . 8
1.2.3 Booleans . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.4 Characters . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.5 Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3 Basic Data Structures: Tuples and Lists . . . . . . . . . . . . . 11
1.3.1 Tuples . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3.2 Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3.3 List Notation and (:) . . . . . . . . . . . . . . . . . . 12
1.3.4 List Comprehensions . . . . . . . . . . . . . . . . . . . 13
1.4 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.4.1 Function Application . . . . . . . . . . . . . . . . . . . 15
1.4.2 Function Types . . . . . . . . . . . . . . . . . . . . . . 15
1.4.3 Operators and Functions . . . . . . . . . . . . . . . . . 16
1.4.4 Function Definitions . . . . . . . . . . . . . . . . . . . 16
1.4.5 Pattern Matching . . . . . . . . . . . . . . . . . . . . . 17
1.4.6 Higher Order Functions . . . . . . . . . . . . . . . . . 19
1.5 Conditional Expressions . . . . . . . . . . . . . . . . . . . . . . 20
1.6 Local Variables: let Expressions . . . . . . . . . . . . . . . . . 21
1.7 Type Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.8 Common Functions on Lists . . . . . . . . . . . . . . . . . . . 22
1.9 Data Type Definitions . . . . . . . . . . . . . . . . . . . . . . . 28
1.10 Type Classes and Overloading . . . . . . . . . . . . . . . . . . 31
1.11 Suggestions for Further Reading . . . . . . . . . . . . . . . . . 33
1.12 Review Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . 33
xiii
xiv CONTENTS
2 Equational Reasoning . . . . . . . . . . . . . . . . . . . . . . . . 37
2.1 Equations and Substitutions . . . . . . . . . . . . . . . . . . . 37
2.2 Equational Reasoning as Hand-execution . . . . . . . . . . . . 38
2.2.1 Conditionals . . . . . . . . . . . . . . . . . . . . . . . . 41
2.3 Equational Reasoning with Lists . . . . . . . . . . . . . . . . . 42
2.4 The Role of the Language . . . . . . . . . . . . . . . . . . . . . 43
2.5 Rigor and Formality in Proofs . . . . . . . . . . . . . . . . . . 44
3 Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.1 Recursion Over Lists . . . . . . . . . . . . . . . . . . . . . . . 48
3.2 Higher Order Recursive Functions . . . . . . . . . . . . . . . . 54
3.3 Peano Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.4 Data Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.5 Suggestions for Further Reading . . . . . . . . . . . . . . . . . 59
3.6 Review Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4 Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.1 The Principle of Mathematical Induction . . . . . . . . . . . . 62
4.2 Examples of Induction on Natural Numbers . . . . . . . . . . . 63
4.3 Induction and Recursion . . . . . . . . . . . . . . . . . . . . . 66
4.4 Induction on Peano Naturals . . . . . . . . . . . . . . . . . . . 67
4.5 Induction on Lists . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.6 Functional Equality . . . . . . . . . . . . . . . . . . . . . . . . 76
4.7 Pitfalls and Common Mistakes . . . . . . . . . . . . . . . . . . 78
4.7.1 A Horse of Another Colour . . . . . . . . . . . . . . . 78
4.8 Limitations of Induction . . . . . . . . . . . . . . . . . . . . . 78
4.9 Suggestions for Further Reading . . . . . . . . . . . . . . . . . 80
4.10 Review Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . 81
5 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5.1 Components of a Tree . . . . . . . . . . . . . . . . . . . . . . . 83
5.2 Representing Trees in Haskell . . . . . . . . . . . . . . . . . . . 86
5.3 Processing Trees with Recursion . . . . . . . . . . . . . . . . . 88
5.3.1 Tree Traversal . . . . . . . . . . . . . . . . . . . . . . . 89
5.3.2 Processing Tree Structure . . . . . . . . . . . . . . . . 90
5.3.3 Evaluating Expression Trees . . . . . . . . . . . . . . . 92
5.3.4 Binary Search Trees . . . . . . . . . . . . . . . . . . . 92
5.4 Induction on Trees . . . . . . . . . . . . . . . . . . . . . . . . . 96
5.4.1 Repeated Reflection Theorem . . . . . . . . . . . . . . 96
5.4.2 Reflection and Reversing . . . . . . . . . . . . . . . . . 97
5.4.3 The Height of a Balanced Tree . . . . . . . . . . . . . 98
5.4.4 Length of a Flattened Tree . . . . . . . . . . . . . . . . 99
5.5 Improving Execution Time . . . . . . . . . . . . . . . . . . . . 100
5.6 Flattening Trees in Linear Time . . . . . . . . . . . . . . . . . 103
CONTENTS xv
II Logic 107
6 Propositional Logic . . . . . . . . . . . . . . . . . . . . . . . . . . 109
6.1 The Need for Formalism . . . . . . . . . . . . . . . . . . . . . 111
6.2 The Basic Logical Operators . . . . . . . . . . . . . . . . . . . 112
6.2.1 Logical And (∧) . . . . . . . . . . . . . . . . . . . . . . 113
6.2.2 Inclusive Logical Or (∨) . . . . . . . . . . . . . . . . . 114
6.2.3 Exclusive Logical Or (⊗) . . . . . . . . . . . . . . . . . 115
6.2.4 Logical Not (¬) . . . . . . . . . . . . . . . . . . . . . . 115
6.2.5 Logical Implication (→) . . . . . . . . . . . . . . . . . 115
6.2.6 Logical Equivalence (↔) . . . . . . . . . . . . . . . . . 117
6.3 The Language of Propositional Logic . . . . . . . . . . . . . . 118
6.3.1 The Syntax of Well-Formed Formulas . . . . . . . . . . 118
6.3.2 Precedence of Logical Operators . . . . . . . . . . . . . 120
6.3.3 Object Language and Meta-Language . . . . . . . . . 120
6.3.4 Computing with Boolean Expressions . . . . . . . . . . 121
6.4 Truth Tables: Semantic Reasoning . . . . . . . . . . . . . . . . 122
6.4.1 Truth Table Calculations and Proofs . . . . . . . . . . 123
6.4.2 Limitations of Truth Tables . . . . . . . . . . . . . . . 124
6.4.3 Computing Truth Tables . . . . . . . . . . . . . . . . . 125
6.5 Natural Deduction: Inference Reasoning . . . . . . . . . . . . . 126
6.5.1 Definitions of True, ¬, and ↔ . . . . . . . . . . . . . . 128
6.5.2 And Introduction {∧I} . . . . . . . . . . . . . . . . . . 129
6.5.3 And Elimination {∧E L }, {∧E R } . . . . . . . . . . . . 131
6.5.4 Imply Elimination {→ E} . . . . . . . . . . . . . . . . 132
6.5.5 Imply Introduction {→ I} . . . . . . . . . . . . . . . . 133
6.5.6 Or Introduction {∨I L }, {∨I R } . . . . . . . . . . . . . . 136
6.5.7 Or Elimination {∨E} . . . . . . . . . . . . . . . . . . . 137
6.5.8 Identity {ID} . . . . . . . . . . . . . . . . . . . . . . . 138
6.5.9 Contradiction {CTR} . . . . . . . . . . . . . . . . . . 138
6.5.10 Reductio ad Absurdum {RAA} . . . . . . . . . . . . . 140
6.5.11 Inferring the Operator Truth Tables . . . . . . . . . . 141
6.6 Proof Checking by Computer . . . . . . . . . . . . . . . . . . . 142
6.6.1 Example of Proof Checking . . . . . . . . . . . . . . . 143
6.6.2 Representation of WFFs . . . . . . . . . . . . . . . . . 146
6.6.3 Representing Proofs . . . . . . . . . . . . . . . . . . . 147
6.7 Boolean Algebra: Equational Reasoning . . . . . . . . . . . . . 149
6.7.1 The Laws of Boolean Algebra . . . . . . . . . . . . . . 150
6.7.2 Operations with Constants . . . . . . . . . . . . . . . . 151
6.7.3 Basic Properties of ∧ and ∨ . . . . . . . . . . . . . . . 153
6.7.4 Distributive and DeMorgan’s Laws . . . . . . . . . . . 154
6.7.5 Laws on Negation . . . . . . . . . . . . . . . . . . . . . 154
6.7.6 Laws on Implication . . . . . . . . . . . . . . . . . . . 155
6.7.7 Equivalence . . . . . . . . . . . . . . . . . . . . . . . . 156
6.8 Logic in Computer Science . . . . . . . . . . . . . . . . . . . . 156
xvi CONTENTS
6.9 Meta-Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
6.10 Suggestions for Further Reading . . . . . . . . . . . . . . . . . 159
6.11 Review Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . 161
7 Predicate Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
7.1 The Language of Predicate Logic . . . . . . . . . . . . . . . . . 163
7.1.1 Predicates . . . . . . . . . . . . . . . . . . . . . . . . . 163
7.1.2 Quantifiers . . . . . . . . . . . . . . . . . . . . . . . . . 164
7.1.3 Expanding Quantified Expressions . . . . . . . . . . . 166
7.1.4 The Scope of Variable Bindings . . . . . . . . . . . . . 168
7.1.5 Translating Between English and Logic . . . . . . . . . 169
7.2 Computing with Quantifiers . . . . . . . . . . . . . . . . . . . 172
7.3 Logical Inference with Predicates . . . . . . . . . . . . . . . . . 174
7.3.1 Universal Introduction {∀I} . . . . . . . . . . . . . . . 175
7.3.2 Universal Elimination {∀E} . . . . . . . . . . . . . . . 177
7.3.3 Existential Introduction {∃I} . . . . . . . . . . . . . . 179
7.3.4 Existential Elimination {∃E} . . . . . . . . . . . . . . 180
7.4 Algebraic Laws of Predicate Logic . . . . . . . . . . . . . . . . 181
7.5 Suggestions for Further Reading . . . . . . . . . . . . . . . . . 183
7.6 Review Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . 184
III Set Theory 187
8 Set Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
8.1 Notations for Describing Sets . . . . . . . . . . . . . . . . . . . 189
8.2 Basic Operations on Sets . . . . . . . . . . . . . . . . . . . . . 192
8.2.1 Subsets and Set Equality . . . . . . . . . . . . . . . . . 192
8.2.2 Union, Intersection, and Difference . . . . . . . . . . . 192
8.2.3 Complement and Power . . . . . . . . . . . . . . . . . 194
8.3 Finite Sets with Equality . . . . . . . . . . . . . . . . . . . . . 196
8.3.1 Computing with Sets . . . . . . . . . . . . . . . . . . . 198
8.4 Set Laws . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
8.4.1 Associative and Commutative Set Operations . . . . . 201
8.4.2 Distributive Laws . . . . . . . . . . . . . . . . . . . . . 202
8.4.3 DeMorgan’s Laws for Sets . . . . . . . . . . . . . . . . 202
8.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
8.6 Suggestions for Further Reading . . . . . . . . . . . . . . . . . 205
8.7 Review Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . 205
9 Inductively Defined Sets . . . . . . . . . . . . . . . . . . . . . . . 207
9.1 The Idea Behind Induction . . . . . . . . . . . . . . . . . . . . 207
9.1.1 The Induction Rule . . . . . . . . . . . . . . . . . . . . 210
9.2 How to Define a Set Using Induction . . . . . . . . . . . . . . 212
9.2.1 Inductive Definition of the Set of Natural Numbers . . 213
CONTENTS xvii
9.2.2 The Set of Binary Machine Words . . . . . . . . . . . 214
9.3 Defining the Set of Integers . . . . . . . . . . . . . . . . . . . . 215
9.3.1 First Attempt . . . . . . . . . . . . . . . . . . . . . . . 215
9.3.2 Second Attempt . . . . . . . . . . . . . . . . . . . . . . 216
9.3.3 Third Attempt . . . . . . . . . . . . . . . . . . . . . . 216
9.3.4 Fourth Attempt . . . . . . . . . . . . . . . . . . . . . . 218
9.3.5 Fifth Attempt . . . . . . . . . . . . . . . . . . . . . . . 219
9.4 Suggestions for Further Reading . . . . . . . . . . . . . . . . . 219
9.5 Review Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . 219
10 Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
10.1 Binary Relations . . . . . . . . . . . . . . . . . . . . . . . . . . 223
10.2 Representing Relations with Digraphs . . . . . . . . . . . . . . 225
10.3 Computing with Binary Relations . . . . . . . . . . . . . . . . 226
10.4 Properties of Relations . . . . . . . . . . . . . . . . . . . . . . 228
10.4.1 Reflexive Relations . . . . . . . . . . . . . . . . . . . . 228
10.4.2 Irreflexive Relations . . . . . . . . . . . . . . . . . . . 229
10.4.3 Symmetric Relations . . . . . . . . . . . . . . . . . . . 231
10.4.4 Antisymmetric Relations . . . . . . . . . . . . . . . . . 233
10.4.5 Transitive Relations . . . . . . . . . . . . . . . . . . . 235
10.5 Relational Composition . . . . . . . . . . . . . . . . . . . . . . 237
10.6 Powers of Relations . . . . . . . . . . . . . . . . . . . . . . . . 240
10.7 Closure Properties of Relations . . . . . . . . . . . . . . . . . . 245
10.7.1 Reflexive Closure . . . . . . . . . . . . . . . . . . . . . 246
10.7.2 Symmetric Closure . . . . . . . . . . . . . . . . . . . . 248
10.7.3 Transitive Closure . . . . . . . . . . . . . . . . . . . . 249
10.8 Order Relations . . . . . . . . . . . . . . . . . . . . . . . . . . 252
10.8.1 Partial Order . . . . . . . . . . . . . . . . . . . . . . . 252
10.8.2 Quasi Order . . . . . . . . . . . . . . . . . . . . . . . . 257
10.8.3 Linear Order . . . . . . . . . . . . . . . . . . . . . . . 258
10.8.4 Well Order . . . . . . . . . . . . . . . . . . . . . . . . . 259
10.8.5 Topological Sort . . . . . . . . . . . . . . . . . . . . . . 260
10.9 Equivalence Relations . . . . . . . . . . . . . . . . . . . . . . . 261
10.10 Suggestions for Further Reading . . . . . . . . . . . . . . . . . 264
10.11 Review Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . 264
11 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267
11.1 The Graph of a Function . . . . . . . . . . . . . . . . . . . . . 268
11.2 Functions in Programming . . . . . . . . . . . . . . . . . . . . 271
11.2.1 Inductively Defined Functions . . . . . . . . . . . . . . 272
11.2.2 Primitive Recursion . . . . . . . . . . . . . . . . . . . . 273
11.2.3 Computational Complexity . . . . . . . . . . . . . . . 274
11.2.4 State . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275
11.3 Higher Order Functions . . . . . . . . . . . . . . . . . . . . . . 276
11.3.1 Functions That Take Functions as Arguments . . . . . 277
xviii CONTENTS
11.3.2 Functions That Return Functions . . . . . . . . . . . . 278
11.3.3 Multiple Arguments as Tuples . . . . . . . . . . . . . . 280
11.3.4 Multiple Results as a Tuple . . . . . . . . . . . . . . . 281
11.3.5 Multiple Arguments with Higher Order Functions . . . 281
11.4 Total and Partial Functions . . . . . . . . . . . . . . . . . . . . 282
11.5 Function Composition . . . . . . . . . . . . . . . . . . . . . . . 287
11.6 Properties of Functions . . . . . . . . . . . . . . . . . . . . . . 291
11.6.1 Surjective Functions . . . . . . . . . . . . . . . . . . . 291
11.6.2 Injective Functions . . . . . . . . . . . . . . . . . . . . 293
11.6.3 The Pigeonhole Principle . . . . . . . . . . . . . . . . . 296
11.7 Bijective Functions . . . . . . . . . . . . . . . . . . . . . . . . 296
11.7.1 Permutations . . . . . . . . . . . . . . . . . . . . . . . 297
11.7.2 Inverse Functions . . . . . . . . . . . . . . . . . . . . . 299
11.8 Cardinality of Sets . . . . . . . . . . . . . . . . . . . . . . . . . 299
11.8.1 The Rational Numbers Are Countable . . . . . . . . . 302
11.8.2 The Real Numbers Are Uncountable . . . . . . . . . . 302
11.9 Suggestions for Further Reading . . . . . . . . . . . . . . . . . 304
11.10 Review Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . 304
IV Applications 311
12 The AVL Tree Miracle . . . . . . . . . . . . . . . . . . . . . . . . 313
12.1 How to Find a Folder . . . . . . . . . . . . . . . . . . . . . . . 313
12.2 The Filing Cabinet Advantage . . . . . . . . . . . . . . . . . . 314
12.3 The New-File Problem . . . . . . . . . . . . . . . . . . . . . . 315
12.4 The AVL Miracle . . . . . . . . . . . . . . . . . . . . . . . . . 316
12.5 Search Trees and Occurrence of Keys . . . . . . . . . . . . . . 317
12.5.1 Ordered Search Trees and Tree Induction . . . . . . . 319
12.5.2 Retrieving Data from a Search Tree . . . . . . . . . . . 324
12.5.3 Search Time in the Equational Model . . . . . . . . . 326
12.6 Balanced Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . 329
12.6.1 Rebalancing in the Easy Cases . . . . . . . . . . . . . 332
12.6.2 Rebalancing in the Hard Cases . . . . . . . . . . . . . 336
12.6.3 Rebalancing Left-Heavy and Right-Heavy Trees . . . . 338
12.6.4 Inductive Equations for Insertion . . . . . . . . . . . . 339
12.6.5 Insertion in Logarithmic Time . . . . . . . . . . . . . . 342
12.6.6 Deletion . . . . . . . . . . . . . . . . . . . . . . . . . . 344
12.6.7 Shrinking the Spine . . . . . . . . . . . . . . . . . . . . 347
12.6.8 Equations for Deleting Root . . . . . . . . . . . . . . . 349
12.6.9 Equations for Deletion . . . . . . . . . . . . . . . . . . 350
12.6.10 Deletion in Logarithmic Time . . . . . . . . . . . . . . 351
12.7 Things We Didn’t Tell You . . . . . . . . . . . . . . . . . . . . 352
CONTENTS xix
13 Discrete Mathematics in Circuit Design . . . . . . . . . . . . . 355
13.1 Boolean Logic Gates . . . . . . . . . . . . . . . . . . . . . . . . 356
13.2 Functional Circuit Specification . . . . . . . . . . . . . . . . . 357
13.2.1 Circuit Simulation . . . . . . . . . . . . . . . . . . . . 358
13.2.2 Circuit Synthesis from Truth Tables . . . . . . . . . . 359
13.2.3 Multiplexors . . . . . . . . . . . . . . . . . . . . . . . . 362
13.2.4 Bit Arithmetic . . . . . . . . . . . . . . . . . . . . . . 363
13.2.5 Binary Representation . . . . . . . . . . . . . . . . . . 366
13.3 Ripple Carry Addition . . . . . . . . . . . . . . . . . . . . . . 367
13.3.1 Circuit Patterns . . . . . . . . . . . . . . . . . . . . . . 369
13.3.2 The n-Bit Ripple Carry Adder . . . . . . . . . . . . . 370
13.3.3 Correctness of the Ripple Carry Adder . . . . . . . . . 371
13.3.4 Binary Comparison . . . . . . . . . . . . . . . . . . . . 372
13.4 Suggestions for Further Reading . . . . . . . . . . . . . . . . . 374
13.5 Review Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . 374
A Software Tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377
B Resources on the Web . . . . . . . . . . . . . . . . . . . . . . . . 379
C Solutions to Selected Exercises . . . . . . . . . . . . . . . . . . . 381
C.1 Introduction to Haskell . . . . . . . . . . . . . . . . . . . . . . 381
C.3 Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384
C.4 Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 387
C.5 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397
C.6 Propositional Logic . . . . . . . . . . . . . . . . . . . . . . . . 398
C.7 Predicate Logic . . . . . . . . . . . . . . . . . . . . . . . . . . 411
C.8 Set Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417
C.9 Inductively Defined Sets . . . . . . . . . . . . . . . . . . . . . . 420
C.10 Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422
C.11 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424
C.13 Discrete Mathematics in Circuit Design . . . . . . . . . . . . . 428
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434