Text (required): Logic for Applications by Anil Nerode and Richard A. Shore, Second Edition, Graduate Texts in Computer Science, Springer Verlag. (ISBN 0-387-94893-7)
Syllabus: Propositional Logic, Predicate Logic (Chapter I, 1-6; Chapter II, 1-8). If time permits: Ultraproducts of Relational Systems.
Grading: Final 80%, Homework: 20%
Take-Home Final Due Thursday, July 5
Homework Problems (due dates will be announced in class):
p.11: 1-3, 7
p.99: 1, 2, 5, 8
An algorithm for checking correct syntax of formulas: Hall's Theorem for Propositional Formulas
Generalities on closure: Closure Operators and Galois Connections
The Ultraproduct Theorem is an important tool for the construction of models. It is not difficult to derive a purely algebraic proof of the Compactness Theorem from it.