< Index

Beweise

In der Mathematik ist ein Beweis eine logische Herleitung einer Behauptung aus einer wahren Prämisse.
Dass heißt, wir leiten aus etwas bereits bewiesenem (etwas wahrem) her, dass unsere Behauptung auch wahr ist.
Um dies zu tun können wir unterschiedliche Beweistechniken verwenden:

Direkter Beweis
Seien $P_1, \ldots , P_n$ unsere Prämissen und $B$ unsere Behauptung, so zeigen wir: Aus $P_1, \ldots , P_n \Rightarrow B$.
Oft sind ein paar Zwischenschritte nötig so dass es eher so aussieht: Aus $P_1, \ldots , P_n \Rightarrow A_1 \Rightarrow A_2 \Rightarrow \dots \Rightarrow A_n \Rightarrow B$.
Indirekter Beweis
Sei unsere Prämisse $P$ und unsere Behauptung $B$, so zeigen wir anstatt von $P \Rightarrow B$ die Implikation $\neg B \Rightarrow \neg P$.
Diese beiden Formen sind ja äquivalent. Man zeigt hier, würde $B$ nicht gelten, dann würde ja auch $P$ nicht gelten aber von $P$ wissen wir, dass es wahr ist.
Aus diesem Widerspruch folgt, dass $B$ nicht falsch sein kann und somit wahr ist.
Widerspruchsbeweis
Anstatt $A\Rightarrow B$ zu zeigen kann man zeigen, dass $A\wedge \neg B$ falsch ist.
Das Gegenteil ist also wahr und dies wäre $\neg \left( A\wedge \neg B\right) = \neg A \vee B$, also $A\Rightarrow B$.
Der Widerspruchsbeweis ist ebenfalls ein Indirekter Beweis.
Vollkommene Fallunterscheidung
Manchmal gibt es nicht viele Möglichkeiten (eine Zahl ist z.B. gerade oder ungerade, eine Aussage wahr oder falsch, ein Extrema existiert oder nicht, ...).
Hier kann man für jeden Fall gesondert zeigen, dass er stimmt. Wir haben diese Beweisvariante bei den Wahrheitstabellen genutzt.
Vollständige Induktion
Hier zeigt man, dass die Aussageform $A(n)$ für einen (Anfangs)-Wert stimmt (z.B. $A(0)$) und zeigt zusätzlich, dass $A(n)\Rightarrow A(n+1)$ wahr ist. Somit gilt die Aussageform $A(n)$ für alle $n$ die größer oder gleich dem Anfangswert sind.
Es gibt noch weitere Möglichkeiten, wie das Schubfach-Prinzip, das Diagonalverfahren,

Uns interessiert hier der direkte und der Indirekte Beweis.

Ein Paar Definitionen

Definition:
Eine ganze Zahl $z$ ist gerade, wenn es eine ganze Zahl $k$ gibt, so dass $z=2\cdot k$ ist.

Somit ist 10 eine gerade Zahl, da $10=2\cdot 5$ gilt. Die Zahl 7 hingegen ist nicht gerade, da es keine ganze Zahl $k$ gibt, so dass $7=2\cdot k$ ist.
Man kann ungerade Zahlen, so definieren, dass sie nicht gerade sind. Allerdings ist die nachstehende Definition hilfreicher.

Definition:
Eine ganze Zahl $z$ ist ungerade, wenn es eine ganze Zahl $k$ gibt, so dass $z=2\cdot k+1$ ist.

Somit ist 7 eine ungerade Zahl, da $7=2\cdot 3+1$. Die Zahl 20 hingegen ist nicht ungerade, da es keine ganze Zahl $k$ gibt, so dass $20=2\cdot k+1$ ist.

Direkter Beweis

Dass eine Aussageform falsch ist lässt sich am leichtesten mit einem Gegenbeispiel zeigen.
Ist eine Aussageform allerdings wahr muss man für alle möglichen Variablenbelegungen zeigen, dass diese wahr sind.

