BuK/IIm12/Studenten/siclsche/Thema6

Wiki-Quelltext dieser Seite.

==Aufgabe 1 ==

Satz: Wenn '''P''' unentscheidbar ist und '''P''' ist reduzierbar auf '''P'''', so ist auch '''P'''' unentscheidbar. 

Beweisen Sie den vorhergehenden 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 des Satzes kann unter Hilfenahme einer Wahrheitstabelle vorgenommen werden. 

{| border="1" cellpadding="5" cellspacing="0"

!$A$
!$B$
!$C$
!$S1 =A \wedge B$
!$S1 \Rightarrow C$
!$S2 =\neg C \wedge B$
!$ S2 \Rightarrow \neg A$
!$A \wedge B \rightarrow C \Leftrightarrow \neg C \wedge B \rightarrow \neg A$
|-
||$$1$$ || $$1$$ || $$1$$ || $$1$$ || $$1$$ || $$0$$ || $$1$$ || $$1$$ 
|-
||$$1$$ || $$1$$ || $$0$$ || $$1$$ || $$0$$ || $$1$$ || $$0$$ || $$1$$ 
|-
||$$1$$ || $$0$$ || $$1$$ || $$0$$ || $$1$$ || $$0$$ || $$1$$ || $$1$$ 
|-
||$$1$$ || $$0$$ || $$0$$ || $$0$$ || $$1$$ || $$0$$ || $$1$$ || $$1$$ 
|-
||$$0$$ || $$1$$ || $$1$$ || $$0$$ || $$1$$ || $$0$$ || $$1$$ || $$1$$ 
|-
||$$0$$ || $$1$$ || $$0$$ || $$0$$ || $$1$$ || $$1$$ || $$1$$ || $$1$$ 
|-
||$$0$$ || $$0$$ || $$1$$ || $$0$$ || $$1$$ || $$0$$ || $$1$$ || $$1$$
|-
||$$0$$ || $$0$$ || $$0$$ || $$0$$ || $$1$$ || $$0$$ || $$1$$ || $$1$$
|-
|}

== Aufgabe 2 == 

Zeigen Sie die Unentscheidbarkeit von $L_{\Sigma^{*}}:=\{\left\langle M \right\rangle | L(M) = \Sigma^{*} \}$ durch Reduktion des Halteproblems.