{"product_id":"discrete-mathematics-with-proof-9780470457931","title":"Discrete Mathematics with Proof","description":"\u003cb\u003eBook Synopsis\u003c\/b\u003e\u003cbr\u003eThis new edition exposes readers to a wide range of modern and technological applications, emphasizes proof throughout, and provides ample opportunities for practicing the presented concepts through homework exercises and worked examples.\u003cbr\u003e\u003cbr\u003e\u003cb\u003eTable of Contents\u003c\/b\u003e\u003cbr\u003e\u003cp\u003ePreface xiii\u003c\/p\u003e \u003cp\u003eAcknowledgments xx\u003c\/p\u003e \u003cp\u003eTo The Student xxii\u003c\/p\u003e \u003cp\u003e\u003cb\u003e1 Introduction 1\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e1.1 What Is Discrete Mathematics? 1\u003c\/p\u003e \u003cp\u003e1.1.1 A Break from the Past 3\u003c\/p\u003e \u003cp\u003e1.2 The Stable Marriage Problem 3\u003c\/p\u003e \u003cp\u003e1.2.1 Seeking a Solution 4\u003c\/p\u003e \u003cp\u003e1.2.2 The Deferred Acceptance Algorithm 5\u003c\/p\u003e \u003cp\u003e1.2.3 Some Concluding Comments 7\u003c\/p\u003e \u003cp\u003e1.3 Other Examples 7\u003c\/p\u003e \u003cp\u003e1.3.1 A Simple Counting and Probability Example 7\u003c\/p\u003e \u003cp\u003e1.3.2 Sierpinski Curves 8\u003c\/p\u003e \u003cp\u003e1.3.3 The Bridges of Konigsberg 9\u003c\/p\u003e \u003cp\u003e1.3.4 Kirkman’s Schoolgirls 9\u003c\/p\u003e \u003cp\u003e1.3.5 Finite-State Machines 10\u003c\/p\u003e \u003cp\u003e1.3.6 The Set of Rational Numbers Is Countably Infinite 11\u003c\/p\u003e \u003cp\u003e1.4 Exercises 13\u003c\/p\u003e \u003cp\u003e1.5 Chapter Review 15\u003c\/p\u003e \u003cp\u003e1.5.1 Summary 15\u003c\/p\u003e \u003cp\u003e1.5.2 Notation 15\u003c\/p\u003e \u003cp\u003e\u003cb\u003e2 Sets, Logic, and Boolean Algebras 17\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e2.1 Sets 19\u003c\/p\u003e \u003cp\u003e2.1.1 Definitions and Notation 19\u003c\/p\u003e \u003cp\u003e2.1.2 Exercises 26\u003c\/p\u003e \u003cp\u003e2.1.3 Proofs about Sets 29\u003c\/p\u003e \u003cp\u003e2.1.4 Exercises 33\u003c\/p\u003e \u003cp\u003e2.2 Logic in Daily Life 34\u003c\/p\u003e \u003cp\u003e2.2.1 General Guidelines for Analyzing Claims 34\u003c\/p\u003e \u003cp\u003e2.2.2 Informal Fallacies 35\u003c\/p\u003e \u003cp\u003e2.2.3 Everyday Logic versus Symbolic Logic 37\u003c\/p\u003e \u003cp\u003e2.2.4 Exercises 37\u003c\/p\u003e \u003cp\u003e2.3 Propositional Logic 38\u003c\/p\u003e \u003cp\u003e2.3.1 Truth Tables 39\u003c\/p\u003e \u003cp\u003e2.3.2 The Operators NOT, AND, OR, and XOR 39\u003c\/p\u003e \u003cp\u003e2.3.3 Negations of AND, OR, and NOT 40\u003c\/p\u003e \u003cp\u003e2.3.4 Exercises 42\u003c\/p\u003e \u003cp\u003e2.3.5 Implication and the Biconditional 43\u003c\/p\u003e \u003cp\u003e2.3.6 Operator Precedence 46\u003c\/p\u003e \u003cp\u003e2.3.7 Logical Equivalence 46\u003c\/p\u003e \u003cp\u003e2.3.8 Derived Implications 47\u003c\/p\u003e \u003cp\u003e2.3.9 Exercises 48\u003c\/p\u003e \u003cp\u003e2.4 Logical Equivalence and Rules of Inference 50\u003c\/p\u003e \u003cp\u003e2.4.1 Important Logical Equivalences and Rules of Inference 53\u003c\/p\u003e \u003cp\u003e2.4.2 Proving that a Statement is a Tautology 54\u003c\/p\u003e \u003cp\u003e2.4.3 Exercises 56\u003c\/p\u003e \u003cp\u003e2.5 Boolean Algebras 58\u003c\/p\u003e \u003cp\u003e2.5.1 Sets and Propositions as Boolean Algebras 60\u003c\/p\u003e \u003cp\u003e2.5.2 Proving Additional Boolean Algebra Properties 63\u003c\/p\u003e \u003cp\u003e2.5.3 Exercises 67\u003c\/p\u003e \u003cp\u003e2.6 Predicate Logic 68\u003c\/p\u003e \u003cp\u003e2.6.1 Quantifiers 69\u003c\/p\u003e \u003cp\u003e2.6.2 Exercises 74\u003c\/p\u003e \u003cp\u003e2.7 Quick Check Solutions 76\u003c\/p\u003e \u003cp\u003e2.8 Chapter Review 81\u003c\/p\u003e \u003cp\u003e2.8.1 Summary 81\u003c\/p\u003e \u003cp\u003e2.8.2 Notation 82\u003c\/p\u003e \u003cp\u003e2.8.3 Fundamental Properties 83\u003c\/p\u003e \u003cp\u003e2.8.4 Additional Review Material 84\u003c\/p\u003e \u003cp\u003e\u003cb\u003e3 Proof 85\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e3.1 Introduction to Mathematical Proof 85\u003c\/p\u003e \u003cp\u003e3.1.1 Mathematics and Proof: The Big Picture 86\u003c\/p\u003e \u003cp\u003e3.1.2 Mathematical Objects Related to Proofs 87\u003c\/p\u003e \u003cp\u003e3.1.3 Exercises 91\u003c\/p\u003e \u003cp\u003e3.2 Elementary Number Theory: Fuel for Practice 92\u003c\/p\u003e \u003cp\u003e3.2.1 The Integers and Other Number Systems 92\u003c\/p\u003e \u003cp\u003e3.2.2 Divisibility 93\u003c\/p\u003e \u003cp\u003e3.2.3 Primes 95\u003c\/p\u003e \u003cp\u003e3.2.4 The Well-Ordering Principle 96\u003c\/p\u003e \u003cp\u003e3.2.5 Congruence, Factorials, Floor and Ceiling Functions 98\u003c\/p\u003e \u003cp\u003e3.2.6 Exercises 99\u003c\/p\u003e \u003cp\u003e3.3 Proof Strategies 100\u003c\/p\u003e \u003cp\u003e3.3.1 Trivial Proof 100\u003c\/p\u003e \u003cp\u003e3.3.2 Direct Proof 101\u003c\/p\u003e \u003cp\u003e3.3.3 Indirect Proof: Proving the Contrapositive 103\u003c\/p\u003e \u003cp\u003e3.3.4 Proof by Contradiction 103\u003c\/p\u003e \u003cp\u003e3.3.5 Proof by Cases 105\u003c\/p\u003e \u003cp\u003e3.3.6 Implications with Existential Quantifiers 105\u003c\/p\u003e \u003cp\u003e3.3.7 Implications with Universal Quantifiers 106\u003c\/p\u003e \u003cp\u003e3.3.8 Proofs Involving the Biconditional and Logical Equivalence 108\u003c\/p\u003e \u003cp\u003e3.3.9 Some Important Examples 109\u003c\/p\u003e \u003cp\u003e3.3.10 Exercises 111\u003c\/p\u003e \u003cp\u003e3.4 Applications of Elementary Number Theory 113\u003c\/p\u003e \u003cp\u003e3.4.1 The Euclidean Algorithm: Calculating gcd(a, b) 113\u003c\/p\u003e \u003cp\u003e3.4.2 Hashing 116\u003c\/p\u003e \u003cp\u003e3.4.3 Pseudorandom Numbers 117\u003c\/p\u003e \u003cp\u003e3.4.4 Linear Congruence and the Chinese Remainder Theorem 119\u003c\/p\u003e \u003cp\u003e3.4.5 Fermat’s Little Theorem and Fermat’s Last Theorem 124\u003c\/p\u003e \u003cp\u003e3.4.6 Encryption 126\u003c\/p\u003e \u003cp\u003e3.4.7 Exercises 130\u003c\/p\u003e \u003cp\u003e3.5 Mathematical Induction 132\u003c\/p\u003e \u003cp\u003e3.5.1 The Principle of Mathematical Induction 132\u003c\/p\u003e \u003cp\u003e3.5.2 Complete Induction 139\u003c\/p\u003e \u003cp\u003e3.5.3 Interesting Mathematical Induction Problems 141\u003c\/p\u003e \u003cp\u003e3.5.4 The Well-Ordering Principle, Mathematical Induction, and Complete Induction 146\u003c\/p\u003e \u003cp\u003e3.5.5 Multidimensional Induction 148\u003c\/p\u003e \u003cp\u003e3.5.6 Exercises 151\u003c\/p\u003e \u003cp\u003e3.6 Creating Proofs: Hints and Suggestions 153\u003c\/p\u003e \u003cp\u003e3.6.1 A Few Very General Suggestions 153\u003c\/p\u003e \u003cp\u003e3.6.2 Some Specific Tactics 156\u003c\/p\u003e \u003cp\u003e3.6.3 Exercises 161\u003c\/p\u003e \u003cp\u003e3.7 Quick Check Solutions 162\u003c\/p\u003e \u003cp\u003e3.8 Chapter Review 167\u003c\/p\u003e \u003cp\u003e3.8.1 Summary 167\u003c\/p\u003e \u003cp\u003e3.8.2 Notation 168\u003c\/p\u003e \u003cp\u003e3.8.3 Additional Review Material 168\u003c\/p\u003e \u003cp\u003e\u003cb\u003e4 Algorithms 169\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e4.1 Expressing Algorithms 170\u003c\/p\u003e \u003cp\u003e4.1.1 Flow of Control 170\u003c\/p\u003e \u003cp\u003e4.1.2 Flow of Information 176\u003c\/p\u003e \u003cp\u003e4.1.3 Exercises 179\u003c\/p\u003e \u003cp\u003e4.2 Measuring Algorithm Efficiency 180\u003c\/p\u003e \u003cp\u003e4.2.1 Big-2 and Its Cousins 181\u003c\/p\u003e \u003cp\u003e4.2.2 Practical Big-2 Tools 185\u003c\/p\u003e \u003cp\u003e4.2.3 Exercises 193\u003c\/p\u003e \u003cp\u003e4.2.4 Big-2 in Action: Searching a List 195\u003c\/p\u003e \u003cp\u003e4.2.5 Exercises 200\u003c\/p\u003e \u003cp\u003e4.3 Pattern Matching 202\u003c\/p\u003e \u003cp\u003e4.3.1 The Obvious Algorithm 202\u003c\/p\u003e \u003cp\u003e4.3.2 KMP: Knuth–Morris–Pratt 204\u003c\/p\u003e \u003cp\u003e4.3.3 BM: Boyer–Moore 206\u003c\/p\u003e \u003cp\u003e4.3.4 Exercises 213\u003c\/p\u003e \u003cp\u003e4.4 The Halting Problem 214\u003c\/p\u003e \u003cp\u003e4.4.1 Setting the Stage 214\u003c\/p\u003e \u003cp\u003e4.4.2 The Halting Problem 215\u003c\/p\u003e \u003cp\u003e4.5 Quick Check Solutions 217\u003c\/p\u003e \u003cp\u003e4.6 Chapter Review 222\u003c\/p\u003e \u003cp\u003e4.6.1 Summary 222\u003c\/p\u003e \u003cp\u003e4.6.2 Notation 223\u003c\/p\u003e \u003cp\u003e4.6.3 Big-2 Shortcuts 224\u003c\/p\u003e \u003cp\u003e4.6.4 Additional Review Material 224\u003c\/p\u003e \u003cp\u003e\u003cb\u003e5 Counting 225\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e5.1 Permutations and Combinations 226\u003c\/p\u003e \u003cp\u003e5.1.1 Two Basic Counting Principles 226\u003c\/p\u003e \u003cp\u003e5.1.2 Permutations 229\u003c\/p\u003e \u003cp\u003e5.1.3 Permutations with Repetition 231\u003c\/p\u003e \u003cp\u003e5.1.4 Combinations 231\u003c\/p\u003e \u003cp\u003e5.1.5 Combinations with Repetition 234\u003c\/p\u003e \u003cp\u003e5.1.6 Exercises 237\u003c\/p\u003e \u003cp\u003e5.1.7 More Complex Counting Problems 239\u003c\/p\u003e \u003cp\u003e5.1.8 Exercises 246\u003c\/p\u003e \u003cp\u003e5.2 Combinatorial Proofs 248\u003c\/p\u003e \u003cp\u003e5.2.1 Introduction to Combinatorial Proofs 248\u003c\/p\u003e \u003cp\u003e5.2.2 Counting Tulips: Three Combinatorial Proofs 251\u003c\/p\u003e \u003cp\u003e5.2.3 Exercises 257\u003c\/p\u003e \u003cp\u003e5.3 Pigeon-Hole Principle; Inclusion–Exclusion 258\u003c\/p\u003e \u003cp\u003e5.3.1 The Pigeon-Hole Principle 258\u003c\/p\u003e \u003cp\u003e5.3.2 Inclusion–Exclusion 261\u003c\/p\u003e \u003cp\u003e5.3.3 Exercises 264\u003c\/p\u003e \u003cp\u003e5.4 Quick Check Solutions 266\u003c\/p\u003e \u003cp\u003e5.5 Chapter Review 270\u003c\/p\u003e \u003cp\u003e5.5.1 Summary 270\u003c\/p\u003e \u003cp\u003e5.5.2 Notation 271\u003c\/p\u003e \u003cp\u003e5.5.3 Some Counting Formulas 272\u003c\/p\u003e \u003cp\u003e5.5.4 Additional Review Material 272\u003c\/p\u003e \u003cp\u003e\u003cb\u003e6 Finite Probability Theory 273\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e6.1 The Language of Probabilities 274\u003c\/p\u003e \u003cp\u003e6.1.1 Sample Spaces, Outcomes, and Events 274\u003c\/p\u003e \u003cp\u003e6.1.2 Probabilities of Events 277\u003c\/p\u003e \u003cp\u003e6.1.3 Exercises 281\u003c\/p\u003e \u003cp\u003e6.2 Conditional Probabilities and Independent Events 283\u003c\/p\u003e \u003cp\u003e6.2.1 Definitions 283\u003c\/p\u003e \u003cp\u003e6.2.2 Computing Probabilities 287\u003c\/p\u003e \u003cp\u003e6.2.3 Exercises 294\u003c\/p\u003e \u003cp\u003e6.3 Counting and Probability 297\u003c\/p\u003e \u003cp\u003e6.3.1 Exercises 299\u003c\/p\u003e \u003cp\u003e6.4 Expected Value 302\u003c\/p\u003e \u003cp\u003e6.4.1 Exercises 308\u003c\/p\u003e \u003cp\u003e6.5 The Binomial Distribution 310\u003c\/p\u003e \u003cp\u003e6.5.1 Exercises 315\u003c\/p\u003e \u003cp\u003e6.6 Bayes’s Theorem 316\u003c\/p\u003e \u003cp\u003e6.6.1 Exercises 319\u003c\/p\u003e \u003cp\u003e6.7 Quick Check Solutions 322\u003c\/p\u003e \u003cp\u003e6.8 Chapter Review 327\u003c\/p\u003e \u003cp\u003e6.8.1 Summary 327\u003c\/p\u003e \u003cp\u003e6.8.2 Notation 328\u003c\/p\u003e \u003cp\u003e6.8.3 Additional Review Material 328\u003c\/p\u003e \u003cp\u003e\u003cb\u003e7 Recursion 329\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e7.1 Recursive Algorithms 332\u003c\/p\u003e \u003cp\u003e7.1.1 General Guidelines for Creating Recursive Algorithms 333\u003c\/p\u003e \u003cp\u003e7.1.2 A Detailed Example 334\u003c\/p\u003e \u003cp\u003e7.1.3 When Should Recursion Be Avoided? 336\u003c\/p\u003e \u003cp\u003e7.1.4 Persian Rugs 339\u003c\/p\u003e \u003cp\u003e7.1.5 Drawing Sierpinski Curves 342\u003c\/p\u003e \u003cp\u003e7.1.6 Adaptive Quadrature 345\u003c\/p\u003e \u003cp\u003e7.1.7 Exercises 349\u003c\/p\u003e \u003cp\u003e7.2 Recurrence Relations 350\u003c\/p\u003e \u003cp\u003e7.2.1 Solving Recurrence Relations 353\u003c\/p\u003e \u003cp\u003e7.2.2 Linear Homogeneous Recurrence Relations with Constant Coefficients 357\u003c\/p\u003e \u003cp\u003e7.2.3 Repeated Roots 366\u003c\/p\u003e \u003cp\u003e7.2.4 The Sordid Truth 373\u003c\/p\u003e \u003cp\u003e7.2.5 Exercises 375\u003c\/p\u003e \u003cp\u003e7.3 Big-2 and Recursive Algorithms: The Master Theorem 377\u003c\/p\u003e \u003cp\u003e7.3.1 Exercises 389\u003c\/p\u003e \u003cp\u003e7.4 Generating Functions 391\u003c\/p\u003e \u003cp\u003e7.4.1 Exercises 401\u003c\/p\u003e \u003cp\u003e7.5 The Josephus Problem 402\u003c\/p\u003e \u003cp\u003e7.5.1 Exercises 407\u003c\/p\u003e \u003cp\u003e7.6 Quick Check Solutions 407\u003c\/p\u003e \u003cp\u003e7.7 Chapter Review 414\u003c\/p\u003e \u003cp\u003e7.7.1 Summary 414\u003c\/p\u003e \u003cp\u003e7.7.2 Notation 416\u003c\/p\u003e \u003cp\u003e7.7.3 Generating Function Table 416\u003c\/p\u003e \u003cp\u003e7.7.4 Additional Review Material 416\u003c\/p\u003e \u003cp\u003e\u003cb\u003e8 Combinatorics 417\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e8.1 Partitions, Occupancy Problems, Stirling Numbers 419\u003c\/p\u003e \u003cp\u003e8.1.1 Partitions of a Positive Integer 419\u003c\/p\u003e \u003cp\u003e8.1.2 Occupancy Problems 423\u003c\/p\u003e \u003cp\u003e8.1.3 Stirling Numbers 427\u003c\/p\u003e \u003cp\u003e8.1.4 Exercises 433\u003c\/p\u003e \u003cp\u003e8.2 Latin Squares, Finite Projective Planes 435\u003c\/p\u003e \u003cp\u003e8.2.1 Latin Squares 435\u003c\/p\u003e \u003cp\u003e8.2.2 Finite Projective Planes 442\u003c\/p\u003e \u003cp\u003e8.2.3 Finite Projective Planes and Latin Squares 447\u003c\/p\u003e \u003cp\u003e8.2.4 Exercises 457\u003c\/p\u003e \u003cp\u003e8.3 Balanced Incomplete Block Designs 460\u003c\/p\u003e \u003cp\u003e8.3.1 Constructing Balanced Incomplete Block Designs 464\u003c\/p\u003e \u003cp\u003e8.3.2 Exercises 471\u003c\/p\u003e \u003cp\u003e8.4 The Knapsack Problem 472\u003c\/p\u003e \u003cp\u003e8.4.1 Exercises 485\u003c\/p\u003e \u003cp\u003e8.5 Error-Correcting Codes 488\u003c\/p\u003e \u003cp\u003e8.5.1 The 7-Bit Hamming Code 489\u003c\/p\u003e \u003cp\u003e8.5.2 A Formal Look at Coding Theory 492\u003c\/p\u003e \u003cp\u003e8.5.3 Combinatorial Aspects of Coding Theory 497\u003c\/p\u003e \u003cp\u003e8.5.4 Exercises 500\u003c\/p\u003e \u003cp\u003e8.6 Distinct Representatives, Ramsey Numbers 502\u003c\/p\u003e \u003cp\u003e8.6.1 Systems of Distinct Representatives 502\u003c\/p\u003e \u003cp\u003e8.6.2 Ramsey Numbers 509\u003c\/p\u003e \u003cp\u003e8.6.3 Exercises 516\u003c\/p\u003e \u003cp\u003e8.7 Quick Check Solutions 518\u003c\/p\u003e \u003cp\u003e8.8 Chapter Review 529\u003c\/p\u003e \u003cp\u003e8.8.1 Summary 529\u003c\/p\u003e \u003cp\u003e8.8.2 Notation 531\u003c\/p\u003e \u003cp\u003e8.8.3 The Fano Plane 532\u003c\/p\u003e \u003cp\u003e8.8.4 Occupancy Problems 532\u003c\/p\u003e \u003cp\u003e8.8.5 Additional Review Material 532\u003c\/p\u003e \u003cp\u003e\u003cb\u003e9 Formal Models in Computer Science 533\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e9.1 Information 533\u003c\/p\u003e \u003cp\u003e9.1.1 A General Model of Communication 534\u003c\/p\u003e \u003cp\u003e9.1.2 A Mathematical Definition of Information 535\u003c\/p\u003e \u003cp\u003e9.1.3 A Summary of Other Ideas in Shannon’s Paper 540\u003c\/p\u003e \u003cp\u003e9.1.4 Exercises 541\u003c\/p\u003e \u003cp\u003e9.2 Finite-State Machines 542\u003c\/p\u003e \u003cp\u003e9.2.1 Finite Automata 543\u003c\/p\u003e \u003cp\u003e9.2.2 Finite-State Machines with Output 547\u003c\/p\u003e \u003cp\u003e9.2.3 Exercises 551\u003c\/p\u003e \u003cp\u003e9.3 Formal Languages 553\u003c\/p\u003e \u003cp\u003e9.3.1 Regular Grammars 554\u003c\/p\u003e \u003cp\u003e9.3.2 Exercises 559\u003c\/p\u003e \u003cp\u003e9.4 Regular Expressions 560\u003c\/p\u003e \u003cp\u003e9.4.1 Introduction to Regular Expressions 560\u003c\/p\u003e \u003cp\u003e9.4.2 Perl Extensions 566\u003c\/p\u003e \u003cp\u003e9.4.3 Exercises 568\u003c\/p\u003e \u003cp\u003e9.5 The Three Faces of Regular 569\u003c\/p\u003e \u003cp\u003e9.5.1 Optional: Completing the Proof of Kleene’s Theorem 576\u003c\/p\u003e \u003cp\u003e9.5.2 Exercises 582\u003c\/p\u003e \u003cp\u003e9.6 A Glimpse at More Advanced Topics 584\u003c\/p\u003e \u003cp\u003e9.6.1 Context-Free Languages and Grammars 584\u003c\/p\u003e \u003cp\u003e9.6.2 Turing Machines 585\u003c\/p\u003e \u003cp\u003e9.6.3 Exercises 590\u003c\/p\u003e \u003cp\u003e9.7 Quick Check Solutions 591\u003c\/p\u003e \u003cp\u003e9.8 Chapter Review 596\u003c\/p\u003e \u003cp\u003e9.8.1 Summary 596\u003c\/p\u003e \u003cp\u003e9.8.2 Notation 597\u003c\/p\u003e \u003cp\u003e9.8.3 Additional Review Material 598\u003c\/p\u003e \u003cp\u003e\u003cb\u003e10 Graphs 599\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e10.1 Terminology 600\u003c\/p\u003e \u003cp\u003e10.1.1 New Graphs from Old 603\u003c\/p\u003e \u003cp\u003e10.1.2 Special Graph Families 605\u003c\/p\u003e \u003cp\u003e10.1.3 Exercises 608\u003c\/p\u003e \u003cp\u003e10.2 Connectivity and Adjacency 609\u003c\/p\u003e \u003cp\u003e10.2.1 Connectivity 609\u003c\/p\u003e \u003cp\u003e10.2.2 The Adjacency Matrix 613\u003c\/p\u003e \u003cp\u003e10.2.3 Exercises 615\u003c\/p\u003e \u003cp\u003e10.3 Euler and Hamilton 618\u003c\/p\u003e \u003cp\u003e10.3.1 Euler Circuits and Euler Trails 618\u003c\/p\u003e \u003cp\u003e10.3.2 Hamilton Cycles and Hamilton Paths 620\u003c\/p\u003e \u003cp\u003e10.3.3 Exercises 624\u003c\/p\u003e \u003cp\u003e10.4 Representation and Isomorphism 626\u003c\/p\u003e \u003cp\u003e10.4.1 Representation 626\u003c\/p\u003e \u003cp\u003e10.4.2 Isomorphism 629\u003c\/p\u003e \u003cp\u003e10.4.3 Exercises 631\u003c\/p\u003e \u003cp\u003e10.5 The Big Theorems: Planarity, Euler, Polyhedra, Chromatic Number 634\u003c\/p\u003e \u003cp\u003e10.5.1 Planarity 634\u003c\/p\u003e \u003cp\u003e10.5.2 The Regular Polyhedra 639\u003c\/p\u003e \u003cp\u003e10.5.3 Chromatic Number 642\u003c\/p\u003e \u003cp\u003e10.5.4 Exercises 648\u003c\/p\u003e \u003cp\u003e10.6 Directed Graphs and Weighted Graphs 651\u003c\/p\u003e \u003cp\u003e10.6.1 Directed Graphs 651\u003c\/p\u003e \u003cp\u003e10.6.2 Weighted Graphs and Shortest Paths 655\u003c\/p\u003e \u003cp\u003e10.6.3 Exercises 662\u003c\/p\u003e \u003cp\u003e10.7 Quick Check Solutions 665\u003c\/p\u003e \u003cp\u003e10.8 Chapter Review 670\u003c\/p\u003e \u003cp\u003e10.8.1 Summary 670\u003c\/p\u003e \u003cp\u003e10.8.2 Notation 671\u003c\/p\u003e \u003cp\u003e10.8.3 Additional Review Material 671\u003c\/p\u003e \u003cp\u003e\u003cb\u003e11 Trees 673\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e11.1 Terminology, Counting 673\u003c\/p\u003e \u003cp\u003e11.1.1 Exercises 680\u003c\/p\u003e \u003cp\u003e11.2 Traversal, Searching, and Sorting 682\u003c\/p\u003e \u003cp\u003e11.2.1 Traversing Binary Trees 682\u003c\/p\u003e \u003cp\u003e11.2.2 Binary Search Trees 685\u003c\/p\u003e \u003cp\u003e11.2.3 Sorting 689\u003c\/p\u003e \u003cp\u003e11.2.4 Exercises 690\u003c\/p\u003e \u003cp\u003e11.3 More Applications of Trees 692\u003c\/p\u003e \u003cp\u003e11.3.1 Parse Trees 692\u003c\/p\u003e \u003cp\u003e11.3.2 Huffman Compression 694\u003c\/p\u003e \u003cp\u003e11.3.3 XML 699\u003c\/p\u003e \u003cp\u003e11.3.4 Exercises 708\u003c\/p\u003e \u003cp\u003e11.4 Spanning Trees 711\u003c\/p\u003e \u003cp\u003e11.4.1 Spanning Trees in Unweighted Graphs 711\u003c\/p\u003e \u003cp\u003e11.4.2 Minimal Spanning Trees in Weighted Graphs 717\u003c\/p\u003e \u003cp\u003e11.4.3 Exercises 722\u003c\/p\u003e \u003cp\u003e11.5 Quick Check Solutions 726\u003c\/p\u003e \u003cp\u003e11.6 Chapter Review 729\u003c\/p\u003e \u003cp\u003e11.6.1 Summary 729\u003c\/p\u003e \u003cp\u003e11.6.2 Notation 729\u003c\/p\u003e \u003cp\u003e11.6.3 Additional Review Material 730\u003c\/p\u003e \u003cp\u003e\u003cb\u003e12 Functions, Relations, Databases, and Circuits 731\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e12.1 Functions and Relations 731\u003c\/p\u003e \u003cp\u003e12.1.1 Functions 731\u003c\/p\u003e \u003cp\u003e12.1.2 Relations 735\u003c\/p\u003e \u003cp\u003e12.1.3 Exercises 737\u003c\/p\u003e \u003cp\u003e12.2 Equivalence Relations, Partially Ordered Sets 739\u003c\/p\u003e \u003cp\u003e12.2.1 Properties that Characterize Relations 739\u003c\/p\u003e \u003cp\u003e12.2.2 Equivalence Relations and Partitions 742\u003c\/p\u003e \u003cp\u003e12.2.3 Exercises 746\u003c\/p\u003e \u003cp\u003e12.3 \u003cb\u003e\u003ci\u003en\u003c\/i\u003e\u003c\/b\u003e-ary Relations and Relational Databases 748\u003c\/p\u003e \u003cp\u003e12.3.1 \u003cb\u003e\u003ci\u003en\u003c\/i\u003e\u003c\/b\u003e-ary Relations 748\u003c\/p\u003e \u003cp\u003e12.3.2 Relational Databases 749\u003c\/p\u003e \u003cp\u003e12.3.3 Functional Dependence; Models and Instances 751\u003c\/p\u003e \u003cp\u003e12.3.4 Keys; Operations on Relations 752\u003c\/p\u003e \u003cp\u003e12.3.5 Normal Forms 757\u003c\/p\u003e \u003cp\u003e12.3.6 Exercises 769\u003c\/p\u003e \u003cp\u003e12.4 Boolean Functions and Boolean Expressions 772\u003c\/p\u003e \u003cp\u003e12.4.1 Boolean Functions 773\u003c\/p\u003e \u003cp\u003e12.4.2 Binary Functions and Disjunctive Normal Form 775\u003c\/p\u003e \u003cp\u003e12.4.3 Binary Expressions and Disjunctive Normal Form 778\u003c\/p\u003e \u003cp\u003e12.4.4 Exercises 784\u003c\/p\u003e \u003cp\u003e12.5 Combinatorial Circuits 785\u003c\/p\u003e \u003cp\u003e12.5.1 Minimizing Binary Expressions 785\u003c\/p\u003e \u003cp\u003e12.5.2 Combinatorial Circuits and Binary Expressions 789\u003c\/p\u003e \u003cp\u003e12.5.3 Functional Completeness 793\u003c\/p\u003e \u003cp\u003e12.5.4 Exercises 795\u003c\/p\u003e \u003cp\u003e12.6 Quick Check Solutions 797\u003c\/p\u003e \u003cp\u003e12.7 Chapter Review 805\u003c\/p\u003e \u003cp\u003e12.7.1 Summary 805\u003c\/p\u003e \u003cp\u003e12.7.2 Notation 806\u003c\/p\u003e \u003cp\u003e12.7.3 Additional Review Material 806\u003c\/p\u003e \u003cp\u003e\u003cb\u003eA Number Systems A1\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003eA.1 The Natural Numbers A1\u003c\/p\u003e \u003cp\u003eA.2 The Integers A2\u003c\/p\u003e \u003cp\u003eA.3 The Rational Numbers A2\u003c\/p\u003e \u003cp\u003eA.4 The Real Numbers A4\u003c\/p\u003e \u003cp\u003eA.5 The Complex Numbers A4\u003c\/p\u003e \u003cp\u003eA.6 Other Number Systems A6\u003c\/p\u003e \u003cp\u003eA.7 Representation of Numbers A7\u003c\/p\u003e \u003cp\u003e\u003cb\u003eB Summation Notation A10\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e\u003cb\u003eC Logic Puzzles and Analyzing Claims A12\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003eC.1 Logic Puzzles A12\u003c\/p\u003e \u003cp\u003eC.1.1 Logic Puzzles about AND, OR, and NOT A12\u003c\/p\u003e \u003cp\u003eC.1.2 Logic Puzzles about Implication, Biconditional, and Equivalence A16\u003c\/p\u003e \u003cp\u003eC.1.3 Exercises A18\u003c\/p\u003e \u003cp\u003eC.2 Analyzing Claims A18\u003c\/p\u003e \u003cp\u003eC.2.1 Analyzing Claims that Contain Implications A18\u003c\/p\u003e \u003cp\u003eC.2.2 Analyzing Claims that Contain Quantifiers A22\u003c\/p\u003e \u003cp\u003eC.2.3 Exercises A23\u003c\/p\u003e \u003cp\u003eC.3 Quick Check Solutions A24\u003c\/p\u003e \u003cp\u003e\u003cb\u003eD The Golden Ratio A27\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e\u003cb\u003eE Matrices A29\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e\u003cb\u003eF The Greek Alphabet A33\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e\u003cb\u003eG Writing Mathematics A34\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e\u003cb\u003eH Solutions to Selected Exercises A36\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003eH.1 Introduction A36\u003c\/p\u003e \u003cp\u003eH.2 Sets, Logic, and Boolean Algebras A36\u003c\/p\u003e \u003cp\u003eH.3 Proof A42\u003c\/p\u003e \u003cp\u003eH.4 Algorithms A47\u003c\/p\u003e \u003cp\u003eH.5 Counting A51\u003c\/p\u003e \u003cp\u003eH.6 Finite Probability Theory A54\u003c\/p\u003e \u003cp\u003eH.7 Recursion A59\u003c\/p\u003e \u003cp\u003eH.8 Combinatorics A63\u003c\/p\u003e \u003cp\u003eH.9 Formal Models in Computer Science A68\u003c\/p\u003e \u003cp\u003eH.10 Graphs A71\u003c\/p\u003e \u003cp\u003eH.11 Trees A75\u003c\/p\u003e \u003cp\u003eH.12 Functions, Relations, Databases, and Circuits A78\u003c\/p\u003e \u003cp\u003eH.13 Appendices A83\u003c\/p\u003e \u003cp\u003eBibliography A85\u003c\/p\u003e \u003cp\u003eIndex A90\u003c\/p\u003e","brand":"John Wiley \u0026 Sons Inc","offers":[{"title":"Default Title","offer_id":49402337165655,"sku":"9780470457931","price":125.06,"currency_code":"GBP","in_stock":true}],"thumbnail_url":"\/\/cdn.shopify.com\/s\/files\/1\/0817\/1739\/5799\/files\/9780470457931.jpg?v=1730480104","url":"https:\/\/bookcurl.com\/products\/discrete-mathematics-with-proof-9780470457931","provider":"Book Curl","version":"1.0","type":"link"}