uebung6
Aus ProgrammingWiki
Reduzierbarkeit
Aufgabe 1
Konstruieren Sie eine Prozedur, welche prüft, ob w die Form uu besitzt.
Aufgabe 2
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 AVerwenden Sie im Beweis die folgenden Aussagen:
A: P' ist entscheidbar. B: P ist reduzierbar auf P'. C: P ist entscheidbar.
| A | B | C | A \wedge B | A \wedge B \rightarrow C | \neg C | \neg C \wedge B | \neg A | \neg C \wedge B \rightarrow \neg A |
|---|---|---|---|---|---|---|---|---|
| | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 |
| | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 |
| | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 |
| | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 |
| | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 |
| | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 |
| | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 |