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

Logik für Informatiker

Übungsblatt 7

Aufgabe 15 Man zeige, dass für alle prädikatenlogische Formeln F und G gilt:

a) ¬(∀x : F) ≡ ∃x : ¬F

b) ¬(∃x : F) ≡ ∀x : ¬F

c) (∀x : F ⇒ ∃x : G) ≡ ∃x : (F ⇒ G)

Aufgabe 16 Gegeben sei die prädikatenlogische Formel

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

Man bringe sie a) in bereinigte Form,

b) in bereinigte Pränexform,

c) in Skolemform.