Logik in der Informatik Prof. Dr. Martin Grohe

Institut für Informatik

Aktuelles

Wir beginnen mit den ersten Voträgen am Dienstag, dem 3. Mai. Bitte lesen Sie alle bis dahin [S] Kap. II, §1 und §2 (S.14-19). Denken Sie daran, dass wir um 17:00 (und nicht um 17:15) beginnen. Eine Liste mit allen Terminen finden Sie hier.

Einführung

Zentrale Ergebnisse der Logik sind Vollständigkeitssätze, die im Prinzip besagen, dass sich das logische Folgern "mechanisch" in gewissen Beweiskalkülen nachvollziehen läßt. Alllerdings stößt man mit solche mechanischen Verfahren zum logischen Schließen schnell an prinzipielle Grenzen. Das wird etwa deutlich in der "Unentscheidbarkeit der Logik der ersten Stufe", welche besagt, dass es keinen Algorithmus gibt, der entscheidet, ob ein gegebener Satz der Logik der ersten Stufe erfüllbar ist.

Diese Grenzen der formalen Methode werden wir in diesem Proseminar genauer untersuchen, von grundlegenden Fragen der Berechenbarkeitstheorie wollen wir uns dabei bis zu den Gödelschen Unvollständigkeitssätzen vorarbeiten.

Das Proseminar schließt sich in an die Vorlesung "Theoretische Informatik I" an, vorausgesetzt werden deshalb gute Kenntnisse des in dieser Vorlesung behandelten Stoffes.

Zeit und Raum

Montags 17-19 im Johann von Neumann Haus (Rudower Chaussee 25), Raum 4.112

Literatur

Alle Vorträge kommen aus folgendem Buch:

[S]	R. M. Smullyan. Gödel's Incompleteness Theorems.

Ergänzend sei auch noch auf die folgenden beiden Bücher verwiesen:

[EFT]	H.-D. Ebbinghaus, J. Flum, W. Thomas, Einführung in die Mathematische Logik.
[BBJ]	G. S. Boolos, J. P. Burgess, R. C. Jeffrey. Computability and Logic.

Vorträge

Vortrag 1 (3. Mai 2004)

[S] Kap. I, S.5-8 (oben). Christian Otto

Vortrag 2 (3. Mai 2004)

[S] Kap. I, S.8-12. Mario Bogacz

Vortrag 3 (10. Mai 2004)

[S] Kap. II, §3-5 (S.19-24). Moritz Grauel

Vortrag 4 (10. Mai 2004)

[S] Kap. II, §6 (S.24-27). Jonathan Hellwig

Vortrag 5 (17. Mai 2004)

[S] Kap. III, §1 und §2 (S.28-33). Thomas Kunze

Vortrag 6 (17. Mai 2004)

[S] Kap. III, §3 (S.33-36). Alexandre Krestiachine

Vortrag 7 (17. Mai 2004)

[S] Kap. III, §4 (S.36-39). Björn Schümann

Vortrag 8 (24. Mai 2004)

[S] Kap. IV, §1-3 (S.40-45). Kornelius Kalnbach

Vortrag 9 (14. Juni 2004)

[S] Kap. IV, §4 und §5 (S.45-49). Steen Manniche

Vortrag 10 (14. Juni 2004)

[S] Kap. IV, §6 und Teil II (S.49-53). Peter Siemen

Vortrag 11 (21. Juni 2004)

[S] Kap. V, §1 (S.56-61). Björn Schümann

Vortrag 12 (21. Juni 2004)

[S] Kap. V, §2 (S.61-66). Moritz Grauel, Jonathan Hellwig

Vortrag 13 (28. Juni 2004)

[S] Kap. V, §3 und §4 (S.66-71). Mario Bogacz, Steen Manniche (?)

Vortrag 14 (28. Juni 2004)

[S] Kap. V, §5 und §6 (S.71-74). Christian Otto

Vortrag 15 (5. Juli 2004)

[S] Kap. VI, §1 und §2 (S.75-80). Kornelius Kalnbach, Peter Siemen (?)

Vortrag 16 (5. Juli 2004)

[S] Kap. VI, §3-5 (S.81-85). Thomas Kunze, Alexandre Krestiachine

Termine

3. Mai, 10. Mai, 17. Mai, 24. Mai, 14. Juni, 21. Juni, 28. Juni, 5. Juli.
(Der 1. Juni ist Feiertag, am 7. Juni und 12. Juli fällt das Proseminar aus).