Wann sollte ich einen Widerspruchsbeweis verwenden?

Er ist eine gute Wahl, wenn die Aussage behauptet, dass etwas nicht existiert (keine größte Zahl, kein Bruch gleich $\sqrt{2}$), oder dass es unendlich viele von etwas gibt. Dann liefert dir die Annahme des Gegenteils ein konkretes Objekt, mit dem du arbeiten kannst.

Ist ein Widerspruchsbeweis dasselbe wie ein Beweis durch Kontraposition?

Nein. Ein Beweis durch Kontraposition zeigt "wenn nicht q, dann nicht p" direkt und endet bei "nicht p". Ein Widerspruchsbeweis nimmt an, dass die Aussage falsch ist, und darf bei irgendeiner Unmöglichkeit enden. Jeder Beweis durch Kontraposition lässt sich als Widerspruchsbeweis umschreiben, aber nicht jeder Widerspruchsbeweis ist ein Beweis durch Kontraposition.

Was bedeutet q. e. d., und was ist "reductio ad absurdum"?

q. e. d. (quod erat demonstrandum, "was zu beweisen war", auf Deutsch auch w. z. b. w.) markiert das Ende eines Beweises. Reductio ad absurdum, "Zurückführung auf das Absurde", ist der lateinische Name des Widerspruchsbeweises.

Lehrermaterialien

Widerspruchsbeweis

Lerne, eine Aussage zu beweisen, indem du annimmst, dass sie falsch ist, und zeigst, dass daraus etwas Unmögliches folgt, mit klassischen Beweisen wie der Irrationalität der Wurzel aus 2.

Fortgeschritten30 MinLektion

Arbeitsblatt zum Drucken

Definition

Ein Widerspruchsbeweis (auch indirekter Beweis) beweist eine Aussage

P

auf einem Umweg: Du nimmst an, dass

P

falsch ist, und zeigst, dass diese Annahme zu etwas Unmöglichem führt. Da korrektes Schließen aus einer wahren Annahme niemals etwas Unmögliches liefern kann, muss die Annahme falsch sein, also ist

P

wahr.

Die Methode hat vier Schritte:

1.Negation annehmen: Die erste Zeile lautet "Angenommen, $\neg P$ gilt (Annahme für den Widerspruch)."
2.Schließen mit Definitionen und bekannten Tatsachen, genau wie bei einem direkten Beweis.
3.Einen Widerspruch erreichen: Eine Aussage $Q$ und ihr Gegenteil $\neg Q$ gelten beide (zum Beispiel " $a/b$ ist vollständig gekürzt" und " $a$ und $b$ sind beide gerade"), oder eine bekannte Tatsache wird verletzt (wie $1 = 0$ ).
4.Folgern: Die Annahme $\neg P$ war falsch, also ist $P$ wahr.

In Symbolen: Wenn

\neg P \Rightarrow (Q \land \neg Q)

, dann gilt

P

. Das funktioniert, weil

Q \land \neg Q

immer falsch ist. Wähle in der interaktiven Wahrheitstabelle weiter unten auf dieser Seite NICHT, um zu sehen, dass

\neg P

immer das Gegenteil von

P

ist, und dann UND: In den zwei Zeilen, in denen

Q

das Gegenteil von

P

ist (F, W und W, F), ist

P \land Q

gleich F. Also ist

P \land \neg P

in jeder Zeile F (W = wahr, F = falsch).

Die Negation richtig aufschreiben ist die wichtigste Zeile des Beweises:

" $\sqrt{2}$ ist irrational" wird zu " $\sqrt{2}$ ist rational"
"Es gibt unendlich viele Primzahlen" wird zu "Es gibt nur endlich viele Primzahlen"
"Es gibt keine größte gerade Zahl" wird zu "Es gibt eine größte gerade Zahl"
" $x > 5$ " wird zu " $x \le 5$ "
"Jedes ... hat die Eigenschaft" wird zu "Mindestens ein ... hat die Eigenschaft nicht"

