Fallunterscheidung und Kontraposition – Serlo „Mathe für Nicht-Freaks“

Neben den verschiedenen Arten mathematischer Beweise gibt es einige Methoden, die du in Beweisen verwenden kannst: die vollständige Fallunterscheidung, der Beweis durch Kontraposition und die vollständige Induktion. Diese Liste ist nicht vollständig und es gibt gewiss vielfältige Wege einen Beweis zu führen. Dennoch kann dir der nachfolgende Abschnitt als Inspirationsquelle für eigene Beweise dienen.

Vollständige Fallunterscheidung

Bei vollständiger Fallunterscheidung wird der Beweis in eine endliche Anzahl von Fällen $\mathrm {F} _{1},\ \mathrm {F} _{2},\ \ldots \ \mathrm {F} _{n}$ aufgeteilt. Für jeden der Fälle muss der zu beweisende Satz unter zusätzlicher Annahme der Fallbedingung $\mathrm {F} _{k}$ bewiesen werden. Ein Beweis durch vollständige Fallunterscheidung hat damit folgende Form:

${\begin{array}{c}{\text{Prämissen}}\\[2ex]{\begin{array}{c}{\text{Fall }}F_{1}:\\{\color {Orange}|}\\{\color {Orange}{\text{logische}}}\\{\color {Orange}{\text{Schlussfolgerungen}}}\\{\color {Orange}\downarrow }\\{\text{zu beweisende Aussage}}\end{array}}{\begin{array}{c}{\text{Fall }}F_{2}:\\{\color {Orange}|}\\{\color {Orange}{\text{logische}}}\\{\color {Orange}{\text{Schlussfolgerungen}}}\\{\color {Orange}\downarrow }\\{\text{zu beweisende Aussage}}\end{array}}\ldots {\begin{array}{c}{\text{Fall }}F_{n}:\\{\color {Orange}|}\\{\color {Orange}{\text{logische}}}\\{\color {Orange}{\text{Schlussfolgerungen}}}\\{\color {Orange}\downarrow }\\{\text{zu beweisende Aussage}}\end{array}}\end{array}}$

Mit dem einfachsten Fall kann man beginnen; manchmal fließen die hierbei gewonnenen Erkenntnisse bei der Bearbeitung anderer Fälle ein. Insofern kann eine relativ schwierige Gesamtaufgabe in mehrere leichter zu lösende Teilaufgaben reduziert werden gemäß dem Motto: teile und herrsche!

Zu achten ist darauf, dass bei der Aufteilung des Beweises in unterschiedliche Fälle der zu beweisende Satz vollständig abgedeckt wird. So kann z. B. beim Beweis eines Satzes, der für alle ganzen Zahlen gelten soll, eine Aufteilung in positive und negative Zahlen sinnvoll sein. Dann muss aber auch das Auftreten der Zahl Null als dritter Fall bewiesen werden.

Beispiel

Als Beispiel beweisen wir folgenden Satz mit Hilfe vollständiger Fallunterscheidung (Quelle: Wikipedia-Artikel „Beweis (Mathematik)“):

„Ist $p$ eine Primzahl ungleich zwei, dann gibt es eine natürliche Zahl $k$ mit $p=4\cdot k+1$ oder $p=4\cdot k+3$.“

Wir werden folgende vier Fälle unterscheiden:

1. $p=4k$
2. $p=4k+1$
3. $p=4k+2$
4. $p=4k+3$

Da $p$ eine natürliche Zahl ist (nur natürliche Zahlen können per Definition Primzahlen sein), muss einer der obigen vier Fälle auftreten. Unsere Fallunterscheidung ist damit vollständig. Betrachten wir nun die vier Fälle:

Fall 1: $p=4k$

$p$ ist durch 4 teilbar und damit keine Primzahl. Somit ist die Prämisse der zu beweisenden Implikation falsch und damit die gesamte Implikation wahr.

Fall 2: $p=4k+1$

Die Konklusion der zu beweisenden Implikation und damit die gesamte Implikation ist wahr.

Fall 3: $p=4k+2$

Es ist $p=4k+2=2(2k+1)$. Damit ist $p$ durch 2 teilbar. Da nach Voraussetzung der zu beweisenden Implikation $p\neq 2$ ist, kann $p$ keine Primzahl sein. Somit ist die Prämisse der zu beweisenden Implikation falsch und damit die gesamte Implikation wahr.

Fall 4: $p=4k+3$

Die Konklusion der zu beweisenden Implikation und damit die gesamte Implikation ist wahr.

In jedem der Fälle konnten wir beweisen, dass unter der Bedingung der jeweiligen Fallunterscheidung die zu beweisende Implikation wahr ist. Da unsere Fallunterscheidung vollständig ist, ist die zu beweisende Implikation unabhängig vom jeweiligen Fall wahr.

Beweis durch Kontraposition

Der Beweis durch Kontraposition ist eine Beweismethode, die für Beweise von Implikationen der Form $A\Rightarrow B$ verwendet werden können. Diese Beweismethode basiert auf der Tautologie $(A\Rightarrow B)\Leftrightarrow (\neg B\Rightarrow \neg A)$.

Verständnisfrage: Zeige, dass die Aussage $(A\Rightarrow B)\Leftrightarrow (\neg B\Rightarrow \neg A)$ eine Tautologie ist.

