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

Logik für Informatiker

Übungsblatt 6

Aufgabe 12 Gegeben sei die Formel

F = (¬∀x_{1}∃x_{2}P_{2}(f_{1}(x_{1}, x_{2}, f_{2}(x_{1}))) ∧ P_{1}(x_{2}, f_{3}))

Man gebe die Matrix von F, sämtliche Teilformeln von F sowie alle in F vorkommenden Terme an und bestimme für jedes Vorkommen einer Variable, ob es frei oder gebunden ist.

Aufgabe 13: Neues von Warlüg Picard und Data finden während ihres Aufenthalts auf Warlüg Folgendes heraus:

1. Eine Person vom Stamm der Xur vermählt sich nur mit jemandem vom Stamm der Xur oder der Yzy, und umgekehrt. Polits vermählen sich nie (weil sie auf eine entscheidende Frage immer mit ”nein“ zu antworten pflegen).

2. Ein Bewohner von Warlüg ist nur dann ein Xur, wenn die Eltern beide Xur oder beide Yzy sind.

Man drücke die Tatsachen 1) und 2) als prädikatenlogische Formeln aus.

Aufgabe 14 Gegeben seien die Formeln

F = ∀x∀y(P (x, y) ⇒ P (x, f(y)))
G = ∀x∀y(P (x, y) ⇒ P (f(x), y))

Man finde ein Modell für F, das nicht Modell für G ist, und ein Modell für G, das nicht Modell für F ist.