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

Aus Wikibooks

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

Direkter Beweis[Bearbeiten]

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

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

Beispiel[Bearbeiten]

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 eine natürliche Zahl ist, dann ist durch 3 teilbar.“

In dieser Implikation ist „ ist eine natürliche Zahl“ die Prämisse und „ 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 orange):

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

„Sei eine natürliche Zahl. Damit ist auch eine natürliche Zahl und somit durch 3 teilbar. Da ist, ist durch 3 teilbar.“

Widerspruchsbeweis [Bearbeiten]

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

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

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

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

Beispiel[Bearbeiten]

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 eine natürliche Zahl ist, dann ist 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: „ ist eine natürliche Zahl und 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:

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

Widerspruchsannahme: Sei eine natürliche Zahl und nicht durch 3 teilbar. Wegen ist nicht durch 3 teilbar. Damit ist keine natürliche Zahl, da, wenn eine natürliche Zahl wäre, so wäre durch 3 teilbar. Wenn keine natürliche Zahl ist, ist auch keine natürliche Zahl. Dies ist aber ein Widerspruch dazu, dass nach Widerspruchsannahme eine natürliche Zahl ist ↯.