Discrete Structures, Logic, and Computability by Hein, James L. -- Read -- Imperial Library of Trantor

Index

Title Page Copyright Page Contents Preface 1 Elementary Notions and Notations

1.1 A Proof Primer

Statements and Truth Tables Something to Talk About Proof Techniques Exercises

1.2 Sets

Definition of a Set Operations on Sets Counting Finite Sets Bags (Multisets) Sets Should Not Be Too Complicated Exercises

1.3 Ordered Structures

Tuples Lists Strings and Languages Relations Counting Tuples Exercises

1.4 Graphs and Trees

Introduction to Graphs Trees Spanning Trees Exercises

2 Facts about Functions

2.1 Definitions and Examples

Definition of a Function Floor and Ceiling Functions Greatest Common Divisor The Mod Function The Log Function Exercises

2.2 Composition of Functions

The Map Function Exercises

2.3 Properties and Applications

Injections, Surjections, and Bijections The Pigeonhole Principle Simple Ciphers Hash Functions Exercises

2.4 Countability

Comparing the Size of Sets Sets That Are Countable Diagonalization Limits on Computability Exercises

3 Construction Techniques

3.1 Inductively Defined Sets

Numbers Strings Lists Binary Trees Cartesian Products of Sets Exercises

3.2 Recursive Functions and Procedures

Numbers Strings Lists Graphs and Binary Trees Two More Problems Infinite Sequences Exercises

3.3 Computer Science: Grammars

Recalling English Grammar Structure of Grammars Derivations Constructing Grammars Meaning and Ambiguity Exercises

4 Binary Relations and Inductive Proof

4.1 Properties of Binary Relations

Composition of Relations Closures Path Problems Exercises

4.2 Equivalence Relations

Definition and Examples Equivalence Classes Partitions Generating Equivalence Relations Exercises

4.3 Order Relations

Partial Orders Topological Sorting Well-Founded Orders Ordinal Numbers Exercises

4.4 Inductive Proof

Proof by Mathematical Induction Proof by Well-Founded Induction A Variety of Examples Exercises

5 Analysis Tools and Techniques

5.1 Analyzing Algorithms

Worst-Case Running Time Decision Trees Exercises

5.2 Summations and Closed Forms

Basic Summations and Closed Forms Approximating Sums Approximations with Definite Integrals Harmonic Numbers Polynomials and Partial Fractions Exercises

5.3 Permutations and Combinations

Permutations (Order Is Important) Combinations (Order Is Not Important) Exercises

5.4 Discrete Probability

Probability Terminology Conditional Probability Independent Events Finite Markov Chains Elementary Statistics Properties of Expectation Approximations (the Monte Carlo Method) Exercises

5.5 Solving Recurrences

Solving Simple Recurrences Divide-and-Conquer Recurrences Generating Functions Exercises

5.6 Comparing Rates of Growth

Big Oh Big Omega Big Theta Little Oh Using the Symbols Exercises

6 Elementary Logic

6.1 How Do We Reason? 6.2 Propositional Calculus

Well-Formed Formulas and Semantics Logical Equivalence Truth Functions and Normal Forms Adequate Sets of Connectives Exercises

6.3 Formal Reasoning

Proof Rules Proofs Derived Rules Theorems, Soundness, and Completeness Practice Makes Perfect Exercises

6.4 Formal Axiom Systems

An Example Axiom System Other Axiom Systems Exercises

7 Predicate Logic

7.1 First-Order Predicate Calculus

Predicates and Quantifiers Well-Formed Formulas Interpretations and Semantics Validity The Validity Problem Exercises

7.2 Equivalent Formulas

Logical Equivalence Normal Forms Formalizing English Sentences Summary Exercises

7.3 Formal Proofs in Predicate Calculus

Universal Instantiation (UI) Existential Generalization (EG) Existential Instantiation (EI) Universal Generalization (UG) Examples of Formal Proofs Exercises

7.4 Equality

Describing Equality Extending Equals for Equals Exercises

8 Applied Logic

8.1 Program Correctness

Imperative Program Correctness Array Assignment Termination Exercises

8.2 Higher-Order Logics

Classifying Higher-Order Logics Semantics Higher-Order Reasoning Exercises

8.3 Automatic Reasoning

Clauses and Clausal Forms Resolution for Propositions Substitution and Unification Resolution: The General Case Theorem Proving with Resolution Logic Programming Remarks Exercises

9 Algebraic Structures and Techniques

9.1 What Is an Algebra?

Definition of an Algebra Concrete Versus Abstract Working in Algebras Inheritance and Subalgebras Exercises

9.2 Boolean Algebra

Simplifying Boolean Expressions Digital Circuits Exercises

9.3 Congruences and Cryptology

Congruences Cryptology: The RSA Algorithm Exercises

9.4 Abstract Data Types

Natural Numbers Data Structures Exercises

9.5 Computational Algebras

Relational Algebras Functional Algebras Exercises

9.6 Morphisms

Exercises

10 Graph Theory

10.1 Definitions and Examples

Traversing Edges Complete Graphs Complement of a Graph Bipartite Graphs Exercises

10.2 Degrees

Regular Graphs Degree Sequences Construction Methods Exercises

10.3 Isomorphic Graphs

Exercises

10.4 Matching in Bipartite Graphs

The Matching Algorithm Hall’s Condition for Matching Perfect Matching Exercises

10.5 Two Traversal Problems

Eulerian Graphs Hamiltonian Graphs (Visiting Vertices) Exercises

10.6 Planarity

Euler’s Formula Characterizing Planarity Exercises

10.7 Coloring Graphs

Chromatic Numbers Bounds on Chromatic Number Exercises

11 Languages and Automata

11.1 Regular Languages

Regular Expressions The Algebra of Regular Expressions Exercises

11.2 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

11.3 Constructing Efficient Finite Automata

Another Regular Expression to NFA Algorithm Transforming an NFA into a DFA Minimum-State DFAs Exercises

11.4 Regular Language Topics

Regular Grammars Properties of Regular Languages Exercises

11.5 Context-Free Languages

Exercises

11.6 Pushdown Automata

Equivalent Forms of Acceptance Context-Free Grammars and Pushdown Automata Exercises

11.7 Context-Free Language Topics

Grammar Transformations Properties of Context-Free Languages Exercises

12 Computational Notions

12.1 Turing Machines

Definition of a Turing Machine Turing Machines with Output Alternative Definitions A Universal Turing Machine Exercises

12.2 The Church-Turing Thesis

Equivalence of Computational Models A Simple Programming Language Partial Recursive Functions Machines That Transform Strings Exercises

12.3 Computability

Effective Enumerations The Halting Problem The Total Problem Other Problems Exercises

12.4 A Hierarchy of Languages

Hierarchy Table Exercises

12.5 Complexity Classes

The Class P The Class NP The Class PSPACE Intractable Problems Reduction Formal Complexity Theory Exercises

Answers to Selected Exercises References Symbol Glossary Index

← Prev
Back
Next →

← Prev
Back
Next →