Beispiel für einen Beweis mit Kontraposition Beweis mit Widerspruch
Eine Aussage ist genau dann wahr, wenn ihre Negation falsch ist. Hierauf basiert der Beweis mit Widerspruch. Man nennt den Widerspruchsbeweis auch Reductio ad absurdum, was soviel bedeutet wie die "Zurückführung auf das Ungereimte". Man negiert die zu zeigende Aussage und leitet daraus eine falsche Aussage ab.
Angewandt auf die Implikation \(A \implies B\) heißt das, dass man ihre Negation \(A \land \lnot B\) widerlegt.
Beweis mit Widerspruch:
Beim Beweis mit Widerspruch widerlegt man \(A \land \lnot B\), um die Implikation \(A \implies B\) zu zeigen.
Nehmen wir an, dass die Voraussetzung \(A\) und die Negation der Behauptung \(B\) gelten, also \(A\land\lnot B\). Dann können wir auf unterschiedliche Weise einen Widerspruch erzeugen:
\((1)\quad\) | Wir folgern, dass die Negation von \(A\) gilt, was ein Widerspruch zu \(A\) ist. Es gilt also die folgende Tautologie: \((A\implies B)\iff ((A \land \lnot B)\implies \lnot A)\) ist eine Tautologie |
\((2)\quad\) | Wir folgern, dass die Behauptung \(B\) gilt, was ein Widerspruch zu \(\lnot B\) ist. Es gilt also die folgende Tautologie: \((A\implies B)\iff ((A \land \lnot B)\implies B)\) ist eine Tautologie |
\((3)\quad\) | Wir folgern, dass eine beliebige falsche Aussage gilt (z.B. \(1=0\)). Es gilt also die folgende Tautologie: \((A\implies B)\iff ((A \land \lnot B)\implies \mathrm{f})\) ist eine Tautologie |
Beweise
Für alle drei Möglichkeiten erstellen wir zuerst die Wahrheitstabelle der Implikation \(A \implies B\) und zeigen danach, dass die Behauptungen auf die gleichen Wahrheitswerte führen:
\(\qquad\) | \(\begin{array}{|c|c|c|c|c|c|c|c|} \hline A & B & \hspace{-0.8em} & A \implies B \ \\ \hline \mathrm{w} & \mathrm{w} & \hspace{-0.8em} & \mathrm{w} \ \\ \hline \mathrm{w} & \mathrm{f} & \hspace{-0.8em} & \mathrm{f}\ \\ \hline \mathrm{f} & \mathrm{w} & \hspace{-0.8em} & \mathrm{w} \ \\ \hline \mathrm{f} & \mathrm{f} & \hspace{-0.8em} & \mathrm{w} \ \\ \hline\end{array}\) |
Beweis von \((1)\):
Wir bilden die Wahrheitstabelle:
\(\qquad\) | \(\begin{array}{|c|c|c|c|c|c|c|c|} \hline A & B & \hspace{-0.8em} & \lnot A & \lnot B & A \land \lnot B & (A \land \lnot B)\implies \lnot A \ \\ \hline \mathrm{w} & \mathrm{w} & \hspace{-0.8em} & \mathrm{f} & \mathrm{f} & \mathrm{f} & \mathrm{w} \ \\ \hline \mathrm{w} & \mathrm{f} & \hspace{-0.8em} & \mathrm{f} & \mathrm{w} & \mathrm{w} & \mathrm{f} \ \\ \hline \mathrm{f} & \mathrm{w} & \hspace{-0.8em} & \mathrm{w} & \mathrm{f} & \mathrm{f} & \mathrm{w}\ \\ \hline \mathrm{f} & \mathrm{f} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w} & \mathrm{f} & \mathrm{w}\ \\ \hline\end{array}\) |
Wir sehen, dass die Wahrheitswerte der Spalte \(A \implies B\) mit den Wahrheitswerten der Spalte \((A \land \lnot B)\implies \lnot A\) übereinstimmen. Das bedeutet, dass beide Aussagen logisch äquivalent sind.
Beweis von \((2)\):
Wir bilden die Wahrheitstabelle:
\(\qquad\) | \(\begin{array}{|c|c|c|c|c|c|c|c|} \hline A & B & \hspace{-0.8em} & \lnot B & A \land \lnot B & (A \land \lnot B)\implies B \ \\ \hline \mathrm{w} & \mathrm{w} & \hspace{-0.8em} & \mathrm{f} & \mathrm{f} & \mathrm{w} \ \\ \hline \mathrm{w} & \mathrm{f} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w} & \mathrm{f} \ \\ \hline \mathrm{f} & \mathrm{w} & \hspace{-0.8em} & \mathrm{f} & \mathrm{f} & \mathrm{w}\ \\ \hline \mathrm{f} & \mathrm{f} & \hspace{-0.8em} & \mathrm{w} & \mathrm{f} & \mathrm{w}\ \\ \hline\end{array}\) |
Wir sehen, dass die Wahrheitswerte der Spalte \(A \implies B\) mit den Wahrheitswerten der Spalte \((A \land \lnot B)\implies B\) übereinstimmen. Das bedeutet, dass beide Aussagen logisch äquivalent sind.
Beweis von \((3)\):
Wir bilden die Wahrheitstabelle:
\(\qquad\) | \(\begin{array}{|c|c|c|c|c|c|c|c|} \hline A & B & \hspace{-0.8em} & \lnot B & A \land \lnot B & (A \land \lnot B)\implies \mathrm{f} \ \\ \hline \mathrm{w} & \mathrm{w} & \hspace{-0.8em} & \mathrm{f} & \mathrm{f} & \mathrm{w} \ \\ \hline \mathrm{w} & \mathrm{f} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w} & \mathrm{f} \ \\ \hline \mathrm{f} & \mathrm{w} & \hspace{-0.8em} & \mathrm{f} & \mathrm{f} & \mathrm{w}\ \\ \hline \mathrm{f} & \mathrm{f} & \hspace{-0.8em} & \mathrm{w} & \mathrm{f} & \mathrm{w}\ \\ \hline\end{array}\) |
Wir sehen, dass die Wahrheitswerte der Spalte \(A \implies B\) mit den Wahrheitswerten der Spalte \((A \land \lnot B)\implies \mathrm{f}\) übereinstimmen. Das bedeutet, dass beide Aussagen logisch äquivalent sind.
Beispiel:
Wir zeigen die folgende Aussage mithilfe eines Beweises mit Widerspruch:
\(\qquad\) | Wenn \(p\) eine Primzahl ist, dann ist \(\sqrt{p}\) keine rationale Zahl. |
Umformen der zu beweisenden Aussage:
Wir zerlegen diese Behauptung in die folgenden beiden Aussagen:
\(\qquad\) | \(A\enspace : \enspace\) | \(p\) ist eine Primzahl |
\(B\enspace : \enspace\) | \(\sqrt{p}\) ist keine rationale Zahl |
Wir beweisen nun \(A \implies B\) durch Widerlegung von \(A \land \lnot B\) und wenden die dritte Möglichkeit des Widerspruchsbeweises an:
\(\qquad\) | Wenn \(p\) eine Primzahl ist und \(\sqrt{p}\) eine rationale Zahl, dann entsteht ein Widerspruch. |
Beweis mit Widerspruch:
Es seien also \(p\) eine Primzahl und \(\sqrt{p}\) eine rationale Zahl. Dann lässt sich \(\sqrt{p}\) als Bruch zweier teilerfremder natürlicher Zahlen \(m\) und \(n\) mit \(n\ne 0\) schreiben. Wir erhalten also
Quadrieren wir die Gleichung, dann erhalten wir
Wir formen die Gleichung um zu
Das bedeutet, dass \(m^2\) durch \(p\) teilbar ist, und damit auch, weil \(p\) eine Primzahl ist, dass \(m\) durch \(p\) teilbar ist. Wir können also \(m\) wie folgt schreiben:
Setzen wir nun \(m=p\cdot k\) in die Gleichung \(n^2 \cdot p = m^2\) ein, dann erhalten wir:
Wir kürzen \(p\) auf beiden Seiten. Dies ergibt:
Dies bedeutet, dass \(n^2\) durch \(p\) teilbar ist, und damit auch, weil \(p\) eine Primzahl ist, dass \(n\) durch \(p\) teilbar ist. Also teilt \(p\) sowohl \(m\) als auch \(n\). Dies ist ein Widerspruch zu der Annahme, dass \(m\) und \(n\) teilerfremd sind. Damit ist also die Annahme, dass \(\sqrt{p}\) eine rationale Zahl ist, widerlegt. | |||||||||||||
\(\blacksquare\) |
\(\enspace\)