Übungen zur Vorlesung Mathematische Logik SS 2008, Blatt 4

Aufgabe 17. Sei S = {P, R, f, g, c, d} eine Symbolmenge, wobei P und f zweistellig, R und g einstellig sind.

1. Welche der folgenden Zeichenreihen sind S-Terme?

f(v_{2}, g(f(c, v_{2}))) f(g(f(c, d))) g(f(g(c), d))

2. Welche der folgenden Zeichenreihen sind S-Ausdrücke?

∀v_{1}∀v_{1}Rv_{1} ∀dP dd ∃v_{2}(P v_{2}v_{3} ∨ Rv_{3}) (∃v_{2}P v_{2}v_{3} ∨ Rv_{3})

Aufgabe 18. Sei S = {g, h, R, c} mit zweistelligen g, h, R und seien x, y, z paarweise verschiedene Variablen. Berechnen Sie rg(g(h(c, c), h(x, c))), fr(∃xRzx → ¬∀yRyx) und fr(∃x(Rzx → ¬∀yRyx)). Aufgabe 19. Sei S = {P, U, <, d} für ein zweistelliges < und einstellige P, U. 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 unendlich viele Primzahlen.

6. Es gibt eine kleinste natürliche Zahl.

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

8. Es gibt unendlich viele Primzahlzwillinge. ((p, q) ist ein Primzahlzwilling gdw. q − p = 2 und p und q prim sind.)

Aufgabe 20. Sei Σ = {a, 5, b}. Die Menge Z ⊆ Σ^{∗} sei definiert durch den folgenden Kalkül.

\begin{matrix}(R_{0}) & \overline{a5} \\ (R_{1}) & \frac{aξ}{aξξ} ξ ∈ Σ^{∗} \\ (R_{2}) & \frac{ξ555η}{ξbη} ξ, η ∈ Σ^{∗} \\ (R_{3}) & \frac{ξbbη}{ξη} ξ, η ∈ Σ^{∗} \end{matrix}

Zeigen Sie:

1. a5, a55, a5555, a5b, a55bb ∈ Z.

2. Für alle ξ ∈ Z gilt: Die Anzahl der 5 in ξ ist nicht durch 3 teilbar.

3. ab ∉ Z.

Aufgabe 21. ”An jeder Stelle in einem Term, an der kein Hilfssymbol steht, beginnt genau ein Term”. Genauer: Sei S eine Symbolmenge und t ∈ T^{S}; sei t = uav für u, v ∈ Σ_{S}^{∗} und einen Buchstaben a ∈ Σ_{S} verschieden von den Klammern ( , ) und dem Komma , . Zeigen Sie, daß es genau einen Term t′ ∈ T^{S} gibt, sodaß t = ut′v′ für ein geeignetes v′ ∈ Σ_{S}^{∗}.

Abgabe: Mittwoch, 28. Mai 2008, vor der Vorlesung.