Vorlesung5
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 Cund
\neg C \wedge B \Rightarrow \neg AMit 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.