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 \varphi$ then $W\cup \{\psi \}\models \varphi$

Beweis:
Angenommen $W\models \varphi$ und $W\cup \{\psi \}\models ̸\varphi$
Dh. es gibt eine Interpretation I für die gilt wegen $W\models \varphi ,I\models W$ und $I\models \varphi$ und gleichzeitig wegen $W\cup \{\psi \}\models ̸\varphi ,I\models W\cup \psi$ und$I\models ̸\varphi$ 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)=\{\varphi |T\models \varphi ,\varphi \text{ closed}\}$

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

(i) $Cn(T)=\{\phi |T\models \phi ,\phi \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,\mathrm{...},A_n$. Betrachten wir nun die Formeln

• $(A_1\wedge \mathrm{...}\wedge A_n)$
• $\mathrm{\neg }(A_1\wedge \mathrm{...}\wedge A_n)$

Nachdem außer $A_1,\mathrm{...},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⊢\phi$ genau dann wenn $E\models \phi$ für jede Extension $E$ von $T$. Untersuchen Sie, ob es ein $T_0=(W_0,{\Delta }_0)$ gibt, sodass aus $T⊢\phi$ und $W^{\prime }\supseteq W_0$ und ${\Delta }^{\prime }={\Delta }_0$ immer $T^{\prime }⊢\phi$ folgt, wobei $T^{\prime }=(W^{\prime },{\Delta }^{\prime })$.

Teilaufgabe e)

TODO Kreuzerl