|
Logik in der Informatik
Prof. Dr. Nicole Schweikardt |
|
Aktuelles Einführung Inhalte Logbuch Termine Prüfung Literatur Links
Die mathematische Logik beschäftigt sich mit den grundlegenden Eigenschaften von formalen Systemen und Sprachen, insbesondere der Ausdrucksstärke von formalen Sprachen und Beweissystemen sowie den Möglichkeiten und Grenzen des automatischen Schließens.
In dieser Vorlesung werden ausgewählte Kapitel der mathematischen Logik und deren Anwendungen in der Informatik behandelt. Themen der Vorlesung sind u.a.der Vollständigkeitssatz, die Sätze von Löwenheim und Skolem und die Gödelschen Unvollständigkeitssätze.
Die Vorlesung richtet sich an fortgeschrittene Studierende in einem Masterstudiengang, die sich im Bereich der Logik spezialisieren wollen. Voraussetzung für die Teilnahme an der Veranstaltung sind Kenntnisse, die in der Veranstaltung "Logik in der Informatik" vermittelt werden.
Das folgende Inhaltsverzeichnis wird im Laufe der Vorlesung noch ergänzt und möglicherweise verändert.
Skript-Fragmente
zu Kapitel 0, 1 (ohne den Teil über nicht-abzählbare Signaturen) und 2
Notizen zu Kapitel 1
(nicht-abzählbare Signaturen) - Seiten 1-7 (Version vom 19.05.2016)
Notizen zu Kapitel 1
(Exkurs: Auswahlaxiom, Wohlordnungssatz und Zornsches Lemma) - Seiten
8-19 (Version vom 25.05.2016)
Notizen zu
Kapitel 3 (Hinweis: In diesen Notizen müssen alle Nummern der Form "9.x"
durch "3.x" ersetzt werden)
Notizen zu
Kapitel 4 (Hinweis: In diesen Notizen müssen alle Nummern der Form "10.x"
durch "4.x" ersetzt werden)
Beachten Sie:
In den Vorlesungs- und Übungsstunden wird hauptsächlich an der Tafel
gearbeitet.
Alle behandelten Inhalte
sind für die Veranstaltung wesentlich und daher auch dann
prüfungsrelevant, wenn sie nicht in den auf den Webseiten erhältlichen
Materialien enthalten sind.
Zur Vorbereitung auf eine Prüfung wird dringend empfohlen,
das gesamte in den Vorlesungs- und Übungsstunden vermittelte
Material durchzuarbeiten.
Es ist daher wichtig, dass Sie sich während der Vorlesungs- und Übungsstunden
Notizen machen.
Hier finden Sie nach den Vorlesungen Informationen zum Inhalt der einzelnen Vorlesungsstunden und gelegentlich ergänzende Bemerkungen.
Dozentin: Prof. Dr. Nicole Schweikardt
Übungsleiter: André Frochaux
Ab der zweiten Vorlesungswoche wird wöchentlich ein Übungsblatt ausgegeben. Auf jedem Übungsblatt können bis zu 100 Punkte erreicht werden.
Das aktuelle Übungsblatt wird jeweils dienstags in der Übung bzw. am Ende der Vorlesung in gedruckter Form ausgeteilt und außerdem im Laufe des Nachmittag hier online bereit gestellt.
Zur Vorbereitung auf eine Prüfung (Modulabschlussprüfung) ist es unbedingt notwendig, das gesamte in den Vorlesungsstunden vermittelte Material durchzuarbeiten.
Die Modulabschlussprüfung wird durch eine mündliche Prüfung abgelegt. Termine für mündliche Modulabschlussprüfungen können nach Vereinbarung bei Frau Sandig angefragt werden.
Voraussetzung für die Zulassung zur Prüfung sind:
Verbindliche "Spielregeln" zum Erwerb von Übungspunkten:
Übungsblätter werden dienstags nach der Vorlesung ausgeteilt. Das jeweilige Übungsblatt wird in der Übungsstunde der darauf folgenden Woche besprochen. Sie können bei jedem Übungsblatt entscheiden, gemäß welcher der folgenden beiden Varianten A bzw. B Ihre Lösung bewertet werden soll:
Variante A:
Sie geben eine schriftliche, ausführlich ausgearbeitete und
mathematisch präzise Lösung spätestens direkt vor Beginn der Übungsstunde am Donnerstag
ab.
Variante B:
Sie geben keine Lösung ab. Stattdessen tragen Sie direkt
vor Beginn der Übung in eine vom Übungsleiter bereitgestellte Liste ein,
wie viele Übungspunkte Sie für Ihre Lösung der einzelnen Aufgaben(teile)
für gerechtfertigt halten.
Während der Übungsstunde werden vom Übungsleiter aus dieser Liste
einzelne Teilnehmer zum Vorrechnen von Aufgaben(teilen) ausgesucht.
Falls sich beim Vorrechnen herausstellen sollte, dass Sie
keine sinnvolle Lösung vorweisen können, obwohl Sie in der Liste
Punkte für diese(n) Aufgabe(nteil) eingetragen haben, werden Ihnen
für das gesamte gerade behandelte Übungsblatt keine Übungspunkte
angerechnet. Eine sinnvolle Lösung muss hierbei nicht notwendigerweise
vollständig korrekt sein.
| [EFT] | H.-D. Ebbinghaus, J. Flum, W. Thomas, Einführung in die mathematische Logik, Spektrum Akademischer Verlag, 4. Auflage, 1996 |
| [S-LI] | N. Schweikardt, Skript zur Vorlesung "Logik in der Informatik" im Wintersemester 2018/19, Humboldt-Universität zu Berlin. Link |
| [E] | H.-D. Ebbinghaus Einführung in die Mengenlehre, Spektrum Akademischer Verlag, 4. Auflage, 2003 |
| [BBJ] | G. S. Boolos, J. P. Burgess, R. C. Jeffrey. Computability and Logic, 5th Edition, Cambridge University Press, 2007. |
| [S] |
N. Schweikardt,
A short tutorial on order-invariant logics, Proceedings of
the 8th International Computer Science Symposium in Russia
(CSR'13),
volume 7913 of Lecture Notes in Computer Science,
pages 112-126, Springer-Verlag, 2013.
Eine Vorabversion des Artikels findet sich hier; Folien zu einer Vorlesungsreihe, die ich zum Thema "order-invariant logics" während der Scandinavian Summer School in Logic 2015 gehalten habe, finden sich hier. |
| [LICS] | IEEE Symposium on Logic in Computer Science (LICS) |
| [EACSL] | European Association for Computer Science Logic (EACSL) |
| [Highlights] | Highlights in Logic, Games and Automata |