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

Logikbasierte Wissensrepräsentation

Teilaufgabe a)

Es sei $T$ eine Menge von aussagenlogischen Formeln. Wir definieren eine Folge $(T{\text{'}}_i{)}_{i\ge 0}$ von Mengen von aussagenlogischen Formeln rekursiv wie folgt:

$T{\text{'}}_0=T$,

$T{\text{'}}_{i+1}=T{\text{'}}_i\cup \{\psi |\{\mathrm{\neg }\phi \vee \psi ,\phi \}\subseteq T{\text{'}}_i\}$ mit $i\ge 0$.

Wir definieren den Abschluss $Cl(T)$ von $T$ wie folgt:

$Cl(T):={\cup }_{i\ge 0}T{\text{'}}_i$

Man zeige, dass

$\phi \in Cl(T)⟹T\models \phi$

für alle Formeln $\phi$ gilt.

(Hinweis: So eine ähnliche Aufgabe haben Sie in der zweiten Übung gesehen.) (4.5 Punkte)

Lösungsvorschlag von --JasonLeroy (Diskussion) 19:48, 26. Jan. 2015 (CET)

Wenn das $\phi \in Cl(T)$, dann stammt es aus einem $T{\text{'}}_i$.

Fall 1: Es stammt aus $T{\text{'}}_0$. Nachdem $T{\text{'}}_0=T$ stammt $\phi$ also aus $T$ und damit gilt klarerweise $T\models \phi$.

Fall 2: Es stammt aus einem anderen $T{\text{'}}_{i+1}$. Damit stammt es entweder aus $T{\text{'}}_i$ oder aus $\{\psi |\{\mathrm{\neg }\phi \vee \psi ,\phi \}\subseteq T{\text{'}}_i\}$. D.h. zu beweisen ist nur, dass $T{\text{'}}_i\models \psi$ mit $\{\mathrm{\neg }\phi \vee \psi ,\phi \}\subseteq T{\text{'}}_i$. Also eigentlich, dass $\psi$ aus $\{\mathrm{\neg }\phi \vee \psi ,\phi \}$ folgt.

Die Aussage $\{\mathrm{\neg }\phi \vee \psi ,\phi \}\models \psi$ ist nur falsch, wenn

1. $I\models \mathrm{\neg }\phi \vee \psi$
2. $I\models \phi$
3. $I\models ̸\psi$

Die erste Zeile ist gültig, wenn $I\models \mathrm{\neg }\phi$ oder $I\models \psi$. Ersteres steht mit Punkt 2 in Widerspruch, letzteres mit Punkt 3.

Teilaufgabe b)

Betrachten Sie die folgende Wissensbasis

$T=\{\mathrm{\forall }x\mathrm{\exists }yR(x,y),\mathrm{\forall }x\mathrm{\neg }R(x,x),\mathrm{\forall }x\mathrm{\forall }y\mathrm{\forall }z(R(x,y)\wedge R(y,z)\to R(x,z))\}$.

(i) Geben Sie ein Modell für $T$ an. Achten Sie auf die korrekte formale Darstellung. (2 Punkte)

(ii) Hat $T$ ein Modell mit endlicher Domäne? Wenn ja, geben Sie eines an, wenn nein, warum nicht? (Sie brauchen keinen Beweis angeben, geben Sie aber eine schlüssige Erklärung.) (2 Punkte)

(iii) Geben Sie ein $\phi$ an, sodass $T\models \phi$, jedoch weder $\phi \in T$ noch $\models \phi$. Beweisen Sie ferner, warum $T\models \phi$ gilt. (1 Punkt)

Lösungsvorschlag von --JasonLeroy (Diskussion) 20:17, 26. Jan. 2015 (CET)

(i) $𝒰=\mathbb{N}$, $I(R)=\{(a,b)\}$ für alle $a,b\in \mathbb{N}$ mit $a<b$

(ii) Nein, da für jedes $x$ ein $y$ in der Domäne existieren muss für die $R(x,y)$ gilt. Wäre die Domäne endlich, würde ein Kreis entstehen (auch das letzte Element braucht einen Nachfolger), doch damit wäre $R(x,x)$ für zumindest ein $x$ ableitbar, was der zweiten Formel widerspricht.

(iii) Anm: Meine Lösung ist falsch. Ich dachte vorher, man könnte daraus schon $\phi =\mathrm{\exists }x\mathrm{\neg }\mathrm{\exists }yR(y,x)$ ableiten, also es gibt ein Element, das keinen Vorgänger hat. Doch mein Beweis war nicht ganz korrekt, wie Tyleet korrekterweise festgestellt hat. Der Beweis kann auch gar nicht funktionieren, da man dies nicht aus der Theorie ableiten kann: Angenommen unsere Domäne ist $\mathbb{Z}$, dann gibt es kein Element, dass keinen Vorgänger hat.

Neuer Lösungsvorschlag: $\mathrm{\forall }w\mathrm{\forall }x\mathrm{\forall }y\mathrm{\forall }z(R(w,x)\wedge R(x,y)\wedge R(y,z)\to R(w,z))$

Lösungsvorschlang von Tyleet

(iii) $\phi =\mathrm{\forall }x\mathrm{\forall }y(R(x,y)\vee \mathrm{\neg }R(y,x))$ TC1 dazu würde dann wie folgt aussehen:

1 $\mathrm{\forall }x\mathrm{\exists }yR(x,y)$

2 $\mathrm{\forall }x\mathrm{\neg }R(x,x)$

3 $\mathrm{\forall }x\mathrm{\forall }y\mathrm{\forall }z(\mathrm{\neg }R(x,y)\vee \mathrm{\neg }R(y,z)\vee R(x,z)$

4 $\mathrm{\exists }x\mathrm{\exists }y(\mathrm{\neg }R(x,y)\wedge R(y,x))$

5 $R(a,b)$ (Aus 1)

6 $\mathrm{\neg }R(a,b)\wedge R(b,a)$ (Aus 4)

7 $\mathrm{\neg }R(a,b)$ (Aus 6)

CLASH (5/7)

Teilaufgabe c)

1. Für jede konsistente Wissensbasis $T$ und geschlossene Formel $\phi$ gilt entweder $T\models \phi$ oder $T\models \mathrm{\neg }\phi$, jedoch nicht beides. ☐ wahr ☐ falsch
2. $\mathrm{\forall }x(P(x)\vee Q(x))\models \mathrm{\forall }xP(x)\vee \mathrm{\forall }xQ(x)$ ☐ wahr ☐ falsch
3. Eine Wissensbasis $T$ ist genau dann konsistent, wenn $T\models ̸\mathrm{\forall }x\phi$ für ein $\phi$. ☐ wahr ☐ falsch
4. $(\mathrm{\exists }xP(x))\to \phi \models \mathrm{\forall }x(P(x)\to \phi )$ falls $x$ in $\phi$ nicht frei vorkommt. ☐ wahr ☐ falsch
5. $\models \phi \to \psi ⟺\mathrm{\forall }I:I\models \phi$ und $I\models \psi .$ ☐ wahr ☐ falsch
6. Falls $\models \psi$ und $\models ̸\psi \to \phi$, dann $\models ̸\phi$. ☐ wahr ☐ falsch

(3 Punkte)

Lösungsvorschlag von --JasonLeroy (Diskussion) 18:11, 26. Jan. 2015 (CET)

1. ☐ wahr ☒ falsch
2. ☐ wahr ☒ falsch
3. ☒ wahr ☐ falsch
4. ☒ wahr ☐ falsch
5. ☐ wahr ☒ falsch
6. ☒ wahr ☐ falsch