TU Wien:Einführung in wissensbasierte Systeme VU (Egly)/Übungen SS12/Blatt 1 - Beispiel 5

Let $\phi \,$ be the knowledge base $\forall x({\text{Pet}}(x)\rightarrow {\text{Cat}}(x)\lor {\text{Dog}}(x))\land \forall x({\text{Cat}}(x)\rightarrow {\text{Cute}}(x))$ and $\psi \,$ be the query $({Pet}(c)\land \neg {Dog}(c))\rightarrow {\text{Cute}}(c))$, and let $c\,$ be a constant symbol.

1. Decide using semantics whether the query $\psi \,$ follows from knowledge base $\phi \,$
2. Use TC1 to check whether the query $\psi \,$ follows from knowledge base $\phi \,$

Theorie

Um die Tableau Regeln anwenden zu können brauchen wir NNF, konkrete Umformungsregeln die wir brauchen:

${\begin{aligned}F\rightarrow G&=\neg F\lor G\\\neg (F\land G)&=\neg F\lor \neg G\\\neg (F\lor G)&=\neg F\land \neg G\\\neg \neg F&=F\end{aligned}}$

Lösungsvorschlag

using semantics

Wir verwenden den selben Ansatz wie bei Beispiel 1.3, in dem wir mit Deduktionstheorem in einem Indirekten Beweis einen Widerspruch konstruieren. Es soll gezeigt werden, dass $\phi \models \psi$, damit das gilt, muss $\phi \rightarrow \psi$ eine gültige Formel sein.

Nehmen wir an $\phi \rightarrow \psi$ sei widerlegbar. So muss $\phi \land \neg \psi$ gelten, bzw. eine Interpretation I existieren, für die gilt

${\begin{aligned}I\models \phi \\I\nvDash \psi \end{aligned}}$

Wegen der Semantik von $\rightarrow$ (Die Implikation ist falsch, gdw. der linke Teil der Implikation wahr und der rechte falsch ist), sehen wir, dass $\neg \psi \,$ nur in einer Interpretation (in der Domäne ${\mathcal {U}}=\{c\}$) gilt, nämlich:

${\begin{aligned}I({\text{Pet}}(c))&=1\\I({\text{Cute}}(c))&=0\\I({\text{Dog}}(c))&=0\end{aligned}}$

Für $\phi \,$ erkennen wir mittels Spezialisierung, dass auch gelten muss:

$({\text{Pet}}(c)\rightarrow {\text{Cat}}(c)\lor {\text{Dog}}(c))\land ({\text{Cat}}(c)\rightarrow {\text{Cute}}(c))$

Was nur gelten kann, wenn beide Teile der Konjunktion wahr sind.

Damit der linke Teil der Konjunktion $({\text{Cat}}(c)\rightarrow {\text{Cute}}(c))$ wahr bleibt, muss $I({\text{Cat}}(c))=0$ gelten, da sonst die Implikation falsch wäre (wir haben bereits $I({\text{Cute}}(c))=0$ angenommen.

Damit der rechte Teil der Konjunktion wahr bleibt, muss, weil $I({\text{Pet}}(c))=1$, der rechte Teil der Implikation wahr sein. Dazu muss, weil $I({\text{Dog}}(c))=0$, $I({\text{Cat}}(c))=1$ gelten.

Wir haben somit einen Widerspruch ($I({\text{Cat}}(c)$) gefunden. $\phi \rightarrow \psi$ ist nicht widerlegbar.

TC1

$\phi \models \psi$ gilt wenn $\phi \rightarrow \psi$ gültig, bzw das Negat davon $\neg (\phi \rightarrow \psi )$ unerfüllbar ist.

In NNF: wir wollen zeigen, dass $\neg \phi \lor \psi$ gültig, bzw. $\phi \land \neg \psi$ unerfüllbar ist.

Mit dem Tableau bauen wir indirekte Beweise, wir nehmen also an: $\phi \land \neg \psi$ sei erfüllbar, und prüfen diese Annahme im Tableau. Finden wir kein Modell für die Annahme, so haben wir einen Widerspruch und die ursprünglich zu zeigende Aussage ist wahr.

NNF Umformung:

${\begin{aligned}{\text{nnf}}(\phi )&=\forall x(\neg {\text{Pet}}(x)\lor {\text{Cat}}(x)\lor {\text{Dog}}(x))\land \forall x(\neg {\text{Cat}}(x)\lor {\text{Cute}}(x))\\{\text{nnf}}(\psi )&=\neg ({\text{Pet}}(c)\land \neg {\text{Dog}}(c))\lor {\text{Cute}}(c)\\&=\neg {\text{Pet}}(c)\lor {\text{Dog}}(c)\lor {\text{Cute}}(c)\\{\text{nnf}}(\neg \psi )&={\text{Pet}}(c)\land \neg {\text{Dog}}(c)\land \neg {\text{Cute}}(c)\end{aligned}}$

D.h. wir können jetzt mit:

$\forall x(\neg {\text{Pet}}(x)\lor {\text{Cat}}(x)\lor {\text{Dog}}(x))\land \forall x(\neg {\text{Cat}}(x)\lor {\text{Cute}}(x))\land {\text{Pet}}(c)\land \neg {\text{Dog}}(c)\land \neg {\text{Cute}}(c)$

ins Tableau einsteigen. Ich spar mir die Einstiegszeile.

1: $\forall x(\neg {\text{Pet}}(x)\lor {\text{Cat}}(x)\lor {\text{Dog}}(x))$
2: $\forall x(\neg {\text{Cat}}(x)\lor {\text{Cute}}(x))$
3: ${\text{Pet}}(c)\,$
4: $\neg {\text{Dog}}(c)\,$
5: $\neg {\text{Cute}}(c)\,$
6 (aus 2): $\neg {\text{Cat}}(c)\lor {\text{Cute}}(c)$
7: $\neg {\text{Cat}}(c)\,$			8: ${\text{Cute}}(c)\,$
9 (aus 1): $\neg {\text{Pet}}(c)\lor {\text{Cat}}(c)\lor {\text{Dog}}(c)$			* mit 5
$\neg {\text{Pet}}(c)\,$	${\text{Cat}}(c)\,$	${\text{Dog}}(c)\,$
* mit 3	* mit 7	* mit 4

Links

• f.thread:92992