Widerspruchsbeweis: √2 ist nicht rational

Worum es geht

Skript Teil 2, Folien 12 und 13: Widerspruchsbeweis.

Zu zeigen ist wieder $A \Rightarrow B$ . Diesmal nimmt man $A$ und das Gegenteil von $B$ zugleich an. Führt das zu einer falschen Aussage, kann das Gegenteil von $B$ nicht stimmen.

So gehen wir vor:

Die Regel und ihre Wahrheitstafel.
Was eine falsche Aussage mit der Annahme zu tun hat.
Wie der Widerspruchsbeweis mit der Kontraposition zusammenhängt.
Was man bei Sätzen ohne Voraussetzung macht.
Der Beweis: $\sqrt{2}$ ist keine rationale Zahl.

Die Annahme A ∧ ¬B

Skript · Widerspruchsbeweis

Der Widerspruchsbeweis basiert auf der Tautologie

\big((A \land \neg B) \Rightarrow 0\big) \Rightarrow (A \Rightarrow B)

Man nimmt zweierlei an: Die Voraussetzung $A$ gilt, und die Behauptung $B$ gilt nicht. Zusammen ist das $A \land \neg B$ . Das Skript nennt diesen Ausdruck $p$ .

Die $0$ in der Regel steht für eine Aussage, die sicher falsch ist, etwa $1 = 2$ . Eine solche Aussage heißt Widerspruch.

Aus p folgt etwas Falsches

Skript

Eine Aussage der Form $p \Rightarrow 0$ ist genau dann wahr, wenn $p$ falsch ist. Es genügt also eine falsche Aussage aus der Hypothese $A \land \neg B$ herzuleiten.

Wann ist $p \Rightarrow 0$ wahr? Eine Implikation ist nur bei „wahr ⇒ falsch“ falsch. Rechts ist die Folgerung immer $0$ . Also ist $p \Rightarrow 0$ genau dann wahr, wenn $p$ falsch ist.

Für den Beweis heißt das: Leitet man aus $p$ eine falsche Aussage her, ist $p$ falsch. Man muss $p$ also nicht selbst widerlegen. Es reicht, einen Widerspruch zu finden.

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

p \Rightarrow q

ist nur falsch, wenn

p

wahr und

q

falsch ist.

Schritt 0Worum es geht

Schritt 1Die Annahme A ∧ ¬B

Schritt 2Aus p folgt etwas Falsches

Wahrheitstafel

Abbildung 1Wahrheitstafel

Worum es geht

Die Annahme A ∧ ¬B

Aus p folgt etwas Falsches