Rosen, Kenneth H.

Student's Solutions Guide to Accompany Discrete Mathematics and Its Applications

Preface iii The Foundations: Logic and Proofs 1(46) Propositional Logic 1(9) Propositional Equivalences 10(5) Predicates and Quantifiers 15(6) Nested Quantifiers 21(9) Rules of Inference 30(4) Introduction to Proofs 34(4) Proof Methods and Strategy 38(9) Guide to Review Questions for Chapter 1 42(1) Supplementary Exercises for Chapter 1 43(2) Writing Projects for Chapter 1 45(2) Basic Structures: Sets, Functions, Sequences, and Sums 47(25) Sets 47(3) Set Operations 50(5) Functions 55(8) Sequences and Summations 63(9) Guide to Review Questions for Chapter 2 68(1) Supplementary Exercises for Chapter 2 69(2) Writing Projects for Chapter 2 71(1) The Fundamentals: Algorithms, the Integers, and Matrices 72(48) Algorithms 72(9) The Growth of Functions 81(5) Complexity of Algorithms 86(3) The Integers and Division 89(2) Primes and Greatest Common Divisors 91(4) Integers and Algorithms 95(5) Applications of Number Theory 100(8) Matrices 108(12) Guide to Review Questions for Chapter 3 112(1) Supplementary Exercises for Chapter 3 113(5) Writing Projects for Chapter 3 118(2) Induction and Recursion 120(47) Mathematical Induction 120(12) Strong Induction and Well-Ordering 132(6) Recursive Definitions and Structural Induction 138(9) Recursive Algorithms 147(5) Program Correctness 152(15) Guide to Review Questions for Chapter 4 154(2) Supplementary Exercises for Chapter 4 156(10) Writing Projects for Chapter 4 166(1) Counting 167(39) The Basics of Counting 167(8) The Pigeonhole Principle 175(5) Permutations and Combinations 180(4) Binomial Coefficients 184(5) Generalized Permutations and Combinations 189(7) Generating Permutations and Combinations 196(10) Guide to Review Questions for Chapter 5 198(1) Supplementary Exercises for Chapter 5 199(6) Writing Projects for Chapter 5 205(1) Discrete Probability 206(22) An Introduction to Discrete Probability 206(3) Probability Theory 209(6) Bayes' Theorem 215(2) Expected Value and Variance 217(11) Guide to Review Questions for Chapter 6 222(1) Supplementary Exercises for Chapter 6 223(4) Writing Projects for Chapter 6 227(1) Advanced Counting Techniques 228(52) Recurrence Relations 228(13) Solving Linear Recurrence Relations 241(10) Divide-and-Conquer Algorithms and Recurrence Relations 251(4) Generating Functions 255(12) Inclusion-Exclusion 267(2) Applications of Inclusion--Exclusion 269(11) Guide to Review Questions for Chapter 7 273(1) Supplementary Exercises for Chapter 7 274(5) Writing Projects for Chapter 7 279(1) Relations 280(40) Relations and Their Properties 280(8) n-ary Relations and Their Applications 288(2) Representing Relations 290(3) Closures of Relations 293(4) Equivalence Relations 297(8) Partial Orderings 305(15) Guide to Review Questions for Chapter 8 313(1) Supplementary Exercises for Chapter 8 314(5) Writing Projects for Chapter 8 319(1) Graphs 320(47) Graphs and Graph Models 320(3) Graph Terminology and Special Types of Graphs 323(6) Representing Graphs and Graph Isomorphism 329(7) Connectivity 336(6) Euler and Hamilton Paths 342(5) Shortest-Path Problems 347(4) Planar Graphs 351(4) Graph Coloring 355(12) Guide to Review Questions for Chapter 9 359(1) Supplementary Exercises for Chapter 9 360(5) Writing Projects for Chapter 9 365(2) Trees 367(32) Introduction to Trees 367(5) Applications of Trees 372(9) Tree Traversal 381(4) Spanning Trees 385(5) Minimum Spanning Trees 390(9) Guide to Review Questions for Chapter 10 393(1) Supplementary Exercises for Chapter 10 394(3) Writing Projects for Chapter 10 397(2) Boolean Algebra 399(21) Boolean Functions 399(4) Representing Boolean Functions 403(2) Logic Gates 405(3) Minimization of Circuits 408(12) Guide to Review Questions for Chapter 11 416(1) Supplementary Exercises for Chapter 11 417(2) Writing Projects for Chapter 11 419(1) Modeling Computation 420(32) Languages and Grammars 420(7) Finite-State Machines with Output 427(5) Finite-State Machines with No Output 432(5) Language Recognition 437(4) Turing Machines 441(11) Guide to Review Questions for Chapter 12 445(1) Supplementary Exercises for Chapter 12 446(4) Writing Projects for Chapter 12 450(2) APPENDIXES 452(3) Appendix 1 Axioms for the Real Numbers and the Positive Integers 452(2) Appendix 2 Exponential and Logarithmic Functions 454(1) Appendix 3 Pseudocode 454(1) A Guide to Proof-Writing 455(11) References and Advice on Writing Projects 466(8) Sample Chapter Tests with Solutions 474(28) Common Mistakes in Discrete Mathematics 502(10) Solving Problems in Discrete Mathematics 502(1) List of Common Mistakes 503(9) Crib Sheets 512