Übungen zur Vorlesung Mathematische Logik SS 2008, Blatt 1

Aufgabe 1. (a) Sei Σ = {a_{0}, …, a_{4}} ein Alphabet mit paarweise verschiedenen a_{0}, …, a_{4}. Wie viele Wörter der Länge 3 gibt es über Σ? Wie viele der Länge n für n ∈ ℕ? Wie viele Wörter der Länge n gibt es, wenn Σ genau k Buchstaben enthält?

(b) Sei Σ = {a_{0}, …, a_{8}} ein Alphabet mit paarweise verschiedenen a_{0}, …, a_{8}. Ordnen Sie die folgenden Wörter bezüglich ≤_{d} und bezüglich ≤_{lex}:

a_{4}a_{0}a_{1}a_{3}, a_{3}a_{2}, a_{1}a_{7}a_{4}, a_{2}a_{1}a_{6}, a_{1}a_{7}a_{1}a_{2}a_{3}, a_{7}

Dabei bezeichne ≤_{d} die Ordnung auf Σ^{∗}, welche der Ordnung im Lexikon entspricht (bzgl. (a_{0}, …, a_{n})), und ≤_{lex} die lexikographische Ordnung auf Σ^{∗} (bzgl. (a_{0}, …, a_{n})).

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

(a) Geben Sie eine bezüglich ≤_{d} unendliche absteigende Folge von Wörtern (w_{i})_{i∈ℕ} ⊆ Σ^{∗} 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 Rechenschritts 10^{−9} Sekunden benötigt. Berechnen Sie seine Laufzeit für je einen Algorithmus, der n, n^{3} bzw. 2^{n} Rechenschritte benötigt, für n = 10, 30 und 70. Wählen Sie für die Antwort eine informative Maßeinheit (Sekunden, Minuten, Tage, Jahre,...).

Aufgabe 4. (a) Die Goldbachsche Vermutung besagt, daß jede gerade natürliche Zahl größer 2 Summe zweier Primzahlen ist. Halten Sie es für möglich, daß diese Vermutung wahr, jedoch nicht beweisbar ist?

(b) Die Kontinuumshypothese besagt, daß es für jede nichtleere Teilmenge X der reellen Zahlen entweder eine Surjektion f : X ⟶ ℝ oder eine Surjektion f : ℕ ⟶ X gibt. Halten Sie es für möglich, daß die Kontinuumshypothese weder bewiesen noch widerlegt werden kann?

Aufgabe 5. 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 6. Σ_{1}, …, Σ_{r} seien Alphabete (r ≥ 1) und W ⊆ Σ_{1}^{∗} × ⋯ × Σ_{r}^{∗}. Definieren Sie, was es heißt, daß W entscheidbar ist.

Abgabe: Mittwoch, 30. April 2008, vor der Vorlesung.