Logik:Klausuren/20.02.2002/B.5 Aufgabe

Aus Tudwiki
Wechseln zu: Navigation, Suche

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 $

4. Alternativen/Diskussion/Hinweise etc.


zur Klausur 20.02.2002