Übungen zur Vorlesung Mathematische Logik SS 2009, Blatt 7

Aufgabe 1.

1. Sei φ ∈ L^{S}. Geben sie den Ausdruck ∃^{≤3}x φ explizit an.

2. Geben Sie einen zu (∀x(∃yRxy∨∀yRyx) → ∃z(∃xRxz ∧ ∀yRyz)) äquivalenten Ausdruck in pränexer Normalform an.

Aufgabe 2. (1) Welche der folgenden Sequenzen sind korrekt?

1. ∀xφ ∃xφ

2. φ ψ (φ ∧ ∀xψ)

(2) Welche der folgenden Regeln sind korrekt?

1. \begin{matrix}Γ & φ & ψ \\ Γ & ψ & χ \\ Γ & & (¬φ ∨ χ) \end{matrix}
2. \begin{matrix}Γ & ∃xφ \\ Γ & ∀xφ \end{matrix}

Aufgabe 3. Berechnen Sie [[∀v_{2}f(v_{2}, v_{3}) ≡ v_{1}]\frac{v_{2}}{v_{1}} ] \frac{f(v_{3},v_{1})}{v_{2}}. Aufgabe 4. Sei 𝔄 eine endliche S-Struktur. Zeigen Sie:

1. Ist S endlich, so gibt es einen Satz φ_{𝔄}, der 𝔄 charakterisiert, d.h. mit Mod(φ_{𝔄}) = {𝔅 | 𝔅 ≅ 𝔄}.

2. Ist S beliebig, so gibt es eine Satzmenge Φ_{𝔄}, die 𝔄 charakterisiert, d.h. mit Mod(Φ_{𝔄}) = {𝔅 | 𝔅 ≅ 𝔄}.

Aufgabe 5. Seien V_{n} und V_{ℕ} wie in Aufgabe 5 auf Blatt 6 definiert. Sei \underline{ε} ein zweistelliges Relationssymbol und

\underline{ε}^{V_{n}} = \{(x, y) | x, y ∈ V_{n}, x ∈ y\}
\underline{ε}^{V_{ℕ}} = \{(x, y) | x, y ∈ V_{ℕ}, x ∈ y\}

(1) Gilt (V_{5}, \underline{ε}^{V_{5}}) ⊧ φ, (V_{ℕ}, \underline{ε}^{V_{ℕ}}) ⊧ φ für folgende Aussagen φ?

(EXT)  φ = ∀x∀y (∀z(\underline{ε}zx ↔ \underline{ε}zy) → x ≡ y)
(PAAR)  φ = ∀x∀y∃z∀w (\underline{ε}wz ↔ (w ≡ x ∨ w ≡ y))
(POT)  φ = ∀x∃y∀z (\underline{ε}zy ↔ ∀w(\underline{ε}wz → \underline{ε}wx))
(AUS)  φ = ∀x_{1} … ∀x_{n}∀x∃y∀z (\underline{ε}zy ↔ (\underline{ε}zx ∧ ψ(z, x_{1}, …, x_{n})))
für ψ(z, x_{1}, …, x_{n}) beliebig

(2) Sei A := \{\overline{n} | n ∈ ℕ\}, 0^{A} := \overline{0} und σ^{A} : A → A sei definiert durch σ^{A}(\overline{n}) := \overline{n + 1}. Zeigen Sie, daß die Struktur A = (A, σ^{A}, 0^{A}) die Peanoaxiome (P1) bis (P3) erfüllt.

Abgabe: Mittwoch, 17. Juni, vor der Vorlesung. Hinweis: Da am Donnerstag, 11.6. ein Feiertag ist, werden die Donnerstagsübungen verschoben auf Freitag, 12.6., 14 Uhr in Raum 119 (Magnus) bzw. Raum 318 (Leander).

Die Übungsblätter und die Einteilung der Übungen findet man auch unter

http://home.mathematik.uni-freiburg.de/bjoern/lehre/logik09/logik09.html