November Lectures

Week of November 1-5

Nov 1: Tautologies; satisfiable and unsatisfiable formulas.
Nov 5: Logical implication and equivalences; some important laws.
Tutorial: Structural induction.

Week of November 8-12

Nov 8: Normal forms: DNF, CNF.
Nov 12: Predicate logic: introduction, combining predicates, quantifiers; examples.
Tutorial: Complete sets of connectives.

Week of November 15-19

Nov 15: Predicate logic: the syntax of predicate logic (first-order languages, predicate formulas, free variables).
Nov 19: Semantics of predicate logic: structures, valuations, interpretations, truth value of a formula; prenex normal form.
Tutorial: Logical implication and equivalences; some important logical equivalences.

Week of November 22-26

Nov 22: Prenex normal form; predicate logic and relational databases; comments on A4.
Nov 26: Introduction to Finite State Automata; languages, operations on languages, regular expressions.
Tutorial: Languages and strings.

Week of November 29 - December 3

Nov 29: Regular expressions; deterministic FSA.
Dec 3: More on DFSA's; NFSA's.
Tutorial: DFSA and NFSA examples.

Week of December 6-10

Dec 6: More on NFSA's; equivalence between DFSA and NFSA.
Dec 10: Course evaluation. Exam preparation.
Tutorial: Example of the equivalence between regular expressions and FSA; A5 handed in.