Logic in Computer Science
(An English-language class)
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.
- Chapters 0-1 - Version: 1.2 - Date: 05/18/17 (PDF, 179 KB)
- Section 2.1 - Version: Slides - Date: 07/11/17 (PDF, 236 KB)
- Section 2.2 - Version: Slides - Date: 07/11/17 (PDF, 673 KB)
- Section 2.3 - Version: Slides - Date: 07/11/17 (PDF, 2 MB)
- Section 2.4 - Version: Slides - Date: 07/11/17 (PDF, 2 MB)
- Chapter 3 - Version: Slides - Date: 07/25/17 (PDF, 840 KB)
- Chapter 4 - Version: Slides - Date: 07/25/17 (PDF, 745 KB)
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.