Beweistechniken

Bei direkten Beweisen beginnen wir mit bestimmten Voraussetzungen und leiten daraus schrittweise die Behauptung her. Wir zeigen die Richtigkeit der zu beweisenden Aussage dabei direkt. Mathematisch ausgedrückt haben direkte Beweise somit die Form A ⇒ B, wobei A die Voraussetzungen sind und B die Aussage darstellt, die bewiesen werden soll.

Man nimmt absichtlich das Gegenteil der Behauptung an (Voraussetzung A ist wahr, aber B ist falsch). Mit dieser Annahme folgert man logisch weiter, bis man zwingend auf einen mathematischen Fehler oder Unsinn stößt. Dieser Widerspruch beweist, dass die Gegenteils-Annahme falsch war und die Originalaussage somit stimmen muss.

Anstatt die Originalaussage (A ⇒ B) direkt zu beweisen, beweist man ihre logisch gleichwertige Umkehrung: ¬B ⇒ ¬A. Man startet mit der Annahme, dass das Ziel falsch ist (¬B), und rechnet zielgerichtet darauf hin, dass dann auch die Voraussetzung falsch sein muss (¬A). Ist dieser umgekehrte Weg bewiesen, gilt aufgrund der Gesetze der Logik automatisch auch die ursprüngliche Behauptung.

>> Wenn nicht B, dann nicht A <<

Häufig stehen wir vor der Aufgabe, mehrere äquivalente Aussagen zu beweisen, die sich alle aus einer gemeinsamen Voraussetzung ergeben.

Hierzu zeigen wir einfach, dass A1 ⇒ A2, A2 ⇒ A3 und A3 ⇒ A1 gilt. Dadurch können wir jede Aussage aus jeder anderen folgern, indem wir einfach den Implikationspfeilen folgen. A2 folgt z. B. aus A3 über A3 ⇒ A1 ⇒ A2.

Ein Beweisverfahren für natürliche Zahlen nach dem Domino-Prinzip. Man beweist zuerst, dass die Aussage für den kleinsten Wert (meist n=1) gilt (Induktionsanfang). Danach beweist man die Regel: Wenn die Aussage für eine beliebige Zahl n gilt, dann muss sie zwingend auch für die Folgezahl n+1 gelten (Induktionsschritt).