uebung4
Aus ProgrammingWiki
Inhaltsverzeichnis |
Übungsaufgaben
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.
- die Klasse der abzählbaren Mengen, von denen es überabzählbar unendliche viele gibt
- die Klasse der aufzählbaren Menegn, von denen es abzählbar unendlich viele gibt
- die Klasse der entscheidbaren Mengen, von denen es ebenfalls abzählbar unendlich viele gibt
- die Klasse der semi-entscheidbaren Mengen, von denen es abzählbar unendlich viele gibt
- die Klassen der endlichen Mengen von denen es abzählbar unendlich viele gibt
- die Mengen A*, $\mathscr{P}$(a), und $\mathscr{P}$(A*) für ein beliebiges Alphabet A
