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

Logikbasierte Wissensrepräsentation:

Teilaufgabe a)

Sei $R$ ein zweistelliges Prädikatensymbol und $S^{*}$ jene Klasse von Interpretationen $I$ für die gilt, dass es für jedes $x\in U$ ein $y\in U$ gibt mit $xI(R)y$, wobei $U$ die Domäne von $I$ ist.

Sei $T=\{\forall x\forall y(R(x,y)\rightarrow R(y,x)),\forall x\forall y\forall z(R(x,y)\wedge R(y,z)\rightarrow R(x,z))\}$ und $I\in S^{*}$. Zeigen Sie, dass $I\models \forall xR(x,x)$ aus $I\models T$ folgt. (4.5 Punkte)

Lösungsvorschlag (Exkalation (Diskussion) 19:33, 18. Jan. 2015 (CET)):
Proof by Contradiction:
Angenommen $I\models \forall xR(x,x)$ folgt nicht aus $I\models T$, wobei $I\in S^{*}$ und $U$ Domäne von $I$,
d.h. $I\models \not \forall xR(x,x)$ folgt aus $I\models T$.

Gegenbeispiel:
Angenommen $U=\{a\}$, dann gilt nach Definition von $T$: $\forall x\forall y(R(x,y)\rightarrow R(y,x))$, d.h. für unser $U$:
$R(a,a)\rightarrow R(a,a)$.
Da laut Definition von $S^{*}$ TODO...

Lösungsvorschlag Schogglomat (Diskussion) 23:27, 19. Jan. 2015 (CET)

1. $I\models \forall x\forall y(R(x,y)\rightarrow R(y,x))$ (Annahme)
2. $I\models \forall x\forall y\forall z(R(x,y)\land R(y,z)\rightarrow R(x,z))$ (Annahme)
3. $I\models \forall x\exists yR(x,y)$ (Annahme, weil $I\in S^{*}$)
4. 1. Sei $c\in {\mathcal {U}}$ beliebig.
   2. $I_{x\leftarrow c}\models \exists yR(c,y)$ (folgt aus 3. und 4.1.)
   3. Wähle $d\in {\mathcal {U}}$ so dass $I_{x\leftarrow c,y\leftarrow d}\models R(c,d)$
   4. $I_{x\leftarrow c,y\leftarrow d}\models R(d,c)$ (folgt aus 1. und 4.3.)
   5. $I_{x\leftarrow c,y\leftarrow d}\models R(c,c)$ (folgt aus 2, 4.3. und 4.4.)
5. $I\models \forall xR(x,x)$ (QED, folgt aus 4.1 bis 4.5)

Lösungsvorschlag Tyleet
Auch in TC1 möglich, da ja nicht semantischer Beweis gefordert wird:

1 $\forall x\forall y(\neg R(x,y)\vee R(y,x))$ (Aus T)
2 $\forall x\forall y\forall z(\neg R(x,y)\vee \neg R(y,z)\vee R(x,z))$ (Aus T)
3 $\forall x\exists yR(x,y)$ (Aus xI(R)y in der Angabe)
4 $\exists x\neg R(x,x)$ (negierte form von $\forall xR(x,x)$
5 $\neg R(a,a)$ (Aus 4)
6 $\exists yR(a,y)$ (Aus 3)
7 $R(a,b)$ (Aus 6)
8 $\neg R(a,b)\vee R(b,a)$ (Aus 1)
9 $\neg R(a,b)\vee \neg R(b,a)\vee R(a,a)$ (Aus 2)
10 $\neg R(a,b)$(Aus 8)	11 $R(b,a)$ (Aus 8)
clash mit 7	12 $\neg R(a,b)$ (Aus 9)	13 $\neg R(b,a)\vee R(a,a)$ (Aus 9)
	clash mit 7	14 $\neg R(b,a)$(Aus 13)	15 $R(a,a)$ (Aus 13)
		clash mit 11	clash mit 5

Teilaufgabe b)

Sei $S^{*}$ wie zuvor. Finden Sie eine Wissensbasis $T'$, sodass für jede Interpretation $I$ gilt

$I\models T'\iff I\not \in S^{*}$

(1 Punkt)

Lösungsvorschlag (Exkalation (Diskussion) 19:13, 18. Jan. 2015 (CET)):
Es solle reichen einen Widerspruch zur Definition der I in S* zu schaffen:
$T'=\{\forall x\not \exists y(R(x,y)\}$

Teilaufgabe c)

Kreuzen Sie Zutreffendes an:

Welche der folgenden Eigenschaften treffen für obige Theorie $T$ zu?

1. Eine Formel $\varphi$ folgt logisch aus einer Wissensbasis $T$ genau dann wenn
   • $\forall I:I\models T\implies I\models \varphi$ richtig ☐ falsch ☐
   • $\forall I:I\models T$ and $I\models \varphi$ richtig ☐ falsch ☐
   • $\neg \exists I:I\models T$ and $I\not \models \varphi$ richtig ☐ falsch ☐
2. Eine Formel ist genau dann erfüllbar wenn ihre Negation nicht gültig ist. richtig ☐ falsch ☐
3. Ist $\varphi$ unerfüllbar, so ist $\forall x(\varphi \rightarrow \psi )$ gültig für bleliebiges $\psi$. richtig ☐ falsch ☐
4. Ist $\forall x(\varphi \rightarrow \psi )$ gültig, so ist $\varphi$ erfüllbar. richtig ☐ falsch ☐
5. Sei $\varphi (x)$ eine Formel mit einer freien Variable $x$. Ist $\forall x(\varphi (x)\rightarrow \bot )$ gültig, dann ist $\exists x\varphi (x)$ erfüllbar. richtig ☐ falsch ☐
6. Um die Gültigkeit einer Formel der Form $\varphi \rightarrow \psi$ in TC1 zu zeigen, betrachten wir die Formel $\varphi \wedge \neg \psi$. Falls $\not \models \varphi \rightarrow \psi$ gilt, so gibt es ein geschlossenes Tableau für $\varphi \wedge \neg \psi$ und somit ist $\varphi \rightarrow \psi$ gültig. richtig ☐ falsch ☐

(4 Punkte)

Lösungsvorschlag Exkalation (Diskussion) 23:44, 23. Jan. 2015 (CET):
1. Nicht absolut sicher, aber relativ überzeugt:
1.a) richtig
1.b) falsch
1.c) richtig (meiner Meinung equivalent zu 1.a)
2. richtig
3. richtig
4. falsch
5. falsch
6. falsch

Teilaufgabe d)

Sei $T$ eine Menge von aussagenlogischen Formeln. Man zeige bzw. widerlege, dass $T\models \bot$ genau dann wenn $T\models \varphi$ für alle Formeln $\varphi$. (3 Punkte)

Lösung Informatikforum: https://web.archive.org/web/*/informatik-forum.at/showthread.php?107778-Pr%FCfungsangabe-2014-01-29-Beispiel-1d&p=831508&viewfull=1#post831508