Widerspruch oder Kontraposition? Ein Beweis durch Kontraposition (vorige Lektion) beweist "wenn

p

, dann

q

", indem er nur

\neg q

annimmt und auf ein festes Ziel hinarbeitet:

\neg p

. Ein Widerspruchsbeweis nimmt an, dass die ganze Aussage falsch ist (bei einer Wenn-dann-Aussage:

p

und

\neg q

zusammen), und darf bei irgendeiner Unmöglichkeit enden.

Probier es gleich aus

Du willst durch Widerspruch beweisen, dass

\sqrt{3}

irrational ist. Wie lautet die richtige erste Zeile?

Lösungsbeispiele

Beweise, dass es keine größte gerade Zahl gibt.

Schreibe die Negation als erste Zeile

Angenommen, es gibt eine größte gerade Zahl $N$ → Annahme: $N$ ist gerade und $N \ge$ jede gerade Zahl

Verwende die Definition von gerade

$N = 2k$ für eine ganze Zahl $k$ , also $N + 2 = 2k + 2 = 2(k + 1)$ → $N + 2$ ist gerade

Vergleiche die beiden Zahlen

$N + 2 > N$ → Es gibt eine gerade Zahl, die größer als $N$ ist

Erkenne den Widerspruch und folgere

$N$ ist die größte gerade Zahl, aber $N + 2$ ist eine größere gerade Zahl → Die Annahme ist falsch

Antwort: Die Annahme führt zu einem Widerspruch, also gibt es keine größte gerade Zahl. q. e. d.

Häufige Fehler

"Es gibt unendlich viele Primzahlen" verneinen als "Es gibt keine Primzahlen"

Warum es falsch ist: Das Gegenteil von "unendlich viele" ist nicht "keine". Die Negation muss jeden Fall abdecken, in dem die Aussage nicht gilt, und das ist "nur endlich viele".

Richtig: Nimm an: "Es gibt nur endlich viele Primzahlen". Ebenso ist die Negation von "jede Primzahl ist ungerade" die Aussage "mindestens eine Primzahl ist nicht ungerade", nicht "jede Primzahl ist gerade".

$x > 5$ verneinen als $x < 5$

Warum es falsch ist: Der Fall $x = 5$ wird vergessen. Wenn der Beweis nur $x < 5$ ausschließt, ist die Zahl $5$ noch möglich.

Richtig: Die Negation von $x > 5$ ist $x \le 5$ , und die Negation von $x \ge 5$ ist $x < 5$ .

"Vollständig gekürzt" im Beweis vergessen, dass $\sqrt{2}$ irrational ist

Warum es falsch ist: Ohne diese Bedingung ist es gar kein Widerspruch, dass $a$ und $b$ beide gerade sind: $\frac{4}{2}$ hat einen geraden Zähler und Nenner.

Richtig: Schreibe $\sqrt{2} = \frac{a}{b}$ vollständig gekürzt. Jeder Bruch lässt sich kürzen, das kostet also nichts, und genau diese Tatsache wird später verletzt.

Ein überraschendes Ergebnis für einen Widerspruch halten

Warum es falsch ist: Ein Ergebnis, das seltsam aussieht (eine sehr große Zahl, ein unerwarteter Bruch), ist nicht unmöglich. Ein Widerspruch muss mit der Annahme oder mit einer bekannten Tatsache kollidieren.

Richtig: Nenne die beiden Aussagen, die sich widersprechen, zum Beispiel " $r$ ist die kleinste" und " $\frac{r}{2} < r$ ", und schreibe dann die Folgerung auf.

Interaktive Visualisierung

Wahrheitstabelle

Operator wählen

P ∧ Q

P	Q	P ∧ Q
F	F	F
F	W	F
W	F	F
W	W	W

W= WahrF= Falsch

Interaktiver Sandkasten

Ausdrucksrechner

Probiere diese:

Verlauf

