Discrete Mathematics Book

(All chapters, except Chapter 10, conclude with a Chapter Summary and Supplementary Exercises.)

1. Sets, Subsets, Induction and Recursion.

The Pascal Triangle (Application: A Counting Problem).

Induction (Application: The Tower of Hanoi).

Sets, Subsets, and Binary Strings (Application: The Knapsack Problem).

Set Operations (Application: An Error-Correcting Code).

Recursions (Application: Shift Registers).

2. Integers, Remainders, and the Golden Ratio.

The Integers (Application: When is Div(n) a Tree?).

Lamé's Theorem (Application: Egyptian Fractions).

The Integers Mod n (Application: Public Key Encryption).

3. Functions, Relations, and Counting.

Functions and Relations (Application: The Prüfer Correspondence).

Counting Rules (Application: Boolean Functions).

Three Counting Techniques (Application: Tenth Powers).

4. Graphs.

Graphs (Application: The Icosahedron and Dodecahedron).

Graph Theory (Application: One-Way Streets).

Trees (Application: Structural Induction).

5. Proof Techniques and Logic.

Proof Techniques (Application: The Liar Problem).

Logic (Application: Logic and the Genetic Code).

The Propositional Calculus (Application: Syllogisms).

6. Boolean Algebras, Boolean Functions, and Logic.

Boolean Algebras and Functions (Application: Normal Forms in the Propositional Calculus).

Boolean Functions and Circuits (Application: Regions in Logic Diagrams).

The Predicate Calculus (Application: Proving Program Correctness).

7. Graphs and Relations.

Graph Coloring and Matching (Application: Register Allocation).

Posets and Lattices (Application: The Kirkman Schoolgirl Problem).

8. Algorithms.

Sorting, Searching, and Listing (Application: The Man, Dog, Goat, and Cabbage Problem).

Graph Algorithms (Application: Network Flows).

The Complexity of an Algorithm (Application: Kruskal's Algorithm and Prim's Algorithm).

9. Combinatorics.

Recursions and Their Solution (Application: AVL trees).

Probabilities (Application: Network Reliability).

Groups and Counting (Application: Rooted Trees).

10. Models of Computation.

Languages and Grammars (Application: The Chomsky Heirarchy).

Finite State Machines and Turing Machines (Application: DNA Computing).

Gödel and Turing (Application: The Vanishing).

Appendices.

Guide to the Literature.

Notes.

Answers to Selected Exercises.

Index.