Organisation

Die Veranstaltung wird als Blockseminar am Ende der Vorlesungszeit durchgeführt. Der Termin für die Vorbesprechung wird den Teilnehmern noch bekannt gegeben.

Content

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

Classification

• 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

Prerequisites

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

Contact

Erich Grädel, Diana Fischer, Tobias Ganzow, Łukasz Kaiser, Michael Ummels