KGRC – Hans Adler

Grundbegriffe der mathematischen Logik

Aktuell:

Leider habe ich für die Eintragung der Noten eine fehlerhafte Liste benutzt, in der die Namen in zufälliger Weise vertauscht waren. Die korrekte Note finden Sie nach wie vor hier unter Ihrer Matrikelnummer. Der ZID-Helpdesk ist seit Montag verständigt. Ich bitte um Entschuldigung für diesen ärgerlichen Fehler und wünsche Ihnen trotzdem schöne Ferien!

• Vorlesung: Dienstag 16:15-17:45, Hörsaal 2 (UZA2)
• Übungen: Montag 17:00-18:00, Hörsaal 3 (UZA2), gehalten von Moritz Müller.

Stoff

Die Vorlesung behandelt die Elemente der Rekursionstheorie und die Prädikatenlogik der 1. Stufe bis zu Gödels erstem Unvollständigkeitssatz. Vorläufiges Inhaltsverzeichnis:

1. Primitive Rekursivität: 1. Primitiv rekursive und LOOP-berechenbare Funktionen. 2. Äquivalenz von primitiver Rekursivität und LOOP-Berechenbarkeit. 3. Hyperoperationen und Ackermannfunktion.
2. Elemente der Prädikatenlogik: 1. Signaturen und Strukturen. 2. Strings, Sprachen, Aussagenlogik. 3. Formeln und Tarskis Definition der Wahrheit.
3. Rekursivität: 1. Rekursive und GOTO-berechenbare Funktionen. 2. Äquivalenz von Rekursivität und GOTO-Berechenbarkeit. 3. Rekursive Aufzählbarkeit und das Halteproblem.
4. Prädikatenlogik der 1. Stufe: 1. Beweisbarkeit. 2. Vollständigkeitssatz. 3. Erster Unvollständigkeitssatz.

Termine

Skript

• vollständiges Skript (400 KB)

Prüfungen

• Prüfungsblatt zu den Übungen (Semestermitte, nur Kapitel 1+2) mit Lösungen
• Prüfungsblatt zur Vorlesung (Semesterende, Kapitel 1-4) mit Lösungen
• Ergebnisse der Vorlesungsprüfung

Fragen und Rückmeldungen zur Vorlesung: Donnerstag 15-16 Uhr im KGRC, per Email oder nach Vereinbarung. Oder Sie können mich am Freitag gegen 12 Uhr nach dem Bachelorseminar (Raum D101) abpassen. Am Donnerstag oder Freitag können Sie Ihren Zettel zurückbekommen. Während der Ferien gerne auch einen Scan per Email.

Nachtermin für die Prüfungen in Vorlesung und Übungen: voraussichtlich Montag, 1. Oktober 2012. Bei Bedarf bitte bis spätestens Montag, 17. September 2012 per Email anmelden. (Details der Organisation der Prüfung hängen von der Zahl der Anmeldungen ab. Deshalb können verspätete Anmeldungen unter Umständen nicht berücksichtigt werden.)

LOOP-Interpreter

Mit der LOOP-Programmiersprache aus der Vorlesung können Sie in einem Online-Interpreter experimentieren. Ihre LOOP-Programme werden direkt in JavaScript übersetzt und in Ihrem Browser ausgeführt. Falls Sie wollen, können Sie die Seite auch auf Ihrem Computer speichern und offline ausführen.

Literatur

• Martin Ziegler, Mathematische Logik, Vieweg 2010. (Die Vorlesung hat sich ursprünglich an diesem Buch orientiert, auch wenn man das jetzt kaum noch erkennt.)
• Martin Ziegler, Mathematische Logik, Vorlesungsskript Freiburg 2008. (Gegenüber dem Buch fehlt neben den zahlreichen Übungsaufgaben nur ein Kapitel, das in dieser Vorlesung nicht behandelt wird. Das Buch ist aber sehr viel schöner.)
• Ralf Schindler, Logik 1, Vorlesungsskript Münster 2009. (Ralf Schindler hat vor Jahren die Grundbegriffe-Vorlesung in Wien gehalten, und dieses Skript ist daraus hervorgegangen. Er setzt deutlich andere Schwerpunkte.)

Vergleich zur gleichnamigen Vorlesung im Sommersemester 2011

Die Vorlesung umfasste ungefähr denselben Stoff wie im Jahr davor, allerdings mit kleineren Änderungen und einer größeren Umstellung. Informationen zur früheren Vorlesung finden Sie hier. Wesentliche Änderungen:

• Aufteilung der beiden Hauptthemen Rekursionstheorie und Prädikatenlogik in jeweils zwei Kapitel ermöglichte abwechselnde Behandlung.
• Eine schriftliche Prüfung über beide Hauptthemen am Ende des Semesters.
• Dafür gab es aber (nur) in der Mitte des Semesters, nach den beiden ersten Kapiteln, eine schriftliche Prüfung in den Übungen.