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

Nichtmonotones Schließen

Threads im Informatik-Forum:

• zu Teilaufgabe d)

Teilaufgabe a)

Was versteht man unter der Monotonie einer Inferenzrelation? Geben Sie eine formal korrekte Definition an! Zeigen Sie, dass die semantische Konsequenzrelation $\models$ der klassischen Logik monoton ist.

Lösungsvorschlag von --Tyleet

Monotonie:
If $W\models \phi$ then $W\cup \{\psi \}\models \phi$

Beweis:
Angenommen $W\models \phi$ und $W\cup \{\psi \}\not \models \phi$
Dh. es gibt eine Interpretation I für die gilt wegen $W\models \phi ,I\models W$ und $I\models \phi$ und gleichzeitig wegen $W\cup \{\psi \}\not \models \phi ,I\models W\cup \psi$ und$I\not \models \phi$ Damit haben wir einen Wiederspruch, also muss die Implikation der Definition von Monotonie einer Inferenzrelation gelten.

Teilaufgabe b)

(i) Geben Sie die allgemeine Definition des deduktiven Abschlusses $Cn(T)$ einer Wissensbasis $T$ an.

(ii) Zeigen bzw. widerlegen Sie, dass es ein konsistentes $T_{0}$ gibt, sodass $Cn(T_{0})$ kofinit¹ ist.

¹ Wir nennen eine Menge von Formeln kofinit, wenn sie alle Formeln bis auf endlich viele enthält.

Lösungsvorschlag
(i) $Cn(T)=\{\phi |T\models \phi ,\phi {\text{ closed}}\}$

Lösungsvorschlag von --JasonLeroy (Diskussion) 17:16, 26. Jan. 2015 (CET)

(i) $Cn(T)=\{\varphi |T\models \varphi ,\varphi {\text{closed}}\}$

(ii) $Cn(.)$ enthält in jedem Fall nur geschlossene Formeln, d.h. die Menge der nicht geschlossenen Formeln ist niemals in $Cn(.)$ enthalten. Da die Menge der nicht geschlossenen Formeln unendlich ist, kann $Cn(.)$ gar nicht kofinit bezüglich aller Formeln sein.

Auf Nachfrage beim LVA-Team habe ich folgende Antwort bekommen:

man sieht die Loesung leicht ein, wenn man sich folgendes Argument ueberlegt. Angenommen es waeren nur endlich viele Formeln in Cn(T_0) nicht enthalten, nennen wir diese A_1,...,A_n. Betrachten wir dann die Formeln A_1 & ... & A_n und -(A_1 & ... & A_n), so muessen beide in Cn(T_0) enthalten sein, was aber T_0 inkonsistent macht. Darum kann Cn(T_0) fuer ein konsistentes T_0 nicht kofinit sein.

Ich versuche nochmal ausführlicher aufzuschreiben (bin mir aber nicht sicher, ob ich das richtig verstanden habe):

Angenommen $Cn(T_{0})$ ist kofinit, d.h. es gibt endlich viele Formeln, die nicht in $Cn(T_{0})$ enthalten sind. Nennen wir diese Formeln $A_{1},...,A_{n}$. Betrachten wir nun die Formeln

• $(A_{1}\wedge ...\wedge A_{n})$
• $\neg (A_{1}\wedge ...\wedge A_{n})$

Nachdem außer $A_{1},...,A_{n}$ alle Formeln in $Cn(T_{0})$ enthalten sind, sind auch diese beiden enthalten. Doch damit das erfüllt ist, muss $T_{0}$ inkonsistent sein.

Teilaufgabe c)

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

Siehe TU_Wien:Einführung_in_wissensbasierte_Systeme_VU_(Egly)/Prüfung_2014-03-28/Beispiel_2#Teilaufgabe_c.29

Teilaufgabe d)

Es sei $T=(W,\Delta )$ eine Default Theorie. Wir definieren $T\vdash \varphi$ genau dann wenn $E\models \varphi$ für jede Extension $E$ von $T$. Untersuchen Sie, ob es ein $T_{0}=(W_{0},\Delta _{0})$ gibt, sodass aus $T\vdash \varphi$ und $W'\supseteq W_{0}$ und $\Delta '=\Delta _{0}$ immer $T'\vdash \varphi$ folgt, wobei $T'=(W',\Delta ')$.

Teilaufgabe e)

TODO Kreuzerl