Aufgabe 3 Indirekter Beweis
Es gibt Behauptungen, die nur schwer direkt zu beweisen sind. Oft hilft dann der indirekte Beweis.
Wollen wir für die Implikation \(A \implies B\) einen indirekten Beweis führen, dann können wir
- entweder den Umkehrschluss \(\lnot B \implies \lnot A\) anwenden oder
- die Implikation mithilfe der Widerlegung der Aussage \(A \land \lnot B\) beweisen.
Erklärung
Der Umkehrschluss \(\lnot B \implies \lnot A\) ist logisch äquivalent zur Implikation \(A \implies B\), wie wir bereits im Lernmodul "Gesetze der Aussagenlogik" gezeigt haben.
Betrachten wir jetzt, wie wir von der Implikation \(A \implies B\) zu ihrer Negation \(A \land \lnot B\) kommen.
Bekannterweise ist die Implikation \(A \implies B\) äquivalent zu \(\lnot A \lor B\) (siehe auch Lernmodul "Grundlagen der Aussagenlogik"). Wir wenden das Gesetz von De Morgan an und erhalten:
\(\qquad\) | \((A \implies B)\) | \(\enspace\iff\enspace\) | \(\underbrace{(\lnot A \lor B)}_{\textsf{Gesetz von De Morgan}}\) |
\(\enspace\iff\enspace\) | \(\lnot (A \land \lnot B)\) |
Dass die beiden Varianten eines indirekten Beweises auch wirklich gleichbedeutend mit dem Beweis der eigentlichen Implikation \(A \implies B\) sind, zeigt auch die folgende Wahrheitstabelle:
\(\qquad\) | \(\begin{array}{|c|c|c|c|c|c|c|c|} \hline A & B &\hspace{-0.8em} & A \implies B & \lnot B \implies \lnot A & \lnot (A \land \lnot B) \ \\ \hline \mathrm{w} & \mathrm{w} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w} & \mathrm{w}\ \\ \hline \mathrm{w} & \mathrm{f} & \hspace{-0.8em} & \mathrm{f} & \mathrm{f} & \mathrm{f} \ \\ \hline \mathrm{f} & \mathrm{w} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w} & \mathrm{w} \ \\ \hline \mathrm{f} & \mathrm{f} & \hspace{-0.8em} & \mathrm{w} & \mathrm{w} & \mathrm{w}\ \\ \hline\end{array}\) |
Wendet man die Regel vom Umkehrschluss an bzw. das Kontrapositionsgesetz, so spricht man auch vom Beweis mit Kontraposition. Die Spalte \(A \implies B\) und die Spalte \(\lnot B \implies \lnot A\) sind identisch, d.h. die beiden Aussagen sind logisch äquivalent.
Zeigt man die Implikation durch Widerlegung der Aussage \(A \land \lnot B\), dann spricht man von einem Beweis mit Widerspruch. Die Spalte \(A \implies B\) und die Spalte \(\lnot (A \land \lnot B)\) haben die gleichen Wahrheitswerte, d.h. negieren wir \(A \land \lnot B\), so gelangen wir zu \(A \implies B\).
Merke:
Das Prinzip des indirekten Beweises ist oft dann sinnvoll, wenn wir eine All-Aussage beweisen müssen, denn durch die Negation einer All-Aussage erhalten wir eine Existenzaussage. Und mit einem einzelnen Objekt können wir meistens besser arbeiten als mit vielen Objekten.
\(\enspace\)