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 $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 C$

zu beweisen ist:

$\neg C \wedge B \Rightarrow \neg A$


Beweis:
<table border=1>
    <tr>
        <th>$A$</th>
        <th>$\neg A$</th>
        <th>$B$</th>
        <th>$C$</th>
        <th>$\neg C$</th>
        <th>$A \wedge B$</th>
        <th>$A \wedge B \Rightarrow C$</th>
        <th>$\Leftrightarrow$</th>
        <th>$B \wedge \neg C$</th>
        <th>$B \wedge C \Rightarrow \neg A$</th>
    </tr>
    <tr>
        <td>$1$</td>
        <td>$0$</td>
        <td>$1$</td>
        <td>$1$</td>
        <td>$0$</td>
        <td>$1$</td>
        <td>$1$</td>
        <td>$1$</td>
        <td>$0$</td>
        <td>$1$</td>
    </tr>
    <tr>
        <td>$1$</td>
        <td>$0$</td>
        <td>$1$</td>
        <td>$1$</td>
        <td>$0$</td>
        <td>$1$</td>
        <td>$1$</td>
        <td>$1$</td>
        <td>$0$</td>
        <td>$1$</td>
    </tr>
    <tr>
        <td>$1$</td>
        <td>$0$</td>
        <td>$1$</td>
        <td>$0$</td>
        <td>$1$</td>
        <td>$1$</td>
        <td>$0$</td>
        <td>$1$</td>
        <td>$1$</td>
        <td>$0$</td>
    </tr>
    <tr>
        <td>$1$</td>
        <td>$0$</td>
        <td>$0$</td>
        <td>$1$</td>
        <td>$0$</td>
        <td>$0$</td>
        <td>$1$</td>
        <td>$1$</td>
        <td>$0$</td>
        <td>$1$</td>
    </tr>
    <tr>
        <td>$1$</td>
        <td>$0$</td>
        <td>$0$</td>
        <td>$0$</td>
        <td>$1$</td>
        <td>$0$</td>
        <td>$1$</td>
        <td>$1$</td>
        <td>$0$</td>
        <td>$1$</td>
    </tr>
    <tr>
        <td>$0$</td>
        <td>$1$</td>
        <td>$1$</td>
        <td>$1$</td>
        <td>$0$</td>
        <td>$0$</td>
        <td>$1$</td>
        <td>$1$</td>
        <td>$0$</td>
        <td>$1$</td>
    </tr>
    <tr>
        <td>$0$</td>
        <td>$1$</td>
        <td>$1$</td>
        <td>$0$</td>
        <td>$1$</td>
        <td>$0$</td>
        <td>$1$</td>
        <td>$1$</td>
        <td>$1$</td>
        <td>$1$</td>
    </tr>
    <tr>
        <td>$0$</td>
        <td>$1$</td>
        <td>$0$</td>
        <td>$1$</td>
        <td>$0$</td>
        <td>$0$</td>
        <td>$1$</td>
        <td>$1$</td>
        <td>$0$</td>
        <td>$1$</td>
    </tr>
    <tr>
        <td>$0$</td>
        <td>$1$</td>
        <td>$0$</td>
        <td>$0$</td>
        <td>$1$</td>
        <td>$0$</td>
        <td>$1$</td>
        <td>$1$</td>
        <td>$0$</td>
        <td>$1$</td>
    </tr>

</table>