Logik in der Informatik Prof. Dr. Nicole Schweikardt

Aktuelles

• Am 19.07.2016 wurde eine aktualisierte Version von Blatt 10 hochgeladen, die eine präzise Formulierung von Aufgabe 3 enthält. Beachten Sie insbes., dass mit Binärbäumen Bäume gemeint sind, bei denen jeder Knoten, der kein Blatt ist, genau 2 Kinder hat.
• Am 25.05.2016 wurde eine neue Version der Skript-Fragmente hochgeladen.
• Im Logbuch finden Sie nach den Vorlesungen Informationen zum Inhalt der einzelnen Vorlesungsstunden und gelegentlich ergänzende Bemerkungen.
• Die Eröffnungsvorlesung fand am Mittwoch, den 20.04.2016 statt.
• Die erste Übungsstunde fand in der zweiten Vorlesungswoche statt, also am Donnerstag, den 28.04.2016.

Einführung

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 Vorlesung "Logik in der Informatik" vermittelt werden.

Inhalte

Das folgende Inhaltsverzeichnis wird im Laufe der Vorlesung noch ergänzt und möglicherweise verändert.

• Kapitel 0: Einleitung
• Kapitel 1: Der Vollständigkeitssatz
• Kapitel 2: Die Sätze von Löwenheim und Skolem
• Kapitel 3: Die Grenzen der Berechenbarkeit
• Kapitel 4: Gödels Unvollständigkeitssätze
• Kapitel 5: Ordnungsinvarianz

Skript-Fragmente zu Kapitel 0, 1 (ohne den Teil über nicht-abzählbare Signaturen) und 2 (Version vom 25.05.2016)
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)
Folien zu Kapitel 5; weitere Details zu Kapitel 5 finden sich bei [S].

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.

Logbuch

Hier finden Sie nach den Vorlesungen Informationen zum Inhalt der einzelnen Vorlesungsstunden und gelegentlich ergänzende Bemerkungen.

Termine

Auf Grund diverser Veranstaltungen (z.B. "Tag der Informatik") und Feiertage werden die Termine für Vorlesung bzw. Übung während des Semesters mehrfach getauscht oder geändert.

Vorlesungen finden an folgenden Terminen statt:
20.4., 21.4., 27.4., 28.4., 12.5., 18.5., 19.5. (an Stelle der Ü findet eine weitere VL statt), 25.5., 26.5. (an Stelle der Ü findet eine weitere VL statt), 1.6., 2.6., 8.6., 15.6., 22.6., 23.6., 29.6., 30.6., 6.7., 7.7. (an Stelle der Ü findet eine weitere VL statt), 13.7., 14.7. (an Stelle der Ü findet eine weitere VL statt)

Übungen finden an folgenden Terminen statt:
28.4., 12.5., 2.6., 9.6. (an Stelle der VL findet eine weitere Ü statt), 23.6., 30.6., 20.7. (an Stelle der VL), 21.7. (an Stelle der VL findet eine weitere Ü statt)
 

Vorlesung

Mittwochs 11:15-13:00 im Schrödinger Zentrum (Rudower Chaussee 26), Raum 1'307 und
Donnerstags 09:15-11:00 im Schrödinger Zentrum (Rudower Chaussee 26), Raum 1'307

Dozentin: Prof. Dr. Nicole Schweikardt

 

Übung

Donnerstags 11:15-13:00 im Schrödinger Zentrum (Rudower Chaussee 26), Raum 1'307

Übungsleiter: Dr. Christoph Berkholz

Melden Sie sich bitte mittels GOYA für die Übungsgruppe an.

Übungsblätter

Ab der ersten Vorlesungswoche wird wöchentlich ein Übungsblatt ausgegeben. Auf jedem Übungsblatt können bis zu 100 Punkte erreicht werden.

Das aktuelle Übungsblatt wird jeweils donnerstags am Ende der Vorlesung in gedruckter Form ausgeteilt und außerdem im Laufe des Donnerstag Nachmittag hier online bereit gestellt.

• Blatt 1 (ausgeteilt am 21.04.; zu bearbeiten bis 28.04., 11:15)
• Blatt 2 (ausgeteilt am 28.04.; zu bearbeiten bis 12.05., 11:15)
• Blatt 3 (ausgeteilt am 19.05.; zu bearbeiten bis 02.06., 11:15)
• Blatt 4 (ausgeteilt am 26.05.; zu bearbeiten bis 09.06., 9:30)
• Blatt 5 (ausgeteilt am 02.06.; zu bearbeiten bis 09.06., 9:30)
• Blatt 6 (ausgeteilt am 15.06.; zu bearbeiten bis 23.06., 11:15)
• Blatt 7 (ausgeteilt am 23.06.; zu bearbeiten bis 30.06., 11:15)
• Blatt 8 (ausgeteilt am 30.06.; zu bearbeiten bis 20.07., 11:15)
• Blatt 9 (ausgeteilt am 07.07.; zu bearbeiten bis 21.07., 09:30)
• Blatt 10 (ausgeteilt am 14.07.; zu bearbeiten bis 21.07., 11:15 — aktualisierte Version von Aufgabe 3 hochgeladen am 19.07.2016)

Prüfung

Zur Vorbereitung auf eine Prüfung (Modulabschlussprüfung) ist es unbedingt notwendig, das gesamte in den Vorlesungs- und Übungsstunden 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:

1. Bestehen der beiden jeweils 90-minütigen schriftlichen Tests, in die in der Mitte und am Ende der Vorlesungszeit geschrieben werden und
2. Erreichen von mindestens 50 Prozent aller Übungspunkte. Um dies zu gewährleisten empfehlen wir dringend, regelmäßig und aktiv an den Übungsstunden teilzunehmen.

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 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.

Literatur

[EFT]	H.-D. Ebbinghaus, J. Flum, W. Thomas, Einführung in die mathematische Logik, Spektrum Akademischer Verlag, 4. Auflage, 1996
[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.
[S-LI]	N. Schweikardt, Skript zur Vorlesung "Logik in der Informatik" im Wintersemester 2015/16, 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.

Links

[LICS]	IEEE Symposium on Logic in Computer Science (LICS)
[EACSL]	European Association for Computer Science Logic (EACSL)