Beweis durch Kontraposition

Schreibe bei jeder Aufgabe deinen Lösungsweg auf.

1.
Welche Aussage ist die Kontraposition von "Wenn $n^2$ gerade ist, dann ist $n$ gerade"?
1. a)Wenn $n^2$ ungerade ist, dann ist $n$ ungerade
2. b)Wenn $n$ ungerade ist, dann ist $n^2$ gerade
3. c)Wenn $n$ ungerade ist, dann ist $n^2$ ungerade
4. d)Wenn $n$ gerade ist, dann ist $n^2$ gerade
Lösung: Wenn $n$ ungerade ist, dann ist $n^2$ ungerade
Die Kontraposition von $p \to q$ ist $\neg q \to \neg p$ : "wenn $n$ ungerade ist, dann ist $n^2$ ungerade". Die erste Antwort ist die Umkehrung, die zweite die Inversion, die letzte hat damit nichts zu tun.
2.
Du willst "Wenn $xy$ ungerade ist, dann sind $x$ und $y$ beide ungerade" durch Kontraposition beweisen. Was nimmst du am Anfang an?
1. a) $x$ und $y$ sind beide ungerade
2. b) $x$ und $y$ sind beide gerade
3. c) $x$ ist gerade oder $y$ ist gerade
4. d) $xy$ ist gerade
Lösung: $x$ ist gerade oder $y$ ist gerade
Die Behauptung " $x$ und $y$ sind ungerade" ist falsch, sobald eine Zahl gerade ist, also lautet ihre Verneinung " $x$ ist gerade oder $y$ ist gerade". " $xy$ ist gerade" musst du erst beweisen, und "beide gerade" lässt Fälle aus.
3.
Was ist die Verneinung von " $x \geq 5$ oder $y \geq 5$ "?
1. a) $x \leq 5$ und $y \leq 5$
2. b) $x < 5$ oder $y < 5$
3. c) $x < 5$ und $y < 5$
4. d) $x > 5$ und $y > 5$
Lösung: $x < 5$ und $y < 5$
"Nicht ( $a$ oder $b$ )" heißt "nicht $a$ und nicht $b$ ", und die Verneinung von $x \geq 5$ ist $x < 5$ . Also lautet die Antwort " $x < 5$ und $y < 5$ ". Mit $\leq$ wäre der Wert 5 fälschlich enthalten.
4.
Bei einem Beweis von $p \to q$ durch Kontraposition nimmst du zuerst $\neg q$ an. Wo musst du am Ende ankommen?
1. a) $\neg p$
2. b) $p$ und $\neg q$ gleichzeitig
3. c) $q$
4. d)Irgendeinen Widerspruch
Lösung: $\neg p$
Ein Beweis durch Kontraposition beweist $\neg q \to \neg p$ , also musst du von $\neg q$ aus genau bei $\neg p$ ankommen. Irgendeinen Widerspruch zu suchen oder $p$ und $\neg q$ zusammen anzunehmen, ist ein Widerspruchsbeweis.
5.
Bei welcher Aussage ist ein Beweis durch Kontraposition deutlich besser als ein direkter Beweis?
1. a)Wenn $n$ gerade ist, dann ist $n^2$ gerade
2. b)Wenn $a$ und $b$ gerade sind, dann ist $a + b$ gerade
3. c)Wenn $5n + 1$ gerade ist, dann ist $n$ ungerade
4. d)Wenn $n$ ungerade ist, dann ist $n + 1$ gerade
Lösung: Wenn $5n + 1$ gerade ist, dann ist $n$ ungerade
Bei den anderen drei Aussagen ist die Voraussetzung konkret ( $n = 2k$ , $a = 2m$ und $b = 2j$ , $n = 2k + 1$ ), ein direkter Beweis geht also schnell. " $5n + 1$ ist gerade" sagt wenig über $n$ , aber die Kontraposition ist leicht: Ist $n = 2k$ , dann ist $5n + 1 = 10k + 1 = 2(5k) + 1$ ungerade.
6.
Schau in der Wahrheitstabelle auf die Zeile, in der $p$ wahr und $q$ falsch ist. Welchen Wert hat $\neg q \to \neg p$ in dieser Zeile? Gib 1 für wahr und 0 für falsch ein.
Lösung: 0
Mit $p$ wahr und $q$ falsch gilt: $\neg q$ ist wahr und $\neg p$ ist falsch, also ist $\neg q \to \neg p$ falsch (0). Genau in dieser Zeile ist auch $p \to q$ falsch: Die beiden Spalten stimmen überein.
7.
Beweis durch Kontraposition von "wenn $n^2$ ungerade ist, dann ist $n$ ungerade": Nimm $n = 2k$ an, also $n^2 = 4k^2 = 2(2k^2)$ . Wie viel ist $2k^2$ für $k = 7$ ?
Lösung: 98
$2k^2 = 2 \cdot 49 = 98$ . Probe: $n = 14$ und $n^2 = 196 = 2 \cdot 98$ , also gerade, wie es die Kontraposition sagt.
8.
Im Beweis, dass ein ungerades $n$ ein ungerades $n^2$ liefert, schreiben wir $n = 2k + 1$ und $n^2 = 2(2k^2 + 2k) + 1$ . Für $n = 9$ ist $k = 4$ . Wie viel ist $2k^2 + 2k$ ?
Lösung: 40
$2k^2 + 2k = 32 + 8 = 40$ . Probe: $2 \cdot 40 + 1 = 81 = 9^2$ , eine ungerade Zahl.
9.
Die Kontraposition von "wenn $x + y \geq 10$ , dann $x \geq 5$ oder $y \geq 5$ " sagt: Wenn $x < 5$ und $y < 5$ , dann $x + y < 10$ . Was ist für ganze Zahlen $x$ und $y$ mit $x < 5$ und $y < 5$ der größtmögliche Wert von $x + y$ ?
Lösung: 8
Die größten Werte sind $x = 4$ und $y = 4$ , also $x + y = 8$ , und das ist kleiner als 10, wie die Kontraposition vorhersagt.
10.
Um "wenn $n^2 - 6n + 5$ gerade ist, dann ist $n$ ungerade" durch Kontraposition zu beweisen, nimm $n = 2k$ an. Dann ist $n^2 - 6n + 5 = 2(2k^2 - 6k + 2) + 1$ . Wie viel ist $2k^2 - 6k + 2$ für $k = 3$ ?
Lösung: 2
$2k^2 - 6k + 2 = 18 - 18 + 2 = 2$ . Probe: $n = 6$ ergibt $36 - 36 + 5 = 5 = 2 \cdot 2 + 1$ , eine ungerade Zahl.
11.
Prüfe die Kontraposition von "wenn $n^2$ gerade ist, dann ist $n$ gerade" mit der ungeraden Zahl $n = 11$ .
Lösung: $121 = 2 \cdot 60 + 1$
1. Wie viel ist $n^2$ ? 121
2. Schreibe $121 = 2m + 1$ . Wie viel ist $m$ ? 60
3. Welcher Rest bleibt, wenn man $121$ durch 2 teilt? 1
12.
Beweise "wenn $3n + 2$ ungerade ist, dann ist $n$ ungerade" durch Kontraposition und prüfe es mit $k = 4$ .
Lösung: 13
1. Nimm an, $n$ ist gerade: $n = 2k$ . Wie viel ist $n$ für $k = 4$ ? 8
2. Wie viel ist $3n + 2$ ? 26
3. Allgemein ist $3n + 2 = 6k + 2 = 2(3k + 1)$ . Wie viel ist $3k + 1$ für $k = 4$ ? 13
13.
Kontraposition von "wenn $xy$ ungerade ist, dann sind $x$ und $y$ ungerade", Fall " $x$ ist gerade". Verfolge den Beweis mit $x = 6$ und $y = 7$ .
Lösung: 21
1. Schreibe $x = 2k$ . Wie viel ist $k$ ? 3
2. Wie viel ist $xy$ ? 42
3. Der Beweis schreibt $xy = 2(ky)$ . Wie viel ist $ky$ ? 21
14.
Vergleiche die Spalten $p \to q$ und $\neg q \to \neg p$ in der Wahrheitstabelle mit 4 Zeilen.
Lösung: 0
1. In wie vielen der 4 Zeilen ist $p \to q$ wahr? 3
2. In wie vielen Zeilen ist $\neg q \to \neg p$ wahr? 3
3. In wie vielen Zeilen haben die beiden Spalten verschiedene Werte? 0
15.
Beweise durch Kontraposition: Für reelle Zahlen $x$ , $y$ , $z$ gilt: Wenn $x + y + z \geq 30$ , dann ist $x \geq 10$ oder $y \geq 10$ oder $z \geq 10$ .
Lösung: $x + y + z < 30$
1. Die verneinte Behauptung lautet " $x < 10$ und $y < 10$ und $z < 10$ ". Wie viele Ungleichungen nimmst du an? 3
2. Addiere die Ungleichungen: $x + y + z$ ist kleiner als welche Zahl? 30
3. Kann dann $x + y + z \geq 30$ gelten? Gib 1 für ja und 0 für nein ein. 0
16.
Aussage: Wenn $n^2 - 6n + 5$ gerade ist, dann ist $n$ ungerade. Prüfe die Kontraposition mit $n = 2k$ und $k = 5$ .
Lösung: 22
1. Wie viel ist $n$ ? 10
2. Wie viel ist $n^2 - 6n + 5$ ? 45
3. Schreibe das Ergebnis als $2m + 1$ . Wie viel ist $m$ ? 22
17.
Beweise durch Kontraposition: Wenn 7 Zahlen eine Summe $S$ größer als 63 haben, dann ist mindestens eine von ihnen größer als 9.
Lösung: $S \leq 63$
1. Verneinte Behauptung: Jede Zahl ist höchstens welcher Wert? 9
2. Wie groß ist die größtmögliche Summe von 7 solchen Zahlen? 63
3. Kann die Summe dann größer als 63 sein? Gib 1 für ja und 0 für nein ein. 0
18.
Beweise "wenn $n^2$ nicht durch 3 teilbar ist, dann ist $n$ nicht durch 3 teilbar" durch Kontraposition und prüfe es mit $k = 7$ .
Lösung: 147
1. Nimm an, $n$ ist durch 3 teilbar: $n = 3k$ . Wie viel ist $n$ für $k = 7$ ? 21
2. Wie viel ist $n^2$ ? 441
3. Allgemein ist $n^2 = 9k^2 = 3(3k^2)$ . Wie viel ist $3k^2$ für $k = 7$ ? 147