s3adkuce
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:
(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.
Relation
Wiederholen Sie die Eigenschaften von Äquivalenzrelationen und geben Sie ein Beispiel an.
Eine Äquivalenzrelation teilt eine Menge restlos in nichtleere und disjunkte (elementfremde) Untermengen, Äquivalenzklassen genannt.
Sie besitzt dabei folgende eigenschaften:
- Reflexivität: a\sim a
- Jedes Objekt ist zu sich selbst äquivalent.
- Symmetrie: a\sim b \ \Rightarrow\ b\sim a
- Wenn a zu b äquivalent ist, dann ist auch b äquivalent zu a (und umgekehrt).
- Transitivität: a\sim b\ \mathrm{und}\ b\sim c\ \Rightarrow\ a\sim c
- Wenn a zu b äquivalent und b zu c äquivalent ist, dann ist a äquivalent zu c.
Beispiel für eine Äquivalenzrelation
Der Fahrplan für Straßenbahnen in einer Stadt.
- reflexiv:
- Von Haltestelle A kommt man zu Haltestelle A. (Weil man schon da ist)
- symmetrisch:
- Wenn man von Haltestelle A zu Haltestelle B kommt, dann kommt man auch von Haltestelle B zu Haltestelle A. (Es gibt praktisch eine Verbindung in beide Richtungen)
- transitiv:
- Wenn man von Haltestelle A zu Haltestelle B kommt und wenn man von Haltestelle B zu Haltestelle C kommt, dann kann man sagen, dass man von Haltestelle A zu Haltestelle C kommt.