Beweis durch Kontraposition

Worum es geht

Skript Teil 2, Folie 11: Beweis durch Kontraposition.

Beim direkten Beweis geht man von $A$ nach $B$ . Beim Beweis durch Kontraposition geht man von $\neg B$ nach $\neg A$ . Das Zeichen $\neg$ heißt „nicht“. Erlaubt ist der Umweg, weil beide Implikationen logisch äquivalent sind: Sie haben dieselbe Wahrheitstafel.

Aus Teil 1, Abschnitt 3 („Wenn-dann, genau dann, XOR, NAND, NOR“): Die Implikation

A \Rightarrow B

ist nur falsch, wenn

A

wahr und

B

falsch ist.

So gehen wir vor:

Die Regel und ihre Wahrheitstafel.
Der Unterschied zur Umkehrung.
Ein Beweis: Ist $a^2$ ungerade, ist auch $a$ ungerade.

Die Regel

Skript · Kontraposition

Beim Beweis durch Kontraposition verwenden wir die Kontraposition (eine Tautologie)

(A \Rightarrow B) \Leftrightarrow (\neg B \Rightarrow \neg A)

um anstelle von $A \Rightarrow B$ die logisch äquivalente Aussage $\neg B \Rightarrow \neg A$ direkt zu beweisen.

Zwei Aussagen heißen logisch äquivalent, wenn sie für jede Belegung denselben Wahrheitswert haben. Die Kontraposition sagt: „Aus $A$ folgt $B$ “ ist logisch äquivalent zu „aus nicht $B$ folgt nicht $A$ “. Man vertauscht die beiden Seiten und verneint beide.

Ein Beispiel aus dem Alltag: „Wenn es regnet, ist die Straße nass.“ Logisch äquivalent ist: „Wenn die Straße nicht nass ist, regnet es nicht.“

Rechts sind $\neg B$ und $\neg A$ markiert: Aus ihnen baut man $\neg B \Rightarrow \neg A$ .

Aus Blatt 1, Aufgabe 2 („Tautologien nachweisen“): Dort wurde mit einer Wahrheitstafel gezeigt, dass die Kontraposition eine Tautologie ist, also für jede Belegung wahr.

Gleiche Spalten

Zeilen 1 bis 4

A \Rightarrow B:\ 1,\,1,\,0,\,1 \qquad \neg B \Rightarrow \neg A:\ 1,\,1,\,0,\,1

Zuerst die Spalte von $\neg B \Rightarrow \neg A$ , Zeile für Zeile. Es ist $\neg B$ : 1, 0, 1, 0 und $\neg A$ : 1, 1, 0, 0. Also rechnet man $1 \Rightarrow 1$ , $0 \Rightarrow 1$ , $1 \Rightarrow 0$ , $0 \Rightarrow 0$ . Das ergibt 1, 1, 0, 1.

$A \Rightarrow B$ hat dieselbe Spalte: $1, 1, 0, 1$ . Beide sind nur in Zeile 3 falsch, also bei $A = 1$ und $B = 0$ . Gleiche Spalten heißen: Die Aussagen sind logisch äquivalent. Wer eine beweist, hat auch die andere bewiesen.

Aus Teil 1, Abschnitt 3 („Wenn-dann, genau dann, XOR, NAND, NOR“):

p \Rightarrow q

ist nur bei

1 \Rightarrow 0

falsch, sonst wahr.

Aus Teil 1, Abschnitt 5 („Tautologie, Gleichheit und Rechengesetze“): Zwei Ausdrücke sind gleich, wenn ihre Spalten in der Wahrheitstafel gleich sind.

Schritt 0Worum es geht

Schritt 1Die Regel

Schritt 2Gleiche Spalten

Wahrheitstafel

Abbildung 1Wahrheitstafel

Worum es geht

Die Regel

Gleiche Spalten