Logik in der Informatik Prof. Dr. Martin Grohe

Institut für Informatik

Aktuelles

Die erste Sitzung des Proseminar findet am Freitag den 20. April statt. Wir beginnen mit den ersten Vorträgen am Freitag den 1.Juni. Bitte lesen Sie alle bis dahin [S] Kap. II, §1 und §2 (S.14-19).

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. Allerdings stößt man mit solchen 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

Freitags 9 - 11 im Erwin Schrödinger Zentrum (Rudower Chaussee 26), Raum 1'307

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 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.
[F]	T. Franzen, Gödel's Theorem.
[NN]	E. Nagel, J. R. Newman, Gödel's Proof.
[S2]	R. M. Smullyan, To Mock a Mockingbird - and Other Logic Puzzles.

Vorträge

Vortrag 1 (1. Juni 2007)

[S] Kap. I, S.5-8 oben.

Folien zu Vortrag 1

Vortrag 2 (1. Juni 2007)

[S] Kap. I, S.8 unten-12.

Folien zu Vortrag 2

Vortrag 3 (8. Juni 2007)

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

Folien zu Vortrag 3

Vortrag 4 (8. Juni 2007)

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

Folien zu Vortrag 4

Vortrag 5 (15. Juni 2007)

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

Folien zu Vortrag 5

Vortrag 6 (15. Juni 2007)

[S] Kap. III, §3 und §4 (S.33-37 oben).

Folien zu Vortrag 6

Vortrag 7 (22.Juni 2007)

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

Folien zu Vortrag 7

Vortrag 8 (22. Juni 2007)

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

Folien zu Vortrag 8

Vortrag 9 (29. Juni 2007)

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

Folien zu Vortrag 9

Vortrag 10 (29. Juni 2007)

[S] Kap. V, §1 (S.56-61).

Folien zu Vortrag 10

Vortrag 11 (6. Juli 2007)

[S] Kap. V, §2 (S.61-66).

Vortrag 12 (6. Juli 2007)

[S] Kap. V, §3 und §4 (S.66-71).

Vortrag 13 (13. Juli 2007)

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