TU Wien:Einführung in wissensbasierte Systeme VU (Egly)/Prüfung 2020-06-17

Gedächtnisprotokoll

• Teil 1 - PL1:
  • Was ist das Replacement Lemma, was das Replacement Theorem? Beweisen Sie, dass das Replacement Theorem gilt mit Hilfe des Replacement Lemma (oder umgekehrt?) (6 Punkte)
  • TC1 ähnlich wie in der 1c Prüfung vom Jänner 2020: Wissensbasis $\Gamma$ mit zwei Formeln gegeben, zeigen, dass aus der Wissensbasis eine dritte Formel folgt (4 Punkte)
  • Zeigen, dass TC1 inkonsistent wird wenn man eine Regel für den Existenzquantor hinzufügt indem man anhand der Formel $\exists xP(x)\land \exists y\neg P(y)$ zeigt, dass TC1 dann auch für erfüllbare Formeln ein geschlossenes Tableaux erzeugt (5 Punkte; ähnlich 1c in der Prüfung vom 9.6.2016)
  • Zusammenhang erklären zwischen (i) Erfüllbarkeit und Gültigkeit, und (ii) Äquivalenz und Erfüllbarkeit (2 Punkte)

• Teil 2 - NMR
  • Default-Theorie gegeben - hat sie Extensions, Begründung (3 Punkte, War normale Default-Theorie, ähnlich zu 2b Prüfung vom Jänner 2020)
  • Beweisen oder widerlegen Sie, dass jede Default Theorie eine Extension hat. (4 Punkte)
  • T_Q,S_asm eine Default-Theorie berechnen, MC: Ist T deduktiv abgeschlossen, ist CWA_Q,S(T) konsistent? (4 Punkte?)
  • Alle Extensions einer Default-Theorie berechnen (16 Kandidaten, 5 Punkte)

• Teil 3 - ASP
  • Logikprogramm gegeben, Grounding berechnen; Gelfond-Lifschitz-Redukt für P und gegebenes E berechnen, ist E ein Answer Set warum/warum nicht? (5 Punkte)
  • 2 Multiple Choice-Fragen (2 Punkte)
  • Default-Theorie aus Logikprogramm übersetzen wie in Vorlesung vorgestellt (3 Punkte)
  • Answer Sets aus 2 Programmen berechnen (3 Punkte)
  • Was ist Abduktion, was ein abduktives Diagnoseproblem? (vgl 3b Prüfung 8.1.2019, 3 Punkte)

• Teil 4 - Probabilistic Reasoning
  • Welche Arten von Zufallsvariablen gibt es, Definitionen (3 Punkte; vgl Teilfrage 4b Prüfung 8.1.2019)
  • Bayes'sche Regel aus Produktregel herleiten (6 Punkte, wie zB 4b Prüfung vom Jänner 2020)
  • Multiple Choice zu 3 Wahrscheinlichkeitsformeln (3 Punkte)
  • Multiple Choice Unabhängigkeiten in Bayes'schem Netz herleiten (4 Punkte)

Anmerkungen: Diesmal kein Textbeispiel!

Beispiel 1

Beispiel 1a

Geben Sie das Equivalent Replacement Lemma und das Equivalent Replacement Theorem an. Zeigen Sie mit Hilfe von Interpretationsstrukturen der Prädikatenlogik erster Stufe und dem Equivalent Replacement Lemma, dass das Equivalent Replacement Theorem gültig ist.

Beispiel 1b

Gegeben sei die Wissensbasis

$$\Gamma :=\{\exists x\forall yR(x,y),\forall x\forall y\forall z(R(x,y)\wedge R(x,z)\rightarrow R(y,z))\}.$$

Verwenden Sie TC1 um zu zeigen, dass der Satz ${\textstyle \forall x\forall y(R(x,y))}$ eine logische Konsequenz von ${\textstyle \Gamma }$ ist.

Beispiel 1c

Verwenden Sie die Formel ${\textstyle \exists xP(x)\wedge \exists y\neg P(y)}$ um zu zeigen, dass TC1 inkorrekt wird, also dass nicht nur unerfüllbare Formeln ein geschlossenes Tableau haben, wenn die folgende Regel hinzugefügt wird.

$${\frac {\exists x\phi }{\phi \{x\leftarrow a\}}}$$

Dabei ist $a$ ein beliebiges Konstantensymbol.

Beispiel 1d

Welche Beziehungen bestehen zwischen

