Fallunterscheidung und Kontraposition – Serlo „Mathe für Nicht-Freaks“

Aus Wikibooks

Neben den verschiedenen Arten mathematischer Beweise gibt es einige Methoden, die du in Beweisen verwenden kannst: die vollständige Fallunterscheidung, der Beweis durch Kontraposition und die vollständige Induktion. Diese Liste ist nicht vollständig und es gibt gewiss vielfältige Wege einen Beweis zu führen. Dennoch kann dir der nachfolgende Abschnitt als Inspirationsquelle für eigene Beweise dienen.

Vollständige Fallunterscheidung [Bearbeiten]

Bei vollständiger Fallunterscheidung wird der Beweis in eine endliche Anzahl von Fällen aufgeteilt. Für jeden der Fälle muss der zu beweisende Satz unter zusätzlicher Annahme der Fallbedingung bewiesen werden. Ein Beweis durch vollständige Fallunterscheidung hat damit folgende Form:

Mit dem einfachsten Fall kann man beginnen; manchmal fließen die hierbei gewonnenen Erkenntnisse bei der Bearbeitung anderer Fälle ein. Insofern kann eine relativ schwierige Gesamtaufgabe in mehrere leichter zu lösende Teilaufgaben reduziert werden gemäß dem Motto: teile und herrsche!

Zu achten ist darauf, dass bei der Aufteilung des Beweises in unterschiedliche Fälle der zu beweisende Satz vollständig abgedeckt wird. So kann z. B. beim Beweis eines Satzes, der für alle ganzen Zahlen gelten soll, eine Aufteilung in positive und negative Zahlen sinnvoll sein. Dann muss aber auch das Auftreten der Zahl Null als dritter Fall bewiesen werden.

Beispiel[Bearbeiten]

Als Beispiel beweisen wir folgenden Satz mit Hilfe vollständiger Fallunterscheidung (Quelle: Wikipedia-Artikel „Beweis (Mathematik)“):

„Ist eine Primzahl ungleich zwei, dann gibt es eine natürliche Zahl mit oder .“

Wir werden folgende vier Fälle unterscheiden:

Da eine natürliche Zahl ist (nur natürliche Zahlen können per Definition Primzahlen sein), muss einer der obigen vier Fälle auftreten. Unsere Fallunterscheidung ist damit vollständig. Betrachten wir nun die vier Fälle:

Fall 1:

ist durch 4 teilbar und damit keine Primzahl. Somit ist die Prämisse der zu beweisenden Implikation falsch und damit die gesamte Implikation wahr.

Fall 2:

Die Konklusion der zu beweisenden Implikation und damit die gesamte Implikation ist wahr.

Fall 3:

Es ist . Damit ist durch 2 teilbar. Da nach Voraussetzung der zu beweisenden Implikation ist, kann keine Primzahl sein. Somit ist die Prämisse der zu beweisenden Implikation falsch und damit die gesamte Implikation wahr.

Fall 4:

Die Konklusion der zu beweisenden Implikation und damit die gesamte Implikation ist wahr.

In jedem der Fälle konnten wir beweisen, dass unter der Bedingung der jeweiligen Fallunterscheidung die zu beweisende Implikation wahr ist. Da unsere Fallunterscheidung vollständig ist, ist die zu beweisende Implikation unabhängig vom jeweiligen Fall wahr.

Beweis durch Kontraposition [Bearbeiten]

Der Beweis durch Kontraposition ist eine Beweismethode, die für Beweise von Implikationen der Form verwendet werden können. Diese Beweismethode basiert auf der Tautologie .

Verständnisfrage: Zeige, dass die Aussage eine Tautologie ist.

Um zu zeigen, dass eine Tautologie ist, können wir die Wahrheitstabelle dieser Aussage aufstellen und uns überzeugen, dass der resultierende Wahrheitswert immer wahr ist:

Die Aussage ist also eine Tautologie und damit immer wahr. Dies bedeutet, dass dann und nur dann wahr ist, wenn wahr ist. Wenn wir also einen Satz der Form beweisen wollen, können wir alternativ auch die Aussage beweisen. Beim Beweis durch Kontraposition macht man genau dies: Anstatt einen Satz der Form direkt zu beweisen, wird die Aussage bewiesen.

Um also Kontraposition erfolgreich anwenden zu können, musst du wissen, wie man Aussagen richtig negiert. Dies kannst du im Abschnitt „Aussagen negieren“ nachlesen.

Beispiel[Bearbeiten]

Als Beispiel wollen wir folgenden Satz mit Hilfe der Kontraposition beweisen (im Folgenden gehe ich davon aus, dass eine Quadratzahl, also ein Element der Menge ist):

„Ist gerade, dann ist gerade.“

Dieser Satz hat die Form einer Implikation mit:

Um diesen Satz durch Kontraposition beweisen zu können, müssen wir erst einmal die Aussage , also die Negation der Aussagen und bestimmen:

Damit erhalten wir für :

Diesen Satz werden wir direkt beweisen. Wir suchen also einen Beweis der Form

Beweis: Sei eine natürliche Zahl und ungerade. Wir müssen nun zeigen, dass ungerade ist. Da ungerade ist, gibt es eine natürliche Zahl mit . Damit ist

Also ist eine ungerade Zahl. q. e. d.

Vollständige Induktion [Bearbeiten]

Die Vollständige Induktion wird im nächsten Abschnitt dieses Buches ausführlich vorgestellt. Zur Vollständigkeit nenne ich hier nur das Prinzip dieser Beweismethode:

Definition (Vollständige Induktion)

Sei eine Aussageform in der freien Variablen . Sei (oder ) eine wahre Aussage (Induktionsanfang) und die Implikation für alle erfüllt (Induktionsschritt), dann ist die Aussageform allgemeingültig in .