Logik:Klausuren/20.02.2002/B.5 Aufgabe: Unterschied zwischen den Versionen

Aktuelle Version vom 21. Februar 2005, 22:09 Uhr

1. Aufgabenstellung[Bearbeiten]

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[Bearbeiten]

3. Lösungsweg[Bearbeiten]

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.[Bearbeiten]

zur Klausur 20.02.2002