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 BeweisBearbeiten

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:

 

BeispielBearbeiten

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.

BeispielBearbeiten

Stelle dir vor, wir wollen den Satz

„Die Summe von drei aufeinanderfolgenden natürlichen 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   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 ↯.