Beispiele

Alle ungeraden Zahlen sind Primzahlen.
Dies ist eine falsche Aussageform, denn $9=2\cdot 4+1$ ist eine ungerade Zahl aber keine Primzahl.
Von zwei aufeinanderfolgenden ganze Zahlen ist eine immer gerade.
Dies ist wahr.
Beweis:
- Seien $n$ und $k$ zwei aufeinanderfolgende Zahlen und sei $k$ die größere der beiden, dann gilt $k=n+1$
- Ist $n$ gerade, so sind wir fertig
- Ist $n$ ungerade so gibt es ein $t$ mit $n=2t+1$
  dann ist $k=(2t+1)+1 = 2t+2 = 2(t+1)$ und somit ist $k$ gerade
Wenn $n$ eine natürliche Zahl ist, dann ist $n+(n+1)+(n+2)$ durch 3 teilbar.
Anders formuliert: Die Summe von drei aufeinanderfolgenden Zahlen ist durch 3 teilbar.
Beweis:
- Zum einen ist $n+(n+1)+(n+2)$ eine natürliche Zahl, wenn $n$ eine natürliche Zahl ist
- Durch umformen ergibt sich: $n+(n+1)+(n+2)=3n+3 = 3(n+1)$
- Der Term $3(n+1)$ ist durch 3 teilbar, da er ein Vielfaches von 3 ist.

Indirekter Beweis

Da die Aussage $A\Rightarrow B$ gleichbedeutend mit $\neg B \Rightarrow \neg A$ ist , können wir indirekt zeigen, dass aus $\neg B$ folgt würde, dass $\neg A$ gilt.
Oder wir zeigen über den Widerspruch, dass $A\wedge \neg B$ falsch ist, dass $A\Rightarrow B$ gilt.

Beispiele

Jede Primzahl größer 2 ist ungerade. Also aus $\mathcal{P}(x) \wedge x\gt 2 \Rightarrow x $ ist ungerade.
Variante 1 (Widerspruch)
Beweis:
- Sei die Aussage $A$ die linke Seite der Implikation (Prämisse)
  $A: \mathcal{P}(x) \wedge x\gt 2$
  und
  sei die Aussage $B$ die rechte Seite der Implikation (Folgerung)
  $B: x$ ungerade
  
  Der Widerspruchsbeweis startet mit $A\wedge \neg B$
  Somit ist $A\wedge \neg B: (\mathcal{P}(x) \wedge x\gt 2)\wedge B$ ist nicht ungerade.
- $(\mathcal{P}(x) \wedge x\gt 2)\wedge B$ ist nicht ungerade
  Dies kann man schöner schreiben: $\mathcal{P}(x) \wedge x\gt 2 \wedge x $ gerade
- Da $x$ gerade ist und größer als 2, muss $x=2k$ gelten und zwar mit $k\gt 1$.
- Jedes solche $x$ hat aber mindestens 3 Teiler, nämlich $2k, 2$ und $1$.
  Somit ist $x$ keine Primzahl und die Aussage ($(\mathcal{P}(x) \wedge x\gt 2)\wedge B$ ist gerade) ist falsch.
  Es gilt also das Gegenteil: $\mathcal{P}(x) \wedge x\gt 2 \Rightarrow x $ ist ungerade.
Variante 2 (Indirekt)
Beweis:
- $A: \mathcal{P}(x) \wedge x\gt 2$ und
  $B: x$ ungerade
  Der indirekte Beweis startet mit $\neg B \Rightarrow \neg A$
- Die Aussage $\neg B$ ist gleichbedeutend mit: $x$ ist gerade
- Aus $x$ ist gerade folgt: Es gibt ein $k$ mit $x=2k$ mit $k\geq 1$
- Für $k=1$ erhält man $x=2$, was nicht größer als 2 ist $\Rightarrow A$ wäre falsch
  für $k\gt 1$ hat $x$ die Teiler $1, 2, k, 2k$, somit ist es keine Primzahl und $A$ wäre falsch
