Mathematical Structures for Computer Science: A Modern Approach to Discrete Mathematics Book

Preface Note to the Student

1. Formal Logic
1.1 Statements, Symbolic Representation, and Tautologies
1.2 Propositional Logic
1.3 Quantifiers, Predicates, and Validity
1.4 Predicate Logic
1.5 Logic Programming
1.6 Proof of Correctness

2. Proofs, Recursion, and Analysis of Algorithms
2.1 Proof Techniques
2.2 Induction
2.3 More on Proof of Correctness
2.4 Recursive Definitions
2.5 Recurrence Relations
2.6 Analysis of Algorithms

3. Sets, Combinatorics, Probability, and Number Theory
3.1 Sets
3.2 Counting
3.3 Principle of Inclusion and Exclusion; Pigeonhole Principle
3.4 Permutations and Combinations
3.5 Probability
3.6 Binomial Theorem
3.7 Number Theory

4. Relations, Functions, and Matrices
4.1 Relations
4.2 Topological Sorting
4.3 Relations and Databases
4.4 Functions
4.5 The Mighty Mod Function
4.6 Matrices

5. Graphs and Trees
5.1 Graphs and their Representations
5.2 Trees and their Representations
5.3 Decision Trees
5.4 Huffman Codes

6. Graph Algorithms
6.1 Directed Graphs and Binary Relations; Warshall's Algorithm
6.2 Euler Path and Hamiltonian Circuit
6.3 Shortest Path and Minimal Spanning Tree
6.4 Traversal Algorithms
6.5 Articulation Points and Computer Networks

7. Boolean Algebra and Computer Logic
7.1 Boolean Algebra Structure
7.2 Logic Networks
7.3 Minimization

8. Modeling Arithmetic, Computation, and Languages
8.1 Algebraic Structures
8.2 Finite-State Machines
8.3 Turing Machines
8.4 Formal Languages

Appendixes
Appendix A Derivation Rules for Propositional and Predicate Logic Appendix B Summation Notation Appendix C The Logarithm Function Answers to Practice Problems Answers to Selected Exercises Answers to Self-Tests Index