Übungen zur Vorlesung Logik (Grundkurs)

Abgabe am Mittwoch, dem 10. 6. 98, (das heißt: in zwei Wochen) fünf Minuten vor der Vorlesung.

8.1 Formulieren Sie die folgenden geometrischen Axiome im Prädikatenkalkül der ersten Stufe. Definieren Sie zunächst eine geeignete Signatur.

(a) Zu zwei verschiedenen Punkten gibt es stets eine Gerade, auf der diese beiden Punkte liegen.

(b) Zu zwei verschiedenen Punkten gibt nicht mehr als eine Gerade, auf der diese beiden Punkte liegen.

(c) Zu je vier Punkten A, B, C, D gibt es einen Punkt E, so daß B zwischen A und E liegt und B von E den gleichen Abstand hat wie C von D.

8.3 Die Menge bvar(A) der gebundenen Variablen einer Formel A ist induktiv definiert durch

(a) bvar(R(t_{1}, …, t_{n})) = ∅ für Atomformeln

(b) bvar(¬A) = bvar(A)

(c) bvar(A ∘ B) = bvar(A) ∪ bvar(B) für ∘ ∈ {∧, ∨, →, ↔}

(d) bvar(∀xA) = bvar(∃xA) = bvar(A) ∪ {x}

Berechnen Sie bvar(A) und fvar(A) für

A = ∀x(R(x, y) → P (x) ∧ ∀y(¬R(x, y) ∧ ∀xP (x)))

9.2, 9.3 Welche der Formeln ist allgemeingültig?

C = (∃xA ∧ ∃xB) → ∃x(A ∧ B) D = ∃x∀yR(x, y) → ∀y∃xR(x, y)

9.4 Finden Sie ein Modell für

F = ∀x¬R(x, x) ∧ ∀x∀y∀z(R(x, y) ∧ R(y, z) → R(x, z)) ∧ ∀x∃yR(x, y)

und zeigen Sie, daß jedes Modell von F unendlich ist.