Essentials Of Discrete Mathematics

Title Page......Page 2
Copyright......Page 3
Contents......Page 5
Preface......Page 11
How to Use This Book......Page 15
Chapter 1 Logical Thinking......Page 18
 1.1 Formal Logic......Page 19
  1.1.2 Connectives and Propositions......Page 20
  1.1.3 Truth Tables......Page 22
  1.1.4 Logical Equivalences......Page 24
  Exercises 1.1......Page 27
 1.2 Propositional Logic......Page 33
  1.2.1 Tautologies and Contradictions......Page 34
  1.2.2 Derivation Rules......Page 37
  1.2.3 Proof Sequences......Page 38
  1.2.4 Forward–Backward......Page 40
  Exercises 1.2......Page 41
 1.3 Predicate Logic......Page 46
  1.3.2 Quantifiers......Page 47
  1.3.3 Translation......Page 49
  1.3.4 Negation......Page 50
  1.3.5 Two Common Constructions......Page 53
  Exercises 1.3......Page 54
 1.4 Logic in Mathematics......Page 60
  1.4.1 The Role of Definitions in Mathematics......Page 61
  1.4.3 Counterexamples......Page 63
  1.4.4 Axiomatic Systems......Page 64
  Exercises 1.4......Page 68
 1.5 Methods of Proof......Page 72
  1.5.1 Direct Proofs......Page 73
  1.5.2 Proof by Contraposition......Page 75
  1.5.3 Proof by Contradiction......Page 77
  Exercises 1.5......Page 79
 2.1 Graphs......Page 83
  2.1.1 Edges and Vertices......Page 84
  2.1.2 Terminology......Page 85
  2.1.3 Modeling Relationships with Graphs......Page 87
  Exercises 2.1......Page 93
 2.2 Sets......Page 99
  2.2.1 Membership and Containment......Page 100
  2.2.2 New Sets from Old......Page 102
  2.2.3 Identities......Page 105
  Exercises 2.2......Page 107
 2.3 Functions......Page 111
  2.3.1 Definition and Examples......Page 112
  2.3.2 One-to-One and Onto Functions......Page 116
  2.3.3 New Functions from Old......Page 120
  Exercises 2.3......Page 122
  2.4.1 Definition and Examples......Page 127
  2.4.2 Graphs of Relations......Page 128
  2.4.3 Relations vs. Functions......Page 129
  2.4.4 Equivalence Relations......Page 131
  2.4.5 Modular Arithmetic......Page 134
  Exercises 2.4......Page 136
 2.5 Partial Orderings......Page 140
  2.5.1 Definition and Examples......Page 141
  2.5.2 Hasse Diagrams......Page 142
  2.5.3 Topological Sorting......Page 143
  2.5.4 Isomorphisms......Page 145
  2.5.5 Boolean Algebras‡......Page 149
  Exercises 2.5......Page 150
 2.6 Graph Theory......Page 154
  2.6.1 Graphs: Formal Definitions......Page 155
  2.6.2 Isomorphisms of Graphs......Page 156
  2.6.3 Degree Counting......Page 158
  2.6.4 Euler Paths and Circuits......Page 159
  2.6.5 Hamilton Paths and Circuits......Page 160
  2.6.6 Trees......Page 162
  Exercises 2.6......Page 165
Chapter 3 Recursive Thinking......Page 170
 3.1 Recurrence Relations......Page 171
  3.1.1 Definition and Examples......Page 172
  3.1.2 The Fibonacci Sequence......Page 173
  3.1.3 Modeling with Recurrence Relations......Page 175
  Exercises 3.1......Page 179
 3.2 Closed-Form Solutions and Induction......Page 184
  3.2.1 Guessing a Closed-Form Solution......Page 185
  3.2.2 Polynomial Sequences: Using Differences‡......Page 186
  3.2.3 Inductively Verifying a Solution......Page 188
  Exercises 3.2......Page 193
 3.3 Recursive Definitions......Page 196
  3.3.1 Definition and Examples......Page 198
  3.3.2 Writing Recursive Definitions......Page 202
  3.3.3 Recursive Geometry......Page 203
  3.3.4 Recursive Jokes......Page 207
  Exercises 3.3......Page 208
 3.4 Proof by Induction......Page 213
  3.4.1 The Principle of Induction......Page 214
  3.4.2 Examples......Page 215
  3.4.3 Strong Induction......Page 220
  3.4.4 Structural Induction......Page 224
  Exercises 3.4......Page 225
 3.5 Recursive Data Structures......Page 229
  3.5.1 Lists......Page 230
  3.5.2 Efficiency......Page 235
  3.5.3 Binary Search Trees Revisited......Page 236
  Exercises 3.5......Page 237
