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

Your boss tells you that any binary relation which is symmetric and transitive is also reflexive. Is he right?

Translate the argument into the symbolism of first-order logic and show by TC1 that the argument is either correct or else extract an interpretation from the tableau showing that the argument is not correct.

Theorie

Symmetrie

Symmetrie

$\forall a,b\in M:aRb\Rightarrow bRa$

Transitivität

Transitivität

$\forall a,b,c\in M:\quad a\circ b\wedge b\circ c\Rightarrow a\circ c$

Reflexivität

Reflexivität

$\forall a\in M:\quad aRa$

Lösungsvorschlag

Übersetzung in PL1:

${\begin{aligned}\phi _{1}&=\forall x\forall y[R(x,y)\rightarrow R(y,x)]\\\phi _{2}&=\forall x\forall y\forall z[(R(x,y)\land R(y,z))\rightarrow R(x,z)]\\\psi &=\forall x[R(x,x)]\end{aligned}}$

Überprüfen sollen wir:

$\phi _{1},\phi _{2}\models \psi$

Übliches Schema

${\begin{aligned}{\text{nnf}}(\phi _{1})&=\forall x\forall y[\neg R(x,y)\lor R(y,x)]\\{\text{nnf}}(\phi _{2})&=\forall x\forall y\forall z[\neg R(x,y)\lor \neg R(y,z)\lor R(x,z)]\\{\text{nnf}}(\neg \psi )&=\neg \forall xR(x,x)\\&=\exists x\neg R(x,x)\end{aligned}}$

1: $\forall x\forall y[\neg R(x,y)\lor R(y,x)]$
2: $\forall x\forall y\forall z[\neg R(x,y)\lor \neg R(y,z)\lor R(x,z)]$
3: $\exists x\neg R(x,x)$
4 (aus 3): $\neg R(a,a)\,$
5 (aus 1): $\forall y[\neg R(a,y)\lor R(y,a)]\,$
6 (aus 5): $\neg R(a,b)\lor R(b,a)\,$
7 (aus 2): $\forall y\forall z[\neg R(a,y)\lor \neg R(y,z)\lor R(a,z)]\,$
8 (aus 7): $\forall z[\neg R(a,b)\lor \neg R(b,z)\lor R(a,z)]\,$
9 (aus 8) $\neg R(a,b)\lor \neg R(b,a)\lor R(a,a)\,$
10 (aus 9): $\neg R(a,b)\,$		11: $\neg R(b,a)\,$		12: $R(a,a)\,$
13 (aus 6): $\neg R(a,b)\,$	14: $R(b,a)\,$	15 (aus 6): $\neg R(a,b)\,$	16:$R(b,a)\,$	* mit 4
	$\Uparrow$	$\Uparrow$	* mit 11

Gegenmodelle $I\nvDash \psi$:

${\begin{aligned}I_{1}(R(b,a))&={\text{t}}\\I_{1}(R(a,b))&={\text{f}}\\I_{1}(R(a,a))&={\text{f}}\end{aligned}}$

${\begin{aligned}I_{2}(R(b,a))&={\text{f}}\\I_{2}(R(a,b))&={\text{f}}\\I_{2}(R(a,a))&={\text{f}}\end{aligned}}$

Es gibt Relationen die transitiv und symmetrisch aber nicht reflexiv sind. Beispielsweise die leere Relation auf eine nicht leere Menge (R(a,b) wird immer falsch) damit gilt offensichtlich:

$R(a,b)\rightarrow R(b,a)$

$R(a,b)\wedge R(b,c)\rightarrow R(a,c)$

weil beide seiten der Implikation immer falsch sind, ist die Implikation jeweils wahr, aber nicht

$R(a,a)\,$

Kommentare

Man verzeihe mir die Faulheit, nicht die richtige einzutragen, aber ich wollte nur darauf hinweisen, dass man, zumindest laut Tutor, beim Allquantor generell schon vorhandene Konstanten benutzt. Was auch Sinn macht, um die Komplexität nicht unnötig zu erhöhen. Tatsächlich ist es sogar falsch, neue einzusetzen, sagte er. Also für unten gilt: Man braucht kein b, nur ein a! Dann clasht es, wenn die Interpretation für alle false ist. Der zweite Clash ergibt sich wohl daraus, dass es falsch ist.

"Tatsächlich ist es sogar falsch, neue einzusetzen, sagte er" bei allquantifizierungen kannst du beliebige terme substituieren, das ist sicher nicht falsch, da hast du eher was falsch verstanden. man kann das tableau sicher auch ohne dem zusätzlich eingeführten b auflösen, aber es ändert am ausgang eigentlich nichts. die lösung ist aus dem TIL skriptum adaptiert und ist mEn nicht falsch. -Thrau (Diskussion) 15:36, 6. Dez. 2012 (CET)