Logik in der Informatik
Prof. Dr. Martin Grohe

Vorlesung Logik in der Informatik

Aktuelles Einführung Inhalt Logbuch Vorlesung Übungen Aufgaben Prüfung Literatur

Aktuelles

An dieser Stelle finden Sie im Laufe der Vorlesung aktuelle Mitteilungen.

Sie können sich diese Vorlesung als mathematisches Ergänzungsfach anrechnen lassen.

Einführung

Logik beschäftigt sich mit den grundlegenden Eigenschaften von formalen Systemen und Sprachen. Wichtige Themen der Logik in der Informatik sind die Ausdruckstärke formaler Sprachen und die Grenzen und Möglichkeiten des automatischen Schließens. Anwendungen der Logik finden sich in so unterschiedlichen Bereichen der Informatik wie Rechnerarchitektur, Softwaretechnik, Programmiersprachen, Datenbanken, künstliche Intelligenz, Komplexitäts- und Berechenbarkeitstheorie.

Aufbauend auf den Grundlagen der Theoretischen Informatik I werden in dieser Vorlesung auch tiefliegendere Ergebnisse und Zusammenhänge aus der Logik vorgestellt. Dabei wird es sowohl um klassische Sätze der mathematischen Logik, etwa die Gödelschen Unvollständigkeitssätze, als auch um die Anwendungen in verschiedenen Bereichen der Informatik gehen.

Inhalt und Skript

Durch Anklicken der einzelnen Kapitel erhalten Sie das Vorlesungsskript. Als Hintergrund mag auch das Skript für meine Vorlesung Theoretische Informatik 1 nützlich sein.

Logbuch

Hier finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungen und gelegentlich ergänzende Bemerkungen.

Informationen zum Vorlesungsbetrieb

Zeiten und Raum: Dienstags und Donnerstags 09-11 Uhr im Schrödinger Zentrum (Rudower Chaussee 26), Raum 1'308
Dozent: Prof. Dr. Martin Grohe; Sprechstunde in WS09/10: Dienstags 11-12 Uhr

Übungen

Ergänzend zu den Vorlesungen finden 2-stündige Übungen statt.

Zeit und Raum: Donnerstags 11-13 Uhr im Schrödinger Zentrum (Rudower Chaussee 26), Raum 1'308
Übungsleiter: Kord Eickmeyer

Übungsaufgaben

Es gibt regelmäßig Übungsaufgaben, deren erfolgreiche Bearbeitung (mindestens 40% der Punkte) Voraussetzung für den Scheinerwerb und die Zulassung zur Prüfung ist.

Blatt 1 (20.10.2009; Abgabe am 27.10.2009)
Blatt 2 (27.10.2009; Abgabe am 3.11.2009)
Blatt 3 (3.11.2009; Abgabe am 10.11.2009)
Blatt 4 (10.11.2009; Abgabe am 17.11.2009)
Blatt 5 (17.11.2009; Abgabe am 24.11.2009)
Blatt 6 (24.11.2009; Abgabe am 1.12.2009)
Blatt 7 (1.12.2009; Abgabe am 8.12.2009)
Blatt 8 (8.12.2009; Abgabe am 15.12.2009)
Blatt 9 (5.1.2010; Abgabe am 12.1.2010)
Blatt 10 (12.1.2010; Abgabe am 19.1.2010)
Blatt 11 (19.1.2010; Abgabe am 26.1.2010)
Blatt 12 (26.1.2010; Abgabe am 2.2.2010)

Prüfung

Zu Beginn der Semesterferien finden mündliche Prüfungen statt. Für die Zulassung zur Prüfung müssen mindestens 40% der Punkte in den Übungsaufgaben erworben werden.

Literatur

Die Vorlesung orientiert sich vor allem an folgenden beiden Büchern:

[EFT]	H.-D. Ebbinghaus, J. Flum, W. Thomas, Einführung in die Mathematische Logik. 4. Auflage, Spektrum Akademischer Verlag, 1996.
[HR]	M. Huth and M. Ryan, Logic in Computer Science – Modelling and Reasoning About Systems . 2nd Edition, Cambridge University Press, 2004.

Als Ergänzung seien auch noch folgende Bücher genannt:

[B]	S. Burris, Logic for Mathematics and Computer Science. Prentice Hall, 1998.
[C]	P. J. Cameron, Sets, Logic and Categories. Springer Verlag, 1998.
[BBJ]	G.S. Boolos, J.P. Burgess, and R.C. Jeffrey, Computability and Logic. 4. Auflage, Cambridge University Press, 2002.
[CL]	R. Cori und D. Lascar, Mathematical Logic - A Course with Exercises. Part I und Part II. Oxford University Press, 2000.
[NS]	A. Nerode und R.A. Shore, Logic for Applications. 2nd Edition, Springer-Verlag 1997.
[S]	U. Schöning, Logik für Informatiker. 5. Auflage, Spektrum Akademischer Verlag, 2000.
[vD]	D. van Dalen, Logic and Structure. 4th Edition, Springer Verlag, 2004.

Last modified: Wed Feb 10 09:40:47 CET 2010
Martin Grohe