Discrete Mathematics with Proof, 2nd Edition

Preface xiii

Acknowledgments xx

To The Student xxii

1 Introduction 1

1.1 What Is Discrete Mathematics? 1

1.1.1 A Break from the Past 3

1.2 The Stable Marriage Problem 3

1.2.1 Seeking a Solution 4

1.2.2 The Deferred Acceptance Algorithm 5

1.2.3 Some Concluding Comments 7

1.3 Other Examples 7

1.3.1 A Simple Counting and Probability Example 7

1.3.2 Sierpinski Curves 8

1.3.3 The Bridges of Konigsberg 9

1.3.4 Kirkman’s Schoolgirls 9

1.3.5 Finite-State Machines 10

1.3.6 The Set of Rational Numbers Is Countably Infinite 11

1.4 Exercises 13

1.5 Chapter Review 15

1.5.1 Summary 15

1.5.2 Notation 15

2 Sets, Logic, and Boolean Algebras 17

2.1 Sets 19

2.1.1 Definitions and Notation 19

2.1.2 Exercises 26

2.1.3 Proofs about Sets 29

2.1.4 Exercises 33

2.2 Logic in Daily Life 34

2.2.1 General Guidelines for Analyzing Claims 34

2.2.2 Informal Fallacies 35

2.2.3 Everyday Logic versus Symbolic Logic 37

2.2.4 Exercises 37

2.3 Propositional Logic 38

2.3.1 Truth Tables 39

2.3.2 The Operators NOT, AND, OR, and XOR 39

2.3.3 Negations of AND, OR, and NOT 40

2.3.4 Exercises 42

2.3.5 Implication and the Biconditional 43

2.3.6 Operator Precedence 46

2.3.7 Logical Equivalence 46

2.3.8 Derived Implications 47

2.3.9 Exercises 48

2.4 Logical Equivalence and Rules of Inference 50

2.4.1 Important Logical Equivalences and Rules of Inference 53

2.4.2 Proving that a Statement is a Tautology 54

2.4.3 Exercises 56

2.5 Boolean Algebras 58

2.5.1 Sets and Propositions as Boolean Algebras 60

2.5.2 Proving Additional Boolean Algebra Properties 63

2.5.3 Exercises 67

2.6 Predicate Logic 68

2.6.1 Quantifiers 69

2.6.2 Exercises 74

2.7 Quick Check Solutions 76

2.8 Chapter Review 81

2.8.1 Summary 81

2.8.2 Notation 82

2.8.3 Fundamental Properties 83

2.8.4 Additional Review Material 84

3 Proof 85

3.1 Introduction to Mathematical Proof 85

3.1.1 Mathematics and Proof: The Big Picture 86

3.1.2 Mathematical Objects Related to Proofs 87

3.1.3 Exercises 91

3.2 Elementary Number Theory: Fuel for Practice 92

3.2.1 The Integers and Other Number Systems 92

3.2.2 Divisibility 93

3.2.3 Primes 95

3.2.4 The Well-Ordering Principle 96

3.2.5 Congruence, Factorials, Floor and Ceiling Functions 98

3.2.6 Exercises 99

3.3 Proof Strategies 100

3.3.1 Trivial Proof 100

3.3.2 Direct Proof 101

3.3.3 Indirect Proof: Proving the Contrapositive 103

3.3.4 Proof by Contradiction 103

3.3.5 Proof by Cases 105

3.3.6 Implications with Existential Quantifiers 105

3.3.7 Implications with Universal Quantifiers 106

3.3.8 Proofs Involving the Biconditional and Logical Equivalence 108

3.3.9 Some Important Examples 109

3.3.10 Exercises 111

3.4 Applications of Elementary Number Theory 113

3.4.1 The Euclidean Algorithm: Calculating gcd(a, b) 113

3.4.2 Hashing 116

3.4.3 Pseudorandom Numbers 117

3.4.4 Linear Congruence and the Chinese Remainder Theorem 119

3.4.5 Fermat’s Little Theorem and Fermat’s Last Theorem 124

3.4.6 Encryption 126

3.4.7 Exercises 130

3.5 Mathematical Induction 132

