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.21: 3,4,5,8,9,10
p.26: 2,3,4
p.35: 1,5,6,7,8,9
p.94: 1-3
p.99: 1, 2, 5, 8
p.118: 1-4
p.125: 2,3,4,11
Additional problems.
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.