Thema4

Aus ProgrammingWiki

Inhaltsverzeichnis 1 Aufgabe 1 2 Aufgabe 2 3 Aufgabe 3 4 Aufgabe 4 5 Aufgabe 5 6 Aufgabe 6

Aufgabe 1

Vervollständigen Sie die Herleitung der Funktionen für x und y aus $z = π(x, y)$ und geben Sie als Beispiel die Ermittlung von x und y aus $z = π(1, 3) = 13$ an.

Aufgabe 2

zu zeigen: Jede Teilmenge $M_2$ einer abzählbaren Menge $M_1$ ist abzählbar. Wenn $M_1$ eine abzählbare Menge ist, dann ist jede Teilmenge $M_2 \subseteq M_1$ abzählbar.

Aufgabe 3

zu zeigen: Nicht jede Teilmenge $M_2$ einer aufzählbaren Menge $M_1$ ist aufzählbar. Wenn M1 eine aufzählbare Menge ist, dann gilt nicht für alle Teilmengen $M_2$ ⊆ $M_1$, dass sie aufzählbar sind.

Aufgabe 4

zu zeigen: Wenn die Menge $M$ entscheidbar ist, dann ist $M$ aufzählbar.

Aufgabe 5

zu zeigen: Wenn M und $A^*$\M aufzählbare Mengen sind, dann ist M eine entscheidbare Menge.

Aufgabe 6

Stellen Sie die folgenden Mengen in genau einem Diagramm grafisch dar.

1. die Klasse der abzählbaren Mengen, von denen es überabzählbar unendliche viele gibt
2. die Klasse der aufzählbaren Menegn, von denen es abzählbar unendlich viele gibt
3. die Klasse der entscheidbaren Mengen, von denen es ebenfalls abzählbar unendlich viele gibt
4. die Klasse der semi-entscheidbaren Mengen, von denen es abzählbar unendlich viele gibt
5. die Klassen der endlichen Mengen von denen es abzählbar unendlich viele gibt
6. die Mengen A*, $\mathscr{P}$(a), und $\mathscr{P}$(A*) für ein beliebiges Alphabet A