- Somit folgt aus $\neg B$ direkt $\neg A$
  Damit gilt $A\Rightarrow B$
Es gibt keine größte natürliche Zahl.
Beweis:
- Angenommen es gäbe eine größte natürliche Zahl, nennen wir sie $N\in\mathbb N$.
- Für jede Zahl $n\in \mathbb{N}$ gilt, dass auch ihr Nachfolger eine natürliche Zahl ist ($n+1\in\mathbb{N}$)
- Da $N$ eine natürliche Zahl ist, muss auch $N+1$ eine natürliche Zahl sein
- Es gilt aber $N\lt N+1$, dies ist ein Widerspruch, da $N$ nicht mehr die größte natürliche Zahl ist.
- Die Annahme "es gibt eine größte natürliche Zahl" ist somit falsch und das Gegenteil gilt.

Aufgaben

Zeige, dass $2k-1$ ungerade ist für alle $k\in\mathbb{Z}$.
Zeige dies direkt.
Lösung:
Wenn $2k-1$ ungerade ist, können wir es durch $2a+1$ darstellen.
- Es muss also ein $a\in\mathbb Z$ geben, so dass $2a+1=2k-1$ ist
- Formen wir nach $a$ um, so erhalten wir: $2a=2k-2\Rightarrow 2a=2(k-1) \Rightarrow a=k-1$
- Mit $a=k-1$ oder mit $k=a+1$ haben wir eine Lösung.
Alternativ können wir argumentieren, dass ungerade und gerade Zahlen immer abwechseln auftreten.
Somit ist der Nachfolger von $2k-1$ die Zahl $2k$ (welche gerade ist), womit $2k-1$ ungerade sein muss.
Zeige, dass die Summe zweier ungeraden Zahlen gerade ist.

Lösung:
Die Zahlen $x=2a+1$ und $z=2b+1$ sind unsere ungeraden Zahlen.
$x+z=(2a+1)+(2b+1) = 2a+2b+2 = 2(a+b+1)$
Mit $k=a+b+1$ erhält man $x+y=2k$ was laut Definition eine gerade Zahl ist.
Zeige, dass die Summe $x+y$ eine gerade Zahl ist, wenn $x$ gerade ist und $y$ gerade ist.

Lösung:
Die Zahlen $x=2a$ und $y=2b$ sind unsere geraden Zahlen.
$x+y=2a+2b = 2a+2b = 2(a+b)$
Mit $k=a+b$ erhält man $x+y=2k$ was laut Definition eine gerade Zahl ist.
Zeige, dass die Summe $x+y$ ungerade ist, wenn $x$ gerade ist und $y$ ungerade ist.

Lösung:
Da $x$ gerade ist, können wir es durch $2k$ ersetzen.
Da $y$ ungerade ist, ersetzen wir es durch $2n+1$.
$x+y=2k+(2n+1) = 2k+2n+1 = 2(k+n)+1$
Mit $a=k+n$ erhalten wir $x+y=2k+1$ was laut Definition eine ungerade Zahl ist.
Für jedes $x\in\mathbb Z$ gilt, dass wenn $7x+9$ gerade ist, ist $x$ ungerade.
Zeigen Sie dies durch einen indirekten Beweis.
Lösung:
Wir starten also mit $x$ ist gerade
- Wenn $x$ gerade ist, können wir es per Definition als $2k$ darstellen (für eine ganze Zahl $k$)
- Setzen wir dies in $7x+9$ ein erhalten wir:
  $7(2k)+9 = 14k+9$
