= Datum der Prüfung: 
24.7.2015
= Benötigte Lernzeit als Empfehlung: 
mehrere Wochen.
= Relevante Materialien 
Vorlesungsskript, Übungsaufgaben
= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
Angenehme Atmosphäre, am Tisch nebeneinander auf einem Blatt, Beisitzer im Verlauf der Prüfung nichts gesagt. Es wird einem die Möglichkeit gegeben, sich an Sachen zu erinnern oder diese kurz herzuleiten und leicht geholfen falls das nicht funktioniert.
= Prüfungsverlauf
Was für Methoden hatten wir, zu zeigen, dass etwas in einer Logik nicht definierbar ist?
    (Alle aufgezählt, auf Reduktion kurz eingegangen, kompositionslemmata vergessen)
Wie waren die 0-1 Gesetze formal definiert, schreiben sie mal alles auf, was man dafür braucht.
Warum gelten die 0-1 Gesetze für FO auf UG? 
    (Angefangen, dass Erweiterungsaxiome in fast allen endlichen Strukturen gelten und gewinnstrategien für duplicator beschreiben)
Wie genau sieht die Gewinnstrategie für Duplicator aus in zwei Strukturen, die beide die EA erfüllen?
    (Konnte ich beantworten)
Wie sieht es aus, wenn zusätzlich zu E die Signatur noch ein Konstantensymbol enthält?
    (Konnte ich beantworten, hat keine 0-1 Gesetze mit Beispiel einer Strukturklasse, bei der mu_n(phi|(UG,c))= 1/2

Was sagt der Satz von Gaifmann?
    (Konnte ich beantworten)
Wann ist eine Formel lokal?
    (Konnte ich nach einigem rumgerudere unsicher herleiten, war richtig)
Was ist ein basislokaler Satz?
    (Habe vergessen, dass die enthaltene lokale Formel nur eine freie variable hat)
Was sagt der Satz von Seese?
    (Konnte ich beantworten)
Wie sieht der Algorithmus aus?
    (Konnte ich nicht mehr genau beantworten, sowohl Schritt 1 (Knoten die die Formel erfüllen markieren) als auch Schritt 2 (In der markierten Knotenmenge genug finden, die den richtigen Abstand hatten) konnte ich nicht angeben. Ich bin nicht auf die Idee gekommen, den auf Hanf basierenden alternativen Algorithmus stattdessen anzugeben)

Was sagt der Satz von Immermann und Vardi?
    (Gibt zwei Sätze, konnte beide angeben)
Bei dieser Frage bin ich mir nicht mehr sicher, irgendwas in der Richtung "Warum beschreibt LFP nicht P auf FIN"?
    (Gegenbeispiel ist mir 20 sekunden nach Prüfungsende eingefallen, wäre EVEN gewesen)
Definieren sie Graphenzusammenhang in LFP
    (Konnte ich)

Note (Optional): 2.0
= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Ich gehe davon aus, dass bei einem etwas besseren Verlauf der Prüfung auch schwerere Fragen noch gekommen wären.

Es wurde genau das Thema (r-lokalität, Gaifmann) getroffen, in dem ich unsicher war. Schweikardt meinte, sie hat dies erkannt und berücksichtigt, grundsätzlich hätte ich das Thema verstanden, deshalb 2.0. Benotung war absolut fair.

= Datum der Prüfung
24.07.15

= Benötigte Lernzeit als Empfehlung
Habe 4 Tage gelernt, etwas mehr wäre besser gewesen.

= Verwendete Materialien (Bücher, Skripte etc...)
Skript und Aufzeichnungen aus VL + Übung

= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
Gemütliche Atmosphäre, Beisitzer hält sich komplett raus

= Prüfungsfragen
- Nennen Sie Beispiele für Zusammenhänge zwischen Logiken und Komplexitätsklassen (also Beispiele für "L definiert C auf S")
- Was sind 0-1-Gesetze und für welche Logiken und welche Strukturklassen gelten sie?
- Wie lassen sich L_{\infty\omega}^\omega und PFP auf FIN unterscheiden?
- Wie funktioniert der Beweis für "PFP beschreibt PSPACE auf FIN_<"? (Grobe Skizze, detaillierte Fragen zu einzelnen Teilen des Beweises, z.B. die Abbruchbedingung der Fixpunktiteration)
- Was sagt der Satz von Hanf aus? (Aufschreiben, Voraussetzungen erklären, Beweis per Induktion über m skizzieren)
- Wie lässt sich der Satz von Seese beweisen? (über Satz von Gaifman oder Satz von Hanf, eine der Möglichkeiten detailliert erklären)

= Note (Optional)
1,3

= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Gute Prüfung mit fairen Fragen. Fehler werden nicht direkt korrigiert, sondern Frau Schweikardt versucht, einen durch geschicktes Nachfragen dazu zu bringen, sich selbst zu korrigieren. Wenn man das schafft, gibt es auch keinen großen Abzug.
Insgesamt wurde nur ein Teil des Stoffes abgefragt, dafür an manchen Stellen sehr detailliert. Die Details musste man aber nicht unbedingt auswendig wissen, wenn man sie sich schnell genug herleiten konnte.

= Datum der Prüfung
Februar 2016

= Benötigte Lernzeit als Empfehlung
6-10 Tage, da es viele Beweise gibt, die zum Teil nur handschriftlich vorliegen. Deshalb: Script/Folien lesen und dann Beweise dazu nachvollziehen.

= Verwendete Materialien (Bücher, Skripte etc...)
Folien, Skript und Übungsblätter reichen aus. Es ist aber wichtig, Literatur wie CM oder AHV verstehen zu können. Dort sind einige Beweise drin, auf die in den Folien nur verwiesen wird.

= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
Die Prof. unterhält sich sehr locker mit einem. Wenn einem etwas nicht bekannt ist, hilft sie. Der Beisitzer hat nur mitgeschrieben und leider nicht auf die Uhrzeit geachtet.

= Prüfungsfragen
1. Die Prof. schrieb eine Anfrage in Umgangssprache auf und diese musste dann in einer geeigneten Anfragesprache umgesetzt werden. Dazu stand das Schema der Kino-DB an der Tafel
2. Gründe für die Wahl der Anfragesprache wurden gefragt. Ich nahm Datalog, weil die Anfrage nicht Monoton war. Deshalb durfte ich gleich noch Beweisen, dass konj. Anfragen immer Monoton sind und dass ihre Anfrage nicht monoton ist
3. Ich sollte eine nicht erfüllbare Anfrage in SPCJR aufschreiben und erklären was dies bedeutet
4. Definitionen (echt detailiert) zum Satz von Trakhtenbrot wurden gefragt
5. Natürlich wurde nach dem Homomorphismus-Satz gefragt und ich sollte die Beweisidee dazu erläutern
6. Die Prof. schrieb eine Tableau-Anfrage auf und wollte wissen, wie dese minimiert wird und welche Rolle FD-Regeln dabei spielen
4. Am Ende darf man noch etwas zu einem Thema erzählen, das einem sehr gefallen hat und nicht abgefragt wurde. Ich erzählte etwas zu Algorithmen mit Anfrageverzögerung, da man dazu etwas malen kann und dabei schön Zeit vertrödelt.

= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Sehr angemessene Benotung. Es ist nicht nötig jeden Beweis zu kennen, aber für eine Note 1,.. ist es sehr wichtig, die Beweise verstanden zu haben.

= Datum der Prüfung
  1.8.2016
= Benötigte Lernzeit als Empfehlung
  2 Wochen sollten passen
= Verwendete Materialien (Bücher, Skripte etc...)
  Skripte und Folien
= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
  relativ entspannte Atmosphäre, Beisitzer sehr ruhig 


= Bemerkung
Frau Schweikardt fragt gerne die ein oder andere Frage über den Stoff der VL hinaus.
Diese sind als weiterführende Fragen gekennzeichnet.
(wenn solche Fragen in der Prüfung kommen, ist man auf einen sehr guten Weg)

= Prüfungsfragen
  praktischer Teil (Freytag)
  * Warum können/werden Daten heute nicht mehr auf einzelnen Maschinen ausgewertet
    Antwort: mehrere "einfache" Rechner sind profitabler als ein Teurer
  * Frage nach neuem Paradigma, das in der VL vorgestellt wurde (Antwort: MapReduce)
  * Formale Definition von Map und Reduce
  * Welche Operatoren wurden von Flink zusätzlich hinzugefügt, Definition von Cross-Operator
  * Welches Verfahren haben wir Kennengelernt zur Behandlung von Dokumentenähnlichkeit
    * 3 schrittiges Verfahren (k-shingles, min-hashing, local-sensitve hashing)
    * "Ein- und Ausgabe" der drei Schritte beschreiben
  theoretischer Teil (Schweikardt)
  * Was ist eine Hash-Familie, welche haben wir in VL kennengelernt
  * Beispiel für eine Hash-Familie
  * (weiterführende Frage) Welche Familie sollten wir beim min-Hashing benutzen
  * Count-Min-Sketch: Aufbau, Anwendungsszenario, Garantien
    * (weiterführende Frage) Was ändert sich, wenn wir nicht mehr das strikten Drehkreuzmodell annehmen
  * Wann ist der Median-Trick einsetzbar und was erreichen durch dessen Einsatz 
= Note (Optional): 1.0
= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
  * Teilweise war mir nicht klar worauf die Fragen abzielen sollten
  * sehr viel in der Breite gefragt, wenig/gar nicht in der Tiefe

= Datum der Prüfung
  1.8.2016
= Benötigte Lernzeit als Empfehlung
  2 Wochen sollten passen
= Verwendete Materialien (Bücher, Skripte etc...)
  Skripte und Folien
= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
  relativ entspannte Atmosphäre, Beisitzer sehr ruhig 


= Bemerkung
Frau Schweikardt fragt gerne die ein oder andere Frage über den Stoff der VL hinaus.
Diese sind als weiterführende Fragen gekennzeichnet.
(wenn solche Fragen in der Prüfung kommen, ist man auf einen sehr guten Weg)

= Prüfungsfragen
  praktischer Teil (Freytag)
  * Warum können/werden Daten heute nicht mehr auf einzelnen Maschinen ausgewertet
    Antwort: mehrere "einfache" Rechner sind profitabler als ein Teurer
  * Frage nach neuem Paradigma, das in der VL vorgestellt wurde (Antwort: MapReduce)
  * Formale Definition von Map und Reduce
  * Welche Operatoren wurden von Flink zusätzlich hinzugefügt, Definition von Cross-Operator
  * Welches Verfahren haben wir Kennengelernt zur Behandlung von Dokumentenähnlichkeit
    * 3 schrittiges Verfahren (k-shingles, min-hashing, local-sensitve hashing)
    * "Ein- und Ausgabe" der drei Schritte beschreiben
  theoretischer Teil (Schweikardt)
  * Was ist eine Hash-Familie, welche haben wir in VL kennengelernt
  * Beispiel für eine Hash-Familie
  * (weiterführende Frage) Welche Familie sollten wir beim min-Hashing benutzen
  * Count-Min-Sketch: Aufbau, Anwendungsszenario, Garantien
    * (weiterführende Frage) Was ändert sich, wenn wir nicht mehr das strikten Drehkreuzmodell annehmen
  * Wann ist der Median-Trick einsetzbar und was erreichen durch dessen Einsatz 
= Note (Optional): 1.0
= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
  * Teilweise war mir nicht klar worauf die Fragen abzielen sollten
  * sehr viel in der Breite gefragt, wenig/gar nicht in der Tiefe

= Datum der Prüfung
01.03.2016

= Benötigte Lernzeit als Empfehlung
2 Wochen

= Verwendete Materialien (Bücher, Skripte etc...)
Skript, Übungsaufgaben

= Prüfungsfragen

Ich hoffe man kanns auch ohne die ganzen griechischen Buchstaben und Sonderzeichen verstehen^^

Existenzquantor: E
Allquantor: A

* * * * * * * * * * * * * * * * *
Aufgabe 1 (31 Punkte)
* * * * * * * * * * * * * * * * *

a) Aussagenlogik-Rätsel

