Mathe für Nicht-Freaks: Beweis: Beweismethoden

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 Inspriationsquelle 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. In jeden der Fälle wird die zu beweisende Aussage unter zusätzlicher Annahme der Fallbedingung $\mathrm F_k$ bewiesen. Ein Beweis durch vollständige Fallunterscheidung hat damit folgende Form:

Prämissen

Fall $\mathrm F_1$: $|$ logische Schlussfolgerungen $\downarrow$ zu beweisende Aussage

Fall $\mathrm F_2$: $|$ logische Schlussfolgerungen $\downarrow$ zu beweisende Aussage

$\ldots$

Fall $\mathrm F_n$: $|$ logische Schlussfolgerungen $\downarrow$ zu beweisende Aussage

Dabei muss sichergestellt sein, dass unter den Prämissen des Satzes mindestens einer der Fälle $\mathrm F_1,\ \mathrm F_2,\ \ldots \mathrm F_n$ auftritt (Deswegen das Wort „vollständig“ im Namen).

Beispiel

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

„Ist $p$ eine Primzahl ungleich 2, dann gibt 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\ne 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 jeden 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 von jeweiligen Fall wahr.

Beweis durch Kontraposition

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:

„Ist $n\in \N$ gerade und $\sqrt n$ eine natürliche Zahl, dann ist $\sqrt{n}$ gerade.“

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

$\underbrace{n\in N\text{ ist gerade und }\sqrt{n}\text{ ist eine nat}\ddot \mathrm u\text{rliche Zahl }}_{=\ A} \Rightarrow \ \underbrace{\sqrt 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{align} \neg A & = \neg \left(n\in N\text{ ist gerade und }\sqrt{n}\text{ ist eine nat}\ddot \mathrm u\text{rliche Zahl }\right)\\[3px] & = \neg \left(n\in N\text{ ist gerade}\right) \text{ oder }\neg \left(\sqrt{n}\text{ ist eine nat}\ddot \mathrm u\text{rliche Zahl }\right) \\[3px] & = n\in N\text{ ist ungerade oder }\sqrt{n}\text{ ist keine nat}\ddot \mathrm u\text{rliche Zahl } \end{align}$

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

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

$\left(\sqrt n \text{ ist ungerade}\right) \ \Rightarrow\ \left(n\in N\text{ ist ungerade oder }\sqrt{n}\text{ ist keine nat}\ddot \mathrm u\text{rliche Zahl }\right)$

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

$\sqrt n$ ist ungerade

$|$

logische Schlussfolgerungen

$\downarrow$

$n\in \N$ ist ungerade oder $\sqrt n$ ist keine natürliche Zahl

Hier wenden wir eine volländige Fallunterscheidung in die Fälle „$\sqrt n$ ist eine natürliche Zahl“ und „$\sqrt n$ ist keine natürliche Zahl“ an (so siehst du an diesem Beispiel auch, dass die verschiedenen Methoden Beweise zu führen, kombiniert werden können).

Fall 1: $\sqrt n$ ist keine natürliche Zahl

Da die Aussage „$\sqrt n$ ist keine natürliche Zahl“ wahr ist, ist insbesondere auch die Aussage „$n\in \N$ ist ungerade oder $\sqrt n$ ist keine natürliche Zahl“ wahr. Dies ist aber die Konklusion der zu beweisenden Implikation. Somit ist die gesamte Implikation wahr (da eine Implikation bereits dann wahr ist, wenn ihre Konklusion wahr ist).

Alternativ kannst du argumentieren, dass die Prämisse der zu beweisenden Implikation „$\sqrt n$ ist ungerade“ bereits impliziert, dass $\sqrt n$ eine natürliche Zahl ist (nur natürliche Zahlen können ungerade sein). Damit kann der Fall „$\sqrt n$ ist keine natürliche Zahl“ nie unter der Voraussetzung „$\sqrt n$ ist ungerade“ auftreten.

Fall 2: $\sqrt n$ ist eine natürliche Zahl

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

$\begin{align} n & = \left(\sqrt 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{align}$

Also ist $n$ eine ungerade Zahl. qed.

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 \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 \N$ erfüllt (Induktionsschritt), dann ist die Aussageform allgemeingültig in $\N$.