BuK/IIm11/Studenten/sifenits/Übung04
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
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 <tt>(Felix Nitsche, Stefan Lüttke)</tt> ===
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:
{| border="1" cellpadding="5" cellspacing="0"
!Zeile
!A
!B
!C
!Kommentar
|-
|| 1 || style="background-color:#fedcba" | 1 || style="background-color:#fedcba" | 1 || style="background-color:#fedcba" | 1 || style="background-color:#fedcba" | gegeben durch Satz 1
|-
|| 2 || style="background-color:#fedcba" | 1 || style="background-color:#fedcba" | 1 || style="background-color:#fedcba" | 0 || style="background-color:#fedcba" | falsch nach Satz 1
|-
|| 3 ||1 || 0 || 1 || ...
|-
|| 4 ||1 || 0 || 0 || ...
|-
|| 5 ||0 || 1 || 1 || ...
|-
|| 6 || style="background-color:#9FF781" | 0 || style="background-color:#9FF781" | 1 || style="background-color:#9FF781" | 0 || style="background-color:#9FF781" | 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)
{| border="1" cellpadding="5" cellspacing="0"
!$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 || style="background-color:#fedcba" | 1 || style="background-color:#fedcba" | 1 || style="background-color:#fedcba" | 1 || style="background-color:#fedcba" | 1 || style="background-color:#fedcba" | 1 ||style="background-color:#fedcba" | 0 || style="background-color:#fedcba" | 1 || style="background-color:#fedcba" | 1 || style="background-color:#fedcba" | gegeben durch Satz 1
|-
|| 2 || style="background-color:#fedcba" | 1 || style="background-color:#fedcba" | 1 || style="background-color:#fedcba" | 0 || style="background-color:#fedcba" | 1 || style="background-color:#fedcba" | 0 || style="background-color:#fedcba" | 1 || style="background-color:#fedcba" | 0 || style="background-color:#fedcba" | 1 || style="background-color:#fedcba" | 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 || style="background-color:#9FF781" | 0 || style="background-color:#9FF781" | 1 || style="background-color:#9FF781" | 0 || style="background-color:#9FF781" | 0 || style="background-color:#9FF781" | 1 || style="background-color:#9FF781" | 1 || style="background-color:#9FF781" | 1 || style="background-color:#9FF781" | 1 || style="background-color:#9FF781" | 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
{| border="1" cellpadding="5" cellspacing="0"
!$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
|-
|}