Logic in Computer Science

This course is over.

Lectures and Tutorials (4 SWS/6 ECTS)

This course provides an introduction to mathematical logic under a computer science perspective. Topics include propositional logic, first-order and second-order logic, completeness and incompleteness results therein, finite model theory and its relation to computation, and introductions to temporal logic, modal logic, and further non-standard logics suitable for the design and analysis of computational systems and processes.

Knowledge equivalent to an introductory course on theoretical computer science is recommended for this class.

Times

Lectures:Tuesday, 17:00-18:30, F 423 (Sven Kosub
Thursday, 13:30-15:00, ML 630 (Sven Kosub)
Oral exams:July 2017, PZ 1004 (1st date)
October 2017, PZ 1004 (2nd date)

Homework Assignments

There will be tutorials every to weeks on Thursday during the lecture time. Assignments are made available on this webpage as a PDF-file (in English) on Thursday in intermediate weeks. You have one week for preparing your solutions. The assignment sheet will then be discussed in the tutorial. Note that there will be no corrections and no scores for your assignments.

Content

The following topics are planned:

  • Propositional logic
  • Predicate logic
  • Completeness, incompleteness, undecidability
  • Finite model theory
  • Temporal logic
  • Modal logic

Lecture Notes

Lecture notes are made available close in time to the lectures. The current version can be downloaded here. In case you have suggestions or comments (typos or any kind of errors) please send an email.

Literature

In-depth and background material of certain course aspects can be found in:

  • Mordechai Ben-Ari: Mathematical Logic for Computer Science. 3rd edition, Springer, London, 2012.
  • Heinz-Dieter Ebbinghaus, Jörg Flum, Wolfgang Thomas: Mathematical Logic. 2nd edition, Springer-Verlag, New York, NY, 1994. German edition: Einführung in die Mathematische Logik. 5. Auflage, Spektrum Akademischer Verlag, 2007.
  • Heinz-Dieter Ebbinghaus, Jörg Flum: Finite Model Theory. 2nd edition, Springer-Verlag, Berlin, 2005.
  • Michael Huth, Mark Ryan: Logic in Computer Science. Modelling and Reasoning about Systems. 2nd edition, Cambridge University Press, Cambridge, 2004.
  • Wolfgang Rautenberg: Einführung in die Mathematische Logik. Ein Lehrbuch. 3., überarbeitete Auflage, Vieweg + Teubner, Wiesbaden, 2008.