CSS.202.1 Mathematical Logic



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


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