| |

| |

| |

Elementary Notions and Notations | |

| |

| |

| |

A Proof Primer | |

| |

| |

| |

Logical Statements | |

| |

| |

| |

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 | |

| |

| |

| |

Relations | |

| |

| |

| |

Counting Tuples | |

| |

| |

Exercises | |

| |

| |

| |

Graphs and Trees | |

| |

| |

| |

Definition of a Graph | |

| |

| |

| |

Paths and Graphs | |

| |

| |

| |

Graph Traversals | |

| |

| |

| |

Trees | |

| |

| |

| |

Spanning Trees | |

| |

| |

Exercises | |

| |

| |

| |

Chapter Summary | |

| |

| |

| |

Facts about Functions | |

| |

| |

| |

Definitions and Examples | |

| |

| |

| |

Definition of a Function | |

| |

| |

| |

Some Useful Functions | |

| |

| |

| |

Partial Functions | |

| |

| |

Exercises | |

| |

| |

| |

Constructing Functions | |

| |

| |

| |

Composition of Functions | |

| |

| |

| |

The Map Function | |

| |

| |

Exercise | |

| |

| |

| |

Properties of Functions | |

| |

| |

| |

Injections and Surjections | |

| |

| |

| |

Bijections and Inverses | |

| |

| |

| |

The Pigeonhole Principle | |

| |

| |

| |

Simple Ciphers | |

| |

| |

| |

Hash Functions | |

| |

| |

Exercises | |

| |

| |

| |

Countability | |

| |

| |

| |

Comparing the Size of Sets | |

| |

| |

| |

Sets that Are Countable | |

| |

| |

| |

Diagonalization | |

| |

| |

| |

Limits on Computability | |

| |

| |

Exercises | |

| |

| |

| |

Chapter Summary | |

| |

| |

| |

Construction Techniques | |

| |

| |

| |

Inductively Defined Sets | |

| |

| |

| |

Numbers | |

| |

| |

| |

Strings | |

| |

| |

| |

Lists | |

| |

| |

| |

Binary Trees | |

| |

| |

| |

Cartesian Products of Sets | |

| |

| |

Exercises | |

| |

| |

| |

Recursive Functions and Procedures | |

| |

| |

| |

Numbers | |

| |

| |

| |

Strings | |

| |

| |

| |

Lists | |

| |

| |

| |

Binary Trees | |

| |

| |

| |

Two More Problems | |

| |

| |

| |

Infinite Sequences | |

| |

| |

Exercises | |

| |

| |

| |

Grammars | |

| |

| |

| |

Recalling an English Grammar | |

| |

| |

| |

Structure of Grammars | |

| |

| |

| |

Derivations | |

| |

| |

| |

Constructing Grammars | |

| |

| |

| |

Meaning and Ambiguity | |

| |

| |

Exercises | |

| |

| |

| |

Chapter Summary | |

| |

| |

| |

Equivalence, Order, and Inductive Proof | |

| |

| |

| |

Properties of Binary Relations | |

| |

| |

| |

Composition of Relations | |

| |

| |

| |

Closures | |

| |

| |

| |

Path Problems | |

| |

| |

Exercises | |

| |

| |

| |

Equivalence Relations | |

| |

| |

| |

Definition and Examples | |

| |

| |

| |

Equivalence Classes | |

| |

| |

| |

Partitions | |

| |

| |

| |

Generating Equivalence Relations | |

| |

| |

Exercises | |

| |

| |

| |

Order Relations | |

| |

| |

| |

Partial Orders | |

| |

| |

| |

Topological Sorting | |

| |

| |

| |

Well-Founded Orders | |

| |

| |

| |

Ordinal Numbers | |

| |

| |

Exercises | |

| |

| |

| |

Inductive Proof | |

| |

| |

| |

Proof by Mathematical Induction | |

| |

| |

| |

Proof by Well-Founded Induction | |

| |

| |

| |

A Variety of Examples | |

| |

| |

Exercises | |

| |

| |

| |

Chapter Summary | |

| |

| |

| |

Analysis Techniques | |

| |

| |

| |

Analyzing Algorithms | |

| |

| |

| |

Worst-Case Running Time | |

| |

