Discrete Mathematics with ApplicationsThis approachable text studies discrete objects and the relationsips that bind them. It helps students understand and apply the power of discrete math to digital computer systems and other modern applications. It provides excellent preparation for courses in linear algebra, number theory, and modern/abstract algebra and for computer science courses in data structures, algorithms, programming languages, compilers, databases, and computation. * Covers all recommended topics in a self-contained, comprehensive, and understandable format for students and new professionals * Emphasizes problem-solving techniques, pattern recognition, conjecturing, induction, applications of varying nature, proof techniques, algorithm development and correctness, and numeric computations* Weaves numerous applications into the text* Helps students learn by doing with a wealth of examples and exercises: - 560 examples worked out in detail - More than 3,700 exercises - More than 150 computer assignments - More than 600 writing projects* Includes chapter summaries of important vocabulary, formulas, and properties, plus the chapter review exercises* Features interesting anecdotes and biographies of 60 mathematicians and computer scientists* Instructor's Manual available for adopters* Student Solutions Manual available separately for purchase (ISBN: 0124211828) |
Contents
| 1 | |
| 67 | |
Chapter 3 Functions and Matrices | 117 |
Chapter 4 Induction and Algorithms | 185 |
Chapter 5 Recursion | 261 |
Chapter 6 Combinatorics and Discrete Probability | 343 |
Chapter 7 Relations | 437 |
Chapter 8 Graphs | 515 |
Chapter 12 Boolean Algebra and Combinatorial Circuits | 803 |
Appendix A | 867 |
References | 899 |
Solutions to OddNumbered Exercises | 907 |
Credits | 1029 |
| 1031 | |
| 1042 | |
| 1043 | |
Chapter 9 Trees | 609 |
Chapter 10 Digraphs | 691 |
Chapter 11 Formal Languages and FiniteState Machines | 733 |
| 1044 | |
List of Symbols | 1045 |
Common terms and phrases
accepted addition adjacency algebra algorithm applications Assume begin binary boolean called Chapter circuit column compute connected Consider consists construct contains corresponding defined definition denote Determine digit digraph divisible edges elements equivalence exactly example Exercises exists expression Figure Find Find the number finite five formula four function given graph illustrates induction input instance language least length letter logic loop mathematics matrix move needed operations output pair path positive integer possible prime principle probability problem proof properties proposition Prove Read recurrence relation recursive relation represented result selected sequence shows simple SOLUTION Solve sort square statement step string subsets Suppose symbols Table takes Theorem theory transitive tree true truth University various verify vertex vertices weight Write yields