## Book description

Following the recent updates to the 2013 ACM/IEEE Computer Science curricula, Discrete Structures, Logic, and Computability, Fourth Edition, has been designed for the discrete math course that covers one to two semesters. Dr. Hein presents material in a spiral medthod of learning, introducing basic information about a topic, allowing the students to work on the problem and revisit the topic, as new information and skills are established. Written for prospective computer scientist, computer engineers, or applied mathematicians, who want to learn about the ideas that inspire computer science, this edition contains an extensive coverage of logic, setting it apart from similar books available in the field of Computer Science.

1. Cover Page
2. Title Page
4. Contents
5. Preface
6. 1 Elementary Notions and Notations
1. 1.1 A Proof Primer
2. 1.2 Sets
3. 1.3 Ordered Structures
4. 1.4 Graphs and Trees
1. 2.1 Definitions and Examples
2. 2.2 Composition of Functions
3. 2.3 Properties and Applications
4. 2.4 Countability
8. 3 Construction Techniques
1. 3.1 Inductively Defined Sets
2. 3.2 Recursive Functions and Procedures
3. 3.3 Computer Science: Grammars
9. 4 Binary Relations and Inductive Proof
1. 4.1 Properties of Binary Relations
2. 4.2 Equivalence Relations
3. 4.3 Order Relations
4. 4.4 Inductive Proof
10. 5 Analysis Tools and Techniques
1. 5.1 Analyzing Algorithms
2. 5.2 Summations and Closed Forms
3. 5.3 Permutations and Combinations
4. 5.4 Discrete Probability
5. 5.5 Solving Recurrences
6. 5.6 Comparing Rates of Growth
11. 6 Elementary Logic
1. 6.1 How Do We Reason?
2. 6.2 Propositional Calculus
3. 6.3 Formal Reasoning
4. 6.4 Formal Axiom Systems
12. 7 Predicate Logic
1. 7.1 First-Order Predicate Calculus
2. 7.2 Equivalent Formulas
3. 7.3 Formal Proofs in Predicate Calculus
4. 7.4 Equality
13. 8 Applied Logic
1. 8.1 Program Correctness
2. 8.2 Higher-Order Logics
3. 8.3 Automatic Reasoning
14. 9 Algebraic Structures and Techniques
1. 9.1 What Is an Algebra?
2. 9.2 Boolean Algebra
3. 9.3 Congruences and Cryptology
4. 9.4 Abstract Data Types
5. 9.5 Computational Algebras
6. 9.6 Morphisms
15. 10 Graph Theory
1. 10.1 Definitions and Examples
2. 10.2 Degrees
3. 10.3 Isomorphic Graphs
4. 10.4 Matching in Bipartite Graphs
5. 10.5 Two Traversal Problems
6. 10.6 Planarity
7. 10.7 Coloring Graphs
16. 11 Languages and Automata
1. 11.1 Regular Languages
2. 11.2 Finite Automata
3. 11.3 Constructing Efficient Finite Automata
4. 11.4 Regular Language Topics
5. 11.5 Context-Free Languages
6. 11.6 Pushdown Automata
7. 11.7 Context-Free Language Topics
17. 12 Computational Notions
1. 12.1 Turing Machines
2. 12.2 The Church-Turing Thesis
3. 12.3 Computability
4. 12.4 A Hierarchy of Languages
5. 12.5 Complexity Classes