Seminar Logik, Komplexität, Spiele: Logik und (Un)Abhängigkeit

WS 2008/09

Organisation

Die Veranstaltung wird als Blockseminar am Ende der Vorlesungszeit durchgeführt. Die Vorbesprechung findet am Donnerstag, den 9. Oktober um 11 Uhr in Raum 4116 (Seminarraum des Lehrstuhls) statt.

Zeitplan

30.10. Gliederung
24.11. Ausarbeitung
18.12. Endgültige Fassung
12.01. Folien
Ende Januar Vorträge

Programm

Mittwoch, 28. Januar
8:30 9:15 Malte Kampschulte Die Komplexität Henkin-definierbarer Relationen
9:15 10:00 Thomas Jache Independence-Friendly-Logik
10:30 11:15 Ruth Cremer Independence-Friendly-Modallogiken
11:15 12:00 Michel Surmacs Independence-Friendly-Fixpunktlogik
12:15 13:00 Björn Marschollek Einfürung in Dependence Logic
Freitag, 30. Januar
9:00 9:45 Christian Schilli Modellexistenz-Spiel für Dependence Logic
9:45 10:30 Daniel Kneer Ehrenfeucht-Fraïssé-Spiel für Dependence Logic
11:00 11:45 Patrick Kabasci Definierbarkeit in Dependence Logic
11:45 12:30 Daniel Medina Cardona Team Logic

Inhalt

Oft lässt sich beobachten, dass Ereignisse oder gemessene Größen voneinander abhängen, in vielen Fällen ist allerdings der genaue Zusammenhang unbekannt. In diesem Seminar werden wir uns hauptsächlich mit der Frage beschäftigen, wie solche Abhängigkeiten in einer Logik formalisiert werden können und welche Schlussfolgerungen daraus gezogen werden können.

Betrachten wir eine Formel ∀x∃y φ(x,y), so ist diese erfüllt, wenn zu jedem Element x ein (von diesem funktional abhängiges) Element y existiert, so dass φ gilt. Es gibt allerdings in der Prädikatenlogik keine Möglichkeit auszudrücken, dass es ein weiteres solches Paar u und v gibt, so dass v nur von u abhängt, denn eine Formel wie ∀x∃y∀u∃v φ(x,y,u,v) beschreibt nur, dass ein passendes Element v abhängig von u und x gewählt werden kann, jedoch nicht, das die Wahl von v unabhängig von x sein soll.

Um solche Aussagen formalisieren zu können, wurden verschiedene Konzepte eingeführt wie z.B. die Independence-Friendly Logic oder die sogenannten Henkin-Quantoren, mit deren Hilfe sich genau solche partiellen und nicht-linearen Abhängigkeiten beschreiben lassen.

In der von Väänänen eingeführten Dependence Logic werden neue atomare Formeln eingeführt, mit denen explizit ausgedrückt werden kann, dass eine Variable von anderen abhängig ist, ohne eine Aussage darüber zu machen, welcher Natur diese Abhängigkeit ist. Im Gegensatz zur Independence-Friendly Logic, die gleich ausdrucksstark ist, ermöglicht die Verwendung atomarer Formeln jedoch die explizite Formulierung und das direkte Schlussfolgern über Abhängigkeitsbeziehungen.

In dem Seminar sollen die verschiedenen Ansätze und deren Ausdrucksmöglichkeiten vorgestellt und mit anderen Logiken verglichen werden. Weiterhin lässt sich das Konzept voneinander abhängiger Variablen in Formeln übertragen auf Spiele mit unvollständiger Information, in denen die Spieler z.B. nicht genau wissen, welchen Zug ihr Gegner zuvor gemacht hat, oder die Position im Spielgraphen nicht genau kennen, d.h. sie können ihren nächsten Zug nur abhängig von einer Teilmenge der gesamten Informationen n-Quantoren machen.

Als Literaturquellen für die Vortragsthemen dienen Kapitel aus dem Buch Dependence Logic von J. Väänänen (Cambridge University Press, 2007) sowie weitere Konferenz- und Zeitschriftenartikel klassischer und aktueller Forschungsergebnisse.

Themen

Thema Vortragende(r) Betreuer(in) Literatur
Henkin-Quantoren Peng Sun B. Puchala [Hen61, Wal70, End70]
Die Komplexität Henkin-definierbarer Relationen Malte Kampschulte R. Rabinovich [BG86]
Independence-Friendly-Logik Thomas Jache M. Ummels [HS97, Hin02]
Independence-Friendly-Modallogiken Ruth Cremer B. Puchala [ST06, Bra00]
Independence-Friendly-Fixpunktlogik Michel Surmacs D. Fischer [Bra04]
Die Komplexität von Independence-Friendly-Fixpunktlogik Sevket Gökay R. Rabinovich [BK07]
Einfürung in Dependence Logic Björn Marschollek M. Ummels [Vaa07, Kapitel 3-5]
Modellexistenz-Spiel für Dependence Logic Christian Schilli T. Ganzow [Vaa07, Kapitel 6.5]
Ehrenfeucht-Fraïssé-Spiel für Dependence Logic Daniel Kneer T. Ganzow [Vaa07, Kapitel 6.6]
Definierbarkeit in Dependence Logic Patrick Kabasci D. Fischer [KV07]
Team Logic Daniel Medina Cardona Ł. Kaiser [Vaa07, Kapitel 8]
Finite Information Logic Chantal Höller Ł. Kaiser [PV05]

Literatur

Zuordnung

  • Informatik (B.Sc.)/Seminar Informatik
  • Mathematik (B.Sc.)/Seminar: Logik, Komplexität, Spiele
  • Informatik (D)/Hauptstudium/Theoretische Informatik
  • Mathematik (D)/Hauptstudium/Reine Mathematik
  • Informatik (S II)
  • Mathematik (S II)/Hauptstudium/Modul Angewandte Mathematik

Voraussetzungen

  • Vorlesung Mathematische Logik
  • für B.Sc. Informatik: bestandenes Modul "Einführung in das wissenschaftliche Arbeiten (Proseminar)"

Rückfragen

Erich Grädel, Diana Fischer, Tobias Ganzow, Łukasz Kaiser, Bernd Puchala, Roman Rabinovich, Michael Ummels