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

Logikbasierte Wissensrepräsentation:

Teilaufgabe a)

Geben Sie eine allgemeine Definition des deduktiven Abschlusses $Cn(T)$ einer Wissensbasis $T$. Zeigen Sie, dass $Cn(.)$ idempotent ist. (3.5 Punkte)

Lösung aus dem Informatik Forum:

deduktiver Abschluss

Deduktiver Abschluss

deduktiver Abschluss:

$Cn(T)=\left\{\varphi \mid T\models \varphi \land \varphi \mathrel {\text{is closed}} \right\}$

Beweis von $Cn(T)=Cn(Cn(T))$:

Die eine Richtung $Cn(T)\subseteq Cn(Cn(T))$ gilt, da $Cn(\cdot )$ inflationaer ist.

Wir zeigen also $Cn(Cn(T))\subseteq Cn(T)$. Angenommen es gibt ein $A\in Cn(Cn(T))$ mit $A\not \in Cn(T)$. Dann gilt $Cn(T)\models A$, jedoch $T\not \models A$ (lt. Definition von $Cn$). Es gibt also ein Modell von $T$, welches kein Modell von $A$ ist. Jedes Modell von $T$ ist aber auch ein Modell von $Cn(T)$. Folglich gibt es ein Modell von $Cn(T)$, welches kein Modell von $A$ ist, ergo $Cn(T)\not \models A$, Widerspruch.

Teilaufgabe b)

Was versteht man unter Nichtmonotonie einer Inferenzrelation? Geben Sie eine formal korrekte Definition an! (1.5 Punkte)

Lösungsvorschlag Tyleet

Nichtmonotonie:
Wenn durch das hinzufügen neuer Informationen in eine Wissensbasis zuvor ableitbares Wissen nicht mehr ableitbar wird.

Formale definition: (Großes Fragezeichen! Nicht sicher!)
If $W\models \phi$ and $W\subseteq W'$ then $W'\not \models \phi$

Beispiel:
$T=\{W,\Delta \}$
$W=\{Bird(Tweety)\}$
$\Delta =\{{\frac {Bird(x):flies(x)}{flies(x)}}\}$
Es gilt:
$T\models flies(Tweety)$
Aber:
$T'=\{W',\Delta \}$
$W'=W\cup \{Penguin(Tweety),\forall x(Penguin(x)\rightarrow \neg flies(x))\}$
Es gilt:
$T'\not \models flies(x)$

Teilaufgabe c)

Man definiere das klassische Redukt einer Default Theorie $T=(W,\Delta )$ bzgl. einer Extension $E$ von $T$. (1.5 Punkte)

Teilaufgabe d)

Geben Sie eine Definition einer nichtmonotonen Konsequenzrelation an, welche definiert wann eine Formel aus einer Default Theorie logisch folgt und zeigen Sie von dieser Relation, dass sie tatsächlich nichtmonoton ist. (3 Punkte)

wtf egly?

Teilaufgabe e)

Gegeben ist eine Default Theorie $T=(W,\Delta )$, mit

$W=\{Person(s)\}\Delta =\{TODO\}$

TODO

(3 Punkte)