Mathe für Nicht-Freaks: Direkter und indirekter Beweis

{{#invoke:Mathe für Nicht-Freaks/Seite|oben}}

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

Direkter BeweisVorlage:Anker

Datei:Beweise - Quatematik.webm 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:

Beispiel

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

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

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:

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

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

Widerspruchsbeweis Vorlage:Anker

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 $\mathrm{\neg }S$ durch logische Schlussfolgerungen zu einem Widerspruch. Dabei nenne ich im Folgendem $\mathrm{\neg }S$ Widerspruchsannahme. Ein Widerspruchsbeweis hat also folgende Form:

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 $\mathrm{\neg }S$ zu einem Widerspruch geführt haben? Wenn du die Widerspruchsannahme $\mathrm{\neg }S$ zu einem Widerspruch geführt hast, so weißt du, dass $\mathrm{\neg }S$ falsch sein muss, also $\mathrm{\neg }S=\mathrm{F}$ ist. Damit ist die doppelte Verneinung $\mathrm{\neg }\mathrm{\neg }S$ von $S$ wahr ($\mathrm{\neg }\mathrm{\neg }S=\mathrm{\neg }\mathrm{F}=W$). Nun ist $\mathrm{\neg }\mathrm{\neg }S\iff S$ eine Tautologie, was du an folgender Wahrheitstabelle erkennst:

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

Da $\mathrm{\neg }\mathrm{\neg }S\iff S$ eine Tautologie ist, ist $\mathrm{\neg }\mathrm{\neg }S$ dann und nur dann wahr, wenn $S$ wahr ist (siehe Definition der Äquivalenz). Wir haben durch den Widerspruchsbeweis bewiesen, dass $\mathrm{\neg }\mathrm{\neg }S$ wahr ist (da $\mathrm{\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

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

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

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

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

{{#invoke:Mathe für Nicht-Freaks/Seite|unten}}