Direkter und indirekter Beweis – Serlo „Mathe für Nicht-Freaks“

Es gibt zwei wichtige Arten von Beweisen: direkte Beweise und indirekte Beweise (auch Widerspruchsbeweise genannt).

Direkter Beweis

Erklärung des direkten Beweises, des Widerspruchsbeweises und der Kontraposition. (YouTube-Video vom Kanal Quatematik)

Beim direkten Beweis wird der zu beweisende Satz $S$ direkt bewiesen. Dies bedeutet, dass man mit den Voraussetzungen von $S$ beginnt und aus diesen die zu beweisende Aussage direkt durch logische Schlussfolgerungen herleitet. Ein direkter Beweis nimmt also folgende Form an:

${\begin{array}{c}{\text{Prämissen und Voraussetzungen von }}S\\{\color {Orange}|}\\{\color {Orange}{\text{logische Schlussfolgerungen}}}\\{\color {Orange}\downarrow }\\{\text{Konklusion von }}S\end{array}}$

Beispiel

Betrachten wir ein Beispiel. Stelle dir vor, wir müssen den Satz

„Die Summe von drei aufeinanderfolgenden natürlichen Zahlen ist durch 3 teilbar.“

beweisen. Dieser Satz lässt sich folgendermaßen als Implikation formulieren:

„Wenn $n$ eine natürliche Zahl ist, dann ist $n+(n+1)+(n+2)$ durch 3 teilbar.“

In dieser Implikation ist „$n$ ist eine natürliche Zahl“ die Prämisse und „$n+(n+1)+(n+2)$ ist durch 3 teilbar“ die Konklusion. Ein direkter Beweis hätte also folgende Form:

${\begin{array}{c}n{\text{ ist eine natürliche Zahl.}}\\{\color {Orange}|}\\{\color {Orange}{\text{logische Schlussfolgerungen}}}\\{\color {Orange}\downarrow }\\n+(n+1)+(n+2){\text{ ist durch 3 teilbar.}}\end{array}}$

Ein solcher Beweis könnte so aussehen (Implikationen der logischen Schlussfolgerungen sind orange):

${\begin{array}{c}n{\text{ ist eine natürliche Zahl.}}\\{\color {Orange}|}\\{\color {Orange}{\text{Wenn }}n{\text{ eine natürliche Zahl ist, dann ist auch }}n+1{\text{ eine natürliche Zahl.}}}\\{\color {Orange}\downarrow }\\n+1{\text{ ist eine natürliche Zahl.}}\\{\color {Orange}|}\\{\color {Orange}{\text{Ist }}k{\text{ eine natürliche Zahl, dann ist }}3\cdot k{\text{ durch 3 teilbar.}}}\\{\color {Orange}\downarrow }\\3\cdot (n+1){\text{ ist durch 3 teilbar.}}\\{\color {Orange}|}\\{\color {Orange}3\cdot (n+1)=3\cdot n+3}\\{\color {Orange}\downarrow }\\3\cdot n+3{\text{ ist durch 3 teilbar.}}\\{\color {Orange}|}\\{\color {Orange}3\cdot n+3=n+n+n+1+2=n+(n+1)+(n+2)}\\{\color {Orange}\downarrow }\\n+(n+1)+(n+2){\text{ ist durch 3 teilbar.}}\end{array}}$

Anstatt deinen Beweis so wie obigen zu strukturieren, kannst du ihn auch als Fließtext schreiben (dies ist meistens kompakter):

„Sei $n$ eine natürliche Zahl. Damit ist auch $n+1$ eine natürliche Zahl und somit $3\cdot (n+1)$ durch 3 teilbar. Da $3\cdot (n+1)=3\cdot n+3=n+(n+1)+(n+2)$ ist, ist $n+(n+1)+(n+2)$ durch 3 teilbar.“

Widerspruchsbeweis

Neben dem direkten Beweis gibt es eine zweite Art des Beweises, den Widerspruchsbeweis oder indirekten Beweis. Wenn du einen mathematischen Satz $S$ indirekt beweisen möchtest, so führst du seine Negation $\neg S$ durch logische Schlussfolgerungen zu einem Widerspruch. Dabei nenne ich im Folgendem $\neg S$ Widerspruchsannahme. Ein Widerspruchsbeweis hat also folgende Form:

${\begin{array}{c}{\text{Widerspruchsannahme }}\neg S\\{\color {Orange}|}\\{\color {Orange}{\text{logische Schlussfolgerungen}}}\\{\color {Orange}\downarrow }\\{\text{Widerspruch}}\end{array}}$

Um einen Widerspruchsbeweis erfolgreich durchzuführen, musst du zunächst den zu beweisenden Satz $S$ richtig negieren. Wie du dies machen kannst, kannst du im Abschnitt „Aussagen negieren“ nachlesen.

