Week 1
- Finite State Automaton
- Logical Encoding
- Propositional Logic
- Well-Formed Formula
- Formula Parsing
- Truth Function
- Valuation
- Modus Ponens
Optional, but interesting:
Week 2
- Model
- Semantic Consequence
- Validity
- Satisfiability
- Substitution
- Resolution (Propositional Logic)
- Negative Normal Form
- Conjunctive Normal Form
- Naïve Satisfiability Algorithm
Week 3
Week 4
- Universe
- Interpretation
- Model
- Variable Assignment
- Truth Value
- Quantifier Equivalences
- Conventions in Predicate Logic
- Skolemization
- CNF (Predicate Logic)
Week 5
- Unification
- Factoring
- Resolution (Predicate Logic)
- Resolution Proof (Predicate Logic)
- Soundness & Completeness
- Horn Clause
- Horn Clause Satisfiability Algorithm
- Automated Reasoning
Week 6
- Computational Problem
- Computational Model
- Finite State Automata
- Language
- Regular Language
- Non-Deterministic Finite Automata (NFA)
Week 7
- Determinisation Of NFAs
- Reversing a FSA
- Minimally Equivalent DFA
- Regular Expression
- Language Operation Axioms
Week 8
- Extended Transition Function
- Memorylessness Lemma
- Distinguishable Pair
- Fooling Set
- Non-Regular Languages
Week 9
Week 10
- Machine Model
- Turing Machine
- Decidability
- Recognisability
- Multi-tape Turing Machine
- Turing Machine Encoding
- Computational Model Problems
- Acceptance Problem
- Emptiness Problem
- Equivalence Problem
Week 11
- Church-Turing Thesis
- Computability
- TM Simulation
- Unrecognisable Language
- Diagonalisation (Proof Technique)
- Proof By Reduction