LERNZIELE:
Am Ende dieser Unterrichtseinheit wird der/die Studierende in der Lage sein:

1. Zu erkennen, dass es zwei Arten von Beweisen gibt, die unterschieden werden müssen: interne oder deduktive und externe oder metamathematische Beweise.
2. Mathematische Induktion anzuwenden, um Beweise über natürliche Zahlen und in der Aussagenlogik zu führen.
3. Konjunktions- und Disjunktionsnotationen zu verwenden, um Aussagenlogik-Ausdrücke zu formulieren.
4. Die verallgemeinerte Form der De-Morgan-Gesetze und der Distributivgesetze der Aussagenlogik zu verstehen.
5. Das Konzept der Induktionshypothese und ihre Rolle im Induktionsbeweis zu verstehen.

INHALTSVERZEICHNIS
INTERNE UND EXTERNE BEWEISE
BEWEISE DURCH MATHEMATISCHE INDUKTION
INDUKTIONSBEWEISE IN DER AUSSAGENLOGIK
VERALLGEMEINERTE FORM DER DE-MORGAN-GESETZE
VERALLGEMEINERTE FORM DER DISTRIBUTIVGESETZE

Interne und externe Beweise

Es gibt zwei Arten von Beweisen, die unterschieden werden müssen. Bisher haben wir viele Beispiele formaler Beweise gesehen. Diese Art von Beweisen ergibt sich aus den Regeln der Logik. Solche Beweise finden „innerhalb der Logik“ statt und werden daher auch als „interne“ oder deduktive Beweise bezeichnet. Diese Art von formalen Beweisen hat einen begrenzten Anwendungsbereich, da sie nur dazu dienen, Aussagen zu beweisen, die in der Sprache der Logik formuliert werden können. Es kann jedoch sein, dass wir etwas über die Logik selbst beweisen wollen. Wir könnten etwa zeigen wollen, dass alle Aussagen der Aussagenlogik eine bestimmte Eigenschaft erfüllen. Solche Aussagen, die sich auf die Logik selbst beziehen, können weder innerhalb der Logik formuliert noch dort bewiesen werden. Um solche Aussagen zu beweisen, verwenden wir einen externen Beweis. Externe Beweise werden manchmal auch „metamathematisch“ genannt, und wir sind dieser Art von Überlegungen bereits begegnet, etwa beim (Meta-)Deduktionstheorem. Hier kommt der Kontext für Induktionsbeweise ins Spiel.

Beweise durch Mathematische Induktion

Die Mathematische Induktion ist eine Beweismethode, mit der wir zeigen können, dass bestimmte Aussagen für alle natürlichen Zahlen gelten.

BEISPIEL:
Es lässt sich zeigen, dass jede Zahl der Form 11^n - 4^n, wobei n eine natürliche Zahl ist, immer durch 7 teilbar ist.
BEWEIS: Betrachten wir zunächst den Fall n=1, so sehen wir:

11^1 - 4^1 = 7

was offensichtlich durch 7 teilbar ist.

Nehmen wir nun an, dass 11^n - 4^n für ein n=k durch 7 teilbar ist. Daraus wollen wir zeigen, dass die Aussage auch für n=k+1 gilt. Dies lässt sich wie folgt durchführen:

Wenn also 11^k - 4^k durch 7 teilbar ist, dann ist es auch 11 ( 11^{k} - 4^{k} ) + 7\cdot 4^{k}, was wiederum bedeutet, dass auch 11^{k+1} - 4^{k+1} durch 7 teilbar ist. Daraus folgt, dass wenn 11^k - 4^k für k=1 teilbar ist, es auch für k=2, k=3, k=4,\cdots usw. gilt – und somit für jedes n\in\mathbb{N}. In diesem Fall spricht man von vollständiger Induktion. ■

Induktionsbeweise in der Aussagenlogik

Für die Induktionsbeweise, die wir im Folgenden durchführen werden, ist es zunächst notwendig, die folgende Notationskonvention einzuführen:

NOTATION: Sei F_1,\cdots, F_n eine endliche Menge beliebiger Ausdrücke der Aussagenlogik. Die Konjunktionen und Disjunktionen dieser Ausdrücke werden eingeführt durch:

\displaystyle \bigwedge_{i=1}^n F_i := F_1\wedge \cdots \wedge F_n

\displaystyle \bigvee_{i=1}^n F_i := F_1\vee \cdots \vee F_n

Mit dieser Notation können wir uns nun den folgenden zwei verallgemeinerten Formen zuwenden.

Verallgemeinerte Form der De-Morgan-Gesetze

Gegeben eine endliche Menge von Ausdrücken der Aussagenlogik F_1,\cdots, F_n, gelten stets die folgenden zwei Eigenschaften:

