Übungen zur Vorlesung Logik (Grundkurs)

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

12.1 Transformieren Sie

∀x∃yP (x, f(y)) ∧ ∀y(Q(x, y) ∨ R(x))

in eine Formel, in der keine Variable gebunden und frei vorkommt und alle quantifizierten Variablen verschieden sind.

12.2 Finden Sie die Pränexform von

∀x∃yP (x, g(y, f(x))) ∨ Q(z) ∨ ¬∀xR(x, y)

11.3 Welche der Strukturen sind Modelle für

∃x∃y∃z(P (x, y) ∧ P (z, y) ∧ P (x, z) ∧ ¬P (z, x)) ?

1. U^{A} = IN, P^{A} = {(m, m + 1) | m ∈ IN}

2. U^{A} = IN, P^{A} = {(m, n) | m, n ∈ IN, m < n}

3. U^{A} = 2^{IN}, P^{A} = {(A, B) | A, B ∈ 2^{IN}, A ⊆ B}

10.1 Zeigen Sie, daß in jedem normalen Modell gilt

• A[x/t] ↔ ∀x(x = t → A(x))

• A[x/t] ↔ ∃x(x = t ∧ A(x)),

wobei x ∉ Var(t) und keine der in t vorkommenden Variablen in A gebunden ist. Zeigen Sie durch ein (Gegen-)Beispiel, daß die Forderung nach Normalität wesentlich ist.