## Instructor:

## Semester:

- 2012 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.