Um zu zeigen, dass $(A\Rightarrow B)\Leftrightarrow (\neg B\Rightarrow \neg A)$ eine Tautologie ist, können wir die Wahrheitstabelle dieser Aussage aufstellen und uns überzeugen, dass der resultierende Wahrheitswert immer wahr ist:

$A$	$B$	$(A\Rightarrow B)$	$\Leftrightarrow$	$(\neg B\Rightarrow \neg A)$
$\mathrm {W}$	$\mathrm {W}$	$\mathrm {W}$	$\mathbf {W}$	$\mathrm {W}$
$\mathrm {W}$	$\mathrm {F}$	$\mathrm {F}$	$\mathbf {W}$	$\mathrm {F}$
$\mathrm {F}$	$\mathrm {W}$	$\mathrm {W}$	$\mathbf {W}$	$\mathrm {W}$
$\mathrm {F}$	$\mathrm {F}$	$\mathrm {W}$	$\mathbf {W}$	$\mathrm {W}$

Die Aussage $(A\Rightarrow B)\Leftrightarrow (\neg B\Rightarrow \neg A)$ ist also eine Tautologie und damit immer wahr. Dies bedeutet, dass $A\Rightarrow B$ dann und nur dann wahr ist, wenn $\neg B\Rightarrow \neg A$ wahr ist. Wenn wir also einen Satz der Form $A\Rightarrow B$ beweisen wollen, können wir alternativ auch die Aussage $\neg B\Rightarrow \neg A$ beweisen. Beim Beweis durch Kontraposition macht man genau dies: Anstatt einen Satz der Form $A\Rightarrow B$ direkt zu beweisen, wird die Aussage $\neg B\Rightarrow \neg A$ bewiesen.

Um also Kontraposition erfolgreich anwenden zu können, musst du wissen, wie man Aussagen richtig negiert. Dies kannst du im Abschnitt „Aussagen negieren“ nachlesen.

Beispiel

Als Beispiel wollen wir folgenden Satz mit Hilfe der Kontraposition beweisen (im Folgenden gehe ich davon aus, dass $n$ eine Quadratzahl, also ein Element der Menge $\{k^{2}\,|\,k\in \mathbb {N} \}$ ist):

„Ist $n$ gerade, dann ist ${\sqrt[{2}]{n}}$ gerade.“

Dieser Satz hat die Form einer Implikation $A\Rightarrow B$ mit:

$\underbrace {n{\text{ ist gerade}}} _{=\ A}\Rightarrow \ \underbrace {{\sqrt[{2}]{n}}{\text{ ist gerade}}} _{=\ B}$

Um diesen Satz durch Kontraposition beweisen zu können, müssen wir erst einmal die Aussage $\neg B\Rightarrow \neg A$, also die Negation der Aussagen $A$ und $B$ bestimmen:

${\begin{aligned}\neg A&=\neg \left(n{\text{ ist gerade}}\right)\\&=n{\text{ ist ungerade}}\end{aligned}}$

${\begin{aligned}\neg B&=\neg \left({\sqrt[{2}]{n}}{\text{ ist gerade}}\right)\\&={\sqrt[{2}]{n}}{\text{ ist ungerade}}\end{aligned}}$

Damit erhalten wir für $\neg B\Rightarrow \neg A$:

$\left({\sqrt[{2}]{n}}{\text{ ist ungerade}}\right)\Rightarrow \left(n{\text{ ist ungerade}}\right)$

Diesen Satz werden wir direkt beweisen. Wir suchen also einen Beweis der Form

${\begin{array}{c}{\sqrt[{2}]{n}}{\text{ ist ungerade}}\\{\color {Orange}|}\\{\color {Orange}{\text{logische Schlussfolgerungen}}}\\{\color {Orange}\downarrow }\\n{\text{ ist ungerade}}\end{array}}$

Beweis: Sei ${\sqrt[{2}]{n}}$ eine natürliche Zahl und ungerade. Wir müssen nun zeigen, dass $n$ ungerade ist. Da ${\sqrt[{2}]{n}}$ ungerade ist, gibt es eine natürliche Zahl $k\geq 0$ mit ${\sqrt[{2}]{n}}=2\cdot k+1$. Damit ist

${\begin{aligned}n&=\left({\sqrt[{2}]{n}}\right)^{2}\\&=\left(2\cdot k+1\right)^{2}\\&=4k^{2}+4k+1\\&=2\cdot \underbrace {\left(2k^{2}+2k\right)} _{=:\ m}+1\\&=2\cdot m+1\\\end{aligned}}$

Also ist $n$ eine ungerade Zahl. q. e. d.

Vollständige Induktion

Die Vollständige Induktion wird im nächsten Abschnitt dieses Buches ausführlich vorgestellt. Zur Vollständigkeit nenne ich hier nur das Prinzip dieser Beweismethode:

Definition (Vollständige Induktion)

Sei $A(n)$ eine Aussageform in der freien Variablen $n\in \mathbb {N}$. Sei $A(1)$ (oder $A(0)$) eine wahre Aussage (Induktionsanfang) und die Implikation $A(k)\Rightarrow A(k+1)$ für alle $k\in \mathbb {N}$ erfüllt (Induktionsschritt), dann ist die Aussageform allgemeingültig in $\mathbb {N}$.