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

Angabe

• Datei:TU Wien-Einführung in wissensbasierte Systeme VU (Egly) - Prüfung 2020-01-09.pdf

Beispiele

Beispiel 1: Logikbasierte Wissensrepräsentation

Beispiel 1a

Wir haben das Zeichen $\models$ in zwei unterschiedlichen Anwendungen kennen gelernt. Geben sie eine formal korrekte Definition für jede der beiden Anwendungen an. Erklären Sie auch den Unterschied zwischen $\models$ und $\to$. (4.5 Punkte)

Beispiel 1b

Zeigen Sie mit Hilfe von Interpretationsstrukturen der Prädikatenlogik erster Stufe, dass das Deduktions Theorem gültig ist.(4 Punkte)

Beispiel 1c

Gegeben sei die Wissensbasis

$\Gamma :=\{\mathrm{\forall }x\mathrm{\forall }y(R(x,y)\to S(x,y)),\mathrm{\forall }x\mathrm{\forall }y(S(x,y)\to R(y,x))\}.$

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

(4 Punkte)

Beispiel 1d

Überprüfen Sie, welche Eigenschaften auf die nachfolgend angeführten Formeln zutreffen und kreuzen Sie jeweils alle zutreffenden Eigenschaften an: (3 Punkte)

Multiple Choice-Quiz:

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

1

$\mathrm{\forall }x\mathrm{\exists }yR(x,y)\leftrightarrow \mathrm{\exists }x\mathrm{\forall }yR(x,y)$

	erfüllbar (satisfiable)
	widerlegbar (refutable)
	Tautologie (tautology)
	Kontradiktion (contradiction)

2

$\mathrm{\neg }(A\to \mathrm{\neg }(A\to \mathrm{\neg }B))\wedge B$

	erfüllbar (satisfiable)
	widerlegbar (refutable)
	Tautologie (tautology)
	Kontradiktion (contradiction)

3

$\mathrm{\forall }x(P(x)\wedge \mathrm{\neg }P(x))\to \mathrm{\forall }xQ(x)$

	erfüllbar (satisfiable)
	widerlegbar (refutable)
	Tautologie (tautology)
	Kontradiktion (contradiction)

Beispiel 1e

Kreuzen Sie Zutreffendes an: (3 Punkte)

Multiple Choice-Quiz:

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

1

Da TC1 nicht immer terminiert, kann TC1 nicht korrekt sein.

	richtig
	falsch

2

Die leere Disjunktion ist in allen Interpretationsstrukturen falsch.

	richtig
	falsch

3

Das Compactness theorem besagt: Eine (unendliche) Menge an Formeln ist genau dann erfüllbar, wenn jede endliche Teilmenge erfüllbar ist.

	richtig
	falsch

Beispiel 2: Nichtmonotones Schließen

Beispiel 2a

Zeigen Sie, dass die semantische Konsequenzrelation $\models$ der klassischen Logik monoton ist. (4 Punkte)

Beispiel 2b

Betrachten Sie die Default Theorie $T:=⟨W,\Delta ⟩$. Dabei sind $W$ und $\Delta$ unter Verwendung der Prädikatssymbole $P,Q,R,S,U,V$ wie folgt definiert.

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

$\Delta :=\{\frac{\mathrm{\top }:\mathrm{\exists }xP(x)}{\mathrm{\exists }xP(x)},\frac{U(x):\mathrm{\neg }Q(x)}{\mathrm{\neg }Q(x)},\frac{R(x,y):V(x)\wedge U(y)\to S(x)}{V(x)\wedge U(y)\to S(x)}\}$

Hat T eine Extension? Begründen Sie ihre Antwort. (2 Punkte)

Lösungsvorschläge:

• T hat eine Extension, da normale Default-Theorien immer Extensions besitzen. T ist eine normale Default-Theorie, da sie ausschließlich normale Defaults enthält.

Beispiel 2c

Betrachten Sie die folgende Default Theorie.

$T_2:=⟨\mathrm{\varnothing },\{\frac{\mathrm{\top }:\mathrm{\neg }{P}_2(a)}{P_1(a)},\frac{\mathrm{\top }:\mathrm{\neg }{P}_1(a)}{P_2(a)}\}⟩$

Für eine Default Theorie $T$ sei $\epsilon (T)$ die Menge aller Extensions von $T$. Dann gilt für $T_2$, dass $|\epsilon (T_2)|\ge 2$. Generalisieren Sie $T_2$, sodass für ein beliebiges $n\ge 2,|\epsilon (T_n)|\ge n$ gilt. (3 Punkte)

Beispiel 2d

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

$T=\{P(a),O(b),P(c),Q(c),\mathrm{\forall }x(Q(x)\to (P(x)\to Q(b)))\}.$

(i) Geben Sie die Closed World Assumption CWA(T) von T an, indem Sie die folgende Gleichung ergänzen: $CWA(T)=Cn(T\cup \{\mathrm{...}\})$

(ii) 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 ist deduktiv abgeschlossen.

	richtig
	falsch

2

CWA(T) ist konsistent.

	richtig
	falsch

Beispiel 2e

Gegeben ist die folgende Default Theorie.

$T=⟨W,\Delta ⟩:=⟨\{\mathrm{\forall }x(Q(a)\to \mathrm{\neg }P(x)),P(b)\to \mathrm{\forall }x\mathrm{\neg }Q(x)\},\{\frac{\mathrm{\top }:\mathrm{\neg }Q(x)}{P(x)},\frac{\mathrm{\top }:\mathrm{\neg }P(x)}{Q(x)}\}⟩$