3.5.1 The Principle of Mathematical Induction 132

3.5.2 Complete Induction 139

3.5.3 Interesting Mathematical Induction Problems 141

3.5.4 The Well-Ordering Principle, Mathematical Induction, and Complete Induction 146

3.5.5 Multidimensional Induction 148

3.5.6 Exercises 151

3.6 Creating Proofs: Hints and Suggestions 153

3.6.1 A Few Very General Suggestions 153

3.6.2 Some Specific Tactics 156

3.6.3 Exercises 161

3.7 Quick Check Solutions 162

3.8 Chapter Review 167

3.8.1 Summary 167

3.8.2 Notation 168

3.8.3 Additional Review Material 168

4 Algorithms 169

4.1 Expressing Algorithms 170

4.1.1 Flow of Control 170

4.1.2 Flow of Information 176

4.1.3 Exercises 179

4.2 Measuring Algorithm Efficiency 180

4.2.1 Big-2 and Its Cousins 181

4.2.2 Practical Big-2 Tools 185

4.2.3 Exercises 193

4.2.4 Big-2 in Action: Searching a List 195

4.2.5 Exercises 200

4.3 Pattern Matching 202

4.3.1 The Obvious Algorithm 202

4.3.2 KMP: Knuth–Morris–Pratt 204

4.3.3 BM: Boyer–Moore 206

4.3.4 Exercises 213

4.4 The Halting Problem 214

4.4.1 Setting the Stage 214

4.4.2 The Halting Problem 215

4.5 Quick Check Solutions 217

4.6 Chapter Review 222

4.6.1 Summary 222

4.6.2 Notation 223

4.6.3 Big-2 Shortcuts 224

4.6.4 Additional Review Material 224

5 Counting 225

5.1 Permutations and Combinations 226

5.1.1 Two Basic Counting Principles 226

5.1.2 Permutations 229

5.1.3 Permutations with Repetition 231

5.1.4 Combinations 231

5.1.5 Combinations with Repetition 234

5.1.6 Exercises 237

5.1.7 More Complex Counting Problems 239

5.1.8 Exercises 246

5.2 Combinatorial Proofs 248

5.2.1 Introduction to Combinatorial Proofs 248

5.2.2 Counting Tulips: Three Combinatorial Proofs 251

5.2.3 Exercises 257

5.3 Pigeon-Hole Principle; Inclusion–Exclusion 258

5.3.1 The Pigeon-Hole Principle 258

5.3.2 Inclusion–Exclusion 261

5.3.3 Exercises 264

5.4 Quick Check Solutions 266

5.5 Chapter Review 270

5.5.1 Summary 270

5.5.2 Notation 271

5.5.3 Some Counting Formulas 272

5.5.4 Additional Review Material 272

6 Finite Probability Theory 273

6.1 The Language of Probabilities 274

6.1.1 Sample Spaces, Outcomes, and Events 274

6.1.2 Probabilities of Events 277

6.1.3 Exercises 281

6.2 Conditional Probabilities and Independent Events 283

6.2.1 Definitions 283

6.2.2 Computing Probabilities 287

6.2.3 Exercises 294

6.3 Counting and Probability 297

6.3.1 Exercises 299

6.4 Expected Value 302

6.4.1 Exercises 308

6.5 The Binomial Distribution 310

6.5.1 Exercises 315

6.6 Bayes’s Theorem 316

6.6.1 Exercises 319

6.7 Quick Check Solutions 322

6.8 Chapter Review 327

6.8.1 Summary 327

6.8.2 Notation 328

6.8.3 Additional Review Material 328

7 Recursion 329

7.1 Recursive Algorithms 332

7.1.1 General Guidelines for Creating Recursive Algorithms 333

7.1.2 A Detailed Example 334

7.1.3 When Should Recursion Be Avoided? 336

7.1.4 Persian Rugs 339

7.1.5 Drawing Sierpinski Curves 342

7.1.6 Adaptive Quadrature 345

7.1.7 Exercises 349

7.2 Recurrence Relations 350

7.2.1 Solving Recurrence Relations 353

