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

Logikbasierte Wissensrepräsentation

Thread im Informatik-Forum

Teilaufgabe a)

Definieren Sie den Begriff einer first-order Interpretation. Gegeben eine Interpretation I, definieren Sie, wann $I\models \phi$ gilt, wobei $\phi$ beliebig ist.

Lösungsvorschlag von --JasonLeroy (Diskussion) 22:25, 25. Jan. 2015 (CET)

Eine first-order interpretation besteht aus einer Domäne $U$ und einer Interpretations-Funktion $I(.)$.

Die Funktion muss folgende Bedingungen erfüllen:

• Für jedes Konstantensymbol $c\in Func$: $I(c)\in U$
• Für jedes Funktionssymbol $f\in Func(n>0)$: $I(f):U^n\mapsto U$
• Für jedes Prädikatensymbol $p\in Pred$: $I(p)\subseteq U^n$

Dadurch dass $\phi$ beliebig sein kann, könnte $\phi$ auch freie Variablen enthalten. Möglicherweise muss das mit $I_{\alpha }(t)$ auch noch definiert werden.

• $I\models \phi$ iff $I(\phi )=1$
• ... (Aufzählung von Seite 29 in pl1.pdf)

Teilaufgabe b)

(i) Zeigen oder widerlegen Sie durch semantische Argumente (kein TC1!), dass die Formel $\mathrm{\exists }x(P(x)\to P(f(x)))$ eine Tautologie ist.

(ii) Unter Zuhilfenahme von (i) zeige oder widerlege man, dass

$\models \mathrm{\exists }x\phi (x)⟹\mathrm{\exists }t:t$ closed and $\models \phi (t)$.

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

(i)

Angenommen es gibt eine Interpretation unter der die Formel falsch ist (also angenommen, die Formel ist keine Tautologie). Dann ist $P(x)\to P(f(x))$ falsch für alle x. $\to$ wird nur falsch, wenn die linke Seite wahr und die rechte falsch ist. In unserer Interpretation muss also gelten

$\mathrm{\forall }x(P(x)\wedge \mathrm{\neg }P(f(x)))$

Das gilt genau dann wenn $I_{\alpha \cup \{x\leftarrow c\}}(P)=1$ und $I_{\alpha \cup \{x\leftarrow c\}}(P(f))=0$ für alle $c\in U$

(a) $I_{\alpha \cup \{x\leftarrow c\}}(P)=1$ für alle $c\in U$ gilt gdw. $u\in I(P)$ für alle $u\in U$ gilt.

(b) $I_{\alpha \cup \{x\leftarrow c\}}(P(f))=0$ für alle $c\in U$ gilt gdw. $f(u)\in ̸I(P)$ für alle $u\in U$ gilt.

Nachdem aber jedes $f(u)$ durch $I(f):U\mapsto U$ auf ein $u\in U$ abgebildet wird, und wegen (a) bereits alle $u\in I(P)$ sein müssen, kann (b) nicht erfüllt werden. Wir haben also einen Widerspruch und somit ist gezeigt, dass die Formel aus der Angabe eine Tautologie ist.

(ii)

Die Formel besagt folgendes: Wenn $\phi$ eine Formel ist, sodass $\models \mathrm{\exists }x\phi (x)$, dann gibt es ein $t$, das geschlossen ist - also keine freien Variablen enthält - und $\phi (t)$ immer wahr werden lässt.

Wir haben bereits bewiesen, dass die Formel aus (i) eine Formel ist, für die $\models \mathrm{\exists }x\phi (x)$ gilt. Wenn wir zeigen können, dass es für diese Formel kein $t$ gibt, das den genannten Voraussetzungen entspricht, haben wir die Implikation bewiesen.

Nachdem hier $t$ geschlossen sein soll und es als Parameter für eine Formel verwendet wird, nehme ich an, $t$ muss ein Ground-Term sein. Die einzige Funktion in $Func$ ist in unserem Fall $f/1$. Nachdem diese einen Parameter erfordert, wir aber keine Konstantensymbole haben, haben wir keine Terme:

$GroundTerms(\Sigma ,Var)=\{\}$

Womit die Implikation aus der Angabe wiederlegt ist, denn ohne Ground-Terme kann es kein geschlossenes $t$ geben.

Anmerkung: Wenn man von einem leeren Universum ausgeht (Was wir in der Vorlesung nicht tun, ist in den Folien definiert) ist jede Existenzquantifizierung nicht erfüllt, womit (i) automatisch keine Tautologie wäre. Hier aber eher als ein Fehler in der Angabe als der Lösung zu werten. Für (ii) können wir den Fall aber nicht verwenden da dann der Quantor in der ersten formel nie wahr und die implikation damit immer erfüllt wäre. Bleibt also nur der fall für ein Universum in dem es GroundTerms gibt um sie zu wiederlegen, in dem es aber auch erfüllt ist.

Teilaufgabe c)

1. Wenn $\models \phi \vee \psi$, dann $\models \phi$ oder $\models \psi$. ☐ wahr ☐ falsch
2. $\models \mathrm{\exists }x(P(x)\wedge Q(x))\leftrightarrow (\mathrm{\exists }xP(x))\wedge (\mathrm{\exists }xQ(x))$ ☐ wahr ☐ falsch
3. Eine Wissensbasis welche aus Formeln besteht, welche nur aus $\vee ,\wedge$, propositionalen Variablen und $\mathrm{\top }$ bestehen, kann nicht inkonsistent sein. ☐ wahr ☐ falsch
4. $\mathrm{\forall }x(P(x)\to \phi )\models (\mathrm{\exists }xP(x))\to \phi$ falls x in $\phi$ nicht frei vorkommt. ☐ wahr ☐ falsch
5. $\models \phi \to \psi \vee \chi ⟺\mathrm{\exists }I:I\models \phi$ und $I\models ̸\psi$ und $I\models ̸\chi$. ☐ wahr ☐ falsch
6. Für jede Formel $\phi (x)$ und jede Interpretation $I$ gilt entweder $I\models \phi (x)$ oder $I\models \mathrm{\neg }\phi (x)$. ☐ wahr ☐ falsch

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

1. wahr ☐ falsch ☒ Beispiel: $\phi =p,\psi =\mathrm{\neg }p$
2. wahr ☐ falsch ☒ Beispiel: $U=\{a,b\},I(P)=\{a\},I(Q)=\{b\}$
3. wahr ☒ falsch ☐
4. wahr ☒ falsch ☐
5. wahr ☒ falsch ☐
6. wahr ☒ falsch ☐