Noch keine Berechnungen

Übungsaufgaben

18 Aufgaben

Aufgabe 1 von 18

Einfach

Du willst durch Widerspruch beweisen, dass $\sqrt{3}$ irrational ist. Wie lautet die richtige erste Zeile?

Warum es wichtig ist

Einige der berühmtesten Ergebnisse der Mathematik lassen sich am bequemsten durch Widerspruch beweisen:

Irrationale Zahlen: Die Griechen bewiesen vor etwa 2.500 Jahren, dass $\sqrt{2}$ kein Bruch ist, und das veränderte das Denken über Zahlen
Primzahlen: Euklids Beweis, dass die Primzahlen nie ausgehen, wird bis heute in jeder Zahlentheorie-Vorlesung verwendet
Informatik: Das Schubfachprinzip erklärt, warum zwei Dateien denselben kurzen Fingerabdruck bekommen können (eine Hash-Kollision) und warum keine Kompression jede Datei verkleinern kann
Rätsel: Ein Sudoku lösen heißt oft: "Wäre in diesem Feld eine 5, stünden zwei 5en in derselben Zeile, also ist es keine 5"
Alltagsdenken: Detektive und Ärzte schließen Möglichkeiten aus, indem sie zeigen, dass sie zu etwas Unmöglichem führen

Wann immer eine Aussage behauptet, dass etwas NICHT existiert (keine größte Zahl, kein Bruch gleich

\sqrt{2}

), ist der Widerspruchsbeweis meist das natürliche Werkzeug.

Anwendungen im echten Leben

Passende Socken im Dunkeln

Das Schubfachprinzip, durch Widerspruch bewiesen, sagt dir, wie viele Dinge du mindestens brauchst, damit sich eines garantiert wiederholt.

Beispiel:

In einer Schublade liegen schwarze, weiße und graue Socken. Könntest du 4 Socken in lauter verschiedenen Farben nehmen, bräuchtest du 4 Farben, es gibt aber nur 3. Also enthalten 4 Socken immer ein passendes Paar.

1Probiere es selbst

In einer Schublade liegen einzelne Socken in 5 verschiedenen Farben, und es ist zu dunkel, um sie zu sehen.

Wie viele Socken musst du nehmen, um sicher zwei derselben Farbe zu haben?

Schritt 1: Schreibe den mathematischen Ausdruck

Anzahl der Farben plus eins:

Hash-Kollisionen in der Informatik

Computer geben Dateien kurze Codes, sogenannte Hashes. Da es mehr mögliche Dateien als Codes gibt, müssen zwei verschiedene Dateien manchmal denselben Code teilen.

Beispiel:

Ein System gibt jeder Datei einen Code von 00 bis 99. Wären bei 101 Dateien alle Codes verschieden, bräuchte man 101 Codes, es gibt aber nur 100, also teilen zwei Dateien einen Code.

2Probiere es selbst

Ein System gibt jeder Datei einen dreistelligen Code von 000 bis 999.

Wie viele Dateien garantieren, dass zwei davon denselben Code haben?

Schritt 1: Schreibe den mathematischen Ausdruck

Anzahl der Codes plus eins:

Warum ein Taschenrechner nie die exakte Wurzel aus 2 zeigt

Weil $\sqrt{2}$ irrational ist, endet ihre Dezimaldarstellung nie und wiederholt sich nie. Jede Dezimalzahl auf dem Display ist nur eine Näherung, und das müssen Ingenieure beim Berechnen von Diagonalen beachten.

Beispiel:

Eine quadratische Fliese mit 1 m Seitenlänge hat die Diagonale $\sqrt{2} \approx 1{,}4142$ m. Der Wert 1,4142 ist nah dran, aber nicht exakt.

3Probiere es selbst

Ein Taschenrechner zeigt $\sqrt{2} \approx 1{,}4142$ .

Prüfe, dass 1,4142 nicht genau die Wurzel aus 2 ist.

