Übungen zur Vorlesung Logik für Informatiker WS 2008/09, Blatt 7

Abgabe: Mittwoch, 17. Dezember 2008, vor der Vorlesung

Schreiben Sie bitte den Namen Ihres Tutors auf Ihr Lösungsblatt! Allgemeiner Hinweis: Es besteht Anwesenheitspflicht bei den Übungen!

Aufgabe 1. Sei L = {P, U, <, d}, wobei < ein zweistelliges und P, U einstellige Relationszeichen sind und d ein Konstantenzeichen. Es sei

𝔑 = (ℕ, P^{𝔑}, U^{𝔑}, <^{𝔑}, d^{𝔑}),

wobei P^{𝔑} die Menge der Primzahlen ist, U^{𝔑} die Menge der ungeraden Zahlen, <^{𝔑} die übliche Ordnung auf ℕ und d^{𝔑} = 3. Symbolisieren Sie:

1. Nicht alle natürlichen Zahlen sind prim.

2. Es gibt eine von 3 verschiedene Primzahl.

3. Zu jeder Primzahl gibt es eine größere.

4. Es gibt genau eine gerade Primzahl.

5. Es gibt eine kleinste natürliche Zahl.

6. Nicht jede natürliche Zahl größer 3 ist prim.

7. Es gibt unendlich viele Primzahlen.

Aufgabe 2. Sei L = {+, ·} für zweistellige Funktionszeichen · und +. Weiterhin sei 𝔄 = (ℕ, +^{ℕ}, ·^{ℕ}) mit der gewöhnlichen Addition +^{ℕ} und Multiplikation ·^{ℕ} auf den natürlichen Zahlen ℕ.

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] ? Begründen Sie jeweils Ihre Antwort.

Aufgabe 3. Sei L = {P, Q, R} mit einstelligen Relationszeichen P, R und zweistelligem Relationszeichen Q. Sei

φ = ∀x(Rx → (Qxy ∧ ¬P y)) .

Geben Sie eine L-Struktur 𝔄 an sowie zwei Belegungen β und γ an, sodaß 𝔄 ⊧ φ[β] und 𝔄 |̸= φ[γ].

Aufgabe 4. Sei G eine Menge und f eine zweistellige Operation auf G. Ein Element g ∈ G heißt neutrales Element bezüglich f, falls für alle h ∈ G gilt:

f(g, h) = f(h, g) = h .

Sei nun L = {∘, e} mit zweistelligem Funktionszeichen ∘ und Konstantenzeichen e. Geben Sie eine L-Struktur 𝔄 = (A, ∘^{𝔄}, e^{𝔄}) an, sodaß e^{𝔄} neutrales Element bezüglich ∘^{𝔄} ist, und eine L-Struktur 𝔅 = (B, ∘^{𝔅}, e^{𝔅}), sodaß e^{𝔅} nicht neutrales Element bezüglich ∘^{𝔅} ist. Können Sie 𝔄 und 𝔅 so angeben, daß sowohl Grundmengen als auch Operationen übereinstimmen?