Startseite Mathematik-Online        Themenliste


Mathematik-Online, Beweistechniken


Eine Aussage ist genau dann wahr, wenn ihre Negation falsch ist. Hierauf basiert der Widerspruchsbeweis (reductio ad absurdum): Man negiert die zu zeigende Aussage und leitet daraus eine offenkundig falsche Aussage ab. Somit lässt sich etwa die Implikation A ⇒ B beweisen, indem man ihre Negation A∧¬B widerlegt. Das ergibt sich unmittelbar aus den Grundregeln der Logik:

Widerspruchsbeweis

Fragestellung
Wie funktioniert der indirekte Beweis der Aussage A ⇒ B ?

Antwort
Nach dem Satz vom ausgeschlossenen Dritten (tertium non datur) ist eine Aussage entweder wahr oder falsch. Die Implikation A ⇒ B ist somit genau dann wahr, wenn ihre Negation ¬(A ⇒ B) falsch ist.
Per Wahrheitstafel lässt sich leicht zeigen, dass die Implikation A ⇒ B logisch äquivalent zu der Aussage ¬A∨B ist. Folglich ist ¬(A ⇒ B) logisch äquivalent zu ¬(¬A∨B) und daher logisch äquivalent zu A∧¬B. Die Implikation A ⇒ B lässt sich damit durch Widerlegung der Aussage A∧¬B beweisen.


Beispiel
Wir zeigen per Widerspruchsbeweis: Für jede Primzahl p ist p keine rationale Zahl. Zuerst zerlegen wir diese Behauptung in die beiden Aussagen A: p ist eine Primzahl und B: p ist keine rationale Zahl. Damit erhalten wir die explizite Implikation A ⇒ B, die wir nun durch Widerlegung ihrer Negation A∧¬B beweisen.
Es sei also p eine Primzahl und wir nehmen an, dass p eine rationale Zahl ist. Demnach lässt sich p als Bruch m/n mit teilerfremden natürlichen Zahlen m, n schreiben. Wir erhalten somit die Gleichung m/n = p, aus der aber mit wenigen elementaren Umformungen folgt, dass m und n jeweils durch p teilbar sind, weil nämlich p eine Primzahl ist. Daher können m und n nicht teilerfremd sein - Widerspruch!
Themenliste vollständige Induktion