A Mathematical Foundation for Computer Science

✍ Scribed by David Mix Barrington

• Year: 2019
• Tongue: English
• Leaves: 731
• Edition: Revised Preliminary Edition
• Category: Library

✦ Table of Contents

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