Doch wie haben wir den Satz $S$ bewiesen, wenn wir die Widerspruchsannahme $\neg S$ zu einem Widerspruch geführt haben? Wenn du die Widerspruchsannahme $\neg S$ zu einem Widerspruch geführt hast, so weißt du, dass $\neg S$ falsch sein muss, also $\neg S=\mathrm {F}$ ist. Damit ist die doppelte Verneinung $\neg \neg S$ von $S$ wahr ($\neg \neg S=\neg \mathrm {F} =W$). Nun ist $\neg \neg S\Leftrightarrow S$ eine Tautologie, was du an folgender Wahrheitstabelle erkennst:

$S$	$\neg S$	$\neg \neg S$	$\neg \neg S\Leftrightarrow S$
$\mathrm {W}$	$\mathrm {F}$	$\mathrm {W}$	$\mathrm {W}$
$\mathrm {F}$	$\mathrm {W}$	$\mathrm {F}$	$\mathrm {W}$

Da $\neg \neg S\Leftrightarrow S$ eine Tautologie ist, ist $\neg \neg S$ dann und nur dann wahr, wenn $S$ wahr ist (siehe Definition der Äquivalenz). Wir haben durch den Widerspruchsbeweis bewiesen, dass $\neg \neg S$ wahr ist (da $\neg S$ falsch ist). Damit muss aber wegen obiger Tautologie $S$ wahr sein. Genau dies ist zu zeigen, wenn wir den Satz $S$ beweisen wollen.

Beispiel

Stelle dir vor, wir wollen den Satz

„Die Summe von drei aufeinanderfolgenden natürlichen Zahlen ist durch 3 teilbar.“

durch einen Widerspruchsbeweis beweisen (diesen Satz haben wir bereits oben direkt bewiesen). Diesen Satz können wir als Implikation definieren:

„Wenn $n$ eine natürliche Zahl ist, dann ist $n+(n+1)+(n+2)$ durch 3 teilbar.“

Um diese Implikation indirekt zu beweisen, müssen wir zunächst die Widerspruchsannahme formulieren, also die obige Implikation negieren. Wir erhalten:

Widerspruchsannahme: „$n$ ist eine natürliche Zahl und $n+(n+1)+(n+2)$ ist nicht durch 3 teilbar.“

Diese Annahme müssen wir nun durch logische Schlussfolgerungen zu einem Widerspruch führen. Eine solche Herleitung könnte so aussehen:

${\begin{array}{c}{\text{Widerspruchsannahme: }}n{\text{ ist eine natürliche Zahl und}}\\n+(n+1)+(n+2){\text{ ist nicht durch 3 teilbar.}}\\{\color {Orange}|}\\{\color {Orange}{\text{Ist }}A\land B{\text{ wahr, so ist }}A{\text{ wahr.}}}\\{\color {Orange}\downarrow }\\n+(n+1)+(n+2){\text{ ist nicht durch 3 teilbar.}}\\{\color {Orange}|}\\{\color {Orange}n+(n+1)+(n+2)=3\cdot n+3}\\{\color {Orange}\downarrow }\\3\cdot n+3{\text{ ist nicht durch 3 teilbar.}}\\{\color {Orange}|}\\{\color {Orange}3\cdot n+3=3\cdot (n+1)}\\{\color {Orange}\downarrow }\\3\cdot (n+1){\text{ ist nicht durch 3 teilbar.}}\\{\color {Orange}|}\\{\color {Orange}{\text{Ist }}3\cdot k{\text{ nicht durch 3 teilbar, so ist }}k{\text{ keine natürliche Zahl.}}}\\{\color {Orange}\downarrow }\\n+1{\text{ ist keine natürliche Zahl.}}\\{\color {Orange}|}\\{\color {Orange}{\text{Ist }}k{\text{ keine natürliche Zahl, so ist }}k-1{\text{ keine natürliche Zahl.}}}\\{\color {Orange}\downarrow }\\(n+1)-1{\text{ ist keine natürliche Zahl.}}\\{\color {Orange}|}\\{\color {Orange}(n+1)-1=n}\\{\color {Orange}\downarrow }\\n{\text{ ist keine natürliche Zahl. Widerspruch!}}\end{array}}$

Auch diesen Beweis kannst du in einem Fließtext schreiben:

Widerspruchsannahme: Sei $n$ eine natürliche Zahl und $n+(n+1)+(n+2)$ nicht durch 3 teilbar. Wegen $n+(n+1)+(n+2)=3\cdot n+3=3\cdot (n+1)$ ist $3\cdot (n+1)$ nicht durch 3 teilbar. Damit ist $n+1$ keine natürliche Zahl, da, wenn $n+1$ eine natürliche Zahl wäre, so wäre $3\cdot (n+1)$ durch 3 teilbar. Wenn $n+1$ keine natürliche Zahl ist, ist auch $n$ keine natürliche Zahl. Dies ist aber ein Widerspruch dazu, dass $n$ nach Widerspruchsannahme eine natürliche Zahl ist ↯.