TU Wien:Einführung in wissensbasierte Systeme VU (Egly)/Prüfung 2013-03-22/Beispiel 2

Nichtmonotones Schließen

Teilaufgabe a)

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

$T=\{\exists xQ(x),P(a),\neg Q(b),\forall x(P(x)\rightarrow Q(x))\}$

Punkt 1

Geben Sie die Elemente der Closed-World Assumption $CWA(T)$ von $T$ an, in dem Sie folgende Gleichungen ergänzen:

$T_{asm}=\{\_\_\_\_\_\}CWA(T)=\{\psi |\_\_\_\_\_\}$

(4 Punkte)

Lösungsvorschlag 1: JasonLeroy (Diskussion) 14:40, 22. Jan. 2014 (CET)

$T_{asm}=\{\neg P(b),\neg P(c),\neg Q(b),\neg Q(c)\}CWA(T)=\{\psi |T\cup T_{asm}\models \psi ,\psi closed\}$

Lösungsvorschlag 2:

$T_{asm}=\{\neg P(b),\neg P(c),\neg Q(c)\}CWA(T)=\{Q(a)\}$

Anmerkung von --JasonLeroy (Diskussion) 11:16, 28. Jan. 2015 (CET) zu Lösungsvorschlag 2: Ich kann nachvollziehen, warum $\neg Q(b)$ nicht aufgenommen wurde, aber ich bin dennoch der Meinung, dass es in $T_{asm}$ enthalten sein muss. Laut Definition werden nämlich $\neg P|Pgroundatom$ aufgenommen, also Atome. In diesem Fall ist $Q(b)$ das ground Atom, $\neg Q(b)$ wäre ein Literal. $Q(b)$ ist nicht aus T ableitbar (es ist nämlich nur $\neg Q(b)$ ableitbar), womit es meiner Ansicht nach mit Negation in $T_{asm}$ aufgenommen werden muss.

Anmerkung von --Stampi (Diskussion) 16:08, 25. Jan. 2014 (CET):

CWA(T) = {Q(a)} kann aufgrund der Definition von CWA(T) nicht stimmen.

Def: $CWA(T)=Cn(W\cup T_{asm})$ Somit müssten zumindest alle Formeln, die in W enthalten sind bzw. abgeleitet werden können, auch in CWA(T) aufgenommen werden.

Lösungsvorschlag 3:

$T_{asm}=\{\neg P(c),\neg Q(c)\}CWA(T)=Loesungsvorschlag1$

an Vorposter: Warum nehmt ihr denn -P(b) und -Q(b) in die Tasm auf?? Die sind doch eh schon in Cn(T U Tasm) drinnen...

Antwort: Aufgrund der Definition von Seite 17 in nmr1.pdf: $T_{asm}=\{\neg P|P\ ground\ atom,T\not \models P\}$. Beispielsweise ist $P(b)$ nicht aus $T$ ableitbar, also ist $\neg P(b)$ Teil der $T_{asm}$

an Vorposter: Augrund der Implikation P(x) -> Q(x) kann man das sehr wohl herleiten. -Q(b) ist bereits in T daher kann man herleiten, dass -P(b) gelten muss da wenn P(b) gelten würde die Implikation 1 -> 0 inkonsistenz erzeugt. Also kann nur -P(b) gelten. Siehe hier (Modus Tollens): http://de.wikipedia.org/wiki/Modus_tollens

an Vorposter: Da aber aus deiner Begründung folgt, dass P(b) aus T nicht abgeleitet werden kann, muss $\neg P(b)$ zwingend in die $T_{asm}$ auch wenn bereits $T\models \neg P(b)$ gilt.

Siehe: $T_{asm}=\{\neg P|P\ is\ a\ ground\ atom,\ T\not \models P\}$

$T\not \models P(b)$ gilt in unserem Fall und da P(b) ein ground atom ist, folgt $\{\neg P(b)\}\subseteq T_{asm}$

Punkt 2

Welche der folgenden Eigenschaften treffen für obige Theorie $T$ zu?

• $T_{asm}$ ist vollständig. richtig ☐ falsch ☐
• $CWA(T)$ ist konsistent. richtig ☐ falsch ☐
• $T$ ist deduktiv abgeschlossen. richtig ☐ falsch ☐

(3 Punkte)

Lösungsvorschlag: JasonLeroy (Diskussion) 14:55, 22. Jan. 2014 (CET)

• richtig ☐ falsch ☒ (aber $T\cup T_{asm}$ ist vollständig)
• richtig ☒ falsch ☐
• richtig ☐ falsch ☒

Teilaufgabe b)

Was versteht man unter Nichtmonotonie? Ist die Default-Logik eine nichtmonotone Inferenzrelation? Belegen Sie Ihre Antwort mit einem Beispiel.

(3 Punkte)

Lösungsvorschlag: JasonLeroy (Diskussion) 17:34, 22. Jan. 2014 (CET)

