Beweistechniken

Direkter Beweis

\( \small A\Rightarrow B \)

Es wird angenommen, dass die Aussage A gültig ist. Aus dieser Gültigkeit folgert man dann die Gültigkeit von B.

Ein solcher Beweis beginnt also mit den Worten:

"Angenommen es gelte A..." oder "Es sei... "

Indirekter Beweis

\( \small A\Rightarrow B \) ist logisch gleichbedeutend mit \( \small \neg B \Rightarrow \neg A \).

Ein solcher Beweis beginnt also mit den Worten:

"Angenommen es gelte B nicht..."

Widerspruchsbeweis

Um die Gültigkeit der Aussage B zu zeigen, kann man eine "reductio ad absurdum" ausführen.

Dazu nimmt man an, dass B nicht erfüllt sei und folgert daraus irgendeine andere Aussage C, von der man aber auf Grund anderer, bereits bewiesener Aussagen weiß, dass sie nicht korrekt sein kann. Das ist dann ein Widerspruch, der oft mit einem Blitz markiert wird.

Wenn aber aus \( \small \neg B \) \( \small C \) folgt, so muss wegen der Beweistechnik des indirekten Beweises aus \( \small \neg C \) \( \small B \) folgen. Damit ist dann die Gültigkeit von B bewiesen.

Oft ist es schwierig, die richtige Aussage \( \small C \) zu finden, die einem die Anwendung des Widerspruchsbeweises erlaubt.

Der Beweis der Irrationalität von \( \small \sqrt{2} \) ist genau so ein Widerspruchsbeweis.

Der Widerspruchsbeweis findet sich auch häufig in der Argumentationstechnik von Anwälten vor Gericht: "Nehmen wir einmal an, ihr Alibi wäre wahr..."

Allaussage

Diese Technik wendet man an, wenn man eine Aussage für alle Elemente einer Menge \( \small M \) zeigen möchte.

Anstatt die Aussage für jedes Element einzeln zu zeigen, wählt man ein beliebiges Element \( \small x \) als Repräsentant aus der Menge aus. An diesem \( \small x \) zeigt man dann die Aussage.

Da man \( \small x \) beliebig gewählt hat, gilt die Aussage dann für alle Elemente der Menge.

Existenzaussage

Wenn man nur zeigen möchte, dass es in einer Menge mindestens ein Element gibt, das eine Aussage erfüllt, so genügt es auch völlig ein solches Element anzugeben.

Ein einziges Beispiel genügt hier tatsächlich als Beweis.

Will man hingegen zeigen, dass eine Aussage von nur genau einem Element erfüllt wird, genügt das nicht. Dann muss man dieses eine Element finden und zeigen, dass die Aussage dafür stimmt. Anschließend muss man aber für alle anderen zeigen, dass sie der Aussage nicht genügen. Das kann schwierig sein.

Völlige Fallunterscheidung

In manchen Fällen kann man eine Allaussage \( \small D \) nicht direkt für ein beliebiges Element zeigen. Dann hilft oft eine Aufteilung der Menge M in mehrere Teilmengen nach dem Prinzip "divide et impera".

Wichtig ist dabei, dass alle Teilmengen die ursprüngliche Menge komplett abdecken. Man darf kein Element und keinen Sonderfall vergessen.

Dann lassen sich für die einzelnen Teilmengen die Aussagen \( \small A \), \( \small B \) und \( \small C \) zeigen, die übertragen auf die ganze Menge wieder zur Aussage \( \small D \) führen.

Beweis durch vollständige Induktion

Die Beweistechnik vollständige Induktion funktioniert nur für Elemente, die sich aufzählen lassen. Dann ist sie aber häufig die einfachste und schnellste aller möglichen Herangehensweisen.

Die vollständige Induktion besteht aus zwei Teilen:

Induktionsanfang

Man zeigt, dass eine Aussage für das Element mit der Nummer 0 wahr ist.

Induktionsschritt

Man wählt sich ein beliebiges Element \( \small n \) aus. Dann nimmt man (ohne es sicher zu wissen) an, dass die Aussage für \( \small n \) schon bewiesen wäre. Wenn dann daraus folgt, dass die Aussage auch für das Element \( \small n+1 \) gelten muss, ist man fertig.