Logik:Klausuren/20.02.2002/B.5 Aufgabe
Inhaltsverzeichnis
1. Aufgabenstellung
Seien $ X,\ Y,\ Z $ Variable, $ a\ $ ein Konstantensymbol, $ t\ $ ein Term, $ f\ $ ein zweistelliges und $ g\ $ ein einstelliges Funktionssymbol. Gegeben seien die Substitutionen
$ \sigma = {X \rightarrow Y,\ Y \rightarrow f(X,\ a)} $
und
$ \theta = {X \rightarrow g(Y), Z \rightarrow a}. $
a) Bestimmen Sie die Kompositionen $ \sigma\theta\ $ und $ \theta\sigma\ . $
b) Kann $ \sigma $ die Lösung eines lösbaren Unifikationsproblemes $ \left\{ X \approx t\right\} $ mit $ X \neq t $ sein?
$ ja \ \ \Box \qquad \qquad nein \ \ \Box $
Beweisen Sie Ihre Antwort.
c) Eine Substitution $ \lambda $ heisst idempotent, wenn $ \lambda\lambda = \lambda $ gilt. Sind alle Substitutionen
idempotent?
$ ja \ \ \Box \qquad \qquad nein \ \ \Box $
Beweisen Sie Ihre Antwort.
2. Lösung
3. Lösungsweg
a)
$ \sigma\theta = \{ X \mapsto Y, Y \mapsto f(g(Y), a), Z \mapsto a\} $
$ \theta\sigma = \{ X \mapsto g(f(X, a)), Z \mapsto a, Y \mapsto f(X, a)\} $
b) Nein, da $ \sigma $ kein allgemeinster Unifikator ist.
c) Nein. Gegenbeispiel.
$ \lambda = \{ X \mapsto f(X)\} $
$ \lambda\lambda = \{ X \mapsto f(f(X)) \} \quad\not =\quad \lambda $