• Erfüllbarkeit und Gültigkeit;
• Äquivalenz und Erfüllbarkeit?

Beispiel 2

Beispiel 2a

Betrachten Sie die Default Theorie ${\textstyle T:=\langle W,\Delta \rangle }$. Dabei sind $W$ und $\Delta$ unter der Verwendung der Prädikatensymbole $P,Q,R,S,U,V$ wie folgt definiert.

$$W:=\{\forall xP(x)\rightarrow Q(x),\forall xQ(x)\rightarrow S(x),\forall x\forall yU(x)\wedge V(y)\rightarrow R(x,y)\}$$

$$\Delta :=\{{\frac {P(x):\exists xP(x)}{\exists xP(x)}},{\frac {\top :\bot }{\bot }},{\frac {R(x,y):\exists x\forall y\exists zP(x)\wedge Q(y)\rightarrow U(z)\vee V(z)}{\exists x\forall y\exists zP(x)\wedge Q(y)\rightarrow U(z)\vee V(z)}}\}$$

Hat $T$ eine Extension? Begründen Sie Ihre Antwort.

Ja, da normale Default Theorien immer mindestens eine Extension haben.

Beispiel 2b

Beweisen oder widerlegen Sie, dass jede Default Theorie eine Extension hat.

Angenommen $T=\langle W,\Delta \rangle$ mit $W=\{\}$ und ${\textstyle \Delta =\{{\frac {\top \;:\;not\;a}{a}}\}}$, dann hat $T$ keine Extension, womit bewiesen ist, dass nicht jede Default Theorie eine Extension hat.

Beispiel 2c

Gegeben ist folgende Wissensbasis $T$ über einer Sprache mit den einzigen Konstantensymbolen $a$ und $b$, dem Variablensymbol $x$ und dem einzigen Prädikatensymbolen $P$, $Q$ und $S$.

$$T=\{\forall x(P(x)\wedge Q(x)\rightarrow S(x)),\forall x(S(x)\wedge \neg Q(x)\rightarrow P(x)),Q(a),P(a),S(b)\}.$$

1. Geben Sie die generalisierte Closed World Assumption ${\textstyle \mathrm {CWA} ^{Q,S}(T)}$ von ${\textstyle T}$ an, indem Sie folgende Gleichung ergänzen:
   $$\mathrm {CWA} ^{Q,S}(T)=Cn(T\cup \{\quad \quad \quad \quad \quad \quad \})$$
2. Welche der folgenden Eigenschaften treffen zu?

Multiple Choice-Quiz:

Pluspunkt für eine richtige Antwort:
Punkt für eine falsche Antwort:
Ignoriere die Fragen-Koeffizienten:

1 $T\cup T_{asm}^{Q,S}$ ist deduktiv abgeschlossen.

	richtig
	falsch

2 $\mathrm {CWA} ^{Q,S}(T)$ ist konsistent.

	richtig
	falsch

Für 1.:

$$\mathrm {CWA} ^{Q,S}(T)=Cn(T\cup \{\neg Q(b)\})$$

Beispiel 2d

Gegeben ist die folgende Default Theorie.

$$T=\langle W,\Delta \rangle :=\langle \{\forall x(P(x)\rightarrow Q(x)),P(a),O(b)\},\{{\frac {\top :\neg Q(x)}{S(x)}},{\frac {\top :\neg S(x)}{P(x)}}\}\rangle$$

Berechnen Sie alle Extensions dieser Theorie.

$$E_{1}=Cn(\{P(a),O(b),Q(a),S(b)\})$$

$$E_{2}=Cn(\{P(a),O(b),Q(a),P(b),Q(b)\})$$

Beispiel 3

Beispiel 3a

Gegeben ist folgendes Answer-Set Programm:

$${\mathcal {P}}:=\left.{\begin{cases}P(a).,Q(a).,S(b).,\\Q(X)\leftarrow \neg P(X),S(X).,\\\neg P(X)\leftarrow S(X),not\;P(Y).\end{cases}}\right\}$$

1. Bestimmen Sie die Grundierung $grnd({\mathcal {P}})$ von ${\mathcal {P}}$.
2. Gegeben ${\textstyle E:=\{P(a),S(b),Q(a),\neg P(b)\}}$, bestimmen Sie das Gelfond-Lifschitz Redukt ${\textstyle {\mathcal {P}}^{E}}$ von ${\mathcal {P}}$. Ist $E$ ein Answer Set von ${\mathcal {P}}$? Begründen Sie Ihre Antwort!