BuK/IIm10/BuK-Übung07 G2

Wiki-Quelltext dieser Seite.

= Wort-spezifische TM =

= Wahrheitstafelmethode für aussagenlogische Äquivalenzen =

== Aufgabe ==
Verwenden Sie die Wahrheitstafelmethode, um zu zeigen, dass aus

<math>\hspace{5mm}</math>Wenn <math>P'\ entscheidbar</math> 
und
<math>P \leq P'</math>, dann 
<math>P\ entscheidbar</math>.

folgt

<math>\hspace{5mm}</math>Wenn 
<math>P\ unentscheidbar</math> 
und 
<math>P  \leq P'</math>, dann 
<math>P'\ unentscheidbar</math>.

== Lösung ==

Die Aussagen werden zuerst Variablen zugeordnet. Diese können entweder wahr oder falsch sein.

<math>A...P'\ entscheidbar</math>

<math>B...P\leq P'</math>

<math>C...P\ entscheidbar</math>

In der folgenden Tabelle sind die Aussagen A, B, C, dargestellt.  Die beiden markierten Spalten stehen für die beiden Sätze, welche durch die logische Aussagen entstehen. Man sieht, dass beide Spalten identisch sind, somit ist der Satz von der Aufgabe korrekt.

[[Bild:Simaklem2_Wahrheitstabelle.PNG]]

= Reduktion =