studyklar
MG · Vorlesung Teil 2 · Abschnitt 6

Beweis durch Fallunterscheidung

Manchmal lässt sich eine Aussage nicht in einem Zug beweisen. Dann teilt man alle Möglichkeiten in Fälle und beweist sie in jedem Fall einzeln. Rechts steht die Regel dahinter, dann ein Beispiel mit Zahlen und sein Beweis. Mit Weiter geht es Schritt für Schritt voran.

Worum es geht

Skript Teil 2, Folien 16 bis 18: Beweis durch Fallunterscheidung.

Eine ganze Zahl ist entweder gerade oder ungerade. Mit jeder der beiden Möglichkeiten kann man gut rechnen, mit „irgendeine Zahl“ dagegen nicht. Darum zerlegt man den Beweis: einmal für gerade Zahlen, einmal für ungerade.

So gehen wir vor:

  1. Die Regel, die eine Fallunterscheidung erlaubt.
  2. Die Division mit Rest, die das Beispiel braucht.
  3. Der Satz: Eine Quadratzahl lässt bei Division durch 4 den Rest 0 oder 1.
  4. Sein Beweis in zwei Fällen.

B folgt aus A und aus ¬A

Skript · Beweis durch Fallunterscheidung

Ein Beweis durch Fallunterscheidung beruht auf der Tautologie

((A⇒B)∧(¬A⇒B))⇔B\big((A \Rightarrow B) \land (\neg A \Rightarrow B)\big) \Leftrightarrow B

BB kann also bewiesen werden, indem die Gültigkeit beider Implikationen gezeigt wird. Wir unterscheiden die Fälle

  1. „AA ist wahr“, und damit gilt AA, und
  2. „AA ist falsch“, und damit gilt ¬A\neg A.

Man will BB beweisen. Man sucht sich eine Aussage AA und zeigt zwei Implikationen: Wenn AA gilt, folgt BB. Und wenn AA nicht gilt, folgt auch BB.

Eins von beiden ist immer so: AA ist wahr oder falsch. In beiden Fällen kommt man bei BB an. Also gilt BB.

In der Tafel kürzt XX die beiden Implikationen ab. Die Spalte von XX ist gleich der Spalte von BB.

Aus Teil 1, Abschnitt 3 („Wenn-dann, genau dann, XOR, NAND, NOR“): A⇒BA \Rightarrow B ist nur falsch, wenn AA wahr und BB falsch ist. X⇔YX \Leftrightarrow Y ist wahr, wenn beide denselben Wert haben.

Eine Tautologie, auch für mehr Fälle

Spalte der Regel, Zeilen 1 bis 4
X⇔B: 1, 1, 1, 1X \Leftrightarrow B:\ 1,\,1,\,1,\,1
Skript

Einer der beiden Fälle tritt immer ein! Es kann mehr als zwei Fälle geben!

Die letzte Spalte ist in allen vier Zeilen 1. Die Regel ist also eine Tautologie und darf in jedem Beweis benutzt werden.

Wichtig ist nur, dass die Fälle zusammen alle Möglichkeiten abdecken. Es dürfen auch mehr als zwei sein. Beispiel: Bei Division durch 3 bleibt der Rest 0, 1 oder 2. Das sind drei Fälle, und jede natürliche Zahl fällt in genau einen.

Aus Teil 1, Abschnitt 5 („Tautologie, Gleichheit und Rechengesetze“): Eine Tautologie ist ein Ausdruck, der für jede Belegung wahr ist.
Noch 6 Schritte bis zum Ergebnis
Den ganzen Lösungsweg sehen Studierende und Lehrende der HS KL. Registriere dich mit deiner Adresse @stud.hs-kl.de oder @hs-kl.de, dann geht es hier direkt weiter.
Registrieren

Wahrheitstafel

Fallunterscheidung

Abbildung 1Wahrheitstafel

Fallunterscheidung

ZeileAABBA⇒BA \Rightarrow B¬A⇒B\neg A \Rightarrow BXXX⇔BX \Leftrightarrow B
1001001
2011111
3100101
4111111
LegendeX=(A⇒B)∧(¬A⇒B)X = (A \Rightarrow B) \land (\neg A \Rightarrow B)Wahrheitstafel der Fallunterscheidung.