TU Wien:Einführung in wissensbasierte Systeme VU (Egly)/Prüfung 2016-04-26 Ausarbeitung

Diese Ausarbeitung bezieht sich auf die Prüfung vom 26.04.2016 (Datei:TU Wien-Einführung in wissensbasierte Systeme VU (Egly) - Prüfung 2016-04-26.pdf) und auf den zugehörigen informatik-forum thread (https://web.archive.org/web/*/www.informatik-forum.at/showthread.php?113018-Pr%FCfung-26-4-2016)

Diese Lösungen sind eher als Lösungsvorschlag zu sehen.

Beispiel 2 - (Nicht monotones Schließen)

a)

Gegeben ist folgende Wissesbasis $T$ über einer Sprache mit den einzigen Konstantensymbolen $a,b,c$, dem Variablensymbol $x$ und den einzigen Prädikatensybolen $P$ und $Q$:

$T=\{\mathrm{\neg }P(a),Q(c)\to P(c),Q(b),\mathrm{\forall }x(Q(x)\vee P(x))\}$

1. Geben Sie die Closed World Assumption $CWA(T)$ von $T$ an, indem Sie folgende Gleichung ergänzen:

$CWA(T)=Cn(T\cup T_{asm})$ where

$T_{asm}=\{\mathrm{\neg }P(a),\mathrm{\neg }P(b),\mathrm{\neg }P(c),\mathrm{\neg }Q(c)\}$

$\mathrm{\neg }Q(a)\in ̸T_{asm}$, since $\{Q(a)\vee P(a),\mathrm{\neg }P(a)\}\models Q(a)$

2. Welche der folgenden Eigenschaften treffen zu?

- $T$ is not deductively closed, since $Cn(T)\ne T$

- $CWA(T)$ is not consistent, since $(T\models Q(c)\vee P(c))\wedge (CWA(T)\models ̸Q(c))\wedge (CWA(T)\models ̸P(c)\})$

e)

Gegeben seien folgende Mengen, wobei $a$ und $b$ Konstantensymbole und $P,Q\text{ und }R$ Prädikate sind.

$W=\{\mathrm{\neg }P(a),R(b)\},$

$\Delta =\{\frac{P(a):\mathrm{\neg }Q(b)}{Q(b)},\frac{R(b):P(b)}{Q(a)},\frac{R(a):P(a)}{Q(b)}\}$

---

1. $T_1=(W,\Delta )$

The formal (or naive) way of computing extensions.

Step 1: Generate all sets of form $Cn(W\cup 𝒞)$ such that:

$𝒞\subseteq \{\chi |\frac{\phi :{\psi }_1,\dots ,{\psi }_n}{\chi }\in \Delta \}$

(intuitively: $Cn(W\cup 𝒞)$ for each $𝒞\in$ power set of derivable atoms in $\Delta$)

$E_1=Cn(W\cup \{\})$

$E_2=Cn(W\cup \{Q(a)\})$

$E_3=Cn(W\cup \{Q(b)\})$

$E_4=Cn(W\cup \{Q(a),Q(b)\})$

Step 2: Generate classical reduct $\Delta$

${\Delta }_{E_1}=\{P(a)/Q(b),R(b)/Q(a)\}$

${\Delta }_{E_2}=\{P(a)/Q(b),R(b)/Q(a)\}$

${\Delta }_{E_3}=\{R(b)/Q(a)\}$

${\Delta }_{E_4}=\{R(b)/Q(a)\}$

Step 3: Apply derived rules recursively using the original knowledge base W. Iff $C{n}^{{\Delta }_E}(W)$ is the original extension candidate $E$ then E is an extension of $T$.

$C{n}^{{\Delta }_{E_1}}(W)=Cn(W\cup \{Q(a)\})\ne E_1$

$C{n}^{{\Delta }_{E_2}}(W)=Cn(W\cup \{Q(a)\})=E_2\Rightarrow \text{Extension of }T$

$C{n}^{{\Delta }_{E_3}}(W)=Cn(W\cup \{Q(a)\})\ne E_3$

$C{n}^{{\Delta }_{E_4}}(W)=Cn(W\cup \{Q(a)\})\ne E_4$

---

2. $T_2=(P(a),\Delta )$

$W_2=\{P(a)\}$

$E_1=Cn(W_2\cup \{\})$

$E_2=Cn(W_2\cup \{Q(a)\})$

$E_3=Cn(W_2\cup \{Q(b)\})$

$E_4=Cn(W_2\cup \{Q(a),Q(b)\})$

${\Delta }_{E_1}=\{P(a)/Q(b),R(b)/Q(a),R(a)/Q(b)\}$

${\Delta }_{E_2}=\{P(a)/Q(b)\}$

${\Delta }_{E_3}=\{R(b)/Q(a),R(a)/Q(b)\}$

${\Delta }_{E_4}=\{R(b)/Q(a)\}$

$C{n}^{{\Delta }_{E_1}}(W_2)=Cn(W_2\cup \{Q(b)\})\ne E_1$

$C{n}^{{\Delta }_{E_2}}(W_2)=Cn(W_2\cup \{Q(b)\})\ne E_2$

$C{n}^{{\Delta }_{E_3}}(W_2)=Cn(W_2\cup \{Q()\})\ne E_3$

$C{n}^{{\Delta }_{E_4}}(W_2)=Cn(W_2\cup \{Q()\})\ne E_4$

$\Rightarrow$ this theory has no extension.