s3adkuce
Aus ProgrammingWiki
Inhaltsverzeichnis |
Indirekter Beweis
Aufgabe 1
Beweisen Sie indirekt, dass $x$ eine gerade Zahl ist, wenn $x^2$ mit $x\in{\mathbb N}$ eine gerade Zahl ist.
Lösung:
zu zeigen: Wenn $x^2$ gerade, dann $x$ gerade (Wenn $2 \mid x^2$, dann $2 \mid x$).
Beispiele: $2^2 = 4$ (gerade), $4^2 = 16$ (gerade), $3^2 = 9$ (ungerade)
Annahme: Wenn $2 \mid x^2$, dann $2 \nmid x$.
Beweis:
$x \text{ ungerade: } 2k+1\text{, } k \in \N $
$x^2 \text{gerade: } 2z \text{, } z \in \N$
$\Rightarrow (2k+1)^2 = 4k^2 + 4k + 1 \Rightarrow = ungerade, da +1$
$\Rightarrow \unicode{x021AF}$ Widerspruch, da $x^2$ gleichzeitig gerade und ungerade wäre.
Aufgabe 2
Beweisen Sie die Aussage, wonach aus der Gültigkeit der Aussagen $A \Rightarrow B$, $B \Rightarrow C$ und $\overline{C}$ die Gültigkeiten von $\overline{A}$ und $\overline{B}$ folgen. Stellen Sie den Sachverhalt in einer Wahrheitstabelle dar.
Lösung:
| Zeile | $A$ | $B$ | $C$ | $\overline{A}$ | $\overline{B}$ | $\overline{C}$ | $A \Rightarrow B$ | $B \Rightarrow C$ |
|---|---|---|---|---|---|---|---|---|
| 1 | W | W | W | F | F | F | W | W |
| 2 | W | W | F | F | F | W | W | F |
| 3 | W | F | W | F | W | F | F | W |
| 4 | W | F | F | F | W | W | F | W |
| 5 | F | W | W | W | F | F | W | W |
| 6 | F | W | F | W | F | W | W | F |
| 7 | F | F | W | W | W | F | W | W |
| 8 | F | F | F | W | W | W | W | W |
Nur in Zeile 8 folgen aus der Gültigkeit der Aussagen $A \Rightarrow B$, $B \Rightarrow C$ und $\overline{C}$ die Gültigkeiten von $\overline{A}$ und
$\overline{B}$, also wenn $A$, $B$ und $C$ nicht gelten.
| Zeile | $\overline{A}$ | $\overline{B}$ | $\overline{C}$ | $A \Rightarrow B$ | $B \Rightarrow C$ |
|---|---|---|---|---|---|
| 8 | W | W | W | W | W |
Aufgabe 3
Was kann man über die Gültigkeit von A und B schließen, wenn bekannt ist, dass $A \Rightarrow B$, $B \Rightarrow C$ und $C$ gelten? Verwenden Sie die Tabelle aus der vorhergehenden Aufgabenlösung.
Lösung:
Laut den Zeilen 1, 5 und 7 aus der obigen Tabelle folgt, dass, wenn bekannt ist, dass $A \Rightarrow B$, $B \Rightarrow C$ und $C$ gelten, $A$ und $B$ entweder beide gelten, beide nicht gelten oder nur $B$, aber nicht $A$ gilt.
| Zeile | $A$ | $B$ | $C$ | $A \Rightarrow B$ | $B \Rightarrow C$ |
|---|---|---|---|---|---|
| 1 | W | W | W | W | W |
| 5 | F | W | W | W | W |
| 7 | F | F | W | W | W |
Kreativaufgabe
Das MU-Rätsel (MU puzzle)
MIU-System (Douglas R. Hofstadter)
Die Hauptfrage lautet: Ist MU ein Satz des MIU-Systems?
Symbole:
M, I, U
Axiom:
MI
Regeln:
x verhält sich in diesem Fall als eine Variable (eine String von Symbolen).
(1) Wenn xI ein Satz ist, dann auch xIU.
(2) Wenn Mx ein Satz ist, dann auch Mxx.
(3) In jedem Satz kann III durch U ersetzt werden.
(4) UU kann aus jedem Satz weggelassen werden.
Typografische Regeln:
Typografische Regeln sind die Regeln, die in einer leicht verständlichen Form der Textmanipulation sind.
(1) "Füge an den rechten Teil eines Satzes ein U an, wenn dieser mit I endet."
(2) "Kopiere den Teil eines Satzes, der rechts neben M steht und füge ihn am rechten Ende an."
(3) "Ersetze den Teil eines Satzes durch U, welcher drei aufeinanderfolgende I's besitzt."
(4) "Lösche den Teil eines Satzes, welcher aus zwei aufeinanderfolgende U's besteht."
Verwendung der typografischen Regeln:
MI $\rightarrow$ MIU $\rightarrow$ MIUIU $\rightarrow$ MIUIUIUIU ... [1,2,2]
MI $\rightarrow$ MII $\rightarrow$ MIIII $\rightarrow$ MUI $\rightarrow$ MUIUI $\rightarrow$ MUIUIUIUI $\rightarrow$ ... [2,2,3,2,2]
$\hspace{20mm}\rightarrow$ MIU $\rightarrow$ ... [2,1]
$\hspace{20mm}\rightarrow$ MIIIIIIII $\rightarrow$ MUUII$\rightarrow$ MII$\rightarrow$ ... [3,4]
Lösung des MU-Rätsels
Ist MU ein Satz des MIU-Systems?
Die Lösung lautet nein. Unabhängig von Anzahl der verwendeten Regeln ist es unmöglich den String MI in den String MU zu wechseln.
Außerdem wird deutlich, dass die Anzahl der Is im Wort relevant ist, da zur Erlangung des Wortes MU eine durch 3 teilbare Anzahl an Is vorhanden sein muss, um sie mit der Regel 3 ersetzen zu können. Es wäre also wünschenswert eine durch 3 teilbare Anzahl an Is zu erzeugen.
Die Ausgangssituation sieht vor, dass es genau ein I gibt - eine nicht durch 3 teilbare Anzahl. Die Betrachtung der Regeln 1 und 4 zeigt, dass sie die Anzahl der Is nicht verändert. Sie können für die weitere Betrachtung also ignoriert werden.
Regel 2 verdoppelt die Zeichenkette nach dem M. Das heißt, dass sie also die Anzahl der vorhandenen Is verdoppelt. Damit nun aber eine durch 3 teilbare Anzahl an Is durch Regel 2 erzeugt werden kann, muss vorher schon eine durch 3 teilbare Anzahl vorhanden sein.
Ähnlich verhält es sich bei Regel 3. Um eine durch 3 teilbare Anzahl von Is durch Anwendung dieser Regel zu erhalten, also auch 0, muss es vorher eine durch 3 teilbare Anzahl vorhanden sein.
Es wird also deutlich, dass keine durch 3 teilbare Anzahl von I erzeugt werden kann, was auch die Begründung zur Lösung des MU-Rätsels liefert:
MU ist kein Satz des MIU-Systems.
Beispiel für Turingmaschine
- TM Beispiel aus dem Buch EAGLE-STARTHILFE Berechenbarkeitstheorie, C. Wagenknecht, Seite 66
- TM berechnet v : n $\rightarrow$ 2n
- TM Definition : M = ({q0,q1,q2,q3,q4,q5,q6}, {1}, {$$,1}, delta, q0, $, {q6})
- (alle möglichen Zustände, Eingabewort, alle Zeichen auf dem Band, Überführungsfunktion, Anfangszustand, Vorbelegungszeichen, Endzustand)
- Wie funktioniert eine TM?
