Übungen zur Vorlesung Mathematische Logik

SS 2009, Blatt 5

Aufgabe 1. Sei S = {f, g, R, c} mit zweistelligen f, g, R und seien x, y, z paarweise verschiedene Variablen. Berechnen Sie

1. rg(f(c, g(c, x)))

2. fr((∃yRxy∧¬∀zRyz))

3. fr(∀z(∃yRyx ∨ Rzy))

Aufgabe 2. Sei 𝔑 = (ℕ, +, ·).

1. Sei t(x, y, z, w) = y·(w+z). Berechnen Sie t^{𝔑}[1, 3, 2, 1] und t^{𝔑}[2, 2, 5, 7].

2. Sei φ(x, y, z) = ∃x z ≡ x + y. Gilt 𝔑 ⊧ φ[2, 1, 2]? Gilt 𝔑 ⊧ φ[4, 6, 2]?

3. Sei ψ ∈ L_{3}^{S} mit ψ = ∃v_{2} v_{3} ≡ v_{2} + v_{2}. Gilt 𝔑 ⊧ ψ[2, 4, 5]? Gilt 𝔑 ⊧ ψ[5, 2, 4]?

Aufgabe 3. Sei P ein einstelliges Relationssymbol und f ein zweistelliges Funktionssymbol. Geben Sie für jeden der Ausdrücke

∀v_{2} f(v_{1}, v_{2}) ≡ v_{1}, ∃v_{1}∀v_{2} f(v_{1}, v_{2}) ≡ v_{2}, ∃v_{1}(P v_{1}∧∀v_{2} P f(v_{1}, v_{2}))

eine Interpretation an, die ihn erfüllt, und eine, die ihn nicht erfüllt.

Aufgabe 4. Diese Aufgabe ist verbindlich und zusätzlich zu den zwei standardmäßig zu bearbeitenden Aufgaben zu bearbeiten! Sei S = {P, G, I} eine Symbolmenge, wobei I ein zweistelliges und P, G einstellige Relationssymbol sind. Wir lesen P x als “x ist ein Punkt”, Gx als “x ist eine Gerade” und Ixy als “x ist ein Punkt, y ist eine Gerade, und x liegt auf y”. Symbolisieren Sie in L^{S}:

1. Zu zwei Punkten gibt es eine Gerade, auf der beide liegen.

2. Zu zwei verschiedenen Punkten gibt es nicht mehr als eine Gerade, auf der beide liegen.

3. Auf jeder Geraden liegen mindestens zwei verschiedene Punkte.

Aufgabe 5. Welche der folgenden Aussagen sind richtig? Geben Sie jeweils einen Beweis oder ein Gegenbeispiel an.

1. (φ ∨ ψ) ⊧ χ gdw φ ⊧ χ und ψ ⊧ χ.

2. (φ ∨ ψ) ⊧ χ gdw φ ⊧ χ oder φ ⊧ χ.

Abgabe: Mittwoch, 27. Mai, vor der Vorlesung.

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

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