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