Übungen zur Vorlesung Mathematische Logik SS 2008, Blatt 5

Aufgabe 22. Sei 𝔄 = (ℕ, +, ·).

1. Sei t(x, y, u, z, v) = x · (y + z); berechnen Sie t^{𝔄}[1, 1, 2, 3, 5] und t^{𝔄}[2, 3, 5, 7, 11].

2. Sei φ(x, y, z) = ∃x z ≡ x + y. Gilt 𝔄 ⊧ φ[2, 1, 2] ? Gilt 𝔄 ⊧ φ[2, 5, 3] ?

3. Sei ψ(y) = ∃x ∀x x + x ≡ y. Gilt 𝔄 ⊧ ψ[4] ?

Aufgabe 23. Zeigen Sie, daß die in der Vorlesung angegebenen Axiome der Theorie der Äquivalenzrelationen unabhängig sind (das heißt, daß keines der Axiome aus den beiden anderen folgt).

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

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

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

Aufgabe 25. Ein Graph G = (G, E^{G}) heißt 3-färbbar, wenn es paarweise disjunkte Teilmengen R, B, L ⊆ G gibt (B die Menge der blauen, R die Menge der roten und L die Menge der lilafarbenen Punkte) mit G = R ∪ B ∪ L, sodaß benachbarte Punkte verschiedene Farben haben, d.h. für alle a, b ∈ G mit (a, b) ∈ E^{G} und für alle M ∈ {R, B, L} gilt: wenn a ∈ M, so b ∉ M.

Zeigen Sie, daß G genau dann 3-färbbar ist, wenn es einen Homomorphismus von G nach dem Graphen [figure]gibt.

Aufgabe 26. Die Bearbeitung dieser Aufgabe ist verbindlich! Sei S = {P, G, I} eine Symbolmenge, wobei I ein zweistelliges und P, G einstellige Relationssymbole sind. Wir lesen P x als “x ist ein Punkt”, Gx als “x ist eine Gerade” und Ixy als “x ist ein Punkt, y 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.

Abgabe: Mittwoch, 4. Juni 2008, vor der Vorlesung.