Elements of Mathematical Logic



  • 2012 Autumn/Monsoon (Aug - Dec)


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.

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.

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.