Übung04
Aus ProgrammingWiki
Behauptung: Eine Menge M ist genau dann aufzählbar, wenn sie semi-entscheidbar ist. [Bearbeiten] Teilaufgabe 1 (Felix Nitsche, Stefan Lüttke, Jens Heider, Daniel Tasche) zu zeigen: Wenn M aufzählbar, dann M semi-entscheidbar.
Annahme:
$M \subseteq X$
$x, n \in N$
für aufzählbare Mengen gilt:
$f(x) : N \rightarrow M$
für semi-entscheidbare Mengen gilt:
$ g(n \in X) = \begin{cases} wahr; & \text{wenn } n \in M;\\ \bot; & sonst \end{cases} $
Es kann nun bewiesen werden dass eine aufzählbare Menge immer auch semi-entscheidbar ist, wenn man einen Algorithmus angibt, der mithilfe der Funktion $f(x)$ die Funktion $g(n)$ nachbildet. Dies kann erreicht werden, indem die Funktion $f(x)$ in einer Schleife nacheinander mit jedem Element aus $X$ aufgerufen wird. Ist das Ergebnis dabei gleich $n$ wird $wahr$ zurückgegeben. Ist nun $n \in M$ gibt der Algorithmus $wahr$ zurück, andernfalls terminiert er nicht.
Teilaufgabe 1 - Beweis (Felix Nitsche, Stefan Lüttke)
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.
Da für $M_2 = \emptyset$ die Aussage offensichtlich zutrifft kann angenommen werden dass wenigstens ein Element $a \in M_2$ existiert.
Für $M_1$ als abzählbare Menge existiert eine Funktion
$f(x) = n \in M_1$
welche die Menge der natürlichen Zahlen auf M_1 abbildet.
Dadurch kann man nun für $M_2$ die folgende Funktion angeben:
$
g(x) = \begin{cases}
f(x); & f(x) \in M_1;\\
a; & sonst
\end{cases}
$
Durch diese Funktion wird nun jedem Element der natürlichen Zahlen eindeutig ein Element der Menge $M_2$ zugeordnet, wodurch deren Abzählbarkeit bewiesen ist.
Aufgabe 2 (Stefan Lüttke, Felix Nitsche)
(Aufgabe siehe: VL Slide 15/16)
Beweisen Sie diesen Satz, indem Sie mittels Aussagenlogik die Äquivalenz dieser Aussage zum vorhergehenden Satz zeigen. Es handelt sich um die Kontraposition:
$A \wedge B \rightarrow C \Leftrightarrow \neg C \wedge B \rightarrow \neg A$
Verwenden Sie im Beweis die folgenden Aussagen:
A: $P'$ ist entscheidbar. B: $P$ ist reduzierbar auf $P'$. C: $P$ ist entscheidbar.
Der Beweis kann in Form einer Wahrheitstabelle erbracht werden. Dabei werden die folgenden Variabeln genutzt:
$A: P'$ ist entscheidbar
$B: P$ ist reduzierbar auf $P'$
$C: P$ ist entscheidbar
Als gegeben kann dabei nach Satz 1 betrachtet werden dass:
$A \wedge B \Rightarrow C$
zu beweisen ist:
$\neg C \wedge B \Rightarrow \neg A$
Beweis:
| Zeile | A | B | C | Kommentar |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | gegeben durch Satz 1 |
| 2 | 1 | 1 | 0 | falsch nach Satz 1 |
| 3 | 1 | 0 | 1 | ... |
| 4 | 1 | 0 | 0 | ... |
| 5 | 0 | 1 | 1 | ... |
| 6 | 0 | 1 | 0 | Einzig verbleibende Möglichkeit für $\neg C \wedge B$ |
| 7 | 0 | 0 | 1 | ... |
| 8 | 0 | 0 | 0 | ... |
In Zeile 6 befindet sich die einzig verbleibende Möglichkeit für $\neg C \wedge B$. Daraus kann abgelesen werden dass in dem Fall $\neg A$ gilt, womit Satz 2 bewiesen ist.
alternativ aufgeschrieben (erweitert)
| $Zeile$ | $A$ | $B$ | $C$ | $E=A \wedge B$ | $F=E\Rightarrow C$ | $G=\neg C \wedge B$ | $H = G \Rightarrow \neg A$ | $I = F \Leftrightarrow H$ | $Kommentar$ |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | gegeben durch Satz 1 |
| 2 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | falsch nach Satz 1 |
| 3 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | ... |
| 4 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | ... |
| 5 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | ... |
| 6 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | Einzig verbleibende Möglichkeit für $\neg C \wedge B$ |
| 7 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | ... |
| 8 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | ... |
von Stefan
| $A$ | $B$ | $C$ | $E = A \wedge B$ | $F = E \rightarrow C$ | $G = \neg C \wedge B$ | $H = G \rightarrow \neg A$ | $I = F \Leftrightarrow H$ |
|---|---|---|---|---|---|---|---|
| w | w | w | w | w | f | w | w |
| f | w | w | f | w | w | w | w |
| w | f | w | f | f | w | f | w |
| f | f | w | w | w | f | w | w |
| w | w | w | w | f | f | f | w |
| f | w | w | f | w | w | w | w |
| w | f | w | f | w | w | w | w |
| f | f | w | w | w | f | w | w |