| |

| |

Decision Trees | |

| |

| |

Exercises | |

| |

| |

| |

Finding Closed Forms | |

| |

| |

| |

Closed Forms for Sums | |

| |

| |

Exercises | |

| |

| |

| |

Counting and Discrete Probability | |

| |

| |

| |

Permutations (Order Is Important) | |

| |

| |

| |

Combinations (Order Is Not Important) | |

| |

| |

| |

Discrete Probability | |

| |

| |

Exercises | |

| |

| |

| |

Solving Recurrences | |

| |

| |

| |

Solving Simple Recurrences | |

| |

| |

| |

Generating Functions | |

| |

| |

Exercises | |

| |

| |

| |

Comparing Rates of Growth | |

| |

| |

| |

Big Theta | |

| |

| |

| |

Little Oh | |

| |

| |

| |

Big Oh and Big Omega | |

| |

| |

Exercises | |

| |

| |

| |

Chapter Summary | |

| |

| |

| |

Elementary Logic | |

| |

| |

| |

How Do We Reason? | |

| |

| |

| |

What Is a Calculus? | |

| |

| |

| |

How Can We Tell Whether Something Is a Proof? | |

| |

| |

| |

Propositional Calculus | |

| |

| |

| |

Well-Formed Formulas and Semantics | |

| |

| |

| |

Equivalence | |

| |

| |

| |

Truth Functions and Normal Forms | |

| |

| |

| |

Complete Sets of Connectives | |

| |

| |

Exercises | |

| |

| |

| |

Formal Reasoning | |

| |

| |

| |

Inference Rules | |

| |

| |

| |

Formal Proof | |

| |

| |

| |

Proof Notes | |

| |

| |

Exercises | |

| |

| |

| |

Formal Axiom Systems | |

| |

| |

| |

An Example Axiom System | |

| |

| |

| |

Other Axiom Systems | |

| |

| |

Exercises | |

| |

| |

| |

Chapter Summary | |

| |

| |

| |

Predicate Logic | |

| |

| |

| |

First-Order Predicate Calculus | |

| |

| |

| |

Predicates and Quantifiers | |

| |

| |

| |

Well-Formed Formulas | |

| |

| |

| |

Semantics and Interpretations | |

| |

| |

| |

Validity | |

| |

| |

| |

The Validity Problem | |

| |

| |

Exercises | |

| |

| |

| |

Equivalent Formulas | |

| |

| |

| |

Equivalence | |

| |

| |

| |

Normal Forms | |

| |

| |

| |

Formalizing English Sentences | |

| |

| |

| |

Summary | |

| |

| |

Exercises | |

| |

| |

| |

Formal Proofs in Predicate Calculus | |

| |

| |

| |

Universal Instantiation | |

| |

| |

| |

Existential Generalization (EG) | |

| |

| |

| |

Existential Instantiation (EI) | |

| |

| |

| |

Universal Generalization (UG) | |

| |

| |

| |

Examples of Formal Proofs | |

| |

| |

| |

Summary of Quantifier Proofs Rules | |

| |

| |

Exercises | |

| |

| |

| |

Chapter Summary | |

| |

| |

| |

Applied Logic | |

| |

| |

| |

Equality | |

| |

| |

| |

Describing Equality | |

| |

| |

| |

Extending Equals for Equals | |

| |

| |

Exercises | |

| |

| |

| |

Program Correctness | |

| |

| |

| |

Imperative Program Correctness | |

| |

| |

| |

Array Assignment | |

| |

| |

| |

Termination | |

| |

| |

Exercises | |

| |

| |

| |

Higher-Order Logics | |

| |

| |

| |

Classifying Higher-Order Logics | |

| |

| |

| |

Semantics | |

| |

| |

| |

Higher-Order Reasoning | |

| |

| |

Exercises | |

| |

| |

| |

Chapter Summary | |

| |

| |

| |

Computational Logic | |

| |

| |

| |

Automatic Reasoning | |

| |

| |

| |

Clauses and Clausal Forms | |

| |

| |

| |

Resolution for Propositions | |

| |

| |

| |

Substitution and Unification | |

| |

| |

| |

Resolution: The General Case | |

| |

| |