- Wir wollen jetzt zeigen, dass $14k+9$ ungerade ist, also in der Form $2a+1$ dargestellt werden kann
- $14k+9 = 14k + 8 + 1 = 2(7k+4)+1$
- Setzen wir $b=7k+4$ erhalten wir $2(7k+4)+1=2b+1$. Somit ist $7x+9$ ungerade, wenn $x$ gerade ist
Man kann diese Aussage auch direkt beweisen, allerdings ist dies nicht so schön und komplizierter.
Als Faustregel beim Beweisen von $A\Rightarrow B$ kann man nehmen, dass wenn
- $A$ einfacher als $B$ ist, man direkt beweist und wenn
- $B$ einfacher als $A$ ist, man indirekt beweist
Für jedes $n\in\mathbb Z$ gilt, dass wenn $n$ gerade ist auch $n^2$ gerade ist.
Zeigen Sie dies direkt.
Lösung:
- Wenn $n$ gerade ist, können wir es per Definition als $2k$ darstellen (für eine ganze Zahl $k$)
- Setzen wir $n=2k$ in $n^2$ ein, erhalten wir: $(2k)^2$
- Jetzt müssen wir $(2k)^2$ so umformen, dass wir es als $2a$ darstellen können (mit $a\in \mathbb Z$)
- Formen wir um: $(2k)^2=2^2\cdot k^2 = 4k^2$
- Den Term $4k^2$ kann man als $2a$ darstellen, wenn man $a=2k^2$ wählt. $4k^2= 2(2k^2)=2a$
- Somit sind die Quadrate aller geraden Zahlen gerade.
Für jedes $n\in\mathbb Z$ gilt, dass wenn $n$ ungerade ist auch $n^2$ ungerade ist.
Zeigen Sie dies direkt.
Lösung:
- Wenn $n$ ungerade ist, können wir es per Definition als $2k+1$ darstellen (für eine ganze Zahl $k$)
- Setzen wir dies für $n$ in $n^2$ ein, erhalten wir: $(2k+1)^2$
- Jetzt müssen wir $(2k+1)^2$ so umformen, dass wir es als $2a+1$ darstellen können (mit $a\in \mathbb Z$)
- Formen wir um: $(2k+1)^2=4k^2+4k+1$
- Den Term $4k^2+4k+1$ ist gleich $2(2k^2+2k)+1$
- Mit $a=2k^2+2k$ gilt: $4k^2+4k+1=2a+1$
- Somit sind die Quadrate ungerader Zahlen ungerade.
Zeige, dass aus $n^2$ ist ungerade folgt, $n$ ist ungerade.
Wählen Sie ihre Beweisart weise und berücksichtigen Sie die Ergebnisse der vorhergehenden Aufgaben.

Lösung:
Vorher haben wir bewiesen, dass aus $n$ gerade folgt, dass $n^2$ gerade ist.
Wenn wir jetzt indirekt beweisen, sind wir schon fertig.
Wir müssen ja beim indirekten Beweis zeigen, dass aus $n$ gerade folgt, dass $n^2$ gerade ist.
Sei hier $A: n^2$ ist ungerade und
$B: n$ ist ungerade
Es ist $A\Rightarrow B$ äquivalent zu $\neg B\Rightarrow \neg A$,
also zu: aus $\neg B$ ($n$ gerade) folgt $\neg A$ (also $n^2$ ist gerade).
Seien $n, z\in\mathbb Z$. Es gilt, dass wenn $n$ gerade ist auch $n\cdot z$ gerade ist.
Zeigen Sie dies direkt.
Lösung:
- Wenn $n$ gerade ist, können wir es per Definition als $2k$ darstellen (für eine ganze Zahl $k$)
- Setzen wir $n=2k$ in $n\cdot z$ ein, erhalten wir: $2n\cdot z$
- $2n\cdot z=2(n\cdot z) = 2a$ mit $a=n\cdot z$
- Somit ist das Produkt zweier Zahlen gerade, wenn mindestens ein Faktor gerade ist.
Zeige, dass aus $n$ ist gerade folgt, $n^3$ ist gerade.
Zeigen Sie dies direkt mittels der Erkenntnisse aus den vorherigen Aufgaben.

