Indirekter Beweis Beweis mit Kontraposition
Beweis mit Kontraposition:
Bei einem Beweis mit Kontraposition wendet man den Umkehrschluss an und zeigt die folgende Tautologie:
\(\qquad\) | \((A \implies B)\iff(\lnot B \implies \lnot A)\) |
Man nimmt also an, dass die zu beweisende Behauptung \(B\) nicht gilt und zeigt dann, dass \(A\) auch nicht gelten kann.
Beispiel:
Wir zeigen die folgende Aussage für natürliche Zahlen \(n\) mithilfe eines Beweises mit Kontraposition:
\(\qquad\) | Wenn \(n^2\) ungerade ist, so ist auch \(n\) ungerade. |
Bilden der Kontraposition:
Die Kontraposition, die wir zeigen müssen, lautet:
\(\qquad\) | Wenn \(n\) nicht ungerade ist, so ist auch \(n^2\) nicht ungerade. |
Dies können wir umformulieren und erhalten:
\(\qquad\) | Wenn \(n\) gerade ist, so ist auch \(n^2\) gerade. |
Beweis mit Kontraposition:
Sei \(n\in\mathbb{N}\) und \(n\) gerade. Dann gibt es eine natürliche Zahl \(m\) so, dass gilt:
Wir bilden nun \(n^2\):
Und somit haben wir gezeigt, dass auch \(n^2\) eine gerade Zahl ist. | |||||
\(\blacksquare\) |
Analog zeigt man die folgende Aussage:
\(\qquad\) | Wenn \(n^2\) gerade ist, so ist auch \(n\) gerade. |
Beweis
Bilden der Kontraposition:
Die Kontraposition, die wir zeigen müssen, lautet:
\(\qquad\) | Wenn \(n\) nicht gerade ist, so ist auch \(n^2\) nicht gerade. |
Dies können wir umformulieren und erhalten:
\(\qquad\) | Wenn \(n\) ungerade ist, so ist auch \(n^2\) ungerade. |
Beweis mit Kontraposition:
Sei \(n\in\mathbb{N}\) und \(n\) ungerade. Dann gibt es eine natürliche Zahl \(m\) so, dass gilt:
Wir bilden nun \(n^2\):
Und somit haben wir gezeigt, dass auch \(n^2\) eine ungerade Zahl ist. | |||||
\(\blacksquare\) |
\(\enspace\)