All- und Existenzaussagen beweisen

Worum es geht

Skript Teil 2, Folien 19 und 20: Beweis von All- und Existenzaussagen.

Eine Allaussage sagt etwas über jedes Element einer Menge. Eine Existenzaussage sagt, dass es mindestens ein passendes Element gibt. Die Menge, aus der die Elemente kommen, heißt Grundmenge.

Aus Teil 1, Abschnitt 9 („Quantoren: für alle und es gibt“):

\forall

heißt „für alle“,

\exists

heißt „es gibt“.

\forall

ist falsch, sobald ein Gegenbeispiel existiert.

\exists

ist wahr, sobald ein Element passt.

So gehen wir vor:

Das Muster für Allaussagen, dann ein Beispiel.
Das Muster für Existenzaussagen, dann ein Beispiel.
Eine Ergänzung zur Form der Existenzaussage auf der Folie.

Das Muster: ein beliebiges a

Skript · Allaussagen

Universelle Aussagen, d. h. Allaussagen, der Form

\forall x: p(x) \Rightarrow q(x)

werden bewiesen, indem man die Gültigkeit der Aussage $p(a) \Rightarrow q(a)$ für jedes Element $a$ aus der Grundmenge zeigt. Dazu genügt üblicherweise ein Beweis, der unabhängig von der Wahl des konkreten Elements $a$ der Grundmenge gültig ist.

Prototypischer Beweis

Wähle ein beliebiges $a$ aus der Grundmenge.
Beweis der Implikation $p(a) \Rightarrow q(a)$ .
Da $a$ beliebig gewählt werden kann, folgt dann $\forall x: p(x) \Rightarrow q(x)$ .

Eine Allaussage kann unendlich viele Elemente betreffen. Man kann sie nicht einzeln prüfen. Darum nimmt man ein Element $a$ , über das man nichts weiter weiß als das, was alle Elemente gemeinsam haben.

Für dieses $a$ beweist man $p(a) \Rightarrow q(a)$ . Der Beweis benutzt keine besondere Eigenschaft von $a$ . Darum gilt er für jedes Element, das man für $a$ einsetzen könnte.

Merke: „Beliebig“ heißt: Im Beweis darf nichts stehen, was nur für ein bestimmtes Element gilt.

Beispiel: Vielfache von 6 sind gerade

Satz

Für alle $a \in \mathbb{Z}$ gilt: Ist $a$ durch 6 teilbar, dann ist $a$ gerade.

Beliebiges a mit p(a)

a = 6j \quad \text{mit } j \in \mathbb{Z}

Grundmenge sind die ganzen Zahlen $\mathbb{Z}$ . $p(a)$ ist „ $a$ ist durch 6 teilbar“, $q(a)$ ist „ $a$ ist gerade“.

Man wählt ein beliebiges $a$ und nimmt an, dass $p(a)$ gilt. Durch 6 teilbar heißt: $a = 6j$ mit einer ganzen Zahl $j$ . Welches $j$ , wird nicht festgelegt.

Zahlen wie 7, die nicht durch 6 teilbar sind, muss man nicht ansehen. Für sie ist $p(a)$ falsch, und aus Falschem folgt alles: $p(a) \Rightarrow q(a)$ ist dort von selbst wahr.

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

p \Rightarrow q

ist nur falsch, wenn

p

wahr und

q

falsch ist. Ist

p

falsch, ist

p \Rightarrow q

immer wahr.

All- und Existenzaussagen beweisen

Worum es geht

Das Muster: ein beliebiges a

Beispiel: Vielfache von 6 sind gerade

Für alle oder für eins

Abbildung 1Für alle oder für eins

Schritt 0Worum es geht

Schritt 1Das Muster: ein beliebiges a

Schritt 2Beispiel: Vielfache von 6 sind gerade

Für alle oder für eins

Abbildung 1Für alle oder für eins

Worum es geht

Das Muster: ein beliebiges a

Beispiel: Vielfache von 6 sind gerade