Das Staffelfinale einer Sendung steht an. Die Autoren überlegen, welche von den Charakteren (Gärtner, Herzogin, Freiherr) sterben soll. Folgende Bedingungen sollen erfüllt sein:

Bed 1) Wenn die der Gärtner stirbt, dann muss auch die Herzogin sterben, weil diese sonst den jährlichen schönster Garten Contest nicht gewinnen könnte.
Bed 2) Es dürfen nicht sowohl der Freiherr als auch die Herzogin sterben, weil es ein Machtvakuum hinterlassen würde.
Bed 3) Wenn die Herzogin stirbt, aber der Freiherr überlebt, dann darf der Gärtner nicht sterben, weil der Freiherr sonst den Blumengarten abreißt.

i) Stellen sie 3 Aussagenlogische Formeln auf, die die 3 Bedingungen repräsentiert. Die Aussagensymole G, H, F bedeuten hierbei: Der Gärtner stirbt, die Herzogin stirbt bzw. der Freiherr stirbt.

ii) Einer der Autoren sagt, dass der Gärtner auf keinen Falls stirbt. Hat er damit recht? Begründen Sie ihre Antwort.

* * * * * * * * * * * * * * * * *

b) Normalformen

i) Kreuzen Sie für folgende zwei Formeln an, ob sie in NNF, DNF und/oder in KNF sind. (...)

ii) Wandeln Sie die Folgende Klauselmenge in eine äquivalente Formel um.
{ {A, ¬B, C}, {¬A, B, D}, {¬C, D}, {B, C, ¬D}}

* * * * * * * * * * * * * * * * *

c) Wahr oder Falsch?

i) Seien A und B zwei aussagenlogische Formeln. Wenn für jede Interpretation I gilt, dass wenn I[A] = 1, dass dann auch I[B] = 1, dann sind die beiden Formeln A und B äquivalent.

ii) Seien TAU1 und TAU2 Mengen von Junktoren, die disjunkt sind (TAU1 ∩ TAU2 = { }). Wenn TAU1 adäquat ist, so ist auch die Vereinigung von TAU1 und TAU2 (TAU1 ∪ TAU2) adäquat.

iii) Sei PHI eine Menge von Formeln und A eine Formel. Es gilt: Aus PHI folgt A, genau dann wenn es eine endliche Teilmenge GAMMA von PHI gibt, sodass gilt, aus GAMMA folgt A (Endlichkeitssatz, Variante 2).

* * * * * * * * * * * * * * * * *

d) Resolution

Geben Sie eine Resolutionswiderlegung oder eine erfüllende Belegung an für
M1 = { {X, ~Y, Z}, {X, Y, Z}, {~X, Z},  {~Z, W}, {~X, ~Z}, {~Z, ~W} }
M2 = { {A, ~B}, {B, ~A},  {C, ~A, D}, {~C, ~A, D }, {C, ~D} }

* * * * * * * * * * * * * * * * *

e) Streichungsalgorithmus

Wenden Sie den Streichungsalgorithmus an auf die Formelmenge:
{ {~W, ~Z, ~Y}, {~Y, ~Z, W}, {Y, ~Z}, {Z}, {Z, ~X} }*

Geben sie in jedem Lauf des Algorithmus die Tatsachenklausel an, die Sie wählen. Geben Sie an, ob der Algorithmus mit der Ausgabe "erfüllbar" oder "unerfüllbar" endet.

