BuK/IIm11/Studenten/sifenits/Übung04

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"
|-
!$a$ !! $b$ !! $c$ !! $\wp (M)$
|-
| 0 || 0  ||  0  || $\{\varnothing \}$
|-
| 0 || 0  ||  1  || $\{ c\}$
|-
| 0 || 1  ||  0  || $\{ b\}$
|-
| 0 || 1  ||  1  || $\{bc\}$
|-
| 1 || 0  ||  0  || $\{a\}$
|-
| 1 || 0  ||  1  || $\{ac\}$
|-
| 1 || 1  ||  0  || $\{ab\}$
|-
| 1 || 1  ||  1  || $\{abc\}$
|-

|}

{| border="1" cellpadding="5" cellspacing="0"
!A
!B
!C
|-
||a ||  b || c ||
|-
||a || b || c ||
-|}