Übungen zur Vorlesung Mathematische Logik

SS 2009, Blatt 1

Aufgabe 1.

(a) Betrachten Sie das Alphabet Σ = {a, b, c, d, e, f}. Wie viele Wörter der Länge 4 gibt es über Σ? Wie viele der Länge n für n ∈ ℕ? Wie viele Wörter der Länge n gibt es über einem Alphabet Σ′, wenn Σ′ genau k Buchstaben enthält?

(b) Betrachten Sie das Alphabet Σ = {a, b, c, d, e, f, g, h}. Ordnen Sie die folgenden Wörter bezüglich ≤_{d} und bezüglich ≤_{lex}:

affe, fechdeg, bach, ha, bade, f

Dabei bezeichne ≤_{d} die Ordnung auf Σ^{∗}, welche voll der Ordnung im Lexikon entspricht, und ≤_{lex} die lexikographische Ordnung auf Σ^{∗}.

Aufgabe 2. Für n ≥ 1 sei Σ = {a_{0}, …, a_{n}} ein Alphabet mit paarweise verschiedenen a_{0}, …, a_{n}. Ferner seien ≤_{d} und ≤_{lex} wie in Aufgabe 1.

(a) Geben Sie eine bezüglich ≤_{d} absteigende unendliche Folge (w_{i})_{i∈ℕ} ⊆ Σ^{∗} von Wörtern an, das heißt eine Folge (w_{i})_{i∈ℕ} mit

… ⪇_{d} w_{2} ⪇_{d} w_{1} ⪇_{d} w_{0}.

(b) Bestimmen Sie alle Wörter w ∈ Σ^{∗}, für die die Menge {v | v ≤_{d} w} unendlich ist.

(c) Zeigen Sie, daß für alle w ∈ Σ^{∗} die Menge {v | v ≤_{lex} w} endlich ist.

Aufgabe 3. Nehmen Sie an, daß Ihr Computer zur Durchführung eines Rechenschrittes 10^{−8} Sekunden benötigt. Berechnen Sie seine Laufzeit für je einen Algorithmus, der n, n^{4} bzw. 2^{n} Rechenschritte benötigt, für n = 10, 20 und 80. Wählen Sie für die Antwort eine informative Maßeinheit (Sekunden, Minuten, Tage, Jahre,...).

Aufgabe 4. Für eine Menge M bezeichne P (M) die Potenzmenge von M. Geben Sie eine injektive Funktion f : P (ℕ) ⟶ ℝ an. Folgern Sie, daß ℝ überabzählbar ist.

Aufgabe 5. Sei M eine Menge und L ⊆ M × M. Eine Teilmenge X von M ist ein L-Schnitt (genauer: ein linker L-Schnitt), wenn ein a ∈ M existiert, so daß gilt:

X = L_{a} := {m ∈ M | (a, m) ∈ L}.

Die Menge Δ_{L} := {m ∈ M | (m, m) ∈ L} ist die L-Diagonale.

(a) (Diagonallemma) Zeigen Sie: Das Komplement der L-Diagonale, das heißt die Menge M ∖ Δ_{L}, ist kein L-Schnitt.

(b) Sei f : M ⟶ P (M). Man setze L_{f} := {(a, b) ∈ M × M | b ∈ f(a)}. Was ist die Menge der L_{f}-Schnitte? Was kann man aus dem Diagonallemma für f folgern?

Abgabe: Mittwoch, 29.April, vor der Vorlesung.