About the Book

Essentials of Discrete Mathematics is the ideal text for a one-term discrete mathematics course to serve computer science majors as well as students from a wide range of other disciplines. The material is organized around five types of mathematical thinking: logical, relational, recursive, quantitative, and analytical. This presentation results in a coherent outline that steadily builds upon mathematical sophistication. Graphs are introduced early and are referred to throughout the text, providing a richer context for examples and applications. Students will encounter algorithms near the end of the text, after they have acquired enough skills and experience to analyze them properly. The final chapter contains in-depth case studies from a variety of fields, including biology, sociology, linguistics, economics, and music. Clear and concise, Essentials of Discrete Mathematics presents a unified and complete picture of discrete mathematics that instructors can move through in a single semester.

About the Author

David J. Hunter, PhD - Westmont College

Table of Contents:
Chapter 1: Logical Thinking • Formal logic • 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 • Counter examples • Axiomatic systems • Exercises • Methods of proof • Direct proofs • Proof by contraposition • Proof by contradiction 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 • Definitions 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 definitions • Isomorphisms of graphs • Degree counting • Euler paths and circuits • Hamilton paths and circuits • Trees • Exercises Chapter 3: Recursive thinking • Recurrence relations • Definitions 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 correspondence • The pigeonhole principle • The generalised 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 • Estimations • Growth of functions • Estimation targets • Properties of Big • 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 of 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 • Heirarchical 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 Hints, Answers, and Solution to Selected Excercises • Index • Index of symbols