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

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

Aufgabe 1. Welche der folgenden Formeln sind allgemeingültig? (∀v_{0}(K(v_{0}) → ∃v_{1}(F (v_{1}) ∧ B(v_{0}, v_{1}))) → (∀v_{0}(F (v_{0}) → ∃v_{1}(K(v_{1}) ∧ B(v_{1}, v_{0})))) (∀v_{0}∀v_{1}(B(v_{0}, v_{1}) → B(v_{0}, g(v_{1})))) → (∀v_{1}(B(v_{2}, v_{1}) → B(v_{2}, g(g(v_{1}))))) Begründen Sie jeweils Ihre Antwort.

Aufgabe 2. a) Sind die Formeln

φ = (∃xP (x) ∨ R(x, y)) und ψ = ∃x(P (x) ∨ R(x, y))

logisch äquivalent? Falls nicht, gilt φ ⊧ ψ oder gilt ψ ⊧ φ?

b) Gibt es zu ∃xP (x) eine logisch äquivalente universelle Aussage?

Aufgabe 3. Bringen Sie die folgende Formel zunächst in pränexe Normalform und anschließend in Skolem-Normalform:

∀v_{1}((F (v_{1}) ∧ ∃v_{2}(K(v_{2}) ∧ B(v_{2}, v_{1}))) → ∃v_{2}(K(v_{2}) ∧ ¬B(v_{2}, v_{1})))

Aufgabe 4. Sei L eine Sprache. Zeigen Sie, daß es keine Theorie T gibt, deren Modelle genau die endlichen L-Strukturen sind. Hinweis: Verwenden Sie den Kompaktheitssatz.