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

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.

BeispielBearbeiten

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:

  1.  
  2.  
  3.  
  4.  

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.

BeispielBearbeiten

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  .