Discrete Mathematics with Proof

A Trusted Guide to Discrete Mathematics with Proof?Now in a Newly Revised Edition Discrete mathematics has become increasingly popular in recent years due to its growing applications in the field of computer science. Discrete Mathematics with Proof, Second Edition continues to facilitate an up-to-date understanding of this important topic, exposing readers to a wide range of modern and technological applications. The book begins with an introductory chapter that provides an accessible explanation of discrete mathematics. Subsequent chapters explore additional related topics including counting, finite probability theory, recursion, formal models in computer science, graph theory, trees, the concepts of functions, and relations. Additional features of the Second Edition include: An intense focus on the formal settings of proofs and their techniques, such as constructive proofs, proof by contradiction, and combinatorial proofs New sections on applications of elementary number theory, multidimensional induction, counting tulips, and the binomial distribution Important examples from the field of computer science presented as applications including the Halting problem, Shannon's mathematical model of information, regular expressions, XML, and Normal Forms in relational databases Numerous examples that are not often found in books on discrete mathematics including the deferred acceptance algorithm, the Boyer-Moore algorithm for pattern matching, Sierpinski curves, adaptive quadrature, the Josephus problem, and the five-color theorem Extensive appendices that outline supplemental material on analyzing claims and writing mathematics, along with solutions to selected chapter exercises Combinatorics receives a full chapter treatment that extends beyond the combinations and permutations material by delving into non-standard topics such as Latin squares, finite projective planes, balanced incomplete block designs, coding theory, partitions, occupancy problems, Stirling numbers, Ramsey numbers, and systems of distinct representatives. A related Web site features animations and visualizations of combinatorial proofs that assist readers with comprehension. In addition, approximately 500 examples and over 2,800 exercises are presented throughout the book to motivate ideas and illustrate the proofs and conclusions of theorems. Assuming only a basic background in calculus, Discrete Mathematics with Proof, Second Edition is an excellent book for mathematics and computer science courses at the undergraduate level. It is also a valuable resource for professionals in various technical fields who would like an introduction to discrete mathematics.

Table of Contents:
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