Übungen zur Vorlesung Logik für Informatiker WS 2008/09, Blatt 10

Abgabe: Mittwoch, 21. Januar 2009, vor der Vorlesung Schreiben Sie bitte den Namen Ihres Tutors auf Ihr Lösungsblatt!

Aufgabe 1. Gegeben sei die Sprache L = {P, f, c}, wobei P ein dreistelliges Relationszeichen, f ein einstelliges Funktionszeichen, sowie c ein Konstantenzeichen ist. Zeigen Sie unter Zuhilfenahme des Satzes von Herbrand, daß die Aussage

∃y∃x∃z (¬P (c, x, z) ∨ P (y, f(x), z))

allgemeingültig ist. Aufgabe 2. Bestimmen Sie für die folgenden Formeln jeweils eine äquivalente pränexe Normalform, eine Skolem-Normalform sowie eine Herbrand-Normalform.

a) ∀v_{1}(∃v_{2}B(v_{1}, v_{2}) ∧ ∃v_{2}B(v_{2}, v_{1}))

b) ∃v_{1}¬∃v_{2}B(v_{2}, v_{1})

c) ∀v_{1}∀v_{3}(B(v_{1}, v_{3}) → ∃v_{2}(B(v_{1}, v_{2}) ∧ B(v_{2}, v_{3})))

d) ∀v_{1}∃v_{3}(B(v_{1}, v_{3}) ∧ ¬∃v_{2}(B(v_{1}, v_{2}) ∧ B(v_{2}, v_{3})))

Aufgabe 3. Entscheiden Sie, ob folgende Termfolgen unifizierbar sind. Geben Sie gegebenenfalls eine universelle unifizierbare Termfolge an.

a) S^{1} = (g(f(x), f(y)), c) und S^{2} = (f(g(x, y)), z)

b) S^{1} = (g(f(x), g(x, u)), y) und S^{2} = (g(z, v), f(w))

c) S^{1} = g(x, g(f(c), g(y, z))) und S^{2} = g(g(g(u, v), f(w)), g(f(c), x))

Aufgabe 4. Sei φ(x) eine L-Formel. Für jedes n ∈ ℕ gebe es eine L-Struktur A mit A ⊧ ∃^{≥n}xφ(x) und A ⊧ ∃^{≥n}x¬φ(x). Folgern Sie, daß es eine L-Struktur A gibt mit der Eigenschaft, daß sowohl {a ∈ A | A ⊧ φ[a]} als auch {a ∈ A | A ⊧ ¬φ[a]} unendlich sind.