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

Consider the following theories:

$T_{1}=\left\lbrace {\begin{aligned}\forall x(\neg P(x)\rightarrow Q(x)),\\\exists x(P(x)\land \neg Q(x)),\\P(a),\\\neg Q(b),\\Q(c).\end{aligned}}\right\rbrace$

$T_{2}=\left\lbrace {\begin{aligned}\forall x(\neg Q(x)\rightarrow R(x)),\\\forall x(\neg R(x)\rightarrow P(x)),\\P(a)\land Q(a),\\R(b),\\Q(c)\lor \neg P(c).\end{aligned}}\right\rbrace$

$P\,$ , $Q\,$, and $R\,$ are predicate symbols, and the considered alphabet contains only $a\,$, $b\,$, and $c\,$ as object constants.

1. Determine ${\text{CWA}}(T_{1})\,$. Is ${\text{CWA}}(T_{1})\,$ consistent? Justify your answer.
2. Determine ${\text{CWA}}(T_{2})\,$. Is ${\text{CWA}}(T_{2})\,$ consistent? Justify your answer.

Theorie

CWA

Closed-world assumption (CWA) of theory T

${\begin{aligned}T_{asm}&=\{\lnot P\mid P\,\,{\text{ground atom}},\,T\nvDash P\}\\{\text{CWA}}(T)&=\{\varphi \mid T\cup T_{asm}\models \varphi ,\varphi \,{\text{closed}}\}=Cn(T\cup T_{asm})\end{aligned}}$

CWA consistency

CWA consistency theorem

Let $T\,$ be a consistent theory. Then:

${\text{CWA}}(T)\,$ is inconsistent iff there are ground atoms $A_{1},...,A_{n}\,$ such that

$T\models A_{1}\lor ...\lor A_{n}\,$

but $T\nvDash A_{i}\,$, for all $i=1,...,n\,$.

Lösungsvorschlag

Lösungsvorschlag von Thrau

T1

Welche Atome fehlen in der Theorie, und damit für deren Vollständigkeit?

$P(b),P(c),Q(a),R(a),R(b),R(c)\notin T_{1}$

keine von diesen ist aus der Theorie ableitbar (mit Tableau überprüfen)

$T_{1}\vDash P(b)$

$T_{1}\nvDash P(c)$

$T_{1}\nvDash Q(a)$

$T_{1}\nvDash R(a)$

$T_{1}\nvDash R(b)$

$T_{1}\nvDash R(c)$

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

die CWA ist daher:

${\begin{aligned}{\text{CWA}}(T_{1})&={\text{Cn}}(T_{1}\cup T_{1asm})\\&={\text{Cn}}(\{\forall x(P(x)\lor Q(x)),\exists x(P(x)\land \neg Q(x)),P(a),\neg Q(b),Q(c),P(b),\neg P(c),\neg Q(a),\neg R(a),\neg R(b),\neg R(c)\})\end{aligned}}$

ist die CWA konsistent?

nein, denn (siehe Theorem):

${\begin{aligned}T&\models P(b)\lor Q(b)\\T&\nvDash P(b)\\T&\nvDash Q(b)\\\end{aligned}}$

Anmerkung: Auch wenn das Ergebnis richtig ist, spießt es sich mit der Behauptung ${\textstyle T_{1}\vDash P(b)}$. ${\textstyle P(b)}$ ist nicht ableitbar wodurch das Ergebnis auch stimmt. —Zenon 22:12, 13. Sep. 2020 (CEST)

Anmerkung 2: ${\textstyle \neg Q(b),\neg P(b)\rightarrow Q(b)\models P(b)}$. Daher ist ${\textstyle P(b)}$ herleitbar und die Theorie konsistent. —Zenon 23:12, 13. Sep. 2020 (CEST)

T2

selbes spiel

$P(a),P(b),P(c),Q(a),Q(b),Q(c),R(a),R(c)\notin T_{2}$

${\begin{aligned}T_{2}&\vDash P(a)\\T_{2}&\nvDash P(b)\\T_{2}&\nvDash P(c)\\T_{2}&\vDash Q(a)\\T_{2}&\nvDash Q(b)\\T_{2}&\nvDash Q(c)\\T_{2}&\nvDash R(a)\\T_{2}&\nvDash R(c)\\\end{aligned}}$

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

${\begin{aligned}{\text{CWA}}(T_{2})&={\text{Cn}}(T_{2}\cup T_{2asm})\\&={\text{Cn}}(\{\forall x(Q(x)\lor R(x)),\forall x(R(x)\lor P(x)),P(a)\land Q(a),R(b),Q(c)\lor \neg P(c),\neg P(b),\neg P(c),\neg Q(b),\neg Q(c),\neg R(a),\neg R(c),P(a),Q(a)\})\end{aligned}}$

Wichtig: $P(a),Q(a)$ sind über den deduktiven Abschluss Cn dazugekommen!

ist die CWA konsistent?

nein, denn (siehe Theorem):

${\begin{aligned}T&\models Q(c)\lor R(c)\\T&\nvDash Q(c)\\T&\nvDash R(c)\\\end{aligned}}$