Prof. Dr. M. Kreuzer Abgabe: 13.12.2002, 14h

Logik für Informatiker

Übungsblatt 9

Aufgabe 20: Ward ihr auch alle artig? Es ist allgemein bekannt, dass der Weihnachtsmann jede Familie besucht, in der alle Kinder artig sind. Nicht so bekannt ist, dass er auch alle kinderlosen Familien besucht, obwohl dies eine Folgerung der ersten Regel ist. Man zeige dies durch Grundresolution, nachdem man die beiden Aussagen als prädikatenlogische Formeln ausgedrückt hat.

Aufgabe 21 Man finde einen Beweis dafür, dass aus der prädikatenlogischen Formel

F = ∀x : ∀y : ∀z : ((P (f(x), x) ∨ Q(x)) ∧ ¬R(f(y)) ∧ (¬P (z, y) ∨ ¬R(y) ∨ R(z)))

folgt ∀w : (R(w) ⇒ Q(w)).

Aufgabe 22 Man wende den Unifikationsalgorithmus an auf die Literalmenge

L = {P (x, y, f(g(z))), P (w, f(a), f(x)), P (w, f(z), f(w))}