Logik:Klausuren/20.02.2002/B.8 Aufgabe

1. Aufgabenstellung

Betrachten Sie das folgende definite Programm $ \mathcal{P} $, wobei $ a,\ b $ Konstantensymbole, $ X\ $ eine Variable und $ p,\ q $ einstellige Relationssymbole sind:

$ \begin{matrix}q(X)&\leftarrow & \\ \ p(a) & \leftarrow & p(a) \\ \ p(b)& \leftarrow & q(X) \\ \ p(s(X)) & \leftarrow & p(X) \end{matrix} $

a) Es sei $ I_0 = \left\{p(a)\right\} $ und $ I_n+1 = T_\mathcal {P} (I_n ) $ für alle $ n \in \mathbb{N} . $ Berechnen Sie $ I_n\ $ für alle $ n \in \mathbb{N} . $

b) Zeigen Sie, dass $ \cup_{n \in \mathbb{N}} I_n $ nicht das kleinste Herbrand-Modell von $ \mathcal{P} $ ist.

3. Lösungsweg

a)

$ I_1 = T_P(I_0) = \{p(a), p(s(a)), q(X) | X \in \mathcal{U}\} $

$ I_2 = T_P(I_1) = \{p(a), p(s(a)), p(s(s(a)), p(b), q(X) | X \in \mathcal{U}\} $

$ I_3 = T_P(I_2) = \{p(a), p(s(a)), p(s(s(s(a)))), p(b), p(s(a)), q(X) | X \in \mathcal{U}\} $

$ I_n = T_P(I_{n-1}) = \{p(s^n(a)), p(s^{n-2}(a)), q(X) | X \in \mathcal{U}, n \ge 2\} $

b)

$ T_P(\emptyset) = \{ q(X) | X \in \mathcal{U}\} = I_1' $

$ T_P(I_1') = \{ q(X), p(b) | X \in \mathcal{U}\} = I_2' $

$ T_P(I_2') = \{ q(X), p(b), p(s(b)) | X \in \mathcal{U}\} = I_3' $

$ I_n' = \{ q(X), p(s^{n - 2}(b)) | X \in \mathcal{U}, n \ge 2\} $

$ I_n' \subseteq I_n $

damit ist es nicht das kleinste Herbrandmodell

4. Alternativen/Diskussion/Hinweise etc.

---

zur Klausur 20.02.2002