Prof. Dr. M. Kreuzer Abgabe: 24.11.2003, 12.15 Uhr Peter Ackermann

Logik für Informatiker

Übungsblatt 6

Aufgabe 13: Seien F, G prädikatenlogische Formeln. Man zeige: Ist α zu F und G passende Struktur, so gilt:

a) Ist α((∀x : F) ∨ (∀x : G)) = 1, so ist auch α(∀x : (F ∨ G)) = 1.

b) Ist α(∃x : (F ∧ G)) = 1, so ist auch α((∃x : F) ∧ (∃x : G)) = 1. Weiter zeige man, dass die Umkehrung nicht gilt.

Aufgabe 14: Man formuliere die folgenden Aussagen über die Bewohner von Transylvanien als prädikatenlogische Formeln und gebe jeweils die passende Struktur an:

1. Alle geisteskranken Vampire sagen die Wahrheit.

2. Ist ein Mensch geistig gesund, so ist mindestens eins seiner Elternteile geistig gesund.

3. Vampire heiraten nur Vampire.

4. Alle geisteskranken Vampire haben mindestens ein Kind.

Aufgabe 15: Gegeben sei die prädikatenlogische Formel

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

a) Bringen Sie F in Matrix-Klausel-Form.

b) Bestimmen Sie den Wahrheitswert für F für die Struktur α = (U, ψ, φ, ξ) mit U = ℤ, ψ(P) = {(x, y) | x > y}, ψ(Q) = Menge aller geraden Zahlen ,

φ(f) : ℤ^{2} → ℤ, φ(f)(x, y) = |x − y|, ξ(x) = ξ(y) = ξ(z) = −1