Vorlesung5
Aus ProgrammingWiki
Konstruieren sie eine Prozedur, welche prüft ob $w$ die Form $uu$ besitzt!
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.
Gegeben ist:
$A \wedge B \Rightarrow C$
und
$\neg C \wedge B \Rightarrow \neg A$
Mit Hilfe der Wahrheitstabelle kann die Äquivalenz gezeigt werden:
| $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$ |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 |
In Zeile 8 ist die Bestätigung des 1. Satzes $A \wedge B \Rightarrow C$. Aus der 3. Zeile ist die einzige Belegung für die Aussage $\neg C \wedge B \Rightarrow \neg A$ zu finden, wobei in dem Fall $\neg A$ gilt und somit der 2. Satz bestätigt ist.
Zeigen Sie die Unentscheidbarkeit von $L_{Σ^∗} := \{\langle M \rangle | L(M) = Σ^∗\}$ durch Reduktion des Halteproblems.
