Grundbegriffe der mathematischen Logik
- Vorlesung: Dienstag 13:05-14:35, Hörsaal 3 (UZA2)
- Übungen: Donnerstag 12:05-12:50, Hörsaal 1 (UZA2), gehalten von Jakob Kellner.
Aktuell: Die erste Übungsstunde findet schon am 7. März statt. Das erste Übungsblatt ist auf Jakob Kellners Seite zu den Übungen zu finden. Es erfordert keine Kenntnisse aus der Vorlesung.
Stoff / Skript
Die Vorlesung behandelt die Elemente der Rekursionstheorie und die Prädikatenlogik der 1. Stufe bis zu Gödels erstem Unvollständigkeitssatz. Inhaltsverzeichnis:
- Primitive Rekursivität: 1. Primitiv rekursive und LOOP-berechenbare Funktionen. 2. Äquivalenz von primitiver Rekursivität und LOOP-Berechenbarkeit. 3. Hyperoperationen und Ackermannfunktion.
- Elemente der Prädikatenlogik: 1. Signaturen und Strukturen. 2. Strings, Sprachen, Aussagenlogik. 3. Formeln und Tarskis Definition der Wahrheit.
- Rekursivität: 1. Rekursive und GOTO-berechenbare Funktionen. 2. Äquivalenz von Rekursivität und GOTO-Berechenbarkeit. 3. Rekursive Aufzählbarkeit und das Halteproblem.
- Prädikatenlogik der 1. Stufe: 1. Beweisbarkeit. 2. Vollständigkeitssatz. 3. Erster Unvollständigkeitssatz.
Die Vorlesung folgt dem Skript vom Vorjahr (400 KB), das evt. noch im Detail korrigiert und durch Kommentare ergänzt wird.
Termine
Datum | Dienstag | Donnerstag |
---|---|---|
5./7. März | Vorlesung 1.1 | Übung |
12./14. März | Vorlesung 1.2 | Übung |
19./21. März | Vorlesung 1.3 | Übung |
26./28. März | Osterferien | Osterferien |
2./4. April | Osterferien | Osterferien |
9./11. April | Vorlesung 2.1 | Übung |
16./18. April | Vorlesung 2.2 | Übung |
23./25. April | Vorlesung 2.3 | Übung |
30. April 2. Mai | Prüfung | Übung |
7./9. Mai | Vorlesung 3.1 | Christi Himmelfahrt |
14./16. Mai | Vorlesung 3.2 | Übung |
21./23. Mai | Pfingstferien | Übung |
28./30. Mai | Vorlesung 3.3 | Fronleichnam |
4./6. Juni | Vorlesung 4.1 | Übung |
11./13. Juni | Vorlesung 4.2 | Übung |
18./20. Juni | Vorlesung 4.3 | Übung |
25./27. Juni | Prüfung | evt. Übung? |
Prüfungen
Zur Vorlesung und zu den Übungen gab es insgesamt zwei schriftliche Prüfungen. Die erste Prüfung fand am 30. April zum Termin der Vorlesung statt, zählte aber für die Übungen. Dadurch und durch den Termin in der Semestermitte war ihr Gewicht reduziert.
Die wichtigere Prüfung, auf der die Vorlesungsnote basiert, fand am 25. Juni zum letzten Vorlesungstermin statt.
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.)