Übungen zur Vorlesung Logik (Grundkurs)

Abgabe am Mittwoch, dem 17. 6. 98, fünf Minuten vor der Vorlesung.

9.1 Man zeige, daß folgende Formeln allgemeingültig sind:

(a) ∀xA(x) → A[x/t]

(b) A[x/t] → ∃xA(x)

Dabei ist t ein Term, dessen Variablen an der Stelle x in A nicht gebunden sind; und A[x/t] ergibt sich aus A, in dem alle Vorkommen der Variablen x durch t ersetzt werden.

Zeigen Sie an einem Beispiel, daß die an t gestellte Bedingung notwendig ist.

10.4 Konstruieren Sie ein unendliches Modell für die Menge

Ax^{∗}(Id) ∪ {∃x∃y(¬x = y ∧ ∀z(z = x ∨ z = y))}

Zeigen Sie, daß jedes normale Modell genau zwei Elemente hat.

11.1 Finden Sie ein dreielementiges Modell für T_{1} sowie ein Modell für T_{2}:

T_{1} = {∀x∀y(R(x, y) → ¬R(y, x)), ∀x∃yR(x, y)}
T_{2} = T_{1} ∪ {∀x∀y(R(x, y) → ∃z(R(x, z) ∨ R(z, y)))}

11.2 Σ enthält das Gleichheitszeichen sowie ein einstelliges Funktionssymbol. Konstruieren Sie Formeln F_{1}, F_{2}, F_{3}, für die gilt

(a) in jedem Modell von F_{1} ist f^{δ} injektiv.

(b) in jedem Modell von F_{2} ist f^{δ} surjektiv.

(c) in jedem Modell von F_{3} ist f^{δ} bijektiv.