Berechnen Sie alle Extensions dieser Theorie (a, b sind Konstantensymbole, x ist ein Variablensymbol und P und Q sind Prädikatensymbole). (4 Punkte)

Beispiel 3: Answer-Set Programming

Beispiel 3a

Gegeben ist folgendes Answer Set Programm:

$𝒫:=\{P(a).Q(b).S(b).R(X,Y)\leftarrow P(X),Q(Y),notS(X).\}$

(i) Bestimmen Sie die Grundierung $grnd(𝒫)$

(ii) Gegeben $E:=\{P(a),S(b),Q(b)\}$, bestimmen Sie das Reduktion ${𝒫}^E$. Ist E ein Answer Set von $𝒫$? Begründen Sie ihre Antwort!

(5 Punkte)

Lösungsvorschläge

Lösungsvorschlag 1

i)

$grnd(P)=\{P(a).Q(b).S(b).R(a,a)\leftarrow P(a),Q(a),notS(a).R(a,b)\leftarrow P(a),Q(b),notS(a).R(b,a)\leftarrow P(b),Q(a),notS(b).R(b,b)\leftarrow P(b),Q(b),notS(b).\}$

ii)

$P^E=\{P(a).Q(b).S(b).R(a,a)\leftarrow P(a),Q(a).R(a,b)\leftarrow P(a),Q(b).\}$

$E$ ist ein Answer-Set von $P$, da es ein minimales Model von $P^E$ ist.

Anmerkung: Ich denke es ist kein Answer Set, da es kein Modell von $P^E$ ist. $R(a,b)$ müsste vorkommen damit es ein AS ist.

Beispiel 3b

Definieren Sie eine konsistenzbasierte Diagnose eines Diagnoseproblems $𝒫=⟨H,T,O⟩$ für Answer-Set Programme. (3 Punkte)

Lösungsvorschläge:

• Lösungsvorschlag vom gescannten Test (3/3 Punkte): konsistenzbasierte Diagnose S. $S\subseteq H$ und $T\cup S\cup O\{\mathrm{\neg }h|h\in H\setminus S\}$ ist consistent.

Beispiel 3c

Kreuzen Sie Zutreffendes an: (5 Punkte)

Multiple Choice-Quiz:

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

1

Wenn $M$ ein minimales Modell eines Programms $𝒫$ ist, dann ist $M$ ein Answer Set von $𝒫$.

	richtig
	falsch

2

Das Programm $𝒫:=\{a\leftarrow .,b\leftarrow a,notb.,b\leftarrow .\}$ hat keine Answer Sets. (unbewertet)

	richtig
	falsch

3

Ein Programm, in dem keine starke Negation benutzt wird, hat immer ein Answer Set.

	richtig
	falsch

4

Leere Programme (Programme ohne Regeln) haben Answer Sets.

	richtig
	falsch

5

Falls eine Query unter cautious reasoning wahr ist dann ist es auch unter brave reasoning wahr.

	richtig
	falsch

Beispiel 3d

Gegeben sei das folgende distinktive Answer-Set Programm:

$𝒫:=\{a\vee b\vee c\vee d\}$

Berechnen Sie die Answer Sets der folgenden Programme:

(i) $𝒫\cup \{\leftarrow a,b.\}$

(ii) $𝒫\cup \{\leftarrow a.\leftarrow b.\}$

(3 Punkte)

Beispiel 4: Probabilistisches Schließen

Beispiel 4a

Was ist ein Bayes'sches Netz (Grundidee, Komponenten, Unabhängigkeitsannahmen, Berechnung der Wahrscheinlichkeiten)? (4 Punkte)

Beispiel 4b

Leiten Sie das Bayes'sche Gesetz aus der Produktregel her. (4 Punkte)

Beispiel 4c

Eine Fabrik produziert auf zwei Maschinen gleichzeitig. Die Erzeugnisse von Maschine 1 sind zu 5% fehlerhaft; die Erzeugnisse von Maschine 2 sind zu 20% fehlerhaft. Die Erzeugnisse werden in einem Verhältnis von 2:3 vermischt. Aus dieser Mischung wird ein Produkt zufällig ausgewählt. Was ist die Wahrscheinlichkeit, dass ein fehlerhafter Produkt gezogen wird? Unter der Annahme, dass das Produkt fehlerhaft ist, was ist die (bedingte) Wahrscheinlichkeit, dass dieses Produkt von der ersten Maschine erzeugt wurde.

Verwenden Sie die Zufallsvariable $M_i(i=1,2)$ für das Ereignis, dass das Produkt von Maschine $i$ produziert wurde und die Zufallsvariable $R$, dass das Produkt fehlerhaft ist. (4 Punkte)

Beispiel 4d

Gegeben ist folgender Graph eines Bayes'schen Netzes:

(siehe Angabe)

Welche der folgenden Eigenschaften treffen zu? (4 Punkte)

Multiple Choice-Quiz:

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

1

G ist bedingt unabhängig von D bei Evidenz J und H.

	richtig
	falsch

2

D ist bedingt unabhängig von J bei Evidenz B, E und I.

	richtig
	falsch

3

F ist bedingt unabhängig von C bei Evidenz J und G.

	richtig
	falsch

4

H ist bedingt unabhängig von E bei Evidenz I.

	richtig
	falsch