A Mathematical Foundation for Computer Science

Chapter 1: Sets, Propositions, and Predicates
	1.1 Sets
	1.2 Strings and String Operations
	1.3 Excursion: What is a Proof?
	1.4 Propositions and Boolean Operations
	1.5 Set Operations and Propositions About Sets
	1.6 Truth-Table Proofs
	1. 7 Rules for Propositional Proofs
	1.8 Propositional Proof Strategies
	1. 9 Excursion: A Murder Mystery
	1.10 Predicates
	1.11 Excursion: Translating Predicates
Chapter 2: Quantifiers and Predicate Calculus
	2.1 Relations
	2.2 Excursion: Relational Databases
	2.3 Quantifiers
	2.4 Excursion: Translating Quantifiers
	2.5 Operations on Languages
	2.6 Proofs With Quantifiers
	2 .7 Excursion: Practicing Proofs
	2.8 Properties of Binary Relations
	2.9 Functions
	2.10 Partial Orders
	2.11 Equivalence Relations
Chapter 3: Number Theory
	3.1 Divisibility and Primes
	3.2 Excursion: Playing With Numbers
	3.3 Modular Arithmetic
	3.4 There are Infinitely Many Primes
	3.5 The Chinese Remainder Theorem
	3.6 The Fundamental Theorem of Arithmetic
	3.7 Excursion: Expressing Predicates in Number Theory
	3.8 The Ring of Congruence Classes
	3.9 Finite Fields and Modular Exponentiation
	3.10 Excursion: Certificates of Primality
	3 .11 The RSA Cryptosystem
Chapter 4: Recursion and Proof by Induction
	4.1 Recursive Definition
	4.2 Excursion: Recursive Algorithms
	4.3 Proof By Induction for Naturals
	4.4 Variations on Induction for Naturals
	4.6 Proving the Basic Facts of Arithmetic
	4.7 Recursive Definition for Strings
	4.8 Excursion: Naturals and Strings
	4 .9 Graphs and Paths
	4.10 Trees and Lisp Lists
	4 .11 Induction For Problem Solving
Chapter 5: Regular Expressions and Other Recursive Systems
	5.1 Regular Expressions and Their Languages
	5.2 Examples of Regular Languages
	5.3 Excursion: Designing Regular Expressions
	5.4 Proving Regular Language Identities
	5.5 Proving Properties of the Regular Languages
	5.6 Excursion: Hofstadter's MU-Puzzle
	5.7 Recursion and Induction in General
	5.8 Top-Down and Bottom-Up Definitions
	5.9 Excursion: Parsing Arithmetic Expressions
	5.10 A Recursive Definition of Imperative Programs
	5.11 Correctness of Imperative Programs
Chapter 9: Trees and Searching
	9.1 Graphs, Trees, and Recursion
	9.2 Excursion: Boolean Expressions
	9.3 Expressions and Recursive Algorithms
	9.4 General Search Algorithms
	9.6 Depth-First and Breadth-First Search on Graphs
	9. 7 Excursion: Middle-First Search
	9.8 Uniform-Cost Search
	9.9 A* Search
	9 .10 Adversary Search
	9.11 Excursion: Hexapawn
Chapter 14: Finite-State Machines
	14.1 Deterministic Finite Automata
	14.2 Proving that DFA's Can't Do Things
	14.3 The Myhill-Nerode Theorem
	14.4 Excursion: Syntactic Monoids
	14.5 Nondeterministic Finite Automata
	14.6 The Subset Construction: NFA's into DFA's
	14. 7 Killing .\-Moves: >.-NF A's into NF A's
	14 .8 Constructing ,\-NFA's From Regular Expressions
	14.9 Excursion: Practicing Multiple Constructions.
	14.10 State Elimination: NFA's into Regular Expressions
	14.11 Excursion: Another Way From NFA's to Regular Expressions.
Chapter 15: A Brief Tour of Formal Language Theory
	15.1 Two-Way Deterministic Finite Automata
	15.2 Grammars, Regular and Otherwise
	15.3 Context-Free Languages
	15.4 Excursion: Chomsky Normal Form
	15.5 CFL's and Pushdown Automata
	15.6 Turing Machine Definitions
	15. 7 Excursion: Unrestricted Grammars
	15.8 Turing Machine Semantics
	15.9 Excursion: Turing-Hangable Languages
	15.10 The Halting Problem and Unsolvabilit
	15.11 A Brief Look at Complexity Theory