Discrete Structures, Logic, and Computability, 4/e

Contents:

Preface 

Chapter 1: Elementary Notions and Notations: A Proof primer • Statements and Truth Tables • Something to Talk About • Proof Techniques • Exercises • Sets • Definition of a Set • Operations on Sets • Counting Finite Sets • Bags (Multisets) • Sets Should Not Be Too Complicated • Exercises • Ordered Structures • Tuples • Lists • Strings and Languages • Relation • Counting Tuples • Exercises • Graphs and Tress • Introduction to Graphs • Trees • Spanning Trees • Exercises

Chapter 2: Facts about Functions • Definitions and Examples • Definitions of a Function • Floor and Ceiling Functions • Greatest Common Divisor • The Mod Function • The Log Function • Exercises • Composition of Functions • The Map Function • Exercises • Properties and Applications • Injections, Surjections, and Bijections • The Pigeonhole Principle • Simple Ciphers • Hash Functions • Exercise • Countability • Comparing the Size of Sets • Sets That Are Countable • Diagonalization • Limits on Computability • Exercises

Chapter 3: Construction Techniques • Inductively Defined Sets • Numbers • Strings • Lists • Binary Trees • Cartesian Products of Sets • Exercises • Recursive Functions and Procedures • Numbers • Strings • Lists • Graphs and Binary Trees • Two More Problems • Infinite Sequences • Exercises • Computer Science: Grammars • Recalling English Grammar • Structure of Grammars • Derivations • Constructing Grammars • Meaning and Ambiguity • Exercises

Chapter 4: Binary Relationships and Inductive Proof • Properties of Binary Relation • Compohsition of Relations • Closures • Path Problems • Exercises • Equivalence Relations • Definition and Examples • Equivalence Classes • Partitions • Generating Equivalence Relations • Exercise • Order Relations • Partial Orders • Topological Sorting • Well-Founded Orders • Ordinal Numbers • Exercises • Inductive Proof • Proof by Mathematical Induction • Proof by Well-Funded Induction • A Variety of Examples • Exercises

Chapter 5: Analysis Tools and Techniques • Analyzing Algorithms • Worst-Case Running Time • Decision Trees • Exercises • Summations and Closed Forms • Basic Summations and Closed Forms • Approximating Sums • Approximations with Definite Integrals • Harmonic Numbers • Polynomials and Partial Fractions • Exercises • Permutations and Combinations • Permutations (Order Is Important) • Combinations (Order Is Not Important) • Exercises • Discrete Probability • Probability Terminology • Conditional Probability • Independent Events • Finite Markov Chains • Elementary Statistics • Approximations (Monte Carlo Method) • Exercises • Solving Recurrences • Solving Simple Recurrences • Divide-and-Conquer Recurrences • Generating Functions • Exercises • Comparing Rates of Growth • Big Oh • Big Omega • Big Theta • Little Oh • Using the symbols • Exercises

Chapter 6: Elementary Logic • How Do We Reason? • Propositional Calculus • Well-Formed Formulas and Semantics • Logical Equivalence • Truth Functions and Normal Forms • Adequate Sets of Connectives • Exercises • Formal Reasoning • Proof Rules • Proofs • Derived Rules • Theorems, Soundness, and Completeness • Practice Makes Perfect • Exercises • Formal Axiom Systems • An Example Axiom System • Other Axiom Systems • Exercises

Chapter 7: Predicate Logic • First-Order Predicate Calculus • Predicates and Quantifiers • Well-Formed Formulas • Interpretations and Semantics • Validity • The Validity Problem • Exercises • Equivalent Formulas • Logical Equivalence • Normal Forms • Formalizing English Sentences • Summary • Exercises • Formal Proofs in Predicate Calculus • Universal Instantiation (UI) • Existential Generalizations (EG) • Existential Instantiation (EI) • Universal Generalization (UG) • Examples of Formal Proofs • Exercises • Equality • Describing equality • Extending Equals for Equals • Exercises

Chapter 8: Applied Logic • Program Correctness • Imperative Program Correctness • Array Assignment • Termination • Exercises • Higher-Order Logics • Classifying Higher-Order Logics • Semantics • Higher-Order Reasoning • Exercises • Automatic Reasoing • Clauses and Clausal Forms • Resolution for Propositions • Substitution and Unification • Resolution: The General Case • Theorem Proving with Resolution • Logic Programming • Remarks • Exercises

Chapter 9: Algebraic Structures and Techniques • What Is an Algebra? • Definition of an Algebra • Concrete Versus Abstract • Working in Algebras • Inheritance and Subalgebras • Exercises • Boolean Algebra • Simplifying Boolean Expressions • Digital Circuits • Exercises • Congruences and Cryptology • Congruences ?
Cryptology: The RSA Algorithm • Exercises • Abstract Data Types • Natural Numbers • Data Structures • Exercises • Computational Algebras • Relational Algebras • Functional Algebras • Exercises • Morphisms • Exercises

Chapter 10: Graphy Theory • Definitions and Examples • Traversing Edges • Complete Graphs • Complement of a Graph • Bipartite Graphs • Exercises • Degrees • Regular Graphs • Degree Sequences • Construction Methods • Exercises • Isomorphic Graphs • Exercises • Matching in Bipartite Graphs • The Matching Algorithm • Hall's Condition for Matching • Perfect Matching • Exercises • Two Traversal Problems • Eulerian Graphs (Traversing Edges) • Hamiltonian Graphs (Visiting Vertices) • Exercises • Planarity • Euler's Formula • Characterizing Planarity • Exercises • Coloring Graphs • Chromatic Numbers • Bounds on Chromatic Numbers • Exercises

Chapter 11: Languages and Automata • Regular Languages • Regular Expressions • The Algebra of Regular Expressions • Exercises • Finite Automata • Deterministic Finite Automata • Nondeterministic Finite Automata • Transforming Regular Expressions into Finite Automata • Transforming Finite Automata into Regular Expression • Finite Automata as Output Devices • Representing and Executing Finite Automata • Exercises • Constructing Efficient Finite Automata • Another Regular Expression to NFA Algorithm • Transforming an NFA into a DFA • Minimum-State DFAs • Exercises • Regular Language Topics • Regular Grammars • Properties of Regular Languages • Exercises • Context-Free Languages • Exercises • Pushdown Automata • Equivalent Forms of Acceptance • Context-Free Grammars and Pushdown Automata • Exercises • Context-Free Language Topics • Grammar Transformations • Properties of Context-Free Languages • Exercies

Chapter 12: Computational Notions • Turing Machines • Definition of a Turing Machine • Turing Machines with Output • Alternative Definitions • A Universal Turing Machine • Exercises • The Church-Turing Thesis • Equivalence of Computational Models • A Simple Programming Language • Partial Recursive Functions • Machines That Transform Strings • Exercises • Computability • Effective Enumeration • The Halting Problem The Total Problem • Other Problems • Exercises • A Hierachy of Languages • Summary • Exercises • Complexity Classes • The Class P • The Class NP • The Class PSPACE • Intractable Problems • Reduction and NP- Completeness • Formal Complexity Theory • Exercises

Answers to Selected Exercises

Refernces

Symbol Glossary

Index 

About the Author:

James L. Hein, Professor Emeritus, Portland State University

James Hein is a Professor Emeritus in the Department of Computer Science at Portland State University. He has a PhD in mathematics from Northwestern University and an MS in computer science from Stanford University. He continues to enjoy finding ways to help students learn about the mathematical foundations of computer science.