Essentials of Discrete Mathematics, 3/e

Contents:

Preface • How to Use This Book

Chapter 1: Logical Thinking • Formal Logic • Inquiry Problems • Connectives and Propositions • Truth Tables • Logical Equivalences • Exercises • Propositional Logic • Tautologies and Contradictions • Derivation Rules • Proof Sequences • Forward?Backward • Exercises • Predicate Logic • Predicates • Quantifiers • Translation • Negation • Two Common Constructions • Exercises • Logic in Mathematics • The Role of Definitions in Mathematics • Other Types of Mathematical Statements • Counterexamples • Axiomatic SystemsExercises • Methods of Proof • Direct Proofs • Proof by Contraposition • Proof by Contradiction • Exercises

Chapter 2: Relational Thinking • Graphs • Edges and Vertices • Terminology • Modeling Relationships with Graphs • Exercises • Sets • Membership and Containment • New Sets from Old • Identities • Exercises • Functions • Definition and Examples • One-to-One and Onto Functions • New Functions from Old • Exercises • Relations and Equivalences • Definition and Examples • Graphs of Relations • Relations vs. Functions • Equivalence Relations • Modular Arithmetic • Exercises • Partial Orderings • Definition and Examples • Hasse Diagrams • Topological Sorting • Isomorphisms • Boolean Algebras??? • Exercises • Graph Theory • Graphs: Formal DefinitionsIsomorphisms of Graphs • Degree Counting • Euler Paths and Circuits • Hamilton Paths and Circuits • Trees • Exercises

Chapter 3: Recursive Thinking • Recurrence Relations • Definition and Examples • The Fibonacci Sequence • Modeling with Recurrence Relations • Exercises • Closed-Form Solutions and Induction • Guessing a Closed-Form Solution • Polynomial Sequences: Using Differences??? • Inductively Verifying a Solution • Exercises • Recursive Definitions • Definition and Examples • Writing Recursive Definitions • Recursive Geometry • Recursive Jokes • Exercises • Proof by Induction • The Principle of Induction • Examples • Strong Induction • Structural Induction • Exercises • Recursive Data Structures • Lists • Efficiency • Binary Search Trees Revisited • Exercises

Chapter 4: Quantitative Thinking • Basic Counting Techniques • Addition • Multiplication • Mixing Addition and Multiplication • Exercises • Selections and Arrangements • Permutations: The Arrangement Principle • Combinations: The Selection Principle • The Binomial Theorem??? • Exercises • Counting with Functions • One-to-One Correspondences • The Pigeonhole Principle • The Generalized Pigeonhole Principle • Ramsey Theory??? • Exercises • Discrete Probability • Definitions and Examples • Applications • Expected Value • Exercises • Counting Operations in Algorithms • Algorithms • Pseudocode • Sequences of Operations • Loops • Arrays • Sorting • Exercises • Estimation • Growth of Functions • Estimation Targets • Properties of Big-T • Exercises

Chapter 5: Analytical Thinking • Algorithms • More Pseudocode • Preconditions and Postconditions • Iterative Algorithms • Functions and Recursive Algorithms • Exercises • Three Common Types of Algorithms • Traversal Algorithms • Greedy Algorithms • Divide-and-Conquer Algorithms • Exercises • Algorithm Complexity • The Good, the Bad, and the Average • Approximate Complexity Calculations • Exercises • Bounds on Complexity • Algorithms as Decisions • A Lower Bound • Searching an Array • Sorting • P vs. NP • Exercises • Program Verification • Verification vs. Testing • Verifying Recursive Algorithms • Searching and Sorting • Towers of Hanoi • Exercises • Loop Invariants • Verifying Iterative Algorithms • Searching and Sorting • Using Invariants to Design Algorithms • Exercises

Chapter 6: Thinking Through Applications • Patterns in DNA • Mutations and Phylogenetic Distance • Phylogenetic Trees • UPGMA • Exercises • Social Networks • Definitions and Terminology • Notions of Equivalence • Hierarchical Clustering • Signed Graphs and Balance • Exercises • Structure of Languages • Terminology • Finite-State Machines • Recursion • Further Issues in Linguistics • Exercises • Discrete-Time Population Models • Recursive Models for Population Growth • Fixed Points, Equilibrium, and Chaos • Predator?Prey Systems • The SIR Model • Exercises • Twelve-Tone Music • Twelve-Tone Composition • Listing All Permutations • Transformations of Tone Rows • Equivalence Classes and Symmetry • Exercises

Hints, Answers, and Solutions to Selected Exercises • Formal Logic • Propositional Logic • Predicate Logic • Logic in Mathematics • Methods of Proof • Graphs • Sets • Functions • Relations and Equivalences • Partial Orderings • Graph Theory • Recurrence Relations • Closed-Form Solutions and Induction • Recursive Definitions • Proof by Induction • Recursive Data Structures • Basic Counting Techniques • Selections and Arrangements • Counting with Functions • Discrete Probability • Counting Operations in Algorithms • Estimation • Algorithms • Three Common Types of Algorithms • Algorithm Complexity • Bounds on Complexity • Program Verification • Loop Invariants

Selected References

Index

Index of Symbols


 

About the Author:
David J. Hunter,  PhD-Westmont College

David Hunter earned a B.S. in mathematics from the University of Illinois, and received an M.S. and Ph.D. in mathematics from the University of Virginia. He currently teaches mathematics and computer science at Westmont College in Santa Barbara, CA. His research interests include algebra, topology, and discrete methods. In addition to teaching and writing, he enjoys hacking, mountain biking, and rooting for four of the five professional sports teams from Chicago.