Chapter 1 Logical Thinking 1
1.1 Formal Logic 2
1.1.1 Inquiry Problems 2
1.1.2 Connectives and Propositions 3
1.1.3 Truth Tables 5
1.1.4 Logical Equivalences 7
Exercises 1.1 10
1.2 Propositional Logic 15
1.2.1 Tautologies and Contradictions 16
1.2.2 Derivation Rules 18
1.2.3 Proof Sequences 20
1.2.4 Forward-Backward 22
Exercises 1.2 23
1.3 Predicate Logic 28
1.3.1 Predicates 29
1.3.2 Quantifiers 29
1.3.3 Translation 31
1.3.4 Negation 32
1.3.5 Two Common Constructions 34
Exercises 1.3 35
1.4 Logic in Mathematics 42
1.4.1 The Role of Definitions in Mathematics 42
1.4.2 Other Types of Mathematical Statements 44
1.4.3 Counterexamples 45
1.4.4 Axiomatic Systems 46
Exercises 1.4 50
1.5 Methods of Proof 54
1.5.1 Direct Proofs 55
1.5.2 Proof by Contraposition 57
1.5.3 Proof by Contradiction 59
Exercises 1.5 61
Chapter 2 Relational Thinking 65
2.1 Graphs 66
2.1.1 Edges and Vertices 66
2.1.2 Terminology 67
2.1.3 Modeling Relationships with Graphs 69
Exercises 2.1 75
2.2 Sets 81
2.2.1 Membership and Containment 82
2.2.2 New Sets from Old 83
2.2.3 Identities 86
Exercises 2.2 88
2.3 Functions 92
2.3.1 Definition and Examples 93
2.3.2 One-to-One and Onto Functions 97
2.3.3 New Functions from Old 101
Exercises 2.3 103
2.4 Relations and Equivalences 107
2.4.1 Definition and Examples 108
2.4.2 Graphs of Relations 108
2.4.3 Relations vs.Functions 109
2.4.4 Equivalence Relations 111
2.4.5 Modular Arithmetic 114
Exercises 2.4 116
2.5 Partial Orderings 121
2.5.1 Definition and Examples 122
2.5.2 Hasse Diagrams 123
2.5.3 Topological Sorting 124
2.5.4 Isomorphisms 126
2.5.5 Boolean Algebras ？ 129
Exercises 2.5 131
2.6 Graph Theory 136
2.6.1 Graphs：Formal Definitions 136
2.6.2 Isomorphisms of Graphs 137
2.6.3 Degree Counting 139
2.6.4 Euler Paths and Circuits 140
2.6.5 Hamilton Paths and Circuits 141
2.6.6 Trees 144
Exercises 2.6 147
Chapter 3 Recursive Thinking 151
3.1 Recurrence Relations 152
3.1.1 Definition and Examples 153
3.1.2 The Fibonacci Sequence 154
3.1.3 Modeling with Recurrence Relations 155
Exercises 3.1 159
3.2 Closed-Form Solutions and Induction 163
3.2.1 Guessing a Closed-Form Solution 164
3.2.2 Polynomial Sequences：Using Differences？ 165
3.2.3 Inductively Verifying a Solution 167
Exercises 3.2 171
3.3 Recursive Definitions 175
3.3.1 Definition and Examples 176
3.3.2 Writing Recursive Definitions 180
3.3.3 Recursive Geometry 181
3.3.4 Recursive Jokes 185
Exercises 3.3 185
3.4 Proof by Induction 190
3.4.1 The Principle of Induction 191
3.4.2 Examples 192
3.4.3 Strong Induction 197
3.4.4 Structural Induction 200
Exercises 3.4 202
3.5 Recursive Data Structures 205
3.5.1 Lists 206
3.5.2 Efficiency 210
3.5.3 Binary Search Trees Revisited 212
Exercises 3.5 213
Chapter 4 Quantitative Thinking 219
4.1 Basic Counting Techniques 220
4.1.1 Addition 220
4.1.2 Multiplication 221
4.1.3 Mixing Addition and Multiplication 225
Exercises 4.1 227
4.2 Selections and Arrangements 231
4.2.1 Permutations：The Arrangement Principle 232
4.2.2 Combinations：The Selection Principle 234
4.2.3 The Binomial Theorem？ 237
Exercises 4.2 239
4.3 Counting with Functions 244
4.3.1 One-to-One Correspondences 244
4.3.2 The Pigeonhole Principle 248
4.3.3 The Generalized Pigeonhole Principle 249
4.3.4 Ramsey Theory？ 250
Exercises 4.3 251
4.4 Discrete Probability 257
4.4.1 Definitions and Examples 257
4.4.2 Applications 259
4.4.3 Expected Value 262
Exercises 4.4 264
4.5 Counting Operations in Algorithms 268
4.5.1 Algorithms 269
4.5.2 Pseudocode 269
4.5.3 Sequences of Operations 271
4.5.4 Loops 271
4.5.5 Arrays 274
4.5.6 Sorting 276
Exercises 4.5 278
4.6 Estimation 283
4.6.1 Growth of Functions 283
4.6.2 Estimation Targets 288
4.6.3 Properties of Big-？ 289
Exercises 4.6 291
Chapter 5 Analytical Thinking 295
5.1 Algorithms 296
5.1.1 More Pseudocode 296
5.1.2 Preconditions and Postconditions 298
5.1.3 Iterative Algorithms 300
5.1.4 Functions and Recursive Algorithms 301
Exercises 5.1 305
5.2 Three Common Types of Algorithms 309
5.2.1 Traversal Algorithms 310
5.2.2 Greedy Algorithms 314
5.2.3 Divide-and-Conquer Algorithms 317
Exercises 5.2 320
5.3 Algorithm Complexity 325
5.3.1 The Good，the Bad，and the Average 326
5.3.2 Approximate Complexity Calculations 330
Exercises 5.3 333
5.4 Bounds on Complexity 339
5.4.1 Algorithms as Decisions 339
5.4.2 A Lower Bound 342
5.4.3 Searching an Array 343
5.4.4 Sorting 344
5.4.5 P vs.NP 345
Exercises 5.4 346
5.5 Program Verification 350
5.5.1 Verification vs.Testing 351
5.5.2 Verifying Recursive Algorithms 351
5.5.3 Searching and Sorting 354
5.5.4 Towers of Hanoi 356
Exercises 5.5 358
5.6 Loop Invariants 362
5.6.1 Verifying Iterative Algorithms 363
5.6.2 Searching and Sorting 366
5.6.3 Using Invariants to Design Algorithms 370
Exercises 5.6 371
Chapter 6 Thinking Through Applications 377
6.1 Patterns in DNA 378
6.1.1 Mutations and Phylogenetic Distance 379
6.1.2 Phylogenetic Trees 380
6.1.3 UPGMA 382
Exercises 6.1 386
6.2 Social Networks 388
6.2.1 Definitions and Terminology 388
6.2.2 Notions of Equivalence 390
6.2.3 Hierarchical Clustering 394
6.2.4 Signed Graphs and Balance 396
Exercises 6.2 400
6.3 Structure of Languages 402
6.3.1 Terminology 403
6.3.2 Finite-State Machines 404
6.3.3 Recursion 407
6.3.4 Further Issues in Linguistics 411
Exercises 6.3 412
6.4 Discrete-Time Population Models 414
6.4.1 Recursive Models for Population Growth 415
6.4.2 Fixed Points，Equilibrium，and Chaos 417
6.4.3 Predator-Prey Systems 419
6.4.4 The SIR Model 421
Exercises 6.4 423
6.5 Twelve-Tone Music 426
6.5.1 Twelve-Tone Composition 426
6.5.2 Listing All Permutations 427
6.5.3 Transformations of Tone Rows 429
6.5.4 Equivalence Classes and Symmetry 430
Exercises 6.5 432
Hints，Answers，and Solutions to Selected Exercises 435
1.1 Formal Logic 435
1.2 Propositional Logic 437
1.3 Predicate Logic 439
1.4 Logic in Mathematics 441
1.5 Methods of Proof 442
2.1 Graphs 444
2.2 Sets 445
2.3 Functions 446
2.4 Relations and Equivalences 448
2.5 Partial Orderings 450
2.6 Graph Theory 453
3.1 Recurrence Relations 454
3.2 Closed-Form Solutions and Induction 455
3.3 Recursive Definitions 458
3.4 Proof by Induction 459
3.5 Recursive Data Structures 462
4.1 Basic Counting Techniques 463
4.2 Selections and Arrangements 464
4.3 Counting with Functions 465
4.4 Discrete Probability 466
4.5 Counting Operations in Algorithms 467
4.6 Estimation 469
5.1 Algorithms 470
5.2 Three Common Types of Algorithms 471
5.3 Algorithm Complexity 473
5.4 Bounds on Complexity 474
5.5 Program Verification 475
5.6 Loop Invariants 476
Selected References 479
Index 483
Index of Symbols 491