Übungen zur Vorlesung Mathematische Logik

SS 2009, Blatt 2

Aufgabe 1. Sei Σ = {a, b}. Geben Sie ein R-Programm P an, welches die Identität auf Σ^{∗} berechnet, das heißt mit P : x ↦ x für alle x ∈ Σ^{∗}.

Aufgabe 2. Sei Σ ein Alphabet und W ⊆ Σ^{∗}. Zeigen Sie, daß W genau dann R-entscheidbar ist, wenn es ein Aufzählungsverfahren P für W gibt, welches die Elemente von W ohne Wiederholungen in lexikographischer Reihenfolge ausgibt.

Aufgabe 3. Sei Σ ein Alphabet und W ⊆ Σ^{∗} eine nichtleere Wortmenge über Σ. Zeigen Sie, daß folgende Aussagen äquivalent sind:

1. W ist R-aufzählbar.

2. Es gibt eine berechenbare Funktion f mit df(f) = W und bd(f) ⊆ Σ^{∗}.

3. Es gibt eine berechenbare Funktion f mit df(f) = Σ^{∗} und bd(f) = W.

Aufgabe 4. Seien Σ_{1} und Σ_{2} Alphabete und W_{1} ⊆ Σ_{1}^{∗}, W_{2} ⊆ Σ_{2}^{∗}. Die Wortmenge W_{1} heißt auf W_{2} (many-one) reduzierbar (in Notation W_{1} ≤_{m} W_{2}), wenn es eine R-berechenbare Abbildung f : Σ_{1}^{∗} ⟶ Σ_{2}^{∗} gibt, so daß für alle x ∈ Σ_{1}^{∗} gilt:

x ∈ W_{1} ⟺ f(x) ∈ W_{2}.

Ein solches f ist eine Reduktion von W_{1} auf W_{2}. Zeigen Sie:

1. Ist W_{1} ≤_{m} W_{2} und W_{2} R-entscheidbar, so ist auch W_{1} R-entscheidbar.

2. Ist W_{1} ≤_{m} W_{2} und W_{2} R-aufzählbar, so ist auch W_{1} R-aufzählbarr.

Wurde in der Vorlesung bereits eine Reduktion (implizit) angegeben?

Aufgabe 5. Sei Σ = {|}. Wie üblich identifizieren wir Σ^{∗} mit ℕ. Sei weiterhin f eine Funktion mit df(f) ⊆ (Σ^{∗})^{2} und bd(f) ⊆ Σ^{∗}. Betrachten Sie die beiden Funktionen

g_{1}(x) = \{ \begin{matrix}das kleinste y mit f(x, y) = 0, & falls ein solches y existiert \\ undefiniert, & sonst \end{matrix}

g_{2}(x) = \{ \begin{matrix}das kleinste y mit f(x, y) = 0 und f(x, z) ist definiert für z < y, & falls ein solches y existiert \\ undefiniert, & sonst \end{matrix}

Ist stets für berechenbares f auch g_{1} berechenbar? Ist stets für berechenbares f auch g_{2} berechenbar? Warum?

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