Mathe für Nicht-Freaks: Beweis: Beweisarten

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

Direkter Beweis

Beim direktem 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:

Prämissen und Voraussetzungen von $S$

$|$

logische Schlussfolgerungen

$\downarrow$

Konklusion von $S$

Beispiel

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

„Die Summe 3er aufeinander folgender natürlicher 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:

$n$ ist eine natürliche Zahl.

$|$

logische Schlussfolgerungen

$\downarrow$

$n+(n+1)+(n+2)$ ist durch 3 teilbar.

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

$n$ ist eine natürliche Zahl.

$|$

Wenn $\color{RedOrange} n$ eine natürliche Zahl ist, dann ist auch $\color{RedOrange} n+1$ eine natürliche Zahl.

$\downarrow$

$n+1$ ist eine natürliche Zahl.

$|$

Ist $\color{RedOrange} k$ eine natürliche Zahl, dann ist $\color{RedOrange} 3\cdot k$ durch 3 teilbar.

$\downarrow$

$3 \cdot (n+1)$ ist durch 3 teilbar.

$|$

$\color{RedOrange} 3 \cdot (n+1) = 3\cdot n + 3$

$\downarrow$

$3 \cdot n+3$ ist durch 3 teilbar.

$|$

$\color{RedOrange} 3 \cdot n + 3 = n + n+ n + 1 + 2 = n +(n+1)+(n+2)$

$\downarrow$

$n + (n+1) + (n+2)$ ist durch 3 teilbar.

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 $n+(n+1)+(n+2)=3\cdot n+3$ 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:

Widerspruchsannahme $\neg S$

$|$

logische Schlussfolgerungen

$\downarrow$

Widerspruch

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

Stell dir vor wir wollen den Satz

„Die Summe 3er aufeinander folgender natürlicher Zahlen ist durch 3 teilbar.“

durch einen Widerspruchsbeweis beweisen (diesen 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:

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

$|$

Ist $\color{RedOrange} A \and B$ wahr, so ist $\color{RedOrange} A$ wahr.

$\downarrow$

$n+(n+1)+(n+2)$ ist nicht durch 3 teilbar.

$|$

$\color{RedOrange} n+(n+1)+(n+2) = 3\cdot n + 3$

$\downarrow$

$3\cdot n + 3$ ist nicht durch 3 teilbar.

$|$

$\color{RedOrange} 3\cdot n + 3 = 3 \cdot (n+1)$

$\downarrow$

$3\cdot (n+1)$ ist nicht durch 3 teilbar.

$|$

Ist $\color{RedOrange} 3 \cdot k$ nicht durch 3 teilbar, so ist $\color{RedOrange} k$ keine natürliche Zahl.

$\downarrow$

$n+1$ ist keine natürliche Zahl.

$|$

Ist $\color{RedOrange} k$ keine natürliche Zahl, so ist $\color{RedOrange} k-1$ keine natürliche Zahl.

$\downarrow$

$(n+1)-1$ ist keine natürliche Zahl.

$|$

$\color{RedOrange} (n+1)-1 = n$

$\downarrow$

$n$ ist keine natürliche Zahl.

$\downarrow$

Widerspruch ↯ ($n$ ist nach Widerspruchsannahme eine natürliche Zahl)

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 ↯.