Schritt 1: Schreibe den mathematischen Ausdruck

Quadriere die Dezimalzahl:

Wichtige Erkenntnisse

1Ein Widerspruchsbeweis nimmt an, dass die Aussage falsch ist, und zeigt, dass daraus etwas Unmögliches folgt
2Die erste Zeile ist die richtige Negation: "unendlich viele" wird zu "nur endlich viele", $x > 5$ wird zu $x \le 5$ , "jedes" wird zu "mindestens ein ... nicht"
3Ein Widerspruch sind zwei Aussagen, die nicht beide wahr sein können, wie $Q \land \neg Q$ , das in jeder Zeile einer Wahrheitstabelle falsch ist
4Klassische Ergebnisse, die so bewiesen werden: $\sqrt{2}$ ist irrational, es gibt unendlich viele Primzahlen, keine größte gerade Zahl und keine kleinste positive rationale Zahl
5Das Schubfachprinzip: Kommen mehr als $n$ Dinge in $n$ Schubfächer, enthält ein Schubfach mindestens zwei Dinge
6Der Beweis durch Kontraposition zeigt "wenn nicht q, dann nicht p" direkt, während der Widerspruchsbeweis annimmt, dass die ganze Aussage falsch ist, und nach irgendeiner Unmöglichkeit sucht

Häufig gestellte Fragen

Korrektes Schließen aus wahren Aussagen liefert immer nur wahre Aussagen. Erreichen wir etwas Unmögliches, war mindestens ein Ausgangspunkt falsch, und der einzige Ausgangspunkt, den wir selbst hinzugefügt haben, war die Annahme

\neg P

. Also ist

\neg P

falsch und

P

wahr.

Glossar

Widerspruchsbeweis: Ein Beweis, der annimmt, dass die Aussage falsch ist, und daraus etwas Unmögliches ableitet, sodass die Aussage wahr sein muss (auch indirekter Beweis)
Widerspruch: Zwei Aussagen, die nicht beide wahr sein können, wie $Q$ und $\neg Q$ ; die Aussage $Q \land \neg Q$ ist immer falsch
Negation: Das Gegenteil einer Aussage, geschrieben $\neg P$ ; sie ist genau dann wahr, wenn $P$ falsch ist
Irrationale Zahl: Eine reelle Zahl, die sich nicht als Bruch $\frac{a}{b}$ ganzer Zahlen schreiben lässt, zum Beispiel $\sqrt{2}$
Schubfachprinzip: Werden mehr als $n$ Dinge auf $n$ Schubfächer verteilt, enthält mindestens ein Schubfach zwei oder mehr Dinge

Formelkarte

Widerspruchsbeweis

\neg P \Rightarrow (Q \land \neg Q) \;\text{ also }\; P

Führt die Annahme nicht P zu einem Widerspruch, dann ist P wahr

Ein Widerspruch ist immer falsch

Q \land \neg Q = F

Eine Aussage und ihre Negation können nie beide wahr sein

Schubfachprinzip

n + 1 \text{ Dinge in } n \text{ Schubfächern}

Mindestens ein Schubfach bekommt zwei oder mehr Dinge

Mehr zu diesem Thema

Definition

Lösungsbeispiele

Häufige Fehler

Interaktive Visualisierung

Wahrheitstabelle

Interaktiver Sandkasten

Ausdrucksrechner

Verlauf

Übungsaufgaben

Warum es wichtig ist

Anwendungen im echten Leben

Passende Socken im Dunkeln

Hash-Kollisionen in der Informatik

Warum ein Taschenrechner nie die exakte Wurzel aus 2 zeigt

Wichtige Erkenntnisse

Häufig gestellte Fragen

Glossar

Formelkarte

Widerspruchsbeweis

Ein Widerspruch ist immer falsch

Schubfachprinzip

Mehr zu diesem Thema

Einführung in mathematische Beweise

Direkter Beweis

Zwei-Spalten-Beweise

Beweise in Textform