CS 81 Notes
- Introduction to Logic
- Well-Formed Formulas
- Models of Classical Logic
- Entailment
- Abbreviating WFFs
- English to WFFs
- Proof Systems
- Resolution
- Propositional Natural Deduction
- Metatheory
- Syntax and Models
- English to Predicate Formulas
- Predicate Natural Deduction
- Proofs for Humans
- Bounded Quantifiers
- Proofs with Implication and Equivalence
- Proofs with Quantifiers
- Proofs in Asymptotic Analysis
- Mathematical Induction
- Countable Sets
- Uncountable Sets
- Prolog
- Prolog to English
- Unification
- Depth-First Search
- DFS Consequences
- List Predicates
- Generate-and-Test
- (In)Equality in Prolog
- Manipulating Lists
- Negation
- Introduction
- String Theory
- State Machines
- Regular Languages
- Kleene's Theorem
- Closure Properties of Regular Languages
- Extended Regular Expressions
- Nonregular Languages and Distinguishable Strings
- Nonregular Languages and the Pumping Lemma
- Context-Free Languages (CFLs)
- Context-Free Grammars (CFGs)
- Parse Trees
- Non-Context-Free Languages
- The CYK Algorithm
- Regular Grammars
- Unrestricted Grammars
- Turing Machines
- Decidability
- Reductions
- Mapping Reductions
- Rice's Theorem
- Computation Histories
- Post Correspondence Problem
- Preconditions, Postconditions, and Invariants