Übungen zur Vorlesung Mathematische Logik SS 2009, Blatt 4

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

1. Welche der folgenden Zeichenreihen sind S-Terme?

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

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

∃v_{1}∀v_{2}Rv_{1} ∀v_{7}(¬P (f(v_{7}), v_{7})∧R(d)) ∀cP cc ∃v_{3}∀v_{3}(P v_{3}v_{2} ∨ Rv_{2})

Aufgabe 2. 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 genau dann, wenn q − p = 2 und p und q sind prim.)

Aufgabe 3.

Are we not drawn onward, we few, drawn onward to new era Sei Σ = {0, 1}. Für ein Wort w = a_{1} … a_{|w|} ∈ Σ^{∗} sei w^{−1} := a_{|w|} … a_{1}. Ein Wort w ∈ Σ^{∗} ist ein Palindrom genau dann, wenn w = w^{−1}. Geben Sie ein nichtdeterministisches R-Programm an, welches die Menge der Palindrome in Σ^{∗} entscheidet.

Aufgabe 4. Sei Σ ein Alphabet. Zeigen Sie, daß es ein universelles Programm gibt, das ist ein Programm P_{0}, so daß für alle R-Programme P und alle y, z ∈ Σ^{∗} gilt:

P_{0} : (x_{P} , y) → halt ⟺ P : y → halt
P_{0} : (x_{P} , y) → z ⟺ P : y → z

Folgern Sie, daß nicht entscheidbar ist, ob P_{0} angesetzt auf (x, y) schließlich hält.

Aufgabe 5. “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, so daß t = ut′v′ für ein geeignetes v′ ∈ Σ_{S}^{∗}.

Abgabe: Mittwoch, 20. 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