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^{\ast }$ 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=\{\mathrm{\forall }x\mathrm{\forall }y(R(x,y)\to R(y,x)),\mathrm{\forall }x\mathrm{\forall }y\mathrm{\forall }z(R(x,y)\wedge R(y,z)\to R(x,z))\}$ und $I\in S^{\ast }$. Zeigen Sie, dass $I\models \mathrm{\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 \mathrm{\forall }xR(x,x)$ folgt nicht aus $I\models T$, wobei $I\in S^{\ast }$ und $U$ Domäne von $I$,
d.h. $I\models \mathrm{\forall }xR(x,x)$ folgt aus $I\models T$.

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

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

1. $I\models \mathrm{\forall }x\mathrm{\forall }y(R(x,y)\to R(y,x))$ (Annahme)
2. $I\models \mathrm{\forall }x\mathrm{\forall }y\mathrm{\forall }z(R(x,y)\wedge R(y,z)\to R(x,z))$ (Annahme)
3. $I\models \mathrm{\forall }x\mathrm{\exists }yR(x,y)$ (Annahme, weil $I\in S^{\ast }$)
4. 1. Sei $c\in 𝒰$ beliebig.
   2. $I_{x\leftarrow c}\models \mathrm{\exists }yR(c,y)$ (folgt aus 3. und 4.1.)
   3. Wähle $d\in 𝒰$ 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 \mathrm{\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 $\mathrm{\forall }x\mathrm{\forall }y(\mathrm{\neg }R(x,y)\vee R(y,x))$ (Aus T)
2 $\mathrm{\forall }x\mathrm{\forall }y\mathrm{\forall }z(\mathrm{\neg }R(x,y)\vee \mathrm{\neg }R(y,z)\vee R(x,z))$ (Aus T)
3 $\mathrm{\forall }x\mathrm{\exists }yR(x,y)$ (Aus xI(R)y in der Angabe)
4 $\mathrm{\exists }x\mathrm{\neg }R(x,x)$ (negierte form von $\mathrm{\forall }xR(x,x)$
5 $\mathrm{\neg }R(a,a)$ (Aus 4)
6 $\mathrm{\exists }yR(a,y)$ (Aus 3)
7 $R(a,b)$ (Aus 6)
8 $\mathrm{\neg }R(a,b)\vee R(b,a)$ (Aus 1)
9 $\mathrm{\neg }R(a,b)\vee \mathrm{\neg }R(b,a)\vee R(a,a)$ (Aus 2)
10 $\mathrm{\neg }R(a,b)$(Aus 8)	11 $R(b,a)$ (Aus 8)
clash mit 7	12 $\mathrm{\neg }R(a,b)$ (Aus 9)	13 $\mathrm{\neg }R(b,a)\vee R(a,a)$ (Aus 9)
	clash mit 7	14 $\mathrm{\neg }R(b,a)$(Aus 13)	15 $R(a,a)$ (Aus 13)
		clash mit 11	clash mit 5

Teilaufgabe b)

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

$I\models T^{\prime }⟺I\in ̸S^{\ast }$

(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^{\prime }=\{\mathrm{\forall }x\mathrm{\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 $\phi$ folgt logisch aus einer Wissensbasis $T$ genau dann wenn
   • $\mathrm{\forall }I:I\models T⟹I\models \phi$ richtig ☐ falsch ☐
   • $\mathrm{\forall }I:I\models T$ and $I\models \phi$ richtig ☐ falsch ☐
   • $\mathrm{\neg }\mathrm{\exists }I:I\models T$ and $I\models ̸\phi$ richtig ☐ falsch ☐
2. Eine Formel ist genau dann erfüllbar wenn ihre Negation nicht gültig ist. richtig ☐ falsch ☐
3. Ist $\phi$ unerfüllbar, so ist $\mathrm{\forall }x(\phi \to \psi )$ gültig für bleliebiges $\psi$. richtig ☐ falsch ☐
4. Ist $\mathrm{\forall }x(\phi \to \psi )$ gültig, so ist $\phi$ erfüllbar. richtig ☐ falsch ☐
5. Sei $\phi (x)$ eine Formel mit einer freien Variable $x$. Ist $\mathrm{\forall }x(\phi (x)\to \mathrm{\perp })$ gültig, dann ist $\mathrm{\exists }x\phi (x)$ erfüllbar. richtig ☐ falsch ☐
6. Um die Gültigkeit einer Formel der Form $\phi \to \psi$ in TC1 zu zeigen, betrachten wir die Formel $\phi \wedge \mathrm{\neg }\psi$. Falls $\models ̸\phi \to \psi$ gilt, so gibt es ein geschlossenes Tableau für $\phi \wedge \mathrm{\neg }\psi$ und somit ist $\phi \to \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 \mathrm{\perp }$ genau dann wenn $T\models \phi$ für alle Formeln $\phi$. (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