## Instructor:

## Semester:

- 2013 Autumn/Monsoon (Aug - Dec)

Syllabus: Propositional logic: Syntax and Semantics, Applications of Propositional Calculus, Properties: functional completeness, decidability, compactness, conjunctive and disjunctive normal forms. Hintikka's lemma and model existence theorem. Semantic tableaux: soundness, completeness and decidability. Hilbert proof systems and Gentzen's sequent calculus. Predicate logic: Syntax and semantics. Applications of predicate logic. Herbrand models. Hintikka's lemma and model existence theorem. Compactness. First-order semantic tableaux: Soundness and completeness. Hilbert proof system for first-order logic and deduction theorem. Gentzen's sequent calculus for First Order Logic. First-order logic with Equality: Axioms and completeness. Normal forms. Properties: Lowenheim-Skolem theorem, Compactness, Interpolation and Definability. Some First-order theories: Presburger and Peano Arithmetic. First-order theory of reals. ZFC axioms for set theory. Limitations: Undecidability of First-order logic. Tarski's Theorem on Undefinability of Truth. Godel's Incompleteness Theorems. Suggested Reading: J. Harrison: Handbook of Practical Logic and Automated Reasoning, Cambridge University Press, 2009. H.B. Enderton: A Mathematical Introduction to Logic, Second Edition, Academic Press, 2001. R.M. Smullyan, First-Order Logic, Dover Publications, 1994. J.H. Gallier: Logic for Computer Science, John Wiley and Sons, 1987. H.D. Ebbinghaus, J. Flum, W. Thomas: Mathematical logic, Second Edition, Springer-Verlag, 1984. M. Fitting: First-order logic and automated theorem proving, Springer-Verlag, 1990.