Chapter 4 Quantitative Thinking......Page 242
  4.1.1 Addition......Page 243
  4.1.2 Multiplication......Page 245
  4.1.3 Mixing Addition and Multiplication......Page 249
  Exercises 4.1......Page 251
 4.2 Selections and Arrangements......Page 255
  4.2.1 Permutations: The Arrangement Principle......Page 256
  4.2.2 Combinations: The Selection Principle......Page 258
  4.2.3 The Binomial Theorem‡......Page 261
  Exercises 4.2......Page 263
 4.3 Counting with Functions......Page 267
  4.3.1 One-to-One Correspondences......Page 268
  4.3.2 The Pigeonhole Principle......Page 272
  4.3.3 The Generalized Pigeonhole Principle......Page 273
  4.3.4 Ramsey Theory‡......Page 274
  Exercises 4.3......Page 275
  4.4.1 Definitions and Examples......Page 281
  4.4.2 Applications......Page 283
  4.4.3 Expected Value......Page 286
  Exercises 4.4......Page 287
 4.5 Counting Operations in Algorithms......Page 291
  4.5.2 Pseudocode......Page 292
  4.5.3 Sequences of Operations......Page 293
  4.5.4 Loops......Page 294
  4.5.5 Arrays......Page 297
  4.5.6 Sorting......Page 299
  Exercises 4.5......Page 300
 4.6 Estimation......Page 305
  4.6.1 Growth of Functions......Page 306
  4.6.2 Estimation Targets......Page 312
  4.6.3 Properties of Big-Θ......Page 313
  Exercises 4.6......Page 314
Chapter 5 Analytical Thinking......Page 318
 5.1 Algorithms......Page 319
  5.1.1 More Pseudocode......Page 320
  5.1.2 Preconditions and Postconditions......Page 321
  5.1.3 Iterative Algorithms......Page 323
  5.1.4 Functions and Recursive Algorithms......Page 325
  Exercises 5.1......Page 328
  5.2.1 Traversal Algorithms......Page 333
  5.2.2 Greedy Algorithms......Page 338
  5.2.3 Divide-and-Conquer Algorithms......Page 341
  Exercises 5.2......Page 344
 5.3 Algorithm Complexity......Page 349
  5.3.1 The Good, the Bad, and the Average......Page 350
  5.3.2 Approximate Complexity Calculations......Page 354
  Exercises 5.3......Page 357
  5.4.1 Algorithms as Decisions......Page 363
  5.4.2 A Lower Bound......Page 366
  5.4.3 Searching an Array......Page 367
  5.4.4 Sorting......Page 368
  5.4.5 P vs. NP......Page 369
  Exercises 5.4......Page 370
 5.5 Program Verification......Page 373
  5.5.2 Verifying Recursive Algorithms......Page 374
  5.5.3 Searching and Sorting......Page 377
  5.5.4 Towers of Hanoi......Page 379
  Exercises 5.5......Page 381
 5.6 Loop Invariants......Page 385
  5.6.1 Verifying Iterative Algorithms......Page 386
  5.6.2 Searching and Sorting......Page 389
  5.6.3 Using Invariants to Design Algorithms......Page 393
  Exercises 5.6......Page 394
Chapter 6 Thinking Through Applications......Page 400
  6.1.1 Mutations and Phylogenetic Distance......Page 402
  6.1.2 Phylogenetic Trees......Page 403
  6.1.3 UPGMA......Page 405
  Exercises 6.1......Page 409
  6.2.1 Definitions and Terminology......Page 411
  6.2.2 Notions of Equivalence......Page 413
  6.2.3 Hierarchical Clustering......Page 417
  6.2.4 Signed Graphs and Balance......Page 420
  Exercises 6.2......Page 424
 6.3 Structure of Languages......Page 426
  6.3.1 Terminology......Page 427
  6.3.2 Finite-State Machines......Page 428
  6.3.3 Recursion......Page 431
  Exercises 6.3......Page 435
 6.4 Discrete-Time Population Models......Page 437
  6.4.1 Recursive Models for Population Growth......Page 438
  6.4.2 Fixed Points, Equilibrium, and Chaos......Page 440
  6.4.3 Predator–Prey Systems......Page 442
  6.4.4 The SIR Model......Page 445
  Exercises 6.4......Page 447
  6.5.1 Twelve-Tone Composition......Page 450
  6.5.2 Listing All Permutations......Page 451
  6.5.3 Transformations of Tone Rows......Page 453
  6.5.4 Equivalence Classes and Symmetry......Page 454
  Exercises 6.5......Page 456
 1.1 Formal Logic......Page 459
 1.2 Propositional Logic......Page 462
 1.3 Predicate Logic......Page 465
 1.4 Logic in Mathematics......Page 466
 1.5 Methods of Proof......Page 467
 2.1 Graphs......Page 469
 2.2 Sets......Page 471
 2.3 Functions......Page 473
 2.4 Relations and Equivalences......Page 475
 2.5 Partial Orderings......Page 477
 2.6 Graph Theory......Page 480
 3.1 Recurrence Relations......Page 481
 3.2 Closed-Form Solutions and Induction......Page 483
 3.3 Recursive Definitions......Page 486
 3.4 Proof by Induction......Page 487
 3.5 Recursive Data Structures......Page 489
 4.1 Basic Counting Techniques......Page 491
 4.2 Selections and Arrangements......Page 492
 4.3 Counting with Functions......Page 493
 4.4 Discrete Probability......Page 494
 4.5 Counting Operations in Algorithms......Page 495
 4.6 Estimation......Page 498
 5.1 Algorithms......Page 499
 5.2 Three Common Types of Algorithms......Page 501
 5.3 Algorithm Complexity......Page 503
 5.4 Bounds on Complexity......Page 504
 5.5 Program Verification......Page 505
 5.6 Loop Invariants......Page 506
Selected References......Page 509
Index......Page 512
Index of Symbols......Page 523