* * * * * * * * * * * * * * * * *

f) 3-DNF

Definition: Eine Formel ist in 3-DNF, wenn Sie in DNF ist und jede konjunktive Klausel aus 3 oder weniger Literalen besteht.

Beweisen Sie: Nicht jede Formel hat eine äquivalente Formel in 3-DNF. (Gegeben: Definition von 3-DNF).

* * * * * * * * * * * * * * * * *
Aufgabe 2 (30 Punkte)
* * * * * * * * * * * * * * * * *

a) Wortstrukturen

Sei E = {A, B, ..., Y, Z} ein Alphabet.
Für jedes Symbol a in E sei P_a ein einstelliges Relationssymbol.
Sei SIGMA_E = {<=} + {P_a | a in E} eine Signatur.

i) Welches Wort w wird durch die folgende Struktur beschrieben:
Das Universum A_w = {1, 2, 3, 4, 5}, <= ist die natürliche lineare Ordnung.
P_G = {3}, P_I = {4}, P_K = {5}, P_L = {1}, P_O = {2}.
(Mit P_G ist natürlich P_G^A_w gemeint, usw.)


ii) SPRACHE = {L w1 G w2 K | w1 und w2 aus dem Alphabet E}. Geben Sie einen Satz an, der die Sprache beschreibt.

iii) Welche Sprache wird durch den folgenden Satz beschrieben: A x P_a(x) -> A y (x < y)

* * * * * * * * * * * * * * * * *

b) Formeln Logik erster Stufe

TAU = {E, c} eine Signatur.
PHI = E x ( NOT E(x, y) AND ( E(c,x) OR A y ( E(y, x) AND E(x, x) ) ) )

i) Geben Sie für PHI eine Interpretation I an, welche PHI erfüllt, und eine Interpretation J, die PHI nicht erfüllt.

ii) Wandeln Sie die Formel in eine äquivalente Formel in NNF um.

iii) Wandeln Sie die Formel in eine äquivalente Formel in PNF (Pränexer Normalform) um.

* * * * * * * * * * * * * * * * *

c) Skolemform

TAU = {E, c} eine Signatur.
PHI = A x1 E x2 A x3 E x4 ( E(x1, x2) OR E(x2, c) OR E(x3, x4) )

Geben Sie eine Signatur TAU' und eine Formel PHI' an, sodass PHI' in Skolemnormalform ist und erfüllbarkeitsäquivalent zu phi.

* * * * * * * * * * * * * * * * *

d) Wahr oder Falsch

i) (A x phi) AND (E x psi) |= A x ( phi AND psi)
ii) A x ( phi AND psi) |= (A x phi) AND (E x psi)
iii) A x (phi OR psi) === (E x phi) OR (E x psi)

* * * * * * * * * * * * * * * * *

e) Existenzielle Normalform

Definition: Zwei Formeln PHI und PSI sind allgemeingültigkeitsäquivalent, wenn gilt: PHI allgemeingültig <-> PSI allgemeingültig.

Definition: Eine Formel ist in existenzieller Normalform, wenn sie folgende Form hat: E x1 ... E xn PHI (wobei PHI quantorenfrei ist).

Zeigen Sie: Zu jeder Formel gibt es eine allgemeingültigkeitsäquivalente Formel in existenzieller Normalform.

* * * * * * * * * * * * * * * * *
Aufgabe 3 (20 Punkte)
* * * * * * * * * * * * * * * * *

a) EF-Spiele

Gegeben zwei Graphen:
A . O . . . B . O . . .
. . | . . . . . | . . .
. . O . . . . . O . . .
. ./ \. . . . ./ \. . .
. O . O . . . O . O - o
. .\ /. . . . .\ /. . .
. . O . . . . . O . . .
. . | . . . . . | . . .
. . O . . . . . O . . .

i) Geben Sie eine Gewinnstrategie für Duplikator im 2 Runde EF-Spiel auf A und B an.

ii) PHI = E x E y A z (x = z OR y = z OR E(x, z) OR E(y, z) ). Es gilt: PHI erfüllt A und PHI erfüllt B nicht. Geben Sie eine Gewinnstrategie für Spoiler an. Insbesondere: Wie viele Runden werden gespielt? Welche Knoten wählt Spoiler in Runde 1 und 2?

* * * * * * * * * * * * * * * * *

b) Wagenräder

Definition eines Wagenrades:
Ein Graph der "aussieht wie ein Wagenrad", also außen ist ein Kreis aus Knoten (Jeder Knoten ist immer mit seinem linken und rechten Nachbarn verbunden), und innen ist ein Knoten, der mit allen anderen verbunden ist.

Beispiel:
. O - O .
 / \ / \
O - O - o
 \ / \ /
. O - O .

Ein Wagenrad der Größe n hat genau n "Außenknoten".

i)Geben Sie für jedes n einen Satz an der genau von Wagenrädern der Größe n erfüllt wird.

ii) Zeigen Sie: Die Menge aller Graphen die kein Wagenrad enthalten ist erststufig axiomatisierbar. Das heißt: Geben Sie eine Formelmenge an, die genau von den Strukturen erfüllt wird, die kein Wagenrad enthalten.

iii) Geben Sie präzise den Endlichkeitssatz der Logik erster Stufe an.

iv) Zeigen Sie: Die Klasse aller Graphen die ein Wagenrad enthalten ist nicht erststufig axiomatisierbar.

* * * * * * * * * * * * * * * * *
Aufgabe 4 (19 Punkte)
* * * * * * * * * * * * * * * * *

a) Kalküle

Wann ist eine Sequenzenregel in einem Kalkül korrekt (als Hilfe war u.a. gegeben, wann eine Sequenz korrekt ist und wie eine Regel aussieht).

* * * * * * * * * * * * * * * * *

b) Wahr oder Falsch

i) Allgemeingültigkeit ist entscheidbar.
ii) Allgemeingültigkeit ist semi-entscheidbar.
iii) Erfüllbarkeit ist semi-entscheidbar.

* * * * * * * * * * * * * * * * *

c) Entscheidbarkeit

Ist das Äquivalenzproblem entscheidbar?


* * * * * * * * * * * * * * * * *

d) Logikprogrammierung

Gegeben ist ein Logikprogramm, dass eine Murmelbahn repräsentiert. Rutsche(a, b) bedeutet hierbei, dass eine Murmel von Station a nach Station b direkt über eine Rutsche gelangen kann.

- - - - - - - - - - - -
1: Rutsche(a, b).
2: Rutsche(a, c).
3: Rutsche(b, e).
4: Rutsche(b, f).
5: Rutsche(c, e).
6: Rutsche(d, c).
 7: 
8: Bahn(X, X, null).
9: Bahn(X, Z, s(W)):- Rutsche(X, Y), Bahn(Y, Z, W).
- - - - - - - - - - - -

i) Geben Sie einen Beweisbaum für Bahn(a, e, s(s(null)) an.

ii) Ergänzen Sie das Programm um einen Ausdruck via(X, Y, Z), der Ausdrückt, dass man von X nach Y über die Zwischenstation Z gelangen kann. Achtung! Insbesondere darf auch gelten, dass X=Y oder Y=Z.

iii) Welche der folgendne Ausdrücke können aus dem Logik-Programm abgeleitet werden?
1) a
2) Bahn(a, e, s(s(null))
3) Bahn(a, b, null)
4) Bahn(b, f)

= Fazit
Ganz schöne Hammer-Prüfung^^ Ich würde jedem empfehlen immer die Übungsaufgaben zu machen, zu den Übungen zu gehen und auch Fragen zu stellen.
Wenn man "die einfachen Sachen draufhat", ist es auf jeden Fall gut möglich zu bestehen, aber manche Aufgaben haben mich echt ins Schwitzen gebracht.

