## Instructor:

## Semester:

- 2021 Autumn/Monsoon (Aug - Dec)

- Propositional Calculus:
- 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 system and Gentzen's sequent calculus.

- First-order logic:
- Syntax and semantics.
- Applications of First-order 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.
- Limitations of First-order logic.

- Logic and Computability:
- Undecidability of First-order logic.

References

- H.B. Enderton: A Mathematical Introduction to Logic, Second Edition, Academic Press, 2001.
- J.H. Gallier: Logic for Computer Science, John Wiley and Sons, 1987.
- H.D. Ebbinghaus, J. Flum, W. Thomas: Mathematical logic, Springer-Verlag, 1984.
- M. Fitting: First-order logic and automated theorem proving, Springer-Verlag, 1990.