7.2.2 Linear Homogeneous Recurrence Relations with Constant Coefficients 357

7.2.3 Repeated Roots 366

7.2.4 The Sordid Truth 373

7.2.5 Exercises 375

7.3 Big-2 and Recursive Algorithms: The Master Theorem 377

7.3.1 Exercises 389

7.4 Generating Functions 391

7.4.1 Exercises 401

7.5 The Josephus Problem 402

7.5.1 Exercises 407

7.6 Quick Check Solutions 407

7.7 Chapter Review 414

7.7.1 Summary 414

7.7.2 Notation 416

7.7.3 Generating Function Table 416

7.7.4 Additional Review Material 416

8 Combinatorics 417

8.1 Partitions, Occupancy Problems, Stirling Numbers 419

8.1.1 Partitions of a Positive Integer 419

8.1.2 Occupancy Problems 423

8.1.3 Stirling Numbers 427

8.1.4 Exercises 433

8.2 Latin Squares, Finite Projective Planes 435

8.2.1 Latin Squares 435

8.2.2 Finite Projective Planes 442

8.2.3 Finite Projective Planes and Latin Squares 447

8.2.4 Exercises 457

8.3 Balanced Incomplete Block Designs 460

8.3.1 Constructing Balanced Incomplete Block Designs 464

8.3.2 Exercises 471

8.4 The Knapsack Problem 472

8.4.1 Exercises 485

8.5 Error-Correcting Codes 488

8.5.1 The 7-Bit Hamming Code 489

8.5.2 A Formal Look at Coding Theory 492

8.5.3 Combinatorial Aspects of Coding Theory 497

8.5.4 Exercises 500

8.6 Distinct Representatives, Ramsey Numbers 502

8.6.1 Systems of Distinct Representatives 502

8.6.2 Ramsey Numbers 509

8.6.3 Exercises 516

8.7 Quick Check Solutions 518

8.8 Chapter Review 529

8.8.1 Summary 529

8.8.2 Notation 531

8.8.3 The Fano Plane 532

8.8.4 Occupancy Problems 532

8.8.5 Additional Review Material 532

9 Formal Models in Computer Science 533

9.1 Information 533

9.1.1 A General Model of Communication 534

9.1.2 A Mathematical Definition of Information 535

9.1.3 A Summary of Other Ideas in Shannon’s Paper 540

9.1.4 Exercises 541

9.2 Finite-State Machines 542

9.2.1 Finite Automata 543

9.2.2 Finite-State Machines with Output 547

9.2.3 Exercises 551

9.3 Formal Languages 553

9.3.1 Regular Grammars 554

9.3.2 Exercises 559

9.4 Regular Expressions 560

9.4.1 Introduction to Regular Expressions 560

9.4.2 Perl Extensions 566

9.4.3 Exercises 568

9.5 The Three Faces of Regular 569

9.5.1 Optional: Completing the Proof of Kleene’s Theorem 576

9.5.2 Exercises 582

9.6 A Glimpse at More Advanced Topics 584

9.6.1 Context-Free Languages and Grammars 584

9.6.2 Turing Machines 585

9.6.3 Exercises 590

9.7 Quick Check Solutions 591

9.8 Chapter Review 596

9.8.1 Summary 596

9.8.2 Notation 597

9.8.3 Additional Review Material 598

10 Graphs 599

10.1 Terminology 600

10.1.1 New Graphs from Old 603

10.1.2 Special Graph Families 605

10.1.3 Exercises 608

10.2 Connectivity and Adjacency 609

10.2.1 Connectivity 609

10.2.2 The Adjacency Matrix 613

10.2.3 Exercises 615

10.3 Euler and Hamilton 618

10.3.1 Euler Circuits and Euler Trails 618

10.3.2 Hamilton Cycles and Hamilton Paths 620

10.3.3 Exercises 624

10.4 Representation and Isomorphism 626

10.4.1 Representation 626

10.4.2 Isomorphism 629

10.4.3 Exercises 631

10.5 The Big Theorems: Planarity, Euler, Polyhedra, Chromatic Number 634

10.5.1 Planarity 634

10.5.2 The Regular Polyhedra 639

