CSS.202.1 Mathematical Logic

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