Hier finden Sie (nach den Vorlesungen) Informationen zum Inhalt der
einzelnen Vorlesungsstunden sowie gelegentlich ergänzende Bemerkungen.
Di, 15.04.2014
Eröffnungsveranstaltung. Klärung von Organisatorischem.
"Kapitel 0: Einleitung":
Einführung ins Thema durch Beispiele von Formeln der Logik zweiter Stufe ("3-Färbbarkeit"), Transitive-Hüllen-Logik
("Erreichbarkeit") und Fixpunktlogik ("Erreichbarkeit").
Start mit "Kapitel 1: Grundlagen": grundlegende Notationen, Turingmaschinen, der Satz von Trakhtenbrot
Lehrbuch [L]: Kapitel 1, Kapitel 2.1 und Kapitel 9.1
Di, 22.04.2014
Abschluss von "Kapitel 1: Grundlagen": Beweis des Satzes von Trakhtenbrot
Start mit "Kapitel 2: Die Logik zweiter Stufe (SO)": Syntax und Semantik von SO, Beispiele für SO-Formeln, Definition von MSO, EMSO und ESO, Vorarbeiten zum Satz von Büchi
Weiter mit "Kapitel 2: Die Logik zweiter Stufe (SO)":
Beweis des Satzes von Büchi, Anwendung des Satzes von Büchi (logische Reduktion zum Nachweis, dass "Hamiltonkreis" nicht MSO-definierbar ist)
Weiter mit "Kapitel 2: Die Logik zweiter Stufe (SO)":
Logische Beschreibung von Komplexitätsklassen, die
Standardkodierung von Strukturen, der Satz von Fagin, Beweis der
"leichten" Richtung des Satzes von Fagin, Vorarbeiten zum Beweis
der "schweren" Richtung des Satzes von Fagin
Weiter mit "Kapitel 2: Die Logik zweiter Stufe (SO)":
Abschluss des Beweises des Satzes von Fagin;
Beweis des Satzes von Cook und Levin (NP-Vollständigkeit des
aussagenlogischen Erfüllbarkeitsproblems) unter Verwendung des
Satzes von Fagin
Weiter mit "Kapitel 2: Die Logik zweiter Stufe (SO)":
Horn-Formeln; der Satz von Grädel (logische Charakterisierung von
P auf der Klasse aller endlichen geordneten Strukturen durch
ESO-HORN-Sätze); Ehrenfeucht-Fraisse Spiele für Fragmente der
Logik zweiter Stufe; das Ajtai-Fagin Spiel für EMSO.
Abschluss von "Kapitel 2: Die Logik zweiter Stufe (SO)":
Satz von Hanf (hier ohne Beweis),
Anwendung des Ajtai-Fagin Spiel für EMSO: Beweis des Satzes von Fagin, der besagt, dass
Graphzusammenhang nicht EMSO-definierbar ist.
Start mit "Kapitel 3: 0-1-Gesetze":
Einführung des Begriffs der asymptotischen Wahrscheinlichkeit; Beispiele: Berechnung der asymptotischen
Wahrscheinlichkeit der Probleme EVEN ("Hat das Universum gerade Kardinalität?"),
PARITY ("Enthält eine Relation gerade viele Tupel?"),
ISOLATED-NODES ("Besitzt ein Graph isolierte Knoten?").
Weiter mit "Kapitel 3: 0-1-Gesetze":
Berechnung der asymptotischen Wahrscheinlichkeit von GRAPH-ZUSAMMENHANG;
Einführung des Begriffs "eine Logik L besitzt das 0-1-Gesetz bzgl. einer Klasse S von Strukturen";
Nachweis des Satzes von Glebskii et al. und Fagin, der besagt, dass FO das 0-1-Gesetz bzgl. der Klasse UG
aller ungerichteten Graph besitzt (dazu wurden betrachtet: Erweiterungsaxiome für ungerichtete Graphen),
und dass FO das 0-1-Gesetz bzgl. der Klasse aller σ-Strukturen (für jede endliche relationale Signatur σ)
besitzt (dazu wurden eingeführt: Erweiterungsaxiome für σ-Strukturen).
Weiter mit "Kapitel 3: 0-1-Gesetze":
Der Rado-Graph; Nachweis, dass jeder abzählbare Graph, der
sämtliche Erweiterungsaxiome erfüllt, isomorph zum Rado-Graphen
ist; Entscheidbarkeit der FO-Theorie des Rado-Graphen;
Berechenbarkeit der asymptotischen Wahrscheinlichkeit von
FO-Sätzen auf ungerichteten Graphen; infinitäre Logik und deren
k-Variablen Fragment
Abschluss von "Kapitel 3: 0-1-Gesetze":
Pebble-Spiele (Spielregeln, Beispiele), Zusammenhang zwischen
k-Pebble-Spielen und Definierbarkeit in infinitärer
k-Variablen-Logik; Nachweis des Satzes von Kolaitis und Vardi, der
besagt, dass die infinitäre Logik mit endlich vielen Variablen das
0-1-Gesetz bzgl. der Klasse UG und bzgl. der Klasse aller
Strukturen über einer endlichen relationalen Signatur besitzt;
Anwendung des 0-1-Gesetzes; Anwendung von Pebble-Spielen zum
Nachweis des Satzes von de Rougemont, der besagt, dass
HAMILTONKREIS nicht in infinitärer Logik mit endlich vielen
Variablen definiert werden kann.
Start mit "Kapitel 4: Fixpunktlogiken":
Grundbegriffe zum Thema "Fixpunkte", der Satz von Knaster und
Tarski,
Syntax und Semantik der kleinsten Fixpunktlogik (LFP), Beispiele
für LFP-Formeln
Weiter mit "Kapitel 4: Fixpunktlogiken":
Syntax und Semantik der inflationären Fixpunktlogik (IFP) und der
partiellen Fixpunktlogik (PFP); Beispiele für IFP- und für
PFP-Formeln; Einbettung von PFP in infinitäre Logik mit endlich
vielen Variablen; Transfer der Nicht-Ausdrückbarkeitsresultate für
infinitäre Logik mit endlich vielen Variablen zu
Nicht-Ausdrückbarkeitsresultaten für Fixpunktlogiken
Weiter mit "Kapitel 4: Fixpunktlogiken":
Beweis der Sätze von Immerman und Vardi ("LPF bzw IFP beschreiben
PTIME auf der Klasse aller endlichen geordneten Strukturen" und
"PFP beschreibt PSPACE auf der Klasse aller endlichen geordneten
Strukturen");
Verwendung der logischen Charakterisierung von PSPACE durch PFP
zum Nachweis, dass die kombinierte Komplexität des
Auswertungsproblems für FO PSPACE-vollständig ist (Beginn des Beweises)
Abschluss von "Kapitel 4: Fixpunktlogiken":
Verwendung der logischen Charakterisierung von PSPACE durch PFP
zum Nachweis, dass die kombinierte Komplexität des
Auswertungsproblems für FO PSPACE-vollständig ist (Abschluss des
Beweises);
Rückblick auf die wichtigsten Themenbereiche, die im Laufe des
Semesters in Vorlesung und Übung behandelt wurden; Ausblick
auf weiterführende Themen im Bereich "Logik und Komplexität"
bzw. "Endliche Modelltheorie".