Logik:Klausuren/28.02.2001/A.5 Aufgabe
Inhaltsverzeichnis
1. Aufgabenstellung
Seien $ a, b\; $ und $ c\; $ Konstanten, $ f\; $ und $ g\; $ einstellige Funktionssymbole sowie $ p, q\; $ Relations- symbole. Gegeben seien die folgenden Substitutionen:
$ \sigma_1 = \{X \mapsto Z, Y \mapsto f(Z)\} \; $<br\> $ \sigma_2 = \{X \mapsto f(Y )\} \; $<br\> $ \sigma_3 = \{X \mapsto a, Y \mapsto f(a), Z \mapsto a\} \; $<br\> $ \sigma_4 = \{X \mapsto f(Y ), Y \mapsto g(Z), W \mapsto V \} \; $<br\> $ \sigma_5 = \{X \mapsto a, Y \mapsto b, Z \mapsto f(Y), V \mapsto W, U \mapsto c\} \; $<br\>
a) Bestimmen Sie die Komposition $ (\sigma_4 \sigma_5) \sigma_2\; $
b) Bestimmen Sie $ S\sigma_5\; $ für $ S = ((\forall Z)(p(a,f(X, g(Y))) \and (\forall Y ) q(Y,Z,b))\and \neg (\exists X)p(Y,X))\; $.
c) Die binäre Relation �$ \ge\; $ über Substitutionen ist folgendermassen definiert:
$ \sigma_1 \ge \sigma_2\; $
gilt genau dann, wenn es eine Substitution $ \lambda\; $ gibt, so dass $ \sigma_1\lambda \ge \sigma_2\; $ . Welche der nachfolgend angegebenen Beziehungen gelten? Kreuzen Sie die jeweils zutreffende Spalte an.
| Beziehung gilt | Beziehung gilt nicht | |
| $ \sigma_1 \ge \sigma_2\; $ | ||
| $ \sigma_2 \ge \sigma_3\; $ | ||
| $ \sigma_1 \ge \sigma_3\; $ | ||
| $ \sigma_2 \ge \sigma_1\; $ |
d) Beweisen Sie, dass die Relation $ \ge\; $ transitiv ist, d.h. wenn für Substitutionen � $ \sigma_1, \sigma_2,\sigma_3\; $3 die Beziehung $ \sigma_1 \ge \sigma_2\; $ und $ \sigma_2 \ge \sigma_3\; $ gilt, dann gilt auch $ \sigma_1 \ge \sigma_3\; $.
