Direkter Beweis und Kettenschluss

Worum es geht

Skript Teil 2, Folien 6 bis 10: Direkter Beweis.

Ein Satz der Form $A \Rightarrow B$ sagt: Wenn $A$ gilt, dann gilt auch $B$ . $A$ heißt Voraussetzung oder Hypothese, $B$ heißt Behauptung. Der direkte Beweis nimmt $A$ als wahr an und leitet daraus $B$ her.

So gehen wir vor:

Die Regel, die jeden Schritt trägt: der Modus ponens.
Wie sich daraus eine Kette von Schritten ergibt.
Ein Beweis an einem Beispiel: Ist $n$ ungerade, ist auch $n^2$ ungerade.
Der Kettenschluss: zwei Implikationen zu einer verbinden.

Wenn A gilt und aus A folgt B

Skript · modus ponendo ponens (Abtrennungsregel, kurz MP)

\big(A \land (A \Rightarrow B)\big) \Rightarrow B

„Wenn $A$ (die Hypothese) gilt und aus $A$ folgt $B$ , dann muss auch $B$ gelten.“

Angenommen, zwei Dinge sind bekannt: $A$ ist wahr, und $A \Rightarrow B$ ist wahr. Dann darf man schließen: $B$ ist wahr. Diese Schlussregel heißt Abtrennungsregel: Man „trennt“ $B$ von der Implikation ab. Das Skript nennt sie lateinisch modus ponendo ponens, etwa „Schlussweise durch Setzen“. Wir sagen kurz Modus ponens oder MP.

Rechts sieht man, warum: $A$ und $A \Rightarrow B$ sind nur in Zeile 4 beide wahr. Und in Zeile 4 ist $B = 1$ .

Aus Teil 1, Abschnitt 3 („Wenn-dann, genau dann, XOR, NAND, NOR“):

A \Rightarrow B

ist nur falsch, wenn

A

wahr und

B

falsch ist.

Der Modus ponens ist eine Tautologie

Voraussetzung und ganze Regel, Zeilen 1 bis 4

A \land (A \Rightarrow B):\ 0,\,0,\,0,\,1

\big(A \land (A \Rightarrow B)\big) \Rightarrow B:\ 1,\,1,\,1,\,1

Die ganze Regel ist selbst ein logischer Ausdruck: eine Implikation mit der Voraussetzung $A \land (A \Rightarrow B)$ . Diese Voraussetzung ist in den Zeilen 1 bis 3 gleich 0. Eine Implikation mit falscher Voraussetzung ist wahr, also steht dort 1. In Zeile 4 ist die Voraussetzung 1 und auch $B = 1$ , also $1 \Rightarrow 1 = 1$ .

Die Spalte ist in allen vier Zeilen 1. Der Ausdruck ist also eine Tautologie: immer wahr, egal was $A$ und $B$ sind.

Darum ist die Regel sicher. Wer sie benutzt, kann nie von Wahrem zu Falschem kommen.

Aus Teil 1, Abschnitt 5 („Tautologie, Gleichheit und Rechengesetze“): Eine Tautologie ist ein Ausdruck, der für jede Belegung wahr ist.

Direkter Beweis und Kettenschluss

Worum es geht

Wenn A gilt und aus A folgt B

Der Modus ponens ist eine Tautologie

Wahrheitstafel

Abbildung 1Wahrheitstafel

Schritt 0Worum es geht

Schritt 1Wenn A gilt und aus A folgt B

Schritt 2Der Modus ponens ist eine Tautologie

Wahrheitstafel

Abbildung 1Wahrheitstafel

Worum es geht

Wenn A gilt und aus A folgt B

Der Modus ponens ist eine Tautologie