10.5.3 Chromatic Number 642

10.5.4 Exercises 648

10.6 Directed Graphs and Weighted Graphs 651

10.6.1 Directed Graphs 651

10.6.2 Weighted Graphs and Shortest Paths 655

10.6.3 Exercises 662

10.7 Quick Check Solutions 665

10.8 Chapter Review 670

10.8.1 Summary 670

10.8.2 Notation 671

10.8.3 Additional Review Material 671

11 Trees 673

11.1 Terminology, Counting 673

11.1.1 Exercises 680

11.2 Traversal, Searching, and Sorting 682

11.2.1 Traversing Binary Trees 682

11.2.2 Binary Search Trees 685

11.2.3 Sorting 689

11.2.4 Exercises 690

11.3 More Applications of Trees 692

11.3.1 Parse Trees 692

11.3.2 Huffman Compression 694

11.3.3 XML 699

11.3.4 Exercises 708

11.4 Spanning Trees 711

11.4.1 Spanning Trees in Unweighted Graphs 711

11.4.2 Minimal Spanning Trees in Weighted Graphs 717

11.4.3 Exercises 722

11.5 Quick Check Solutions 726

11.6 Chapter Review 729

11.6.1 Summary 729

11.6.2 Notation 729

11.6.3 Additional Review Material 730

12 Functions, Relations, Databases, and Circuits 731

12.1 Functions and Relations 731

12.1.1 Functions 731

12.1.2 Relations 735

12.1.3 Exercises 737

12.2 Equivalence Relations, Partially Ordered Sets 739

12.2.1 Properties that Characterize Relations 739

12.2.2 Equivalence Relations and Partitions 742

12.2.3 Exercises 746

12.3 n-ary Relations and Relational Databases 748

12.3.1 n-ary Relations 748

12.3.2 Relational Databases 749

12.3.3 Functional Dependence; Models and Instances 751

12.3.4 Keys; Operations on Relations 752

12.3.5 Normal Forms 757

12.3.6 Exercises 769

12.4 Boolean Functions and Boolean Expressions 772

12.4.1 Boolean Functions 773

12.4.2 Binary Functions and Disjunctive Normal Form 775

12.4.3 Binary Expressions and Disjunctive Normal Form 778

12.4.4 Exercises 784

12.5 Combinatorial Circuits 785

12.5.1 Minimizing Binary Expressions 785

12.5.2 Combinatorial Circuits and Binary Expressions 789

12.5.3 Functional Completeness 793

12.5.4 Exercises 795

12.6 Quick Check Solutions 797

12.7 Chapter Review 805

12.7.1 Summary 805

12.7.2 Notation 806

12.7.3 Additional Review Material 806

A Number Systems A1

A.1 The Natural Numbers A1

A.2 The Integers A2

A.3 The Rational Numbers A2

A.4 The Real Numbers A4

A.5 The Complex Numbers A4

A.6 Other Number Systems A6

A.7 Representation of Numbers A7

B Summation Notation A10

C Logic Puzzles and Analyzing Claims A12

C.1 Logic Puzzles A12

C.1.1 Logic Puzzles about AND, OR, and NOT A12

C.1.2 Logic Puzzles about Implication, Biconditional, and Equivalence A16

C.1.3 Exercises A18

C.2 Analyzing Claims A18

C.2.1 Analyzing Claims that Contain Implications A18

C.2.2 Analyzing Claims that Contain Quantifiers A22

C.2.3 Exercises A23

C.3 Quick Check Solutions A24

D The Golden Ratio A27

E Matrices A29

F The Greek Alphabet A33

G Writing Mathematics A34

H Solutions to Selected Exercises A36

H.1 Introduction A36

H.2 Sets, Logic, and Boolean Algebras A36

H.3 Proof A42

H.4 Algorithms A47

H.5 Counting A51

H.6 Finite Probability Theory A54

H.7 Recursion A59

H.8 Combinatorics A63

H.9 Formal Models in Computer Science A68

H.10 Graphs A71

H.11 Trees A75

H.12 Functions, Relations, Databases, and Circuits A78

H.13 Appendices A83

Bibliography A85

Index A90