| |

Theorem Proving with Resolution | |

| |

| |

| |

Remarks | |

| |

| |

Exercises | |

| |

| |

| |

Logic Programming | |

| |

| |

| |

Family Trees | |

| |

| |

| |

Definition of a Logic Program | |

| |

| |

| |

Resolution and Logic Programming | |

| |

| |

| |

Logic Programming Techniques | |

| |

| |

Exercises | |

| |

| |

| |

Chapter Summary | |

| |

| |

| |

Algebraic Structures and Techniques | |

| |

| |

| |

What Is an Algebra? | |

| |

| |

| |

Definition of an Algebra | |

| |

| |

| |

Concrete Versus Abstract | |

| |

| |

| |

Working in Algebras | |

| |

| |

Exercises | |

| |

| |

| |

Boolean Algebra | |

| |

| |

| |

Simplifying Boolean Expressions | |

| |

| |

| |

Digital Circuits | |

| |

| |

Exercises | |

| |

| |

| |

Abstract Data Types as Algebras | |

| |

| |

| |

Natural Numbers | |

| |

| |

| |

Lists and Strings | |

| |

| |

| |

Stacks and Queues | |

| |

| |

| |

Binary Trees and Priority Queues | |

| |

| |

Exercises | |

| |

| |

| |

Computational Algebras | |

| |

| |

| |

Relational Algebras | |

| |

| |

| |

Functional Algebras | |

| |

| |

Exercises | |

| |

| |

| |

Other Algebraic Ideas | |

| |

| |

| |

Congruence | |

| |

| |

| |

Cryptology: The RSA Algorithm | |

| |

| |

| |

Subalgebras | |

| |

| |

| |

Morphisms | |

| |

| |

Exercises | |

| |

| |

| |

Chapter Summary | |

| |

| |

| |

Regular Languages and Finite 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 Expressions | |

| |

| |

| |

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 | |

| |

| |

| |

Chapter Summary | |

| |

| |

| |

Context-Free Languages and Pushdown Automata | |

| |

| |

| |

Context-Free Languages | |

| |

| |

Exercises | |

| |

| |

| |

Pushdown Automata | |

| |

| |

| |

Equivalent Forms of Acceptance | |

| |

| |

| |

Context-Free Grammars and Pushdown Automata | |

| |

| |

| |

Representing and Executing Pushdown Automata | |

| |

| |

Exercises | |

| |

| |

| |

Parsing Techniques | |

| |

| |

| |

LL(k) Parsing | |

| |

| |

| |

LR(k) Parsing | |

| |

| |

Exercises | |

| |

| |

| |

Context-Free Language Topics | |

| |

| |

| |

Transforming Grammars | |

| |

| |

| |

Properties of Context-Free Languages | |

| |

| |

Exercises | |

| |

| |

| |

Chapter Summary | |

| |

| |

| |

Turing Machines and Equivalent Models | |

| |

| |

| |

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 | |

| |

| |

| |

Recursive Functions | |

| |

| |

| |

Machines That Transform Strings | |

| |

| |

Exercises | |

| |

| |

| |

Chapter Summary | |

| |

| |

| |

Computational Notions | |

| |

| |

| |

Computability | |

| |

| |

| |

Effective Enumerations | |

| |

| |

| |

The Halting Problem | |

| |

| |

| |

The Total Problem | |

| |

| |

| |

Other Problems | |

| |

| |

Exercises | |

| |

| |

| |

A Hierarchy of Languages | |

| |

| |

| |

The Languages | |

| |

| |

| |

Summary | |

| |

| |

Exercises | |

| |

| |

| |

Complexity Classes | |

| |

| |

| |

The Class P | |

| |

| |

| |

The Class NP | |

| |

| |

| |

The Class PSPACE | |

| |

| |

| |

Intractable Problems | |

| |

| |

| |

Completeness | |

| |

| |

| |

Formal Complexity Theory | |

| |

| |

Exercises | |

| |

| |

| |

Chapter Summary | |

| |

| |

Answers to Selected Exercises | |

| |

| |

Bibliography | |

| |

| |

Greek Alphabet | |

| |

| |

Symbol Glossary | |

| |

| |

Index | |