Logik:Klausuren/20.02.2002/B.8 Aufgabe
Inhaltsverzeichnis
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.
2. Lösung
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