Lösung:
Vorher haben wir gezeigt dass von jedem geraden $n$ das Quadrat $n^2$ gerade ist.
Der Term $n^3$ ist: $n\cdot n^2$, da $n$ gerade ist und somit auch $n^2$ haben wir hier das Produkt zweier geraden Zahlen.
Ein Produkt ist gerade, wenn mindestens ein Faktor gerade ist.
Somit ist $n\cdot n^2$ gerade, wenn $n$ gerade ist.
Zeige, dass für alle $a,b\in\mathbb{Z}$ gilt, dass wenn $a^2(b^2-2b)$ ungerade ist auch $a$ und $b$ ungerade sind.

Lösung:
Hier ist ein indirekter Beweis:
Laut De'Morgan ist das Gegenteil von $a$ ist ungerade und $b$ ist ungerade: $a$ gerade oder $b$ gerade.
Wir können jetzt zwei Fälle getrennt untersuchen:
Fall 1: $a$ ist gerade
Fall 2: $b$ ist gerade
In beiden Fällen muss folgen, dass $a^2(b^2-2b)$ gerade. Wenn dies folgt, haben wir den indirekten Beweis fertig.

Fall 1: $a$ gerade
Da $a$ gerade ist, ersetzen wir es mit $2k$:
$a^2(b^2-2b)=(2k)^2(b^2-2b)=2(2k^2)(b^2-2b)$ ist gerade.

Fall 2: $b$ gerade
Da $b$ gerade ist, ersetzen wir es mit $2k$:
$a^2(b^2-2b)=$ $a^2((2k)^2-2(2k))=$ $a^2(4k^2-4k)=$ $2\cdot a^2(2k^2-2k)$ ist gerade.

Der Fall $a$ und $b$ sind gerade muss nicht untersucht werden, da wir weder bei $a$ ist gerade noch bei $b$ ist gerade die andere Variable eingeschränkt haben.

Lösung:
$a^2(b^2-2b)$ ist ein Produkt aus $a^2$ und $b^2-2b$.
Ein Produkt ist ungerade, wenn alle Faktoren ungerade sind.
Somit muss $a^2$ ungerade sein (woraus folgt, dass $a$ ungerade ist) und
$b^2-2b$ ist ungerade, also $b(b-2)$ muss ungerade sein.
Somit muss $b$ und $b-2$ ungerade sein. Wenn $b$ ungerade ist ist $b=2k+1$ und dann ist $b-2=2k-1$, was ebenfalls ungerade ist.
Seien $x, y \in\mathbb Z$. Wenn $x^2(y + 3)$ gerade ist, dann ist $x$ gerade oder $y$ ist ungerade.
Zeigen Sie dies durch einen indirekten Beweis.

Lösung:
Wir zeigen, dass aus $x^2(y + 3)$ gerade folgt, das $x$ gerade oder $y$ ungerade ist,
indem wir zeigen dass aus $\neg (x\text{ gerade} \vee y\text{ ungerade})$ folgt, dass $x^2(y + 3)$ ungerade ist.

Laut De'Morgan ist $\neg (x\text{ gerade} \vee y\text{ ungerade})$ das gleiche wie: $x$ ungerade und $y$ gerade.
Wir ersetzen also $x=2a+1$ und $y=2b$:
$x^2(y + 3)=(2a+1)^2(2b+3) =$ $(4a^2+4a+1)(2b+3)=$ $(2(2a^2+2a)+1)(2(b+1)+1)$
Dies ist das Produkt zweier ungeraden Zahlen, denn $2(2a^2+2a)+1$ ist ungerade und $2(b+1)+1$ ist ebenfalls ungerade.
Ein Produkt aus zwei ungeraden Zahlen ist ungerade, da $(2k+1)(2n+1)=4kn+2k+2n+1 = 2(2kn+k+n)+1$.
Wenn also $x$ ungerade und $y$ gerade gilt, folgt $x^2(y + 3)$ ist ungerade, damit gilt auch, dass aus $x^2(y + 3)$ gerade folgt, das $x$ gerade oder $y$ ungerade ist.