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

Nichtmonotones Schließen

Teilaufgabe a)

Was versteht man unter der Monotonie einer Inferenzrelation? Geben Sie eine formal korrekte Definition an.

Lösungsvorschlag --JasonLeroy (Diskussion) 00:16, 5. Mai 2014 (CEST)

Wenn $S\models A$ und $S\subseteq S^{\prime }$, dann $S^{\prime }\models A$.

Lösungsvorschlag --JasonLeroy (Diskussion) 00:16, 5. Mai 2014 (CEST)

$W\models \psi$ impliziert $W\cup \{\varphi \}\models \psi$

Teilaufgabe b)

Geben Sie die allgemeine Definition des deduktiven Abschlusses $Cn(T)$ eine Wissensbasis $T$ an. Zeigen bzw. Widerlegen Sie, dass es ein $T_0$ gibt, sodass $Cn(T_0)$ endlich ist. Ferner zeige man, dass $Cn(\cdot )$ monoton ist.

Lösungsvorschlag:

Definition dedukiver Abschluss:

Sei $T$ eine Theorie, dann ist ihr logischer Abschluss $Cn$ definiert als:

$Cn(T)=\{\varphi |T\models \varphi and\varphi isclosed\}$

Monotonie (Ansatz): Sich aufs Dedukutionstheorem berufen ($T\models F$ genau dann wenn $T⊢F$) und dann argumentieren, dass ein Sequenzkalkülbeweis von $T_1,\dots ,T_n⊢F$ auch genauso durchgeführt werden kann, wenn die Theorie größer, d.h. wir einen Sequent $T_1,\dots ,T_n,U_1,\dots ,U_m⊢F$ ableiten wollen: der zweite lässt sich durch m Anwendungen der weakening Regel aus dem ersten erzeugen.

Alternativ kann auch mit der Monotonie von klassischer Logik argumentiert werden.

Zeigen bzw. Widerlegen Sie, dass es ein $T_0$ gibt, sodass $Cn(T_0)$ endlich ist:

• $Cn(\mathrm{\varnothing })$ ist infinit

Die Sprache enthält immer zumindestens ein Prädikatensymbol P mit Arität n, aus dem sich die Formel $F\equiv \mathrm{\forall }{x}_1\dots \mathrm{\forall }{x}_n(P(x_1,\dots ,x_n)\vee \mathrm{\neg }P(x_1,\dots ,x_n))$ bilden lässt. F ist geschlossen und eine Tautologie, dh. $\models F$. Für jede Formel $G$ gilt, dass $\mathrm{\neg }\mathrm{\neg }G$ eine logische Konsequenz von $G$ ist, d.h. $G\models \mathrm{\neg }\mathrm{\neg }G$. D.h für F sind auch die Formeln $\mathrm{\neg }\mathrm{\neg }F$, $\mathrm{\neg }\mathrm{\neg }\mathrm{\neg }\mathrm{\neg }F$ etc. eine logische Konsequenz aus F. Nachdem dies unendlich viele Formeln sind, muss $Cn(\mathrm{\varnothing })$ immer infinit sein.

• $Cn(T_0)$ ist infinit

Für jede Theorie $T$ gilt: $\mathrm{\varnothing }\subseteq T$. Wegen der Monotonieeigenschaft von Cn gilt auch $Cn(\mathrm{\varnothing })\subseteq Cn(T)$. Weil aber schon $Cn(\mathrm{\varnothing })$ infinit ist, muss es deshalb auch $Cn(T)$ sein.

Teilaufgabe c)

Man formuliere den Satz über die semi-rekursive Charakterisierung von Extension.

Lösungsvorschlag: --JasonLeroy (Diskussion) 00:49, 5. Mai 2014 (CEST)

Anmerkung: Diese Lösung stammt aus den Folien im WS13/14. Im WS14/15 gab es die Definition nicht mehr in den Folien, allerdings bei Beispiel 3 von Übung 3.

Sei $E$ eine Menge geschlossener Formeln und $T=(W,\Delta )$ eine geschlossene Default-Theorie.

Man definiere eine Sequenz $(E_i{)}_{i>0}$ von Mengen von Formeln wie folgt:

$E_0=W$

$E_{i+1}=Cn(E_i)\cup \{\chi |(\varphi :{\psi }_1,\mathrm{...},{\psi }_n/\chi )\in \Delta ,E_i\models \varphi$ und $\mathrm{\neg }{\psi }_1,\mathrm{...},\mathrm{\neg }{\psi }_n\in ̸E\}.$

Dann ist $E$ eine extension von $T$ gdw.

$E={\cup }_{i\ge 0}{E}_i$

Teilaufgabe d)

Es sei $T<W,\Delta >$ eine Default Theorie. Wir definieren $T⊢\varphi$ genau dann, wenn $E\models \varphi$ für jede Extension $E$ von $T$ ist. Man zeige, dass die Relation $⊢$ nicht monoton ist.

Teilaufgabe e)

Gegeben ist eine Default Theorie $T=<W,\Delta >$

$W=\{\text{parent}(r,p)\wedge \text{parent}(r,s),\mathrm{\neg }\text{lazy}(s)\wedge \text{lazy}(p),\text{lazy}(p)\Rightarrow \text{scolds}(r,p),\text{lazy}(s)\Rightarrow \text{scolds}(r,s),\mathrm{\forall }x\text{lazy}(x)\Rightarrow \mathrm{\exists }x\text{lazy}(x)\}$

$\Delta =(\text{parent}(r,p):\mathrm{\neg }\text{scolds}(r,p)/\mathrm{\neg }\text{scolds}(r,p),\text{parent}(r,s):\mathrm{\neg }\text{scolds}(r,s)/\text{scolds}(r,s))$

Kreuzen Sie zutreffendes an:

1. $\text{Cn}(\{\text{parent}(r,p),\text{parent}(r,s),\mathrm{\neg }\text{lazy}(s),\text{lazy}(p),\text{scolds}(r,p),\text{scolds}(r,s)\})$ wahr ☐ falsch ☐
2. $\text{Cn}(\{\text{parent}(r,p),\text{parent}(r,s),\mathrm{\neg }\text{lazy}(s),\text{lazy}(p),\mathrm{\neg }\text{scolds}(r,p),\text{scolds}(r,s)\})$ wahr ☐ falsch ☐
3. $\text{Cn}(\{\text{parent}(r,p),\text{parent}(r,s),\mathrm{\neg }\text{lazy}(s),\text{lazy}(p),\text{scolds}(r,p),\mathrm{\neg }\text{scolds}(r,s)\})$ wahr ☐ falsch ☐

Lösungsvorschlag --JasonLeroy (Diskussion) 01:00, 5. Mai 2014 (CEST)

1. wahr ☒ falsch ☐
2. wahr ☐ falsch ☒
3. wahr ☐ falsch ☒

Kommentar Exkalation (Diskussion) 00:35, 24. Jan. 2015 (CET):

1. Meiner Meinung kann es hier gar keine Extensions geben, da der zweite Default ungültig ist.

[vik_xxxl:Vorschlag] @Exklataion: ich glaube auch dass es keine von die drei extensions sind. Aber wenn T/F/F ist laut EWBS team richtig, es kann sein dass die frage war "welche sind konsistente kandidaten für extension". Dann wäre T/F/F.