Lässt sich eine Aussage aus einer Menge von anderen Aussagen (Prämissen) herleiten, so lässt sich die selbe Aussage auch dann noch herleiten, wenn man eine beliebige weitere Prämisse hinzufügt. Diese Eigenschaft nennt man Monotonie. Folgerungen im Alltag haben allerdings oft nicht-monotonen Charakter. Erfahren wir beispielsweise, dass Tux ein Vogel ist, so könnten wir schlussfolgern, dass Tux fliegen kann. Erfahren wir dann jedoch, dass Tux ein Pinguin ist, so würden wir nicht mehr schließen, dass Tux fliegen kann, da wir wissen, dass Pinguine nicht fliegen können.

Die Default-Logik ist eine nichtmonotone Inferenzrelation. Beispiel:

$D=\{{\frac {Bird(X):Flies(X)}{Flies(X)}}\}$

In Worten: Wenn X ein Vogel ist, und wir davon ausgehen können, dass X fliegen kann (d.h. die Aussage X kann nicht fliegen lässt sich nicht ableiten), dann kann X fliegen. Der Sonderfall Pinguin zeigt uns, dass wir es hier mit Nichtmonotonie zu tun haben (auch, wenn nicht alle Sonderfälle explizit aufgezählt werden).

Teilaufgabe c)

Geben Sie die Definition des klassischen Redukts $\Delta _{E}$ einer Menge $\Delta$ von geschlossenen Defaults bezüglich einer Menge $E$ von geschlossenen Formeln an.

(3 Punkte)

Lösungsvorschlag:

$\Delta _{E}=\{\varphi /\chi |(\varphi :\psi _{1},...,\psi _{n}/\chi )\in \Delta ,\{\neg \psi _{1},...,\neg \psi _{n}\}\cap E=\emptyset \}$

Teilaufgabe d)

Gegeben seien folgende Mengen ($p$, $q$, $r$ und $s$ sind aussagenlogische Konstanten):

$\Delta =\{{\frac {r:\neg s}{\neg p}},{\frac {s,q:\neg r}{r}},{\frac {\neg r:q,s}{s}},{\frac {:\neg s}{p}}\},$
$W_{1}=\{r\},E_{1}=Cn(W_{1}\cup \{\neg q,p\}),$
$W_{2}=\{r,\neg p\},E_{2}=Cn(W_{2}),$
$W_{3}=\{s,q\},E_{3}=Cn(W_{3}\cup \{\neg r,p\}).$

Punkt 1

Geben Sie die klassischen Redukte $\Delta _{E}$ von $\Delta$ bezüglich den Mengen $E_{i}$ an, für $i=1,2,3$.

$\Delta _{E_{1}}=\{\_\_\_\}\Delta _{E_{2}}=\{\_\_\_\}\Delta _{E_{3}}=\{\_\_\_\}$

(6 Punkte)

Lösungsvorschlag: JasonLeroy (Diskussion) 21:33, 22. Jan. 2014 (CET)

Aktualisiert am 28. Jan. 2015 wegen Stampi's Anmerkung (siehe unten)

$\Delta _{E_{1}}=\{(r/\neg p),(/p)\}\Delta _{E_{2}}=\{(r/\neg p),(\neg r/s),(/p)\}\Delta _{E_{3}}=\{(s,q/r),(\neg r/s)\}$

Vorschlag von --Stampi (Diskussion) 19:19, 28. Jan. 2014 (CET)

mMn ist $\Delta _{E_{2}}$ falsch. $\Delta _{E_{2}}=\{{\frac {r}{\neg p}},{\frac {\neg r}{s}},{\frac {T}{p}}\}$

Antwort: --JasonLeroy (Diskussion) 12:48, 3. Mai 2014 (CEST)

Glaube ich nicht. Wir wissen ja, dass $r$ der Fall ist, also können wir den Default ${\frac {\neg r:irgendwas}{irgendwas}}$ gar nicht anwenden.

Antwort: Ich denke das Stampi recht hat, würde sich auch mit alten Prüfungen decken. [[1]] Nach der Definition des Redukts, es werden nur die justifications überprüft und da gibt es kein problem mit $r$. (Def.Redukt: nmr2.pdf 19/21)

--JasonLeroy (Diskussion) 11:29, 28. Jan. 2015 (CET)
Ein Jahr später, ein Jahr gescheiter. Stampi hat recht.

Punkt 2

Markieren Sie die korrekten Aussagen:

1. $E_{1}$ ist eine Extension der Default Theorie $T_{1}=(W_{1},\Delta )$. richtig ☐ falsch ☐
2. $E_{2}$ ist eine Extension der Default Theorie $T_{2}=(W_{2},\Delta )$. richtig ☐ falsch ☐
3. $E_{3}$ ist eine Extension der Default Theorie $T_{3}=(W_{3},\Delta )$. richtig ☐ falsch ☐

(6 Punkte)

Lösungsvorschlag: JasonLeroy (Diskussion) 14:55, 22. Jan. 2014 (CET)

1. richtig ☐ falsch ☒
2. richtig ☐ falsch ☒
3. richtig ☐ falsch ☒

Links

• Datei:TU Wien-Einführung in wissensbasierte Systeme VU (Egly) - Prüfung 2013-03-22.pdf
• Diskussion im Informatik-Forum