Äquivalenzbeweis und Ringschluss

Worum es geht

Skript Teil 2, Folien 14 und 15: Äquivalenzbeweis und Ringschluss.

$A \Leftrightarrow B$ sagt: $A$ und $B$ sind entweder beide wahr oder beide falsch. Das ist mehr als eine Implikation. Darum braucht der Beweis auch mehr als einen direkten Beweis.

So gehen wir vor:

Warum eine Äquivalenz aus zwei Implikationen besteht.
Das Lemma „ $a$ gerade genau dann, wenn $a^2$ gerade“: erst die Hinrichtung, dann die Rückrichtung.
Der Ringschluss für drei und mehr Aussagen.

Eine Äquivalenz sind zwei Implikationen

Skript · Äquivalenzbeweis

Beim Äquivalenzbeweis zeigen wir die Gültigkeit von Aussagen der Form $A \Leftrightarrow B$ . Der Beweis basiert auf der Äquivalenz von

(A \Leftrightarrow B) \Leftrightarrow \big((A \Rightarrow B) \land (B \Rightarrow A)\big)

und erfolgt durch 2 direkte Beweise:

(⇒) zu zeigen $A \Rightarrow B$ (Hinrichtung)
(⇐) zu zeigen $B \Rightarrow A$ (Rückrichtung)

$A \Leftrightarrow B$ ist genau dann wahr, wenn $A \Rightarrow B$ und $B \Rightarrow A$ beide wahr sind. Der Ausdruck im Kasten sagt genau das. Man beweist darum zwei Implikationen, jede für sich.

Das Skript spricht von „2 direkten Beweisen“. Gemeint ist: Jede Richtung wird als eigene Implikation bewiesen. Mit welchem Verfahren, ist frei. Gleich läuft die Rückrichtung zum Beispiel über die Kontraposition.

Die Richtung $A \Rightarrow B$ heißt Hinrichtung, kurz (⇒). Die Richtung $B \Rightarrow A$ heißt Rückrichtung, kurz (⇐).

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

A \Leftrightarrow B

ist wahr, wenn

A

und

B

denselben Wahrheitswert haben; sie ist wie eine Implikation in beide Richtungen.

Hinrichtung: a gerade, also a² gerade

Satz · Lemma

$a$ ist gerade genau dann, wenn $a^2$ gerade ist.

(⇒) direkter Beweis

a = 2k \ \Rightarrow\ a^2 = (2k)^2 = 4k^2 = 2 \cdot (2k^2), \quad 2k^2 \in \mathbb{Z} \ \Rightarrow\ a^2 \text{ gerade}

Ein Lemma ist ein kleiner Hilfssatz. Hier ist $A$ „ $a$ ist gerade“ und $B$ „ $a^2$ ist gerade“, für eine ganze Zahl $a$ .

Für die Hinrichtung nimmt man $A$ als wahr an. Eine ganze Zahl ist gerade, wenn sie sich als $2k$ mit einer ganzen Zahl $k$ schreiben lässt. Quadrieren gibt $4k^2$ . Darin steckt eine 2, die man ausklammert.

Übrig bleibt $2k^2 = 2 \cdot k \cdot k$ . Das ist ein Produkt ganzer Zahlen, also selbst eine ganze Zahl. Damit hat $a^2$ die Form „2 mal ganze Zahl“ und ist gerade.

Probe mit $a = 6$ , also $k = 3$ : $2 \cdot (2 \cdot 9) = 36 = 6^2$ .

Aus Abschnitt 3 („Beweis durch Kontraposition“): Dort wurde dieselbe Rechnung schon geführt:

a = 2k

ergibt

a^2 = 2 \cdot 2k^2

, also ist

a^2

gerade.

Schritt 0Worum es geht

Schritt 1Eine Äquivalenz sind zwei Implikationen

Schritt 2Hinrichtung: a gerade, also a² gerade

Beweis

Abbildung 1Beweis

Worum es geht

Eine Äquivalenz sind zwei Implikationen

Hinrichtung: a gerade, also a² gerade