\displaystyle\neg\left(\bigwedge_{i=1}^n F_i \right) \equiv \left( \bigvee_{i=1}^n \neg F_i \right)

\displaystyle\neg\left(\bigvee_{i=1}^n F_i \right) \equiv \left( \bigwedge_{i=1}^n \neg F_i \right)

BEWEIS: Zunächst beweisen wir durch Induktion über n, dass \neg\left(\bigwedge_{i=1}^n F_i \right) \equiv \left( \bigvee_{i=1}^n \neg F_i \right) gilt.

Zuerst betrachten wir den Anfangsfall n=1. In diesem Fall ist offensichtlich \neg F_1 \equiv \neg\left(\bigwedge_{i=1}^1F_i\right)\equiv \left(\bigvee_{i=1}^n \neg F_i \right) \equiv\neg F_1

Nehmen wir nun an, dass die Eigenschaft für ein n=k gilt; das heißt, dass für eine endliche Sammlung von Ausdrücken F_1, F_2, \cdots, F_k folgendes gilt:

\displaystyle \neg\left(\bigwedge_{i=1}^k F_i\right) \equiv \left(\bigvee_{i=1}^k \neg F_i\right)

Dann zeigen wir, dass daraus folgt:

\displaystyle \neg\left(\bigwedge_{i=1}^{k+1} F_i\right) \equiv \left(\bigvee_{i=1}^{k+1} \neg F_i\right)

Unter Verwendung der Definition der Konjunktion ergibt sich:

\displaystyle \neg\left(\bigwedge_{i=1}^{k+1} F_i\right) := \neg\left[\left(\bigwedge_{i=1}^{k} F_i\right) \wedge F_{k+1}\right]

Auf diesen Ausdruck können wir das klassische De-Morgan-Gesetz (für zwei Terme) anwenden und erhalten:

\displaystyle \neg\left(\bigwedge_{i=1}^{k+1} F_i\right)\equiv \left[\neg\left(\bigwedge_{i=1}^{k} F_i\right) \vee \neg F_{k+1}\right]

Wenden wir nun die Induktionsannahme an, erhalten wir:

\displaystyle \neg\left(\bigwedge_{i=1}^{k+1} F_i\right)\equiv \left[ \left(\bigvee_{i=1}^k \neg F_i\right) \vee \neg F_{k+1}\right] := \left(\bigvee_{i=1}^{k+1}\neg F_i \right)

Deshalb ist die Induktion abgeschlossen und die Eigenschaft gilt allgemein für jedes n. Die zweite Beziehung lässt sich auf vollkommen analoge Weise zeigen – das überlasse ich aber als Übung für die Lesenden, muajaja!

Verallgemeinerte Form der Distributivgesetze

Ähnlich wie bei den De-Morgan-Gesetzen lassen sich auch die Distributivgesetze wie folgt verallgemeinern. Seien \{F_1, \cdots, F_n\} und \{G_1,\cdots, G_m\} zwei endliche Mengen beliebiger Ausdrücke, dann gelten die folgenden Äquivalenzen:

\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^m G_j \right) \right] \equiv \left[\bigwedge_{i=1}^n\left(\bigwedge_{j=1}^m(F_i\vee G_j) \right) \right]

\displaystyle \left[ \left(\bigvee_{i=1}^n F_i \right) \wedge \left(\bigvee_{j=1}^m G_j \right) \right] \equiv \left[\bigvee_{i=1}^n\left(\bigvee_{j=1}^m(F_i\wedge G_j) \right) \right]

BEWEIS: Um diesen Beweis zu führen, müssen wir eine doppelte Induktion durchführen, über n und m. Im Folgenden führe ich zuerst die Induktion über n und danach über m durch, bezogen auf den Ausdruck \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^m G_j \right) \right] \equiv \left[\bigwedge_{i=1}^n\left(\bigwedge_{j=1}^m(F_i\vee G_j) \right) \right]

Nehmen wir m=1, dann wird dieser Ausdruck zu:

\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^1 G_j \right) \right] \equiv \left[\bigwedge_{i=1}^n\left(\bigwedge_{j=1}^1(F_i\vee G_j) \right) \right].

Was gleichbedeutend ist mit:

\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee G_1 \right] \equiv \left[\bigwedge_{i=1}^n\left( F_i\vee G_1 \right) \right].

Nun beweisen wir diesen Ausdruck durch Induktion über n.

Nehmen wir n=1, dann reduziert sich der Ausdruck auf

F_1 \vee G_1 \equiv F_1 \vee G_1.

Was natürlich wahr ist. Nehmen wir nun an, dass der Ausdruck für ein beliebiges n=k gilt; das heißt, die Induktionsannahme ist:

