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
Frage
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.
Die Implikation A ⇒ B beweisen wir nun durch Widerlegung ihrer Negation A∧¬B.
Es sei also p eine Primzahl und √p eine rationale Zahl.
Demnach lässt sich √p als Bruch m/n mit teilerfremden natürlichen Zahlen m, n
schreiben.
Das ergibt die Gleichung m/n = √p, aus der aber
mit wenigen 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!
