BuK/IIm18/Vorlesung6

Wiki-Quelltext dieser Seite.

== Ü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

=== 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$
!$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 || ...

|-

|}


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.