\displaystyle \left[ \left(\bigwedge_{i=1}^k F_i \right) \vee G_1 \right] \equiv \left[\bigwedge_{i=1}^k\left( F_i\vee G_1 \right) \right].

Dann zeigen wir im Folgenden, dass der Ausdruck auch für n=k+1 gilt.

Nach der Definition der Konjunktion gilt:

\displaystyle \left[\left(\bigwedge_{i=1}^{k+1}F_i \right) \vee G_1 \right] := \left[\left(\left(\bigwedge_{i=1}^{k}F_i \right)\wedge F_{k+1} \right) \vee G_1 \right]

Nun wenden wir das Distributivgesetz der \vee-Verknüpfung an und erhalten:

\displaystyle \left[\left(\bigwedge_{i=1}^{k+1}F_i \right) \vee G_1 \right] \equiv \left[\left(\left(\bigwedge_{i=1}^{k}F_i \right)\vee G_{1} \right) \wedge \left(F_{k+1} \vee G_1 \right) \right]

Und genau an diesem Punkt können wir die Induktionsannahme verwenden, um zu erhalten:

\displaystyle \left[\left(\bigwedge_{i=1}^{k+1}F_i \right) \vee G_1 \right] \equiv \left[\left(\bigwedge_{i=1}^k\left( F_i\vee G_1 \right) \right) \wedge \left(F_{k+1} \vee G_1 \right) \right] := \left[\bigwedge_{i=1}^{k+1}(F_{i}\vee G_1 \right]

Damit haben wir durch Induktion bewiesen, dass für alle n\in\mathbb{N} gilt:

\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right)\vee G_1\right] \equiv \left[\bigwedge_{i=1}^n(F_i\vee G_1)\right]

Da die Induktion über n abgeschlossen ist und der Fall m=1 funktioniert, bleibt nur noch die Induktion über m. Dazu formulieren wir die Induktionsannahme für ein m=l, also dass gilt:

\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^l G_j \right) \right] \equiv \left[\bigwedge_{i=1}^n\left(\bigwedge_{j=1}^l(F_i\vee G_j) \right) \right]

und daraus wollen wir zeigen, dass es auch für m=l+1 gilt.

Ausgehend, wie immer, von der Definition der Konjunktion ergibt sich:

\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j \right) \right] := \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\left(\bigwedge_{j=1}^{l} G_j \right) \wedge G_{l+1}\right) \right]

Nun wenden wir das Distributivgesetz für \vee an, dann ergibt sich:

\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j \right) \right] \equiv \left[ \left( \left(\bigwedge_{i=1}^n F_i \right) \vee \left( \bigwedge_{j=1}^l G_j \right) \right) \wedge \left( \left( \bigwedge_{i=1}^n F_i \right)\vee G_{l+1} \right) \right]

Infolgedessen können wir mit der Induktionsannahme schreiben:

\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j \right) \right] \equiv \left[ \bigwedge_{i=1}^n\left(\bigwedge_{j=1}^l(F_i\vee G_j) \right) \wedge \left( \left( \bigwedge_{i=1}^n F_i \right)\vee G_{l+1} \right) \right]

Und wenn wir nun das Resultat der Induktion über n anwenden, erhalten wir:

\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j \right) \right] \equiv \left[ \bigwedge_{i=1}^n\left(\bigwedge_{j=1}^l(F_i\vee G_j) \right) \wedge \left( \bigwedge_{i=1}^n (F_i \vee G_{l+1} )\right) \right]

Was schließlich durch die Definition der Konjunktion gleichbedeutend ist mit:

\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j \right) \right] \equiv \left[ \bigwedge_{i=1}^n\left(\bigwedge_{j=1}^{l+1}(F_i\vee G_j) \right) \right]

Und somit ist die Induktion über m abgeschlossen, und der Ausdruck

\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{m} G_j \right) \right] \equiv \left[ \bigwedge_{i=1}^n\left(\bigwedge_{j=1}^{m}(F_i\vee G_j) \right) \right]

gilt für alle n,m\in\mathbb{N}.

Dieser Streifzug durch die Induktionsbeweise hat gezeigt, wie sich rigorose mathematische Beweistechniken nicht nur im Bereich der natürlichen Zahlen, sondern auch in der Aussagenlogik anwenden lassen. Durch die Induktion konnten wir die Gültigkeit der verallgemeinerten Formen der De-Morgan-Gesetze und der Distributivgesetze etablieren und damit das Verständnis der logischen Grundlagen stärken, die zahlreichen Bereichen des mathematischen Wissens zugrunde liegen. Dieser Ansatz ist nicht nur wesentlich für die Entwicklung abstrakter Denkfähigkeiten, sondern stellt auch ein mächtiges Werkzeug dar, um komplexe Probleme in der Mathematik und darüber hinaus zu bewältigen.