Als Warnung vorneweg: Der Folgende Braindump ist nicht “klassisch”, denn er gibt nicht den Prüfungsverlauf wieder. Stattdessen sind die Fragen aufgelistet, die im jeweiligen Themenbereich beantwortet werden mussten. (Grund: Im Gespräch hat es sich ergeben, dass manchmal der Themenbereich gewechselt wurde.) Zusätzlich sind nicht nur Fragen aus meiner Prüfung enthalten, sondern auch die eines Kommilitonen. Als Zusatz habe ich außerdem die Fragen aufgeführt, auf die ich vorbereitet gewesen wäre. Das betrifft hauptsächlich Fragen aus anderen Braindumps sowie Themen aus der Vorlesung, die klausurrelevant gewirkt haben. Häufig lässt sich das nicht ganz scharf trenne, weswegen so viele Fragen im Prüfungsteil sind.

Grundsätzlich sollte man die Zusammenhänge verstehen und erklären können. Insbesondere Komplexität, Entscheidbarkeit und Ausdrucksstärke der behandelten Logiken sollten verstanden sein. Beweise wurden zwar keine abgefragt, aber man muss für die wichtigsten Themen erklären können, was die Ideen und Abläufe sind. Ab und zu wurden auch (spontane?) Transferfragen gestellt. Da musste ich nicht sofort eine Antwort wissen, sondern konnte mich (zum Teil mit Hilfestellungen) zur richtigen Lösung vorarbeiten.

• Welche Komplexität hat Aussagenlogik?

• Was ist die Syntax?
• Wie forme ich um zu NNF/CNF/CNF ohne exponentiellen Platz?
• Welche Komplexität hat CSAT/3SAT/kSAT/2SAT?
• Was ist ein BDD/OBDD?
• Was sind die Komplexitäten der einzelnen Darstellungsformen? Warum?
• Wie funktioniert Resolution/DPLL?
• Was ist ein Tableau?
• Wie konstruiert man ein Tableau?
• Wie wertet man ein Tableau aus?
• Welchen Zusammenhang gibt es zwischen Formel und Knoten im Tableau?

• Wie genau ist FOL unentscheidbar (re/co-re)? Warum?
• Was ändert sich im Endlichen? Warum?
• Welche Formel ist nur im unendliche gültig?
• Wie wurde die Unentscheidbarkeit gezeigt?
• Was ist PCP?
• Was ist partieller Iso/Struktur/Quantorenrang/m-Äquivalenz?
• Wie geht das EF-Spiel?
• Was ist Kompaktheit? Wo wurde sie verwendet? Was ändert es sich im Endlichen?
• Was ist FO-Definierbarkeit? Wo wurde FO-Definierbarkeit in der Vorlesung verwendet?
• Wie funktioniert logische Reduktion?

• Was ist die Syntax?
• Was ist die Semantik/Modell/Umgebung?
• Wie funktioniert Reduktion?

Wurde nicht abgefragt

• Was ist die Syntax?
• Was sind die Deduktionsprobleme?
• Was sind T-Box/A-Box/GCI/T-Modell?
• Wann ist eine T-Box klassisch/azyklisch?
• Was ist lokale/globale Konsequenz?

• Was ist das Äquivalent zu EFS in Modallogik?
• Was ist eine Simulation? Was eine Bisimulation? Was ist ein unterscheidendes Beispiel?
• Was ist die entscheidende Eigenschaft bzgl. Bisimulation?
• Was ist Bisimulationsinvarianz? Was ermöglicht sie uns? Wann gilt die Umkehrung?
• Was ist ein Beispiel für unterschiedliches Verhalten im Endlichen?
• Warum ist Modallogik entscheidbar?
• Welche Regeln hat das Tableau?
• Wie funktioniert die ¬□ Regel? Gibt es Einschränkungen?
• Woran erkennt man, ob eine Modalformel erfüllbar ist?
• Wie erzeugt man aus einem Tableau ein erfüllendes Modell?
• Welche Komplexität hat Modallogik?
• Wie wurde die obere/untere Schranke gezeigt?
• Was ist QBF/TGBF/Quantorenbaum?

• Was ist die Syntax?
• Wie schaut ein Kripke-Modell aus?
• Was ist die Standardübersetzung? Welche Regeln gibt es? Was sagt das aus?
• Wann ist ein Label propositional saturiert/eklatant inkonsistent?
• Was sind AND/OR-Knoten? Was muss im jeweiligen Knoten gemacht werden?
• Wann ist ein Knoten erfolgreich?

• Was ist das Deduktionsprobleme?
• Welche Komplexität hat das Deduktionsprobleme? Warum?
• Wie funktioniert der Algorithmus?
• Was ist simulationsstabil/Materialisator?
• Was ist ein Beispiel für eine in EL nicht ausdrückbare Modalformel?

• Was ist die Syntax?
• Warum in PTIME?
• Wie konstruiert man einen Materialisator?
• Was sind positive/monotone Formeln?