= 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