1 Sprache und Logik
1.1 Mathematik ist eine Sprache
Mathematik ist die Sprache der naturwissenschaftlichen Modellbildung. So entspricht zum Beispiel der Ausdruck \[\begin{equation} F = ma \end{equation}\] im Sinne des zweiten Newtonschen Axioms einer Theorie zur Bewegung von Objekten unter der Einwirkung von Kräften (Newton (1687)). Gleichermaßen entspricht der Ausdruck \[\begin{equation} \max_{q(z)} \int q(z) \ln \left(\frac{p(y,z)}{q(z)}\right)\,dz \end{equation}\] im Sinne der Variational Inference der zeitgenössischen Theorie zur Funktionsweise des Gehirns (Friston (2005)). Mathematische Symbolik dient dabei insbesondere der genauen Kommunikation wissenschaftlicher Erkenntnisse und zielt darauf ab, komplexe Sachverhalte exakt und effizient zu beschreiben. Wie beim reflektierten Umgang mit jeder Form von Sprache steht also die Frage “Was soll das heißen?” als Leitfrage im Umgang mit mathematischen Inhalten und Symbolismen immer im Vordergrund.
Als Sprachgebäude weist die Mathematik einige Besonderheiten auf. Zum einen sind ihre Inhalte oft abstrakt. Dies rührt daher, dass sich die Mathematik um eine möglichst breite Allgemeinverständlichkeit und Anwendbarkeit bemüht. Mathematische Zugänge zu den Phänomenen der Welt sind dabei an einer möglichst einfachen Transferierbarkeit von Erkenntnissen in andere Kontexte interessiert. Um dies zu ermöglichen, versucht die Mathematik möglichst genau und verständlich, also im Sinne präziser Begriffe zu arbeiten. Sie geht dabei streng hierarchisch vor, sodass an späterer Stelle eingeführte Begriffe oft ein gutes Verständnis der ihnen zugrundeliegenden und an früherer Stelle eingeführten Begriffe voraussetzen.
Die Genauigkeit der mathematischen Sprache impliziert eine hohe Informationsdichte. Sie ist daher eher nüchtern und lässt überflüssiges weg, sodass in mathematischen Texten im besten Fall alles für die Kommunikation einer Idee relevant ist. Als Rezipient:in mathematischer Texte nimmt man ihre Informationsdichte anhand des hohen Verbrauchs kognitiver Energie beim Lesen eines mathematischen Textes wahr. Dieser hohe Energieverbrauch gebietet insbesondere Ruhe und Langsamkeit bei einem auf ein gutes Verständnis abzielenden Lesen. Als Leitsatz im Umgang mit mathematischen Texten mag dabei folgendes Zitat dienen: “Einen mathematischen Text kann man nicht lesen wie einen Roman, man muss ihn sich erarbeiten” (Unger (2000)). Nach dem Lesen eines kurzen mathematischen Textes sollte man sich immer kritisch fragen, ob man das Gelesene wirklich verstanden hat oder ob man zur Klärung des Sachverhaltes weitere Quellen heranziehen sollte. Auch ist es hilfreich, sich im Sinne des berühmten Zitats “What I cannot create, I do not understand” von Richard Feynman eigene Aufzeichnungen anzufertigen und mathematische Sprachgebäude selbst nachzukonstruieren.
Möchte man sich also die Welt der naturwissenschaftlichen Modellbildung erschließen, so ist es hilfreich, beim Umgang mit ihrer mathematischen Ausdrucksweise und Symbolik die gleichen Strategien wie beim Erlernen einer Fremdsprache anzuwenden. Hierzu gehört neben dem Eintauchen in den entsprechenden Sprachraum, also der ständigen Exposition mit mathematischen Ausdrucksweisen, sicherlich auch zunächst einmal das Auswendiglernen von Begriffen und das Übersetzen von Texten in die Alltagssprache. Ein tiefes und sicheres Verständnis mathematischer Modellbildung ergibt sich dann insbesondere durch die Anwendung mathematischer Herangehensweisen in schriftlicher und mündlicher Form.
1.2 Grundbausteine
Im Folgenden stellen wir mit den Begriffen der Definition, des Theorems und des Beweises drei Grundbausteine mathematischer Kommunikation vor, die uns durchgängig begleiten.
Definition
Eine Definition ist ein Grundstein eines mathematischen Systems, der innerhalb dieses Systems weder begründet noch deduktiv abgeleitet wird. Definitionen können nur nach ihrer Nützlichkeit innerhalb eines mathematischen Systems bewertet werden. Eine Definition lernt man am besten erst einmal auswendig und hinterfragt sie erst dann, wenn man ihren Nutzen in der Anwendung verstanden hat oder von diesem nicht überzeugt ist. Etwas Entspannung und Ruhe beim Umgang mit auf den ersten Blick komplexen Definitionen ist generell hilfreich. Um zu kennzeichnen, dass wir ein Symbol als etwas definieren, nutzen wir die Schreibweise “\(:=\)”. Zum Beispiel definiert der Ausdruck “\(a := 2\)” das Symbol \(a\) als die Zahl Zwei. Definitionen enden in diesem Text immer mit dem Symbol \(\bullet\).
Theorem
Ein Theorem ist eine mathematische Aussage, die mittels eines Beweises als richtig (wahr) erkannt werden kann. Das heißt, ein Theorem wird immer aus Definitionen und/oder anderen Theoremen hergeleitet. Theoreme sind in diesem Sinne die empirischen Ergebnisse der Mathematik. Im Deutschen werden Theoreme oft auch als Sätze bezeichnet. In der angewandten, datenanalytischen Mathematik sind Theoreme häufig für Berechnungen hilfreich. Es lohnt sich also, sie auswendig zu lernen, da sie meist die Grundlage für Datenauswertung und Dateninterpretation bilden. Oft tauchen in Theoremen Gleichungen auf. Diese ergeben sich dabei aus den Voraussetzungen des Theorems. Um Gleichungen zu kennzeichnen, nutzen wir das Gleichheitszeichen “\(=\)”. So besagt beispielsweise der Ausdruck “\(a = 2\)” in einem gegebenen Kontext, dass aufgrund bestimmter Voraussetzungen die Variable \(a\) den Wert zwei hat. Theoreme enden in diesem Text immer mit dem Symbol \(\circ\).
Beweis
Ein Beweis ist eine Argumentationskette, die auf bekannte Definitionen und Theoreme zurückgreift, um die Richtigkeit (Wahrheit) eines Theorems zu belegen. Kurze Beweise tragen dabei oft zum Verständnis eines Theorems bei, lange Beweise eher nicht. Beweise sind also insbesondere die Antwort auf die Frage, warum eine mathematische Aussage gilt (“Warum ist das so?”). Beweise lernt man nicht auswendig. Wenn Beweise kurz sind, ist es sinnvoll, sie durchzuarbeiten, da sie meist als bekannt vorausgesetzte Inhalte wiederholen. Wenn sie lang sind, ist es sinnvoller sie zunächst zu übergehen, um sich nicht in Details zu verlieren und vom eigentlichen Weg durch das mathematische Gebäude abzukommen. Beweise enden in diesem Text immer mit dem Symbol \(\Box\).
Neben Definitionen, Theoremen und Beweisen gibt es mit Axiomen, Lemmata, Korollaren und Vermutungen noch weitere typische Bausteine mathematischer Texte. Wir werden diese Begriffe nicht verwenden und geben deshalb für sie nur einen kurzen Überblick.
- Axiome sind unbeweisbare Theoreme, in dem Sinne, als dass sie als Grundannahmen zum Aufbau mathematischer Systeme dienen. Der Übergang zwischen Definitionen und Axiomen ist dabei oft fließend. Da wir mathematisch nicht besonders tief arbeiten, bevorzugen wir in den allermeisten Fällen den Begriff der Definition.
- Ein Lemma ist ein “Hilfstheorem”, also eine mathematische Aussage, die zwar bewiesen wird, aber nicht so bedeutend ist wie ein Theorem. Da wir einerseits auf bedeutende Inhalte fokussieren und andererseits mathematische Aussagen nicht diskriminieren wollen, verzichten wir auf diesen Begriff und nutzen stattdessen durchgängig den Begriff des Theorems.
- Ein Korollar ist eine mathematische Aussage, die sich durch einen einfachen Beweis aus einem Theorem ergibt. Da die “Einfachheit” mathematischer Beweise eine relative Eigenschaft ist, verzichten wir auf diesen Begriff und nutzen stattdessen auch hier durchgängig den Begriff des Theorems.
- Vermutungen sind mathematische Aussagen, von denen unbekannt ist, ob sie beweisbar oder widerlegbar sind. Da wir im Bereich der angewandten Mathematik arbeiten, treffen wir nicht auf Vermutungen.
1.3 Aussagenlogik
Nachdem wir nun einige Grundbausteine mathematischer Sprachgebäude kennengelernt haben, wollen wir uns mit der Aussagenlogik einem einfachen System nähern, das es erlaubt, Beziehungen zwischen mathematischen Aussagen herzustellen und zu formalisieren. Die Aussagenlogik spielt zum Beispiel in der Definition von Mengenoperationen, bei Optimierungsbedingungen von Funktionen und in vielen Beweisen eine tragende Rolle. In der datenanalytischen Anwendung ist die Aussagenlogik die Grundlage der Booleschen Logik der Programmierung. In der mathematischen Psychologie ist die Aussagenlogik die Grundlage der Repräsentationstheorie des Messens.
Wir beginnen mit der Definition des Begriffs der mathematischen Aussage.
Definition 1.1 (Aussage) Eine Aussage ist ein Satz, dem eindeutig die Eigenschaft wahr oder falsch zugeordnet werden kann.
Das Adjektiv wahr kann auch als richtig verstanden werden. Wir kürzen wahr mit “w” und falsch mit “f” ab. Im Körper der reellen Zahlen ist zum Beispiel die Aussage \(1 + 1 = 2\) wahr und die Aussage \(1 + 1 = 3\) falsch. Man beachte, dass die Binärität des Wahrheitsgehalts von Aussagen eine Grundannahme der Aussagenlogik und damit formal wissenschaftlich und nicht empirisch zu verstehen ist. Wahrheitsgehalte beziehen sich nicht auf Definitionen, Definitionen sind immer wahr.
Eine erste Möglichkeit, mit Aussagen zu arbeiten, ist, sie zu negieren. Dies führt auf folgende Definition.
Definition 1.2 (Negation) \(A\) sei eine Aussage. Dann ist die Negation von \(A\) die Aussage, die falsch ist, wenn \(A\) wahr ist und die wahr ist, wenn \(A\) falsch ist. Die Negation von \(A\) wird mit \(\neg A\), gesprochen als “nicht \(A\)”, bezeichnet.
Beispielsweise ist die Negation der Aussage “Die Sonne scheint” die Aussage “Die Sonne scheint nicht”. Die Negation der Aussage \(1 + 1 = 2\) ist die Aussage \(1 + 1 \neq 2\) und die Negation der Aussage \(x>1\) ist die Aussage \(x \le 1\). Tabellarisch stellt man die Definition der Negation einer Aussage \(A\) wie folgt dar:
| \(A\) | \(\neg A\) |
|---|---|
| w | f |
| f | w |
Tabellen dieser Form nennt man Wahrheitstafeln. Sie sind ein beliebtes Hilfsmittel in der Aussagenlogik, das wir im Folgenden oft einsetzen werden.
Möchte man zwei Aussagen logisch verbinden, so bieten sich die Begriffe der Konjunktion und der Disjunktion an.
Definition 1.3 (Konjunktion) \(A\) und \(B\) seien Aussagen. Dann ist die Konjunktion von \(A\) und \(B\) die Aussage, die dann und nur dann wahr ist, wenn \(A\) und \(B\) beide wahr sind. Die Konjunktion von \(A\) und \(B\) wird mit \(A \land B\), gesprochen als “\(A\) und \(B\)”, bezeichnet.
Die Definition der Konjunktion impliziert folgende Wahrheitstafel:
| \(A\) | \(B\) | \(A \land B\) |
|---|---|---|
| w | w | w |
| w | f | f |
| f | w | f |
| f | f | f |
Als Beispiel sei \(A\) die Aussage \(2\ge1\) und \(B\) die Aussage \(2>1\). Da sowohl \(A\) und \(B\) wahr sind, ist auch die Aussage \(2 \ge 1 \land 2 > 1\) wahr. Als weiteres Beispiel sei \(A\) die Aussage \(1\ge 1\) und \(B\) die Aussage \(1>1\). Hier ist nur \(A\) wahr und \(B\) falsch. Also ist die Aussage \(1 \ge 1 \land 1 > 1\) falsch.
Definition 1.4 (Disjunktion) \(A\) und \(B\) seien Aussagen. Dann ist die Disjunktion von \(A\) und \(B\) die Aussage, die dann und nur dann wahr ist, wenn mindestens eine der beiden Aussagen \(A\) und \(B\) wahr ist. Die Disjunktion von \(A\) und \(B\) wird mit \(A \lor B\), gesprochen als “\(A\) oder \(B\)”, bezeichnet.
Die Definition der Disjunktion impliziert folgende Wahrheitstafel:
| \(A\) | \(B\) | \(A \lor B\) |
|---|---|---|
| w | w | w |
| w | f | w |
| f | w | w |
| f | f | f |
\(A \lor B\) ist also insbesondere auch dann wahr, wenn \(A\) und \(B\) beide wahr sind. Damit ist das hier betrachtete “oder” genauer ein “und/oder”. Man nennt die Disjunktion daher auch ein “nicht-exklusives oder”. Als Beispiel sei \(A\) die Aussage \(2\ge1\) und \(B\) die Aussage \(2>1\). \(A\) ist wahr und \(B\) ist wahr. Also ist die Aussage \(2 \ge 1 \lor 2 > 1\) wahr. Sei nun wiederrum \(A\) die Aussage \(1\ge 1\) wahr und \(B\) die Aussage \(1>1\). Dann ist \(A\) wahr und \(B\) falsch. Also ist die Aussage \(1 \ge 1 \lor 1 > 1\) wahr.
Eine Möglichkeit, Aussagen in einen mechanischen logischen Zusammenhang zu stellen, ist die Implikation. Diese ist wie folgt definiert.
Definition 1.5 (Implikation) \(A\) und \(B\) seien Aussagen. Dann ist die Implikation, bezeichnet mit \(A \Rightarrow B\), die Aussage, die dann und nur dann falsch ist, wenn \(A\) wahr und \(B\) falsch ist. \(A\) heißt dabei die Voraussetzung (Prämisse) und \(B\) der Schluss (Konklusion) der Implikation. \(A \Rightarrow B\) spricht man als “aus \(A\) folgt \(B\)”, “\(A\) impliziert \(B\)”, oder “wenn \(A\), dann \(B\)”.
Die Definition der Implikation kann durch folgende Wahrheitstafel dargestellt werden:
| \(A\) | \(B\) | \(A \Rightarrow B\) |
|---|---|---|
| w | w | w |
| w | f | f |
| f | w | w |
| f | f | w |
Ein intuitives Verständnis der Definition der Implikation im Sinne obiger Wahrheitstafel ergibt sich am ehesten, indem man sie als Versuch liest, die intuitive Vorstellung einer Folgerung im Kontext der Aussagenlogik abzubilden und zu formalisieren. Um dies nachzuvollziehen, liest man die Wahrheitszustände in Tabelle 1.4 am besten in der Reihenfolge Wahrheitszustand von \(A\), Wahrheitszustand von \(A \Rightarrow B\) und betrachtet schließlich den Wahrheitszustand von \(B\). Liest man die Wahrheitstafel auf diese Weise, so sieht man, dass wenn \(A\) wahr ist und \(A \Rightarrow B\) wahr ist, \(B\) wahr ist. Konstruiert man basierend auf einer wahren Aussage also (zum Beispiel durch das Umformen von Gleichungen) eine wahre Implikation, so folgt, dass auch \(B\) wahr ist. Ist dies nicht möglich, wenn also gilt, dass, wenn \(A\) wahr ist, \(A \Rightarrow B\) immer falsch ist, dann ist auch \(B\) falsch. So mag man Aussagen widerlegen. Schließlich sieht man, dass wenn \(A\) falsch ist und \(A \Rightarrow B\) wahr ist, \(B\) wahr oder falsch sein kann. Nur aus einer wahren Voraussetzung folgt also bei wahrer Implikation immer eine wahre Konklusion. Insbesondere genügt die Definition der Implikation damit der Forderung “Aus Falschem folgt beliebiges (ex falso sequitur quodlibet)”. Man kann aus falschen Aussagen also mithilfe der Implikation nichts Sinnvolles folgern.
Im Kontext der Implikation ergeben sich die Begriffe der hinreichenden und der notwendigen Bedingungsaussagen: Wenn \(A \Rightarrow B\) wahr ist, sagt man, dass “\(A\) hinreichend für \(B\) ist” und dass “\(B\) notwendig für \(A\) ist”. Diese Sprechweise erklärt sich im Kontext der Implikation folgendermaßen: Wenn \(A \Rightarrow B\) wahr ist, gilt dass, wenn \(A\) wahr ist, auch \(B\) wahr ist. Die Wahrheit von \(A\) reicht also für die Wahrheit von \(B\) aus. \(A\) ist also hinreichend (ausreichend) für \(B\). Weiterhin gilt, dass wenn \(A \Rightarrow B\) wahr ist, dass wenn \(B\) falsch ist, dann auch \(A\) falsch ist. Die Wahrheit von \(B\) ist also für die Wahrheit von \(A\) notwendig.
Schließlich wollen wir zu Illustration von Tabelle 1.4 noch ein lebensnahes Beispiel geben. Dazu sei \(A\) die Aussage “Die Brücke ist beschädigt”, \(B\) die Aussage “Die Brücke ist gesperrt” und \(A \Rightarrow B\) die Implikation “Wenn die Brücke beschädigt ist, dann ist die Brücke gesperrt”. Wir diskutieren die vier Fälle von Tabelle 1.4.
- \(A\) wahr, \(B\) wahr, \(A \Rightarrow B\) wahr. Wenn \(A\) wahr ist, dann ist die Brücke beschädigt und wenn dazu auch \(B\) wahr ist, dann ist die Brücke außerdem gesperrt. In diesem Fall ist die Implikation “Wenn die Brücke beschädigt ist, dann ist die Brücke gesperrt” also offensichtlich wahr.
- \(A\) wahr, \(B\) falsch, \(A \Rightarrow B\) falsch. Wenn \(A\) wahr ist, dann ist die Brücke beschädigt und wenn \(B\) falsch ist, dann ist die Brücke also nicht gesperrt. In diesem Fall ist die Implikation “Wenn die Brücke beschädigt ist, dann ist die Brücke gesperrt” also offensichtlich falsch.
- \(A\) falsch, \(B\) wahr, \(A \Rightarrow B\) wahr. Wenn \(A\) falsch ist, dann ist die Brücke nicht beschädigt und wenn \(B\) wahr ist, dann ist die Brücke gesperrt. Da die Brücke allerdings nicht beschädigt ist, kann man keine Schlussfolgerung hinsichtlich der Implikation “Wenn die Brücke beschädigt ist, dann ist die Brücke gesperrt” ziehen, man kann also insbesondere nicht zeigen, dass diese falsch wäre. Also unterstellt man, dass die Aussage “Wenn die Brücke beschädigt ist, dann ist die Brücke gesperrt” wahr ist.
- \(A\) falsch, \(B\) falsch, \(A \Rightarrow B\) wahr. Wenn \(A\) falsch ist, dann ist die Brücke nicht beschädigt und wenn \(B\) wahr ist, dann ist die Brücke nicht gesperrt. Da die Brücke allerdings nicht beschädigt ist, kann man keine Schlussfolgerung hinsichtlich der Implikation “Wenn die Brücke beschädigt ist, dann ist die Brücke gesperrt” ziehen, man kann also insbesondere nicht zeigen, dass diese falsch wäre. Also unterstellt man wiederrum, dass die Aussage “Wenn die Brücke beschädigt ist, dann ist die Brücke gesperrt” wahr ist.
Eine sehr häufig autretender Zusammenhang zwischen zwei Aussagen ist ihre Äquivalenz.
Definition 1.6 (Äquivalenz) \(A\) und \(B\) seien Aussagen. Die Äquivalenz von \(A\) und \(B\) ist die Aussage, die dann und nur dann wahr ist, wenn \(A\) und \(B\) beide wahr sind oder wenn \(A\) und \(B\) beide falsch sind. Die Äquivalenz von \(A\) und \(B\) wird mit \(A \Leftrightarrow B\) bezeichnet und gesprochen als “\(A\) genau dann, wenn \(B\)” oder “\(A\) ist äquivalent zu \(B\)”.
Die Definition der Äquivalenz impliziert folgende Wahrheitstafel:
| \(A\) | \(B\) | \(A \Leftrightarrow B\) |
|---|---|---|
| w | w | w |
| w | f | f |
| f | w | f |
| f | f | w |
Die Definition des Begriffes der logischen Äquivalenz erlaubt es unter anderem, die Äquivalenz zweier Aussagen mithilfe von Implikationen nachzuweisen.
Definition 1.7 (Logische Äquivalenz) Zwei Aussagen heißen logisch äquivalent, wenn ihre Wahrheitstafeln gleich sind.
Als Beispiele für logische Äquivalenzen, die häufig in Beweisargumentationen genutzt werden, zeigen wir die Aussagen folgenden Theorems.
Theorem 1.1 (Logische Äquivalenzen) \(A\) und \(B\) seien zwei Aussagen. Dann sind folgende Aussagen logisch äquivalent:
- \(A \Leftrightarrow B\) und \((A \Rightarrow B) \land (B \Rightarrow A)\)
- \(A \Rightarrow B\) und \((\neg B) \Rightarrow (\neg A)\)
Beweis. Nach Definition des Begriffs der logischen Äquivalenz müssen wir zeigen, dass die Wahrheitstafeln der betrachteten Aussagen gleich sind. Wir zeigen erst (1), dann (2).
(1) Wir erinnern an die Wahrheitstafel von \(A \Leftrightarrow B\):
| \(A\) | \(B\) | \(A \Leftrightarrow B\) |
|---|---|---|
| w | w | w |
| w | f | f |
| f | w | f |
| f | f | w |
Wir betrachten weiterhin die Wahrheitstafel von \((A \Rightarrow B) \land (B \Rightarrow A)\):
| \(A\) | \(B\) | \(A \Rightarrow B\) | \(B \Rightarrow A\) | \((A \Rightarrow B) \land (B \Rightarrow A)\) |
|---|---|---|---|---|
| w | w | w | w | w |
| w | f | f | w | f |
| f | w | w | f | f |
| f | f | w | w | w |
Der Vergleich der Wahrheitstafel von \(A \Leftrightarrow\) mit den ersten beiden und der letzten Spalte der Wahrheitstafel von \((A \Rightarrow B) \land (B \Rightarrow A)\) zeigt ihre Gleichheit.
(2) Wir erinnern an die Wahrheitstafel von \(A \Rightarrow B\):
| \(A\) | \(B\) | \(A \Rightarrow B\) |
|---|---|---|
| w | w | w |
| w | f | f |
| f | w | w |
| f | f | w |
Wir betrachten weiterhin die Wahrheitstafel von \((\neg B) \Rightarrow (\neg A)\):
| \(A\) | \(B\) | \(\neg B\) | \(\neg A\) | \((\neg B) \Rightarrow (\neg A)\) |
|---|---|---|---|---|
| w | w | f | f | w |
| w | f | w | f | f |
| f | w | f | w | w |
| f | f | w | w | w |
Der Vergleich der Wahrheitstafel von \(A \Rightarrow B\) mit den ersten beiden und der letzten Spalte der Wahrheitstafel von \((\neg B) \Rightarrow (\neg A)\) zeigt ihre Gleichheit.
Die erste Aussage von Theorem 1.1 besagt, dass die Aussage “\(A\) und \(B\) sind äquivalent” logisch äquivalent zur Aussage “Aus \(A\) folgt \(B\)” und zur Aussage “Aus \(B\) folgt \(A\)” ist. Dies ist die Grundlage für viele sogenannte direkte Beweise mithilfe von Äquivalenzumformungen. Die zweite Aussage von Theorem 1.1 besagt, dass die Aussage “Aus \(A\) folgt \(B\)” logisch äquivalent zur Aussage “Aus nicht \(B\) folgt nicht \(A\)” ist. Dies ist die Grundlage für die Technik des indirekten Beweises. Wir betrachten diese Beweistechniken im folgenden Abschnitt genauer. Zunächst fassen wir die Bedeutungen der in diesem Abschnitt eingeführte Symbole noch einmal in untenstehender Tabelle zusammen.
| Symbol | Bedeutung | Bemerkung |
|---|---|---|
| \(\neg A\) | Nicht \(A\) | Wahr, wenn \(A\) falsch ist und umgekehrt |
| \(A \land B\) | \(A\) und \(B\) | Nur wahr, wenn \(A\) und \(B\) beide wahr sind |
| \(A \lor B\) | \(A\) und/oder \(B\) | Wahr, wenn mindestens eine der Aussagen wahr ist |
| \(A \Rightarrow B\) | Aus \(A\) folgt \(B\) | \(B\) ist notwendig für \(A\), \(A\) ist hinreichend für \(B\) |
| \(A \Leftrightarrow B\) | \(A\) ist äquivalent zu \(B\) | Es gelten \(A \Rightarrow B\) und \(B \Rightarrow A\) |
1.4 Äquivalenzumformungen
Mathematische Probleme führen oft auf den Fall, dass Information über eine unbekannte Variable implizit mithilfe einer Gleichung oder einer Ungleichung dargestellt wird. Um die Information über die entsprechende Variable explizit darzustellen, also im Falle von Gleichungen ihren Wert zu bestimmen oder im Falle von Ungleichungen den Zahlenbereich zu ermitteln, in dem der Wert der Variable liegt, nutzt man Äquivalenzumformungen. Wir betrachten hier lediglich die aus der Schulmathematik bekannten Äquivalenzumformungen von (Un)Gleichungen berzüglich reeller Variablen. Äquivalenzumformungen von (Un)Gleichungen haben dabei die Eigenschaft, dass sich der Wahrheitsgehalt der durch eine (Un)Gleichung formulierten Aussage bei Anwendung der entsprechenden Umformung nicht ändert. Dabei werden stets beide Seiten der (Un)Gleichung umgeformt. Damit es sich bei der Anwendung einer mathematischen Operation auf eine (Un)gleichungsaussage \(A\) in eine (Un)gleichungsaussage \(B\) um eine Äquivalenzumformung der Form \(A \Leftrightarrow B\) handelt, müssen bekanntlich sowohl \(A \Rightarrow B\) als auch \(B \Rightarrow A\) gelten. Dies impliziert, dass es sich bei Äquivalenzumformungen um umkehrbare (invertierbare) Operationen handelt.
Bei Gleichungen sind zulässige Äquivalenzumformungen insbesondere
- die Addition einer Zahl auf beiden Seiten der Gleichung,
- die Subtraktion einer Zahl auf beiden Seiten der Gleichung,
- die Multiplikation mit einer Zahl auf beiden Seiten der Gleichung,
- die Division durch eine von null verschiedenen Zahl auf beiden Seiten der Gleichung,
- die Anwendung einer invertierbaren Funktion auf beiden Seiten der Gleichung.
Beispiel
Wir betrachten unter Vorgriff auf Kapitel 4.3 die Aussage \[\begin{equation} 2 \exp(x) - 2 = 0. \end{equation}\] Dann gelten \[\begin{align} \begin{split} 2 \exp(x) - 2 & = 0 \\ \Leftrightarrow 2 \exp(x) - 2 + 2 & = + 2 \\ \Leftrightarrow 2 \exp(x) & = 2 \\ \Leftrightarrow \frac{1}{2} \cdot 2 \exp(x) & = \frac{1}{2} \cdot 2 \\ \Leftrightarrow \exp(x) & = 1 \\ \Leftrightarrow \ln(\exp(x)) & = \ln(1) \\ \Leftrightarrow x & = 0. \\ \end{split} \end{align}\] Zusammengefasst gilt also \[\begin{equation} 2 \exp(x) - 2 \Leftrightarrow x = 0. \end{equation}\]
Bei Ungleichungen sind zulässige Äquivalenzumformungen insbesondere
- die Addition einer Zahl auf beiden Seiten der Ungleichung,
- die Subtraktion einer Zahl auf beiden Seiten der Ungleichung,
- die Multiplikation mit einer Zahl auf beiden Seiten der Gleichung, wobei die Multiplikation mit einer negativen Zahl das Ungleichungszeichen umkehrt,
- die Division durch eine von null verschiedenen positiven Zahl auf beiden Seiten der Gleichung, wobei die Division mit einer negativen Zahl das Ungleichungszeichen umkehrt,
- die Anwendung einer invertierbaren monotonen Funktion auf beiden Seiten der Ungleichung.
Beispiel
Wir betrachten die Aussage \[\begin{equation} -5 x - 2 \ge 8. \end{equation}\] Dann gelten \[\begin{align} \begin{split} -5x - 2 & \ge 8 \\ \Leftrightarrow -5x - 2 + 2 & \ge 8 + 2 \\ \Leftrightarrow -5x & \ge 10 \\ \Leftrightarrow -\frac{1}{5} \cdot 5x & \ge \frac{1}{5} \cdot 10 \\ \Leftrightarrow -x & \ge 2 \\ \Leftrightarrow x & \le -2. \\ \end{split} \end{align}\] Zusammengefasst gilt also \[\begin{equation} -5x - 2 \ge 8 \Leftrightarrow x \le -2. \end{equation}\]
1.5 Beweistechniken
In diesem Abschnitt wollen wir mit den Begriffen der direkten und indirekten Beweise sowie des Beweises durch Widerspruch drei fundamentale Beweistechniken skizzieren. Dabei wird vor allem die erste im Folgenden immer wieder zur Begründung von Theoremen herangezogen werden.
Es gilt dabei
- Direkte Beweise nutzen Äquivalenzumformungen, um \(A \Rightarrow B\) zu zeigen.
- Indirekte Beweise nutzen die logische Äquivalenz von \(A \Rightarrow B\) und \((\neg B) \Rightarrow (\neg A)\).
- Beweise durch Widerspruch zeigen, dass \((\neg B) \land A\) falsch ist.
Damit ausgestattet wollen wir nun folgendes Theorem mithilfe eines direkten Beweises, eines indirekten Beweises und eines Beweises durch Widerspruch beweisen (vgl. Arens et al. (2018)).
Theorem 1.2 (Quadrate positiver Zahlen) Es seien \(a\) und \(b\) zwei positive Zahlen. Dann gilt \(a^2 < b^2 \Rightarrow a < b\).
Beweis. Wir geben zunächst einen direkten Beweis. Dazu sei \(a^2 < b^2\) die Aussage \(A\) und \(a < b\) die Aussage \(B\). Dann gilt \[\begin{equation} a^2 < b^2 \Leftrightarrow 0 < b^2 - a^2 \Leftrightarrow 0 < (b+a)(b-a) \Leftrightarrow 0 < (b-a) \Leftrightarrow a < b. \end{equation}\] Wir geben nun einen indirekten Beweis. Es sei \(a^2 \ge b^2\) die Aussage \(\neg A\). Weiterhin sei \(a \ge b\) die Aussage \(\neg B\). Dann gilt \[\begin{equation} a \ge b \Leftrightarrow a^2 \ge ab \land ab \ge b^2 \Leftrightarrow a^2 \ge b^2. \end{equation}\] Schließlich geben wir einen Beweis durch Widerspruch. Wir zeigen, dazu, dass die Annahme \((\neg B) \land A\) auf eine falsche Aussage führt. Es gilt \[\begin{equation} a \ge b \land a^2 < b^2 \Leftrightarrow a^2 \ge ab \land a^2 < b^2 \Leftrightarrow ab \le a^2 < b^2. \end{equation}\] Weiterhin gilt \[\begin{equation} a \ge b \land a^2 < b^2 \Leftrightarrow ab \ge b^2 \land a^2 < b^2 \Leftrightarrow a^2 < b^2 \le ab. \end{equation}\] Insgesamt gilt dann also die falsche Aussage \[\begin{equation} ab \le a^2 < b^2 \le ab \Leftrightarrow ab < ab. \end{equation}\]