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'$, dann $S'\models A$.

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

$W\models \psi$ impliziert $W\cup \{\phi \}\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)=\{\phi \ |\ T\models \phi \ and\ \phi \ is\ closed\}$

Monotonie (Ansatz): Sich aufs Dedukutionstheorem berufen ($T\models F$ genau dann wenn $T\vdash F$) und dann argumentieren, dass ein Sequenzkalkülbeweis von $T_{1},\ldots ,T_{n}\vdash F$ auch genauso durchgeführt werden kann, wenn die Theorie größer, d.h. wir einen Sequent $T_{1},\ldots ,T_{n},U_{1},\ldots ,U_{m}\vdash 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(\emptyset )$ ist infinit

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

• $Cn(T_{0})$ ist infinit

Für jede Theorie $T$ gilt: $\emptyset \subseteq T$. Wegen der Monotonieeigenschaft von Cn gilt auch $Cn(\emptyset )\subseteq Cn(T)$. Weil aber schon $Cn(\emptyset )$ 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 |(\phi :\psi _{1},...,\psi _{n}/\chi )\in \Delta ,E_{i}\models \phi$ und $\neg \psi _{1},...,\neg \psi _{n}\not \in E\}.$

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

$E=\cup _{i\geq 0}E_{i}$

Teilaufgabe d)

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

Teilaufgabe e)

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

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

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

Kreuzen Sie zutreffendes an:

1. $\mathop {\text{Cn}} (\{\mathop {\text{parent}} (r,p),\mathop {\text{parent}} (r,s),\neg \mathop {\text{lazy}} (s),\mathop {\text{lazy}} (p),\mathop {\text{scolds}} (r,p),\mathop {\text{scolds}} (r,s)\})$ wahr ☐ falsch ☐
2. $\mathop {\text{Cn}} (\{\mathop {\text{parent}} (r,p),\mathop {\text{parent}} (r,s),\neg \mathop {\text{lazy}} (s),\mathop {\text{lazy}} (p),\neg \mathop {\text{scolds}} (r,p),\mathop {\text{scolds}} (r,s)\})$ wahr ☐ falsch ☐
3. $\mathop {\text{Cn}} (\{\mathop {\text{parent}} (r,p),\mathop {\text{parent}} (r,s),\neg \mathop {\text{lazy}} (s),\mathop {\text{lazy}} (p),\mathop {\text{scolds}} (r,p),\neg \mathop {\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.