= Datum der Prüfung: 24.02.2017
= Benötigte Lernzeit als Empfehlung: 1 Woche, falls man die Aufgaben bearbeitet hat 
= Verwendete Materialien (Bücher, Skripte etc...): Skript durchlesen und Anwendungsaufgaben bearbeiten
= "Atmosphäre" der Prüfung / Verhalten der Beisitzer: Etwas kühl, Jacke mitnehmen, sonst alles gut
= Prüfungsfragen:

Aufgabe 1

a)
Polizist Dietmar ist mit einem heiklen Mordfall beschäftigt. Nach sorgfältigen Ermittlungen kann er den Kreis der Verdächtigen auf die drei Personen Lydia, Norbert und Pit einschränken, es ist jedoch unklar, ob der Mord von nur einer oder von mehreren der verdächtigen Personen begangen wurde.
Folgende Aussagen:
1. Wenn Pit kein Mörder ist, dann ist auch Lydia keine Mörderin.
2. Pit würde einen Mord auf jeden Fall alleine durchziehen.
3. Lydia ist eine Mörderin oder Norbert hat den Mord ohne Hilfe begangen.

Aufgabe:

Formalisieren Sie jede der drei Zeugenaussagen durch je eine aussagenlogische Formel, indem Sie die atomaren Aussagen L (Lydia ist eine Mörderin), N (Norbert ist ein Mörder) und P (Pit ist ein Mörder) benutzen.

Unteraufgabe von a)
Dietmar stellt fest, dass er aus den drei Aussagen nicht bestimmen kann, wer den Mord begangen hat.
Ist Dietmars Aussage korrekt? Ja/Nein, Lösungsweg

-----------------------------------------------
b)
Ankreuzaufgabe, ob gegebene Formeln in NNF, DNF, KNF sind.
Formel1: (A_0 /\ ~A_1 /\ A_2)
Formel2: (~(A_1 \/ A_2) /\ (~A_1 \/ ~A_2))

-----------------------------------------------
c)
Welche der Aussagen sind wahr/falsch?

1. Es gibt eine aussagenlogische Formel, die zu keiner Formel in disjunktiver Normalform äquivalent ist.
2. Es gibt eine Formel phi Element AL mit phi erfüllt 1.
3. Für alle Formeln phi Element AL gilt: Wenn phi erfüllt 0, dann ist phi unerfüllbar.

-----------------------------------------------
d)
Aussagenlogische Formel angeben, die durch die Folgende Klauselmenge repräsentiert wird:
Gamma := { {A_0,~A_1}, {~A_1,~A_2}, {~A_1,A_2,~A_3} }

-----------------------------------------------
e)
Für folgende Klauselmenge entweder eine erfüllende Interpretation angeben oder Resolutionswiderlegung:
Gamma1 := { {X,Y}, {Y,Z}, {~X,~Y,Z}, {~X}, {~Y,~Z} }
Gamma2 := { {A,~C}, {A,C}, {~A,~B}, {~A,B,C}, {~A,~B,~C} }

-----------------------------------------------
f)
Streichungsalgorithmus auf folgende Klauselmenge anwenden:
Gamma := { {~A,~B,C,~D,~E}, {A,~E}, {~A,B}, {D}, {E,~D} }
Geben Sie für jeden Schleifendurchlauf des Algorithmus die in diesem Durchlauf gewählte Tatsachenklausel und die am Ende des Durchlaufs aktuelle Klauselmenge an.
Welche Ausgabe liefert der Streichungsalgorithmus zum Schluss?

-----------------------------------------------
g)
Für zwei aussagenlogische Interpretationen I_1, I_2 schreiben wir I_1 ≼ I_2, wenn für alle X Element AS gilt:
I_1(X) ≤ I_2(X).
Eine formel heißt monoton, wenn für alle Interpretationen I_1,I_2 mit I_1 ≼ I_2 gilt:
Wenn I_1 erfüllt phi, dann I_2 erfüllt phi.

(i) Geben Sie je ein Beispiel für eine monotone und für eine nicht monotone Formel an.
(ii) Beweisen Sie, dass alle Formeln phi Element AL({0,1,\/}) monoton sind.

-----------------------------------------------

Aufgabe 2

a)

-----------------------------------------------
b)
Sei sigma := {E} die Signatur, die aus dem 2-stelligen Relationssymbol E besteht. Betrachten Sie die FO[sigma]-Formel:
phi(y) := füralle x_1 ( füralle x_2 E(x_2,y) -> füralle x_2 (E(x_2,x_1) /\ ~E(y,x_1)) )
Konstruieren Sie eine zu phi äquivalente Formel phi_p in Pränex-Normalform.

-----------------------------------------------
c)

-----------------------------------------------

Aufgabe 3

a) EF Spiel. Graphen:

A:................B:..............
O--------O...................
.\............/......................
...\......../......O--------O
......\../...........\............/.
.......O..............\......../...
........|..................\../.....
........|...................O......
.......O................../..\......
....../..\............../........\...
.../........\........./............\.
./............\......O--------O
O--------O....................

(i)
Kleinste Zahl m Element N angeben, für die Spoiler eine Gewinnstrategie im m-Runden EF-Spiel auf A und B hat.
Und beschreiben Sie die Gewinnstrategie.

(ii)
Geben Sie für Ihre Zahl m aus Aufgabenstellung (i) einen FO[sigma]-Satz phi der Quantorentiefe m an, so dass gilt:
A erfüllt phi und B erfüllt nicht phi.

(iii)
Begründen Sie, warum für Ihren Satz phi aus (ii) tatsächlich A erfüllt phi und B erfüllt nicht phi gilt.

-----------------------------------------------
b)

(iv) Geben Sie eine präzise Formulierung des Endlichkeitssatzes der Logik erster Stufe an. (1 von 5 Punkten, da noch eine Teilaufgabe).

-----------------------------------------------
c)

-----------------------------------------------

Aufgabe 4)

a)
Sequenzenkalkül K_S
Regeln gegeben: (V), (E), (FU),...

Aufgabe: Ist die Sequenz (füralle P(x) /\ füralle Q(x)) |- füralle x (P(x) /\ Q(x)) ableitbar.
Ankreuzen, ob ja oder nein (1 Punkt), Beweis 4 Punkte.

-----------------------------------------------
b)
(i)
Ankreuzen, ob richtig/falsch:

1. Das Erfüllbarkeitsproblem für FO[sigma] ist entscheidbar.
2. Das Folgerungsproblem für FO[sigma] ist semi-entscheidbar.
3. Das Erfüllbarkeitsproblem für FO[sigma] ist semi-entscheidbar.

(ii)
Erfüllbarkeitsproblem für gleichheitsfreie FO[sigma]-Sätze in Skolemform.
Eingabe: Ein gleichheitsfreier FO-Satz phi in Skolemform.
Ausgabe: Ist phi erfüllbar?

Ist das Erfüllbarkeitsproblem für gleichheitsfreie FO[sigma]-Sätze in Skolemform entscheidbar? Begründen SIe.

c) Prolog

Gegeben:

Atomate Formeln:
t_0 = 0 und t_1 = 1

Rekursive Formeln:
t_{~phi} = not(t_phi)
t_{phi\/psi} = or(t_phi, t_psi)
t_{phi/\psi} = and(t_phi, t_psi)

Logikprogramm PI:
01. true(1).
02. false(0).
03. true(not(F)) :- false(F).
04. false(not(F)) :- true(F).
05. true(or(F, G)) :- true(F).
06. true(or(F, G)) :- true(G).
07. false(or(F, G)) :- false(F), false(G).
08. true(and(F, G)) :- true(F), true(G).
09. false(and(F, G)) :- false(F).
10. false(and(F,G)) :- false(G).

(i) Beweisbaum für Term: true(or(and(1, 0), not(0)))
(ii) Bedeutung B(PI) von PI angeben.

(iii) Schreiben Sie ein Logik-Programm PI', so dass B(PI') = {dual(t_phi, t_(dualphi)) : phi Element AL'}
Erinnerung: [Hier wurde beschrieben, was die duale Formel ist, und wie sie gebildet wird.]

= Note (Optional): Im Durchschnitt
= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...):
Bei 40% zum Bestehen, war die Prüfung fair. Etwa 50% können locker gemacht werden, beim Rest muss man etwas mehr nachdenken.

= Datum der Prüfung 20. Juli 2020 (30 Minuten mündlich via Zoom)

= Benötigte Lernzeit als Empfehlung Eine Woche, wenn man die Hausaufgaben grundlegend verstanden hat

= Verwendete Materialien (Bücher, Skripte etc...) Ihr Skript

= "Atmosphäre" der Prüfung / Verhalten der Beisitzer: Die Prüfung hat sich um 10 Minuten verschoben, was mir im Zoom Warteraum schon mitgeteilt wurde. Zu Beginn musste ich CampusCard in die Kamera halten und die vorgelesene Selbstständigkeitserklärung bestätigen. Der Beisitzer hatte sein Mikrofon die ganze Zeit stumm und war unauffällig. Sie hat auf ihrem Whiteboard mitgeschrieben, so dass Gesagtes konkret formuliert werden konnte.
 
= Prüfungsfragen
1. Erläutern, was Φ |= φ formal bedeutet und was die Symbole sind. 
2. Erläutern, was eine Resolvente ist und wie diese gebildet wird.
  - An einem gegebenen Beispiel zwei Resolventen bilden {A, ~B, ~C} und {~A, C, D} 
  - Was sagt das Resolutionslemma aus?
  - Die einfache Richtung des Resulutionslemma (<==) prinzipiell beweisen.
3. Kurz die Regeln des Ehrenfeucht-Fraiisse-Spiel erläutern und an folgendem Graph in 3 Runden als Spoiler eine Gewinnstrategie ermitteln:

A: o-->o-->o-->o-->o
B: o-->o-->o-->o-->o-->o

4. Kann man einen FO[singma] Satz definieren, der die Menge aller Graphen mit der Kardinalität einer Primzahl definiert?
  - Begründen (warum nicht?)

= Note (Optional): gut

= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Ich war letzten endlich überrascht, wie wenig inhaltlich abgefragt wurde. Das war dann jedoch sehr spezifisch und man musste die Beweise aus dem Skript in die einfache Richtung können.
Die halbe Stunde ging schnell vorbei und die Note habe ich dann nach etwa fünf Minuten erfahren. 

= Datum der Prüfung
14.04.2021

= Benötigte Lernzeit als Empfehlung
Zwei Wochen

= Verwendete Materialien (Bücher, Skripte etc...)
Ich habe mit dem Skript, den Übungsblättern und den Tafelschrieben gelernt. In der AHV Literatur habe ich
nur das Kapitel gelesen, dass uns vorgegeben wurde. Die Angabe, dass man andere angegebene Kapitel
"bei Interesse lesen kann, aber nicht muss", ist keine Falle und auch für eine sehr gute Note nicht notwendig.
(Aber vielleicht hilfreich? Ich habe sie nicht gelesen)

= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
Sehr angenehme Unterhaltung. Bei kleinen Fehlern (in einer Anfrage x und y vertauscht etc.) und wenn man
mal nicht weiter weiß, hilft die Professorin auch.
 
= Prüfungsfragen

1. Eine Anfrage an die Film Datenbank aus der Vorlesung in einer selbstgewählten Anfragesprache formulieren.
Das Schema der Datenbank war gegeben. Die Anfrage war (ungefähr, den genauen Wortlaut weiß ich nicht mehr):
Gib alle Filme aus, in denen jemand Regie geführt hat, der auch als Schauspieler in einem Film mitgespielt hat, in dem
auch Doris Day Schauspielerin war.
Habe ich als regelbasierte, konjunktive Anfrage angegeben

2. Modifikation der Anfrage: Gib alle Filme aus, in denen jemand Regie geführt hat, der NICHT auch als Schauspieler
in einem Film mitgespielt hat, in dem auch Doris Day Schauspielerin war.
Das habe ich im Relationenkalkül angegeben.

3. Zu meiner Anfrage im Relationenkalkül: Ist die Anfrage in CALC_sr?
Ich habe gesagt, dass ich die Anfrage dazu in Safe-Range Normalform umformen müsste und dann die Menge
der range restricted Variablen bestimmen müsste. Ich sollte dann erklären, wann eine Anfrage in Safe-Range
Normalform ist (war meine Anfrage schon). Dann habe ich rr berechnet. (Die Anfrage war in CALC_sr).
Die Professorin hat die Anfrage noch einmal modifiziert (ein „und“ durch „oder“ ersetzt) und ich sollte wieder
bestimmen, ob sie in CALC_sr ist (war sie nicht mehr)

4. Ist die Anfrage (die aus 2.) in CALC_di?
Ja, ist sie, da alle Anfragen aus CALC_sr in CALC_di sind. Generell ist Bereichsunabhängigkeit aber unentscheidbar.

5. Was ist die Beweisidee für die Unentscheidbarkeit des Problems Bereichsunabhängigkeit für CALC?
Hier habe ich den Satz von Trakhtenbrot definiert und dann die Anfrage Q und die Beweisidee. Bei den genauen
Details zu Q wurde (zum Glück) nicht nachgefragt.
(Diesen Beweis haben wir handschriftlich an der Tafel gemacht, es sind nicht nur die Beweise aus dem Skript relevant!)

6. Wie ist das Query Containment Problem bzgl. einer Menge F von FDs definiert?

7. Ist das Problem für Anfragen in einer konjunktiven Anfragesprache entscheidbar? Wenn ja, wie?
Umwandlung in Tableau Anfrage, dann wendet man Chase Prozedur an und bekommt ein normales Query
Containment Problem. Das kann man dann mit dem Homomorphismussatz lösen

8. Ist das Problem für Anfragen einer relational vollständigen Anfragesprache entscheidbar?
Hier war ich zuerst etwas ratlos. Habe dann erstmal gesagt, dass das allgemeine Query Containment Problem für
relational vollständige Anfragen unentscheidbar ist, aber ich nicht wirklich weiter weiß. Die Professorin meinte dann,
dass wir das zwar in der Vorlesung nicht explizit hatten, ich mir das aber zusammenreimen kann. Ist mir dann auch
schnell gelungen (einfache Reduktion)

= Note (Optional)
sehr gut

= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Sehr nette Prüfung. Mir wurde für die kleinen Fehler, die ich beim Beweis zur Bereichsunabhängigkeit gemacht habe,
nichts abgezogen. Über die gute Bewertung habe ich mich natürlich gefreut!
Die letzte Frage hat mich zuerst leicht gestresst, war dann aber doch recht einfach und ich bin schnell auf die Lösung gekommen.

= Datum der Prüfung 14.04.2021
= Benötigte Lernzeit als Empfehlung: 2 Wochen
= Verwendete Materialien (Bücher, Skripte etc...)
Skript, Übungsaufgaben, ihre Handschriftlichen Notizen
= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
Sehr angenehme und freundliche Atmosphäre, von der Atmosphäre, die beste mündliche Prüfung, die ich bis jetzt hatte, Beisitzerin hat nur zugehört und nichts gesagt
= Ablauf der Prüfung
Die mündliche Prüfung fand auf Zoom statt, Frau Schweikardt hat ihr Bildschirm geteilt und aufgeschrieben was man ihr diktiert hat, man hatte genug Zeit um nachzudenken, sich Notizen zu machen und es ihr dann zu notieren, sie war sehr geduldig und man hatte gar nicht das Gefühl, dass man jetzt hetzen muss und schnell eine Antwort finden muss, wenn man mal etwas nicht wusste, hat sie Tipps gegeben 
= Prüfungsfragen
Man sollte die Anfrage: Gib x und y aus, wobei x der Schauspieler ist, deren Film zur Zeit im Kino y läuft in einer Sprache seiner Wahl formulieren
Ich habe regelbasierte konjunktive Anfrage gewählt und sollte das dann in das konjunktive Kalkül umwandeln
Dann sollte ich den Algorithmus beschreiben, mit dem man, das umwandeln kann
Ich sollte die Anfrage so ändern, dass Gib x und y aus, wobei x der Schauspieler ist, deren Film zur Zeit im Kino y läuft und der Schauspieler nicht "George Clooney" ist
Wieder sagen, was für eine Sprache man verändert hat, ich habe CALC gewählt. 
Sollte dann die Definition von CALC_di sagen (das konnte ich nicht perfekt)
Was ist adom(Q) von der Anfrage, die wir gerade aufgeschrieben haben
Ich sollte dann die Definition von CALC_sr sagen und sagen ob die Anfrage von vorher bereichsunabhängig ist, also rr(phi) bestimmen.
Dann sollte ich sagen, ob es einen Algorithmus gibt, der bestimmt, ob CALC_di bereichsunabhängig ist. 
Ich sollte den Satz von Trakhtenbrot formulieren und damit dann beweisen, warum es keinen solchen Algorithmus gibt. (Das konnte ich auch nicht vollständig)
Wir sind dann zu FD Mengen gewechselt. Wie ist Q_1 enthalten in_F Q_2 definiert? 

= Note (Optional)
2,0
= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
sehr nette Benotung, insgesamt sehr gute Prüfung

= Datum der Prüfung
27.07.2022

= Benötigte Lernzeit als Empfehlung
eine Woche (mit fleißig Lernen kann man es auch in 2-3 Tagen schaffen)

= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
freundlich, aber auch nicht gelassen

= Prüfungsfragen

Definition Isomorphie (schriftlich)

FO-Satz, so dass alle Graphen, die diesen erfüllen, isomorph zu einem gegebenen Graphen A sind
(A bestand aus 3 Knoten, wobei eine Kante vom Knoten “1” auf sich selbst und eine zu Knoten “2” war, ansonsten keine Kanten)

Sie hat danach den Graphen verändert, indem sie die Kanten von “1” auf sich selbst entfernt, eine von “2” auf sich selbst, und eine Kante von “2” zu “1” hinzugefügt hat. Ich sollte daraufhin den FO-Satz anpassen.

Sie hat erneut den Graphen verändert, indem sie die Kante von “1” auf sich selbst wieder hinzugefügt hat.
(ACHTUNG: Ich habe den FO-Satz in Teilsätze aufgeteilt, wodurch ich bei der Symmetrie dieses Graphs ein Problem bekommen habe)

Satz von Ehrenfeucht (mündlich)

3-Runden EF-Spiel (k=0) auf zwei Strukturen A, B
- erste Runde einfach um zu zeigen, dass man die Regeln verstanden hat
- danach sollte ich überlegen, ob es eine Gewinnstrategie für Spoiler gibt
(A bestand aus einem Pfad mit 8 Knoten und einem Kreis aus 6 Knoten mit jeweils gerichteten Kanten in eine Richtung)
(B bestand aus einem Pfad mit 8 Knoten (später hat sie daraus 9 gemacht))

Endlichkeitssatz der Aussagenlogik (schriftlich)
Beweise in beide Richtungen bei (a) und (b)
(HINWEIS: Sie hat nach dem Beweis gefragt und hier ist es ratsam mit den Richtungen zu beginnen, die man kann. Ich habe den Fehler gemacht nach den leichten Richtungen nicht mit der Hinrichtung von (b) zu beginnen, sondern mit der Rückrichtung von (a), bei welcher ich nach der Definition von Ψ gefragt wurde, die ich nur halb konnte. Sie ist danach direkt weiter gegangen und ich musste die letzte Richtung nicht mehr zeigen)

Endlichkeitssatz für FO (schriftlich)
Beweise in beide Richtungen (hierfür sollte ich den Vollständigkeitssatz aufschreiben, aber die Beweise musste ich nur mündlich nennen)

= Note (Optional)
1,0

= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Es war eine gute Prüfung und ich habe immer noch 1,0 bekommen, obwohl mein einer Satz bei dem angepassten Graphen (wie oben erwähnt) Probleme hatte und ich die Rückrichtung von (a) beim Endlichkeitssatz der Aussagenlogik nicht konnte.

= Datum der Prüfung
2023-07-20

= Benötigte Lernzeit als Empfehlung
14 Tage nach Ende der VL-Zeit.
Wegen Prüfungstermin in der letzten VL-Woche konnte ich jedoch nur 3 ganze und 4 halbe Tage zur Wiederholung nutzen.

= Verwendete Materialien (Bücher, Skripte etc...)
Alles an Material von der Website (Prof. Schweikardts handschriftliche Notizen, provisorisches Skript, eigene Mit-/Abschriften, eigene Lösungen und Mitschriften aus den Übungsstunden, vereinzelt die Bücher [EF] und [L])
Die VL hatte ich nur sporadisch besucht, aber zeitnah zuhause vor- bzw. nachgearbeitet. Ich war bei allen Übungsstunden und habe alle Blätter gewissenhaft bearbeitet.

= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
Prüferin, Beisitzer und Prüfling sitzen an einem Doppeltisch. Alle haben Papier und Stift vor sich. Der Beisitzer macht sich die meiste Zeit Notizen (daran merke ich, ob ich gerade etwas Sinnvolles gesagt habe). Die Prüferin schreibt einerseits Dinge auf, die ich nur mündlich gesagt habe, um Präzisierungen zu verlangen, und andererseits notiert sie neue Fragen. Die Prüferin sitzt lässig zurückgelehnt und stellt ihre Fragen sehr ruhig. Gerade wenn ich schneller werde, und mich beginne zu verhaspeln, spricht sie besonders langsam, um die Situation zu entspannen. Häufig kann ich an ihrer Mimik erkennen, ob ich auf dem richtigen Weg bin. Bei den Transferfragen bleibt sie aber erst neutral, um nichts zu verraten. Wenn ich etwas arg durcheinanderbringe, dann guckt sogar der Beisitzer fragend, aber ich habe versucht, nicht auf ihn zu achten.
Insb. zum Ende hin wurde es ein lockereres Gespräch, was auch daran zu bemerken war, dass der Beisitzer den Stift weggelegt und sich ebenfalls zurückgelehnt hat. Da hat er sich sogar eingemischt, als ich damit argumentieren wollte, dass ESO 2-Färbbarkeit ausdrücken kann. Die einzig andere Interaktion mit dem Beisitzer war die Frage der Prüferin nach der Zeit.

Prof. Schweikardt hatte beim letzten VL-Termin angekündigt, dass es ihr lieber ist, wenn wir direkt sagen, wenn wir zu einem Thema nichts sagen können, damit wir in der Prüfung damit keine Zeit verschwenden und stattdessen mehr zu etwas anderem erzählen können. (Halte ich für erwähnenswert, da das nicht alle Prüfer*innen so sehen.)

= Prüfungsfragen
Was sagt der Satz von Fagin?
- Es gibt ja mehrere Sätze von Fagin. Die aufgezählt, bei Ajtai und Fagin die infinitäre Logik mit EMSO verwechselt.

Wie haben wir den Satz von Fagin „ESO beschreibt NP auf FIN“ bewiesen?
- Erst grobe Idee erzählt, dann weiter ins Detail anhand von Nachfragen. Darauf eingegangen, dass wir Polyzeit als Einschränkung brauchen, damit wir die Zeitpunkte als k-Tupel über dem Universum darstellen können. Vergleich zu Immerman und Vardi gezogen.

(Transfer) Können wir diese Konstruktion aus dem Satz von Fagin mit einer einzigen Relationsvariablen machen?
- Vmtl ja, denn bei Immerman und Vardi ging das ja auch, aber mit der Ordnung müssen wir vmtl aufpassen. Wir können die Subrelationen anhand einer Markerkomponente auftrennen wie in Immerman und Vardi.

Was sagt der Satz von Immerman und Vardi denn aus?
- Aussage, Beweisidee und Unterschiede zu Fagin. Beschrieben, wie die Induktionsstufen der Lauf der DTM simulieren.

Was sagt der Satz von Knaster und Tarski?
- Einordnung ins Thema Fixpunktlogik, Aussage, Beginn des Beweises, bei der Richtung des ersten Beweisschrittes verzettelt, von ihr abgebrochen.

In welche Logik können wir die Fixpunktlogiken einbetten?
- IFP \leq LFP \leq PFP < L_{infty, omega}^{omega}. Die erste Ungleichung müsste andersrum sein, von ihr auf den richtigen Pfad gebracht, konnte aber nicht zu allen Hinweisen etwas Sinnvolles sagen. Nach einem Beispiel für etwas, das wir in infinitärer Logik ausdrücken können, aber in PFP nicht, wurde nicht gefragt.

(Transfer) Was wissen wir über das Verhältnis von LFP und SO auf FIN_<?
- Verbindung von Immerman-Vardi und Fagin.

(Transfer) Gleiches auf FIN ohne Ordnung?
- Nach Bedenkzeit und Hinweisen der Prüferin: Uns genügt, dass LFP in PTIME ausgewertet werden kann (unabhängig von Ordnung). Wir müssen nicht wissen, welche Komplexitätsklasse LFP auf FIN (ohne Ordnung) beschreibt.

0-1-Gesetze. Was ist das? Erstmal für ungerichtete Graphen.
- Erst grobe Erklärung, dann Aussage, dass FO das 0-1-Gesetz bzgl UG hat. Beweisvorgehen: erst Erweiterungsaxiome, Idee am Bildchen, Formel aufschreiben, wie wir daraus das 0-1-Gesetz beweisen, weiterer Zwischenschritt: wenn zwei Strukturen alle EA_k für k \leq m erfüllen, dann sind sie m-äquivalent.

Für welche Logiken bzgl. welcher Klassen von Strukturen haben wir 0-1-Gesetze gezeigt?
- Alles aufgezählt, inkls den Fixpunktlogiken und warum (Einbettung von eben gerade).

(Transfer) Hat ESO ein 0-1-Gesetz?
- Bedenkzeit, erst falsches Beispiel (ESO kann bipartite Graphen definieren, aber die sind eh sparse), dann ein sinnvolles, weil wir wegen Fagin wissen, dass wir mit ESO alle NP-Eigenschaften ausdrücken können: ESO kann gerade Universen definieren, daher kein 0-1-Gesetz (genau das Beispiel hatten wir am letzten VL-Termin besprochen).

= Note (Optional)
1,0

= Fazit (Gute/schlechte Prüfung, angemessene Benotung etc...)
War wie bei den bisherigen beiden Prüfungen bei Schweikardt. Dass es diesmal 1,0 und nicht 1,3 geworden ist, war eher Glückssache (Fragen und Tagesform).

22.07.2024


Benötigte Lernzeit als Empfehlung:
etwa fünf Tage, wenn Inhalte in Vorlesung gut mitbekommen


Verwendete Materialien:
Skript


„Atmosphäre“ der Prüfung / Verhalten der Beisitzer:
nett, wirkten nicht gestresst





Prüfungsfragen


Resolvente definieren

Resolutionslemma beweisen

Vollständigkeitssatz der Resolutionswiderlegungen/-ableitungen beweisen


Endlichkeitssatz formulieren 

für FO[σ]-Formeln beweisen

Vollständigkeitssatz Sequenzenkalkül beweisen

widerspruchsfrei definieren

Φ   |—    φ   definieren
         ks
       

gegeben:  k^ := k U { ———— :  Γ endl. TM von FO[σ]-Formeln, φ in FO[σ]-Formeln, Γ |= φ }
Frage:  wenn  Φ   |—   φ , gilt dann auch  Φ  |—   φ ? und warum?
                                k^                                       k

        Lösungsidee: ja, denn Γ |— φ ist in der Menge abs(ks)




Note: 
sehr gut

Fazit:
faire Benotung, passte zum Gefühl vor und während Prüfung

= Datum der Prüfung 
19.02.26
= Benötigte Lernzeit als Empfehlung
Habe das Semester über Mitschriften gemacht. Damit haben 5 Tage Lernen früh bis spät gereicht. Aber mehr zu empfehlen, wenn man noch ein Leben haben will :(

= Verwendete Materialien (Bücher, Skripte etc...)
Eigene Mitschriften, (Skript)
= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
Angenehm, Sie konnte Druck wegnehmen
= Prüfungsfragen


- HAMILTON ist in welchen Logiken definierbar und in welchen nicht

- eingegangen auf warum für MSO nicht und Satz von Büchi (Elgot Trakhtenbrot) (REG --> EMSO)

- warum ist HAMILTON für ESO definierbar (Formel bzw. Satz von Fagin)

- Wie kann HAMILTON in infinitärer Logik beschrieben werden (gebe Formel an)

- Wieso geht es nicht in infinitärer Logik mit beschränkter Variablenanzahl (Beweis dafür)

- Warum geht es für die Fixpunktlogiken nicht? (Zeigen, dass pfp <= L_infty, omega ^omega)



- Definition 0-1-Gesetze (und was dazu gehört)

- welche Logiken haben auf welchen Klassen 0-1-Gesetze

- warum hat ESO keins auf UG? (EVEN --> warum erfüllt es das? --> Formel/Fagin/Büchi mit EMSO)

- Wenn du für ungerichtete Graphen noch eine Konstante hinzufügst, hat FO dann immer noch ein 0-1-Gesetz?

- --> Bin ich nicht drauf gekommen und wurde geleitet --> was ist mit einstelligen Relationen statt E? (drin oder nicht --> \mu=0.5) Was ist mit gerichteten Graphen? (Pfad zu sich selber --> \mu 0.5)
- trotzdem nicht auf Lösung der ursprünglichen Frage gekommen


= Note (Optional)
1.0
= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Sehr angenehme Prüfung, hat mir persönlich Spaß gemacht.

= Datum der Prüfung
Wintersemester 25/26, erster Prüfungszeitraum

= Benötigte Lernzeit als Empfehlung
Ich habe ca 12-15 volle Tage verteilt auf 3 Wochen gelernt. Ich denke die Zeit reicht auch für eine bessere Prüfung aus, wenn sie effizienter genutzt wird.
Während des Semesters habe ich fast alle Übungsblätter komplett bearbeitet, war bei fast allen Übungen und etwas mehr als der Hälfte der Vorlesungen anwesend.

= Verwendete Materialien (Bücher, Skript etc...)
Die Skriptfragmente, handschriftlichen Notizen und Übungsblätter von der Website, sowie meine Lösungen der Übungsblätter, bzw. der Mitschriften aus der Übung.
Zusätzlich habe ich während des Lernens eine Zusammenfassung zu den Zusammenhängen der Logiken & Komplexitätsklassen (NP=ESO auf FIN, ESO-Horn=P auf FIN_<, Fixpunktlogiken < k-Frgament der infinitären Logiken auf FIN, etc.) sowie der Definierbarkeit von Graphzusammenhang, reachability (in gerichteten und ungerichteten Graphen) und Hammilton-Kreis, sowie der Gültigkeit der 0-1-Gesetzte inkl. Beweis(ideen) auf allen behandelten Logiken geschrieben

= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
Die Prüferin und der Beisitzer haben ihr bestes getan, für eine ruhige & entspannte Atmosphäre zu sorgen. 
Es wurde klar auf Basis der ersten Frage anhand eines roten Fadens entlang die weiteren Fragen gestellt. Auch basierend auf den Antworten auf vorherige Fragen, bzw. meiner Fähigkeit diese überhaupt zu beantworten.

= Prüfungsfragen
# Graphzusammenhang
    - Frage: In welchen der von uns behandelten Logiken können wir Graphzusammenhang definieren.
    - Antwort: Ich bin die Logiken in der selben Reihenfolge, wie ich sie auf meinem Lernzettel hatte, durchgegangen, habe gesagt, ob es geht, oder nicht und bei den, wo es nicht ging das ganz kurz begründet (wirklich mit max. einem Satz). Bei MSO bin ich kurz durcheinander gekommen, bin dann aber doch noch selbstständig drauf gekommen, dass es doch geht.
    
## auf MSO
    - Frage: (Ich denke, weil ich da vorher durcheinander gekommen bin) Wie sieht denn eine solche Formel in MSO aus?
    - Antwort: Erst mündlich, dann auf nachfrage explizit hingeschrieben, dass man über den Allquantor und alle mengen die die Transitive Hülle enthalten reachability definieren kann. Da bin ich bei den freien & gebundenen Variablen etwas durcheinander gekommen und habe die (um ehrlich zu sein grundlegenden Fehler) erst mit 1-2 Nachfragen gesehen und korrigiert.
    
## Auf ESO
    - Frage: Warum brauchen wir für die geg. MSO-Formel den Allquantor? und (nach kurzer Begründung, dass wir in MSO nicht verhindern können, dass in die Transitive Hülle zusätzliche Zusammenhangkomponenten geschmuggelt werden):
    Wieso geht das denn in ESO?
    - Antwort: Zunächst angefangen eine explizite Formel aufzuschreiben, mit der Nachfrage, ob es denn nicht auch einfacher geht dann schnell gesagt, dass Zusammengang klar in NP ist und ESO=NP auf FIN gilt.
    
## EMSO
    - Frage: Warum geht das nich in EMSO?
    - Antwort: grob erklärt, wie wir das mit dem Ajtaji-Fagin-Spiel gezeigt haben unter Erwähnung davon, dass der Kreis "groß genug" sein muss, damit Spoiler gezwungen ist, zwei identische 3^m-Umgebungen zu erzeugen
    - Nachfrage(n): kurzes Hin und her, wie "groß genug" denn aussieht, was ich verstanden habe als, dass die explizite Größe hergeleitet/begründet werden soll. Gemeint war aber, wie der Kreis geschnitten wird/warum das funktioniert.
    - Antwort: Erklärt, wie wir den Kreis schneiden (festlegen auf eine Richtung, Schneiden nach den Elementen mit selbem 3^m Umgebungstyp, dann zusammenkleben) und das wir damit keine 3^m Umgebungen verändern und mit Hanf dann eine Duplicator-Strategie für das EF-Spiel haben.
    
# Satz von Hanf
## Statement
    - Frage: Was sagt der Satz von Hanf? 
    - Antwort: den Satz gestatet.
## Aussage
    - Frage: Wie haben wir den Gezeigt?
    - Antwort: Beweisidee Angegeben:
        - Induktionsinvariante gestatet (mit den r_i, da zunächst nur 3^#verbleibende Runden gesagt, von ihr korrigiert worden mit der Aussage, dass das +1 wichtig ist)
        - Fallunterscheidung zwischen komplett enthalten in der r_i-Umgebung und komplett disjunkt von der r_{i+1}-Umgebung begründet und die Invariante in beiden Fällen mit der Induktionshypothese begründet
    - Rückfrage: Was ist mit komplett disjunkt gemeint?
    - Antwort: Das die Knotenmengen sich nicht überschneiden
    - Hinweis durch die Prüferin, dass es für den Beweis auch noch essentiell war, dass die Nachbarschaften nicht benachbart sind und wir daher die +1 in den r_i brauchten.

# infinitäre Logiken
## Graphzusammenhang (cont.)
    - Frage: Wieso ist Graphzusammenhang auf einem endlichen Variablen-Fragment der infinitären Logik definierbar?
    - Antwort: Weil es in den Fixpunktlogiken geht und die < L_\infty_\omega^\omega sind.
    - Nachfrage: Wie geht das denn auf LFP?
    - Auch wieder gesagt, dass wir reachability durch das iterative Bauen der transitiven Hülle definieren können und versucht das aufzuschreiben
        - das ist leider komplett gescheitert, ich habe das ganze eher als SO-Formel aufgeschrieben und nicht beachtet, dass nach der Semantik ja automatisch zu R hinzugefügt wird. Daher denke ich auch der folgende Block an Fragen:
        
## LFP Grundlagen
    - Frage: wie sieht denn LFP aus?
    - Antwort: Rekusionsvorschriften wie in FO + den lft-Operator, dann den definiert und die Idee hinter der Semantik angegeben
    (ohne dabei explizit auf die Definition der Funktion F_{\mathcal A \varphi} einzugehen).
    - Darauf dann "den" Fehler in der LFP formel gesehen und die Formel korrekt aufgestellt, angegeben, welche Variablen frei sind und welche dann in der Formel [lfp_{R, b} \varphi](b) frei sind.

## Knaster-Tarski
    - Frage: Was sagt der Satz von Knaster-Tarski aus?
    - Antwort: Nach etwas Bedenken und Unsicherheit bzgl. der Teilmenge in dem zweiten schnitt korrekt hin geschrieben.

## LFP=SO?
    - Frage: Wie stehen LFP und SO zueinander (beide Richtungen: <=/>=, angefangen mit LFP<= SO?)
    - Antwort: LFP<=SO stimmt, dazu aber leider eine falsche Begründung gegeben (Idee war LFP <= PSpace <= NP = SO, aber Pspace <= NP gilt nicht (da war etwas Unsicherheit, ob das nicht sogar ein offenes Problem ist)). Wurde glaube ich nicht allzu groß angekreidet, da der Fehler in einem Themenbereich außerhalb der Vorlesung lag.
    - Hinweis, dass es gilt und man über Knaster-Tarski einen entsprechenden SO-Satz bauen könnte, um den Fixpunkt zu beschreiben (jetzt wo ich das schreibe, glaube ich, dass wir das sogar in der Vorlesung hatten. Ist mir in der Prüfung aber nicht aufgefallen.)
    - Rückfrage: Und was ist mit >=?   
    -Antwort: Intuitiv glaube ich nicht, dass das gilt. Nach kurzem Überlegen drauf gekommen, dass wir den Hammilton-Kreis nicht in L_\infty_\omega^\omega, also auch nicht in LFP, aber in SO definierbar ist.
    

= Note (Optional)
Ich fand sie auf Basis meiner Performance vollkommen angemessen, nicht zu gut und nicht zu schlecht. Negativ aufgefallen waren speziell die falsch hingeschrieben expliziten MSO/IFP - Formeln.

= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Ich kann (auch auf Basis der anderen Prüfungsprotokolle und Gespräche mit anderen Teilnehmer*innen) sagen, dass eine Übersicht (und diese auch komplett zu können) dazu, was wir wo und warum (nicht) definieren können sehr empfiehlt, speziell für Graphen. Darauf wird die Prüfung anscheinend immer aufgebaut, das ist also irgendwo eine Grundlage.
Auf Basis meiner Prüfung kann ich außerdem empfehlen, zu üben Formeln explizit hin zu schreiben (wenn du da sonst auch Probleme in einer Stress-Situation mit hättest).