Vorlesung6
Aus ProgrammingWiki
Archivierte Version vom 2019-05-05T18:57:57+00:00. Aktuelle Version
Übungsaufgabe 1
Eine TM soll überprüfen ob w die Form uu besitzt. Für u gilt a^ib^ic^i, bei Korrektheit von w soll u auf dem Band hinterlassen werden.
Übungsaufgabe 2
Beweisen sie mittels Aussagenlogik A \wedge B \rightarrow C \Leftrightarrow \neg C \wedge B \rightarrow \neg A.
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 Czu beweisen ist:
\neg C \wedge B \Rightarrow \neg ABeweis:
| 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 | ... |
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.