s3jeleus
Inhaltsverzeichnis |
Übungsaufgabe 1
Prinzipiell Unlösbares:
- unscharfe Fragestellung
- Regeln zur Suche einer Antwort sind unklar
- zu viele abhängige Parameter
- emotionale Ebene
- exakte Vorhersagen
- begrenzte Ressourcen
- Annäherung an Ergebnisse durch Methoden der KI
Übungsaufgabe 2
Zeigen Sie, dass die folgenden Mengen abzählbar unendlich sind: \mathbb{Z}, \mathbb{Q}, die Menge der Primzahlen, die geraden Zahlen.
\Z ist abzählbar unendlich
z.z. \mathbb{Z} ist abzählbar unendlich, d.h. es existiert eine Funktion \mathbb{f}: \mathbb{N} \xrightarrow{\text{bij.}} \mathbb{Z}
| | 0 | 1 | 2 | 3 | 4 | 5 | ... |
| | 0 | -1 | 1 | -2 | 2 | 3 | ... |
Beweis durch vollständige Induktion
1. Gleichung
f(k) + 1 = f(k + 2) f(2n) + 1 = f(2n + 2)1.1Induktionsanfang
f(2 \cdot 0) + 1 = f(2 \cdot 0 + 2) f(0) + 1 = f(2) \frac{0}{2} + 1 = \frac{2}{2} 1 = 11.2 Induktionsvoraussetzung
f(2n) + 1 = f(2n +2)1.3Induktionsbehauptung
f(2(n + 1) + 1 = f(2(n +1) + 2) \frac{2(n + 1)+ 1}{2} = \frac{2(n+ 1)+ 2}{2} n + 1 +1 = n + 1 + 1 n + 2 = n + 2 n = n2. Gleichung
f(2n + 1) - 1 = f(2n + 3)2.1 Induktionsanfang
f(2 \cdot 0 + 1) - 1 = f(2 \cdot 0 + 3) f(1) - 1 = f(3) \frac{1 + 1}{-2} = \frac{3 +1}{-2} -2 = -22.2 Induktionsvoraussetzung
f(2n +1) - 1 = f(2n + 3)2.3Induktionsbehauptung
f(2(n + 1) + 1) -1 = f(2(n +1) + 3) f(2n + 2 + 1) -1 = f(2n +5) f(2n + 3 )- 1) = f(2n +5) \frac{((2n + 3) + 1)}{-2} -1 = \frac{2n + 5 + 1}{-2} \frac{2n + 4}{-2} - 1 = \frac{2n +6}{-2} \frac{2n + 4}{- 2} - \frac{1 \cdot (-2)}{-2} = \frac{2n + 6}{-2} \frac{2n + 4 +2}{-2} = \frac{2n +6}{-2} \frac{2n +6}{-2} = \frac{2n + 6}{ -2}\Q ist abzählbar unendlich
z.z. \mathbb{Q} ist abzählbar unendlich, d.h. es existiert eine Funktion \mathbb{f}: \mathbb{N} \xrightarrow{\text{bij.}} \mathbb{Q}
f(n) = \begin{cases} 1, & \text{wenn n = 1};\\ f(\frac{n}{2}) + 1, & \text{wenn n gerade};\\ \frac{1}{f(n-1)}, & \text{sonst }.\\ \end{cases}| \N^+ \ \Z | -1 | 1 | -2 | 2 | -3 | ... |
|---|---|---|---|---|---|---|
| | 1 | -1/1 | 1/1 | -2/1 | 2/1 | -3/1 | ... |
| | 2 | -1/2 | 1/2 | -2/2 | 2/2 | -3/2 | ... |
| | 3 | -1/3 | 1/3 | -2/3 | 2/3 | -3/3 | ... |
| | 4 | -1/4 | 1/4 | -2/4 | 2/4 | -3/4 | ... |
| | 5 | -1/5 | 1/5 | -2/5 | 2/5 | -3/5 | ... |
| | ... | ... | ... | ... | ... | ... | ... |
Durch das cantorschn Diagonalverfahren 1. Art lässt sich zeigen, dass die Menge \Q abzählbar unendlich ist.
Die Primzahlen sind abzählbar unendlich
1. Die Menge der Primzahlen P ist unendlich (nach Satz von Euklid).
2. Die Menge der Primzahlen P ist abzählbar unendlich, da gilt: P \subset \N.
Die geraden Zahlen sind abzählbar unendlich
1. Die geraden Zahlen G sind unendlich (per Definition) und abzählbar unendlich, da gilt: G \subset \Z.
Übungsaufgabe 3
Beweisen Sie den folgenden Satz: Wenn M_1, M_2, M_3, ... ∞ abzählbare Mengen sind, dann ist auch die Menge M_n n=1 abzählbar.
Eine Menge M ist endlich sofern eine surjektive Abbildung auf diese Menge existiert.
z.z. Es existiert eine Funktion f: \N \xrightarrow{\text{sur.}} \cup_{n = 1}^{∞} M_n
f_1: \N \xrightarrow{\text{bij.}} M_1 f_2: \N \xrightarrow{\text{bij.}} M_2 f_3: \N \xrightarrow{\text{bij.}} M_3 f_4: ...| \R \ \N | 0 | 1 | 2 | .... | j | ... |
|---|---|---|---|---|---|---|
| | M_{1} | f_1(1) | f_1(2) | f_1(3) | ... | f_1(j) | ... |
| | M_{2} | f_2(1) | f_2(2) | f_2(3) | ... | f_2(j) | ... |
| | M_{3} | f_3(1) | f_3(2) | f_3(3) | ... | f_3(j) | ... |
| | ... | ... | ... | ... | ... | ... | ... |
| | M_{i} | f_i(1) | f_i(2) | f_i(3) | ... | f_i(j) | ... |
Mit Hilfe des cantorschn Diagonalverfahrens 1. Art lässt sich eine surjektive Abbildung darstellen.
Übungsaufgabe 4
Verifizieren Sie, dass die folgende Funktion f : N^+ \xrightarrow{} \Q^+ eine bijektive Funktion ist und implementieren Sie eine Prozedur, die die zugehörige Umkehrfunktion f ^−1 berechnet.
f(n) = \begin{cases} 1, & \text{wenn } n=1;\\ f(\frac{n}{2})+1, & \text{wenn } n \text{ gerade};\\ \frac{1}{f(n-1)}, & \text{wenn } n \text{ ungerade}. \end{cases}| \N^+ \ \Z^+ | 1 | 2 | 3 | 4 | 5 | ... |
|---|---|---|---|---|---|---|
| | 1 | 1/1 | 2/1 | 3/1 | 4/1 | 5/1 | ... |
| | 2 | 1/2 | 2/2 | 3/2 | 4/2 | 5/2 | ... |
| | 3 | 1/3 | 2/3 | 3/3 | 4/3 | 5/3 | ... |
| | 4 | 1/4 | 2/4 | 3/4 | 4/4 | 5/4 | ... |
| | 5 | 1/5 | 2/5 | 3/5 | 4/5 | 5/5 | ... |
| | ... | ... | ... | ... | ... | ... | ... |
Umkehrfunktion:
f^{-1}(n) = \begin{cases}1, & n = 1 \\ f^{-1}(n-1) * 2, & n > 1 \\ f^{-1}(\frac{1}{n}) + 1, & sonst\end{cases}Übungsaufgabe 5
Indirekter Beweis: R ist abzählbar unendliche Menge, d.h es existiert eine Funktion f: \N \xrightarrow{\text{bij.}} \R
n_{ij} \in [0,9]Es lässt sich stets eine neue Zeile, die eine neue reele Zahl repräsentiert, hinzufügen.
n_i = \begin{cases} n_{ii} + 1, & \text{wenn $n_{ii} \neq 9$};\\ 0, & \text{sonst }.\\ \end{cases}| \R \ \N | 0 | 1 | 2 | ... | j | ... |
|---|---|---|---|---|---|---|
| | n_{1} | n_{10} | n_{11} | n_{12} | ... | n_{1j} | ... |
| | n_{2} | n_{20} | n_{21} | n_{22} | ... | n_{2j} | ... |
| | n_{3} | n_{30} | n_{31} | n_{32} | ... | n_{3j} | ... |
| | ... | ... | ... | ... | ... | ... | ... |
| | n_{i} | n_{i0} | n_{i1} | n_{i2} | n_{i3} | n_{ij} | ... |
Kreativaufgabe Gödelisierung und \mu-rekursive Funktionen
Aufgabe
Sei h: S^{*} \rightarrow N_{0} eine Gödelisierung von S^{*}, d.h. h ist injektiv, total und berechenbar. h(S*) ist entscheidbar und h^{-1} : h(S^{*}) \rightarrow S^{*} ist berechenbar.
Dann können die Wörter aus S^{*} vermöge h gödelgeordnet werden, so dass w_{i} \prec w_{j} \Leftrightarrow h(w_{i}) < h(w_{j}), für alle w_{i},w_{j} \in S^{*} und w_{i} \neq w_{j}.
Die folgende µ-rekursive Funktion liefert die Folge der Gödelnummern h(w_{0}), h(w_{1}), . . . in aufsteigender Form.
g(1) = \mu f(n, i) = \begin{cases} \text{das kleinste } n \in N_{0}, \text{ mit } 1- p(0, n) = 0 & , \text{wenn}\\ & \text{(1) so ein n existiert und}\\ & \text{(2) }1-p(0,m) \text{ f\"ur alle } m <= n \text{ definiert ist} \\ \text{undefiniert} & , \text{sonst} \end{cases}Für i \geq 1 gilt:
g(i + 1) = \mu f(n, i) = \begin{cases} \text{das kleinste }n \in N_{0} \text{, mit }1 - p(g(i) + 1, n) = 0 &\text{, wenn} \\ & \text{(1) so ein }n\text{ existiert und}\\ & \text{(2) }1 - p(g(i) + 1,m)\text{ f\"ur alle }m \leq n\text{ definiert ist}\\ \text{undefiniert} &\text{, sonst}\\ \end{cases}Die zur Definition von g verwendete zahlentheoretische Funktion p ist
p(r, y) =\begin{cases} 1 & \text{, wenn }y \geq r\text{ und }y\text{ ist G\"odelnummer}\\ 0 & \text{, sonst} \end{cases}Illustrieren Sie die folgenden Aussagen durch den Einsatz selbst entwickelter Scheme- Prozeduren. Wählen Sie exemplarisch S = {a, b} und die Verschlüsselung im 3er-System, mit a \rightarrow 1, b \rightarrow 2 als Gödelisierung h mit h(w) = \Sigma ^{\|w\|-1}_{i=0} a_{i}*3^{i} mit a_{i} \in \{1,2\}. Das Wort aba erhält dann die Gödelnummer h(aba) = 1*3^{2}+2*3^{1}+1*3^{0} = 16. Nicht jede natürliche Zahl ist Gödelnummer eines Wortes aus S^{*}: Beispielsweise ist 10 = 1 * 3^{2} + 0 * 3^{1} + 1 * 3^{0} keine.
p: N_{0} \times N_{0} \rightarrow \{0,1\} ist ein total berechenbares Prädikat. (Hinweis: Hierzu benötigen Sie eine Scheme-Prozedur für ein total berechenbares Prädikat, das feststellt, ob eine gegebene Zahl y Gödelnummer ist, d.h. y muss in der Form \Sigma ^{n}_{i=0} a^{i}*3^{i} mit a_{i} \in \{1,2\} darstellbar sein.)
g: N \rightarrow N_{0} wächst streng monoton und ist total. (Hinweis: Verwenden Sie eine Scheme-Prozedur zur Berechnung der ersten 10 Gödelnummern.)
Mit Hilfe der Funktion k : N \rightarrow S^{*}, k(n) = h^{-1}(g(n)) kann man das n-te Wort in der gödelgeordneten Folge der Wörter aus S^{*} bestimmen. k ist total und injektiv. Die zugehörige Umkehrfunktion k^{-1} : S^{*} \rightarrow N liefert somit auch wieder die Gödelisierung mit k^{-1}(w_{n}) = h(n).
Eine Prozedur zur Berechnung einer Gödelnummer ist gegeben durch
Eine Funktion zum Testen ob eine gegebene natürliche Zahl eine Gödelnummer ist gegeben durch die Funktion
f(x) = \begin{cases} 1, x < 3\\ 0, x mod 3 = 0\\ f( \lfloor{}x/3 \rfloor{}), sonst \end{cases}.
Beweis: Eine Gödelnummer über einem Alphabet {a,b} lässt sich zerlegen in
p_{i}3^{i} + p_{i-1}3^{i-1} + ... + p_{1}3^{1} + p_{0}3^{0}