Content

1. Aussagenlogik und mathematische Beweisführung in:

Michael Merz, Mario V. Wüthrich

Mathematik für Wirtschaftswissenschaftler, page 15 - 42

Die Einführung mit vielen ökonomischen Beispielen

1. Edition 2012, ISBN print: 978-3-8006-4482-7, ISBN online: 978-3-8006-4483-4, https://doi.org/10.15358/9783800644834_15

Bibliographic information
Teil I Mathematische Grundlagen Kapitel1 Aussagenlogik und mathematische Beweisführung Kapitel 1 Aussagenlogik und mathematische Beweisführung 1.1 Was ist Mathematik? P. Erdös Auf die Frage „Was ist ein Mathematiker?“ gab der bedeutende ungarische Mathematiker Paul Erdös (1913–1996) die kurze Antwort:1 „A mathematician is a machine for turning coffee into theorems.“ Die Frage „Was ist Mathematik?“ lässt sich jedoch nicht so einfach und prägnant beantworten. Selbst unter Mathematikern existieren die verschiedensten Auffassungen darüber, wie diese Frage zu beantworten sei. Die Mathematik ist jedenfalls eine der ältesten Wissenschaften der Welt. Sie entstand aus der Untersuchung von geometrischen Formen und Figuren sowie dem Messen und dem Rechnen mit Zahlen. Die Geschichte der Mathematik reicht bis ca. 3000 Jahre v. Chr. zu den alten Ägyptern und Babyloniern zurück, wobei der Begriff „Mathematik“ seinen Ursprung im griechischen Wort „mathema“, der ursprünglichen Bezeichnung für Wissenschaft überhaupt, hat. Aufgrund ihrer umfassenden Bedeutung und Anwendbarkeit gibt es bis heute keine allgemein anerkannte Definition dafür, was unter dem Begriff „Mathematik“ genau zu verstehen ist. Selbst die Frage, ob die Mathematik zu der Wissenschaftskategorie der Naturwissenschaften oder doch eher zu den Geisteswissenschaften zu zählen ist, wird seit langer Zeit kontrovers diskutiert. Für einige überwiegt bei ihrer Einordnung vor allem der Aspekt, dass viele mathematische Fragestellungen und Begriffe durch natur- und ingenieurwissenschaftliche Problemstellungen motiviert sind, während sich andere bei ihrer Einordnung mehr von der Tatsache leiten lassen, dass die Mathematik starke methodische und inhaltliche Gemeinsamkeiten zur Philosophie aufweist. Wieder andere kategorisieren die Mathematik – neben weiteren Disziplinen wie z. B. der Informatik und der reinen Linguistik – als Struktur- bzw. Formalwissenschaft. Sie betonen damit den Aspekt, dass sich die Mathematik mit der Analyse von formalen Systemen beschäftigt und nicht mit der Untersuchung vorgefundener Gegebenheiten, wie es in der real- oder er- 1 Einige Quellen ordnen dieses Zitat auch dem ungarischen Mathematiker Alfréd Rényi (1921–1970) zu, der ein kaffeeabhängiger Kollege von Erdös war. fahrungswissenschaftlichen Forschung der Fall ist. Der USamerikanische Mathematiker Norbert Wiener (1894–1964) war dagegen einer ganz anderen Auffassung und sagte: „Mathematics is an experimental science. It matters little that the mathematician experiments with pencil and paper while the chemist uses testtube and retort, or the biologist stains and the microscope. The only great point of divergence between mathematics and the other sciences lies in the circumstance that experience only whispers ‘yes’ or ‘no’ in reply to our questions, while logic shouts.“ N. Wiener Unabhängig von dieser Kontroverse wird jedoch die Mathematik heute üblicherweise als eine Wissenschaft beschrieben, die abstrakte Strukturen und Objekte bezüglich ihrer Eigenschaften und Muster untersucht. Dabei wird oftmals auch zwischen reiner und angewandter Mathematik unterschieden, wobei die Grenze zwischen diesen beiden Teilgebieten durchaus fließend ist. Während die reine Mathematik durch abstrakte Konzepte ohne jeglichen Bezug zu außermathematischen Anwendungen geprägt ist, hat sich die angewandte Mathematik den Einsatz und die Entwicklung mathematischer Methoden zur Lösung von Problemen aus der Physik, Chemie, Biologie, Medizin, Wirtschaft, Informatik, Technik usw. zum Ziel gesetzt. Zur angewandten Mathematik zählen z. B. die Bereiche numerische Mathematik, Ingenieurmathematik, mathematische Physik, Technomathematik, mathematische Psychologie, Graphentheorie, Kryptologie usw. Andere Bereiche der angewandten Mathematik, die einen sehr starken Anwendungsbezug speziell zu den Wirtschaftswissenschaften besitzen, sind z. B. Wahrscheinlichkeitstheorie, Statistik, Finanzmathematik, Versicherungsmathematik, Spiel- und Entscheidungstheorie, Ökonometrie, Optimierungstheorie oder Operations Research. Das Ziel dieses Lehrbuches ist es, den Lesern die Grundlagen aus den mathematischen Teilgebieten Algebra (insbesondere lineare Algebra) und Analysis zu vermitteln, die für das Erlernen der Konzepte, Methoden und Modelle in diesen für die modernen Wirtschaftswissenschaften wichtigen Bereichen der angewandten Mathematik benötigt werden. 4 Kapitel 11.2 Axiom, Definition und mathematischer Satz 1.2 Axiom, Definition und mathematischer Satz Wie in Abschnitt 1.1 bereits erläutert wurde, ist die Mathematik durch die Untersuchung von abstrakten Strukturen und Objekten bezüglich ihrer Eigenschaften und Muster geprägt. Um dabei zum einen Missverständnissen und Mehrdeutigkeiten in der Formulierung von Definitionen und mathematischen Resultaten vorzubeugen, und zum anderen die universelle Anwendbarkeit der mathematischen Konzepte und Methoden zu gewährleisten, bedient man sich in der Mathematik einer eigenen künstlichen Sprache. Büste von Aristoteles Diese Kunstsprache wird als formale Logik bezeichnet. Das Wort „Logik“ stammt aus dem Altgriechischen und bedeutet soviel wie „denkende Kunst“ oder „Vorgehensweise“. Die formale Logik hat ihre Ursprünge bereits in der Antike und wurde durch Aristoteles (384–322 v. Chr.) zu einem bis in die heutige Zeit gültigen Stand entwickelt. In der formalen Logik erfolgt die Analyse und Konstruktion von Aussagen und logischen Schlussfolgerungen nicht mit Hilfe einer natürlichen Sprache, sondern auf Basis einer formalen, künstlichen Sprache mit speziellen Symbolen und streng definierten Schlussregeln. Dabei stehen ausschließlich formale Aspekte im Vordergrund und die Analyse und Konstruktion von Aussagen erfolgt unabhängig von ihrem konkreten Inhalt. Kennzeichnend für die formale Logik ist auch, dass neue Erkenntnisse ausschließlich innerhalb logisch abgeschlossener und widerspruchsfreier Systeme gewonnen werden und dass ihr Wahrheitsgehalt nur von logisch korrekten Schlüssen abhängt. H. Weyl Ein Beispiel für solch ein formales System ist die Aussagenlogik, die Gegenstand von Abschnitt 1.3 ist. Die Bedeutung der Logik für die gesamte Mathematik kommt sehr gut durch das Zitat „Logic is the hygiene the mathematician practices to keep his ideas healthy and strong.“ des deutschen Mathematikers Hermann Weyl (1885–1955) zum Ausdruck. Axiomatische Theorien Ein weiteres Charakteristikum für die mathematische Vorgehensweise ist, dass die Mathematik in Form von Theorien präsentiert wird, die aus bestimmten Grundbegriffen gewisse Grundsachverhalte formulieren. Diese Grundsachverhalte, die nicht bewiesen, sondern als wahr angesehen werden, hei- ßen Axiome. Aus diesen Grundpostulaten (Axiomen) werden dann weitere wahre Aussagen, die sogenannten (mathematischen) Sätze, abgeleitet. Die Herleitung erfolgt dabei nach genau festgelegten Schlussregeln und wird als Beweis des Satzes bezeichnet (siehe hierzu die Abschnitte 1.5 und 1.6). Axiome bilden somit die Grundlage für die Entwicklung einer mathematischen Theorie, die schließlich durch die Definition weiterer mathematischer Objekte und die logisch korrekt hergeleiteten Eigenschaften dieser Objekte – in Form von mathematischen Sätzen – entsteht. Aus diesem Grund werden mathematische Theorien auch als axiomatische Theorien bezeichnet. Die Wahl der Axiome, die einer mathematischen Theorie zugrunde gelegt werden sollen, wird jedoch häufig kontrovers diskutiert. E. Zermelo Ein Beispiel hierfür ist das 1904 von dem deutschen Mathematiker Ernst Zermelo (1871–1953) formulierte Auswahlaxiom. Vereinfacht besagt es, dass es zu jeder Menge von nichtleeren Mengen eine Funktion gibt, die jeder dieser Mengen ein Element derselben zuordnet, d. h. „auswählt“. Während das Auswahlaxiom von der überwiegenden Mehrheit der Mathematiker akzeptiert wird, da es in vielen Zweigen der Mathematik zu besonders bedeutenden und ästhetischen Ergebnissen führt, verzichten Anhänger der sogenannten konstruktivistischen Mathematik bewusst auf das Auswahlaxiom. Dieser Gruppe von Mathematikern steht eine ganze Reihe bedeutender mathematischer Sätze, zu deren Beweis das Auswahlaxiom benötigt wird, nicht zur Verfügung. Auf der anderen Seite werden jedoch auf diese Weise einige eigentümlich erscheinende Konsequenzen vermieden, die sich ebenfalls mit Hilfe des Auswahlaxioms beweisen lassen. Das bekannteste Beispiel hierfür ist sicherlich das nach den 5 Kapitel 1 Aussagenlogik und mathematische Beweisführung S. Banach beiden polnischen Mathematikern Stefan Banach (1892–1945) und Alfred Tarski (1901–1983) benannte Banach-Tarski-Paradoxon. Vereinfacht besagt es, dass eine Kugel in n ≥ 3 Dimensionen stets derart zerlegt werden kann, dass sich ihre Teile wieder zu zwei vollständigen Kugeln zusammenfügen lassen, von denen jede denselben Radius besitzt wie die ursprüngliche Kugel. A. Tarski Das heißt, das Volumen einer Kugel kann alleine durch Zerlegen der Kugel und anschließendes Wiederzusammenfügen der entstehenden Teile verdoppelt werden, ohne dass dabei erklärt werden kann, wie durch einen solchen Vorgang Volumen aus dem Nichts entstehen soll (vgl. Abbildung 1.1). Abb. 1.1: Veranschaulichung des Banach-Tarski-Paradoxons Unstrittig ist jedoch unter allen Mathematikern, dass die einer mathematischen Theorie zugrunde gelegten Axiome sowohl konsistent, d. h. widerspruchsfrei, als auch unabhängig, d. h. nicht auseinander ableitbar, sein sollen. Axiomensystem von Peano G. Peano Das Vorgehen bei der Entwicklung einer mathematischen auf Axiomen basierender Theorie lässt sich exemplarisch sehr gut anhand der Defnition der Menge N der natürlichen Zahlen nachvollziehen. Im Folgenden wird deshalb das sogenannte Axiomensystem von Peano betrachet, welches 1889 vom italienischen Mathematiker Giuseppe Peano (1858– 1932) formuliert wurde und zur Definition der Menge N der natürlichen Zahlen dient. Es besteht aus fünf Axiomen und charakterisiert die Menge N der natürlichen Zahlen und ihre Eigenschaften anhand des Begriffs des „Nachfolgers“: Definition 1.1 (Axiomensystem von Peano) (P1) 1 ist eine natürliche Zahl. (P2) Jede natürliche Zahl n hat eine natürliche Zahl m als Nachfolger. (P3) 1 ist kein Nachfolger einer natürlichen Zahl. (P4) Verschiedene natürliche Zahlen haben verschiedene Nachfolger. (P5) Enthält eine Menge A das Element 1 und mit jeder natürlichen Zahl n auch deren Nachfolger, dann ist die Menge der natürlichen Zahlen eine Teilmenge von A. Das Axiom (P1) stellt für sich allein genommen zunächst nur sicher, dass es eine mit dem Symbol 1 („Eins“) bezeichnete natürliche Zahl gibt. Bezeichnet ferner N(n) den Nachfolger einer natürlichen Zahl n, dann wird durch die Axiome (P2)–(P5) gewährleistet, dass man sukzessive und widerspruchsfrei durch die Definitionen 2 := N(1), 3 := N(2), 4 := N(3), 5 := N(4), 6 := N(5), . . . unendlich viele weitere natürliche Zahlen erhält, die mit den Symbolen 2, 3, . . . bezeichnet werden. Die auf diese Weise resultierende Menge N := {1, 2, 3, 4, 5, . . .} (1.1) wird als Menge der natürlichen Zahlen bezeichnet. Das Axiom (P5) heißt Induktionsaxiom, da auf ihm das Beweisprinzip der vollständigen Induktion beruht (siehe hierzu Abschnitt 1.7). Für die Menge der natürlichen Zahlen definiert man nun die Addition durch n+ 1 := N(n) und n+N(m) := N(n+m) 6 Kapitel 11.3 Aussagenlogik für alle n und m aus N. Dies führt dann zu der Additionstabelle 1 + 1 = N(1) = 2 1 + 2 = 1 +N(1) = N(1 + 1) = N(2) = 3 1 + 3 = 1 +N(2) = N(1 + 2) = N(3) = 4 2 + 1 = N(2) = 3 2 + 2 = 2 +N(1) = N(2 + 1) = N(3) = 4 2 + 3 = 2 +N(2) = N(2 + 2) = N(4) = 5 3 + 1 = N(3) = 4 3 + 2 = 3 +N(1) = N(3 + 1) = N(4) = 5 ... Aufbauend auf der Addition wird für die Menge der natürlichen Zahlen die Multiplikation definiert durch n · 1 := n und n ·N(m) := n+ n ·m für alle n und m aus N. Aus der Definition n · 1 := n folgt, dass 1 ein neutrales Element der Multiplikation ist. Durch die Konvention, dass die Multiplikation stets vor der Addition ausgeführt wird, ergibt sich folgende Multiplikationstabelle 1 · 1 = 1 1 · 2 = 1 ·N(1) = 1 + 1 · 1 = 1 + 1 = 2 1 · 3 = 1 ·N(2) = 1 + 1 · 2 = 1 + 2 = 3 2 · 1 = 2 2 · 2 = 2 ·N(1) = 2 + 2 · 1 = 2 + 2 = 4 2 · 3 = 2 ·N(2) = 2 + 2 · 2 = 2 + 4 = 6 3 · 1 = 3 3 · 2 = 3 ·N(1) = 3 + 3 · 1 = 3 + 3 = 6 ... Anschließend lassen sich für die Addition und die Multiplikation mit Hilfe des Axioms (P5) und der Konvention, dass die Multiplikation stets vor der Addition ausgeführt wird, die folgenden grundlegenden Rechengesetze beweisen. Es gelten für beliebige natürliche Zahlen l, m, n: a) Assoziativgesetze: l+ (m+ n) = (l+m)+ n und l · (m · n) = (l ·m) · n b) Kommutativgesetze: m+ n = n+m und m · n = n ·m c) Distributivgesetz: l · (m+ n) = l ·m+ l · n Aus den beiden Assoziativgesetzen lässt sich schließen, dass beliebige (mehrfache) Summen und Produkte stets ohne Klammern geschrieben werden können. Die Kommutativgesetze besagen darüber hinaus, dass es bei beliebigen (mehrfachen) Summen und Produkten grundsätzlich nicht auf die Reihenfolge der Summanden bzw. Faktoren ankommt. An diesem Beispiel einer Einführung der Menge N der natürlichen Zahlen ist ersichtlich, wie in der Mathematik ausgehend von Axiomen und logischen Schlüssen neue mathematische Aussagen hergeleitet und durch die Definition zusätzlicher mathematischer Objekte und mit erneuten logischen Schlüssen weitere mathematische Aussagen gewonnen werden. Diese grundsätzliche Vorgehensweise beim Aufbau mathematischer Theorien ist auch in diesem Lehrbuch immer wieder sichtbar. Denn ausgehend von Axiomen und/oder Definitionen für grundlegende mathematische Objekte werden immer wieder Aussagen über die wichtigsten Eigenschaften eines mathematischen Objekts in Form eines mathematischen Satzes formuliert. Anschließend erfolgt der Beweis des Satzes oder es wird ein Hinweis gegeben, wie der Beweis geführt werden kann. In manchen Fällen wird auch eine Literaturquelle angegeben, in welcher der Beweis zu finden ist. Ferner werden bei der Definition neuer mathematischer Objekte häufig die Symbole „:=“ oder „:⇔“ verwendet. Diese Symbole drücken aus, dass das mathematische Objekt auf der linken Seite durch den Ausdruck auf der rechten Seite definiert wird. 1.3 Aussagenlogik Die Aussagenlogik ist der Bereich der formalen Logik, der sich mit Aussagen und deren Verknüpfung durch logische Operatoren, die sogenannten Junktoren, befasst. Ausgehend von sogenannten Elementaraussagen, denen einer der beiden Wahrheitswerte „wahr“ oder „falsch“ zugeordnet ist, werden mit Hilfe von Junktoren zusammengesetzte Aussagen gebildet und deren Wahrheitswert – ohne zusätzliche Informationen – aus den Wahrheitswerten der Elementaraussagen abgeleitet. Die Aussagenlogik bildet damit auch die Grundlage für die anderen Teilgebiete der formalen Logik und damit insbesondere auch die Basis für die mathematische Beweisführung, die Gegenstand von Abschnitt 1.6 ist. 7 Kapitel 1 Aussagenlogik und mathematische Beweisführung Aussagen Der Begriff der Aussage ist für die Aussagenlogik von zentraler Bedeutung: Definition 1.2 (Aussage) Eine Aussage A ist ein Satz, der entweder wahr (kurz: w) oder falsch (kurz: f ) ist. Anstelle vonw bzw. f wird für den Wahrheitswert einer Aussage oftmals auch 1 bzw. 0 geschrieben. Die Definition 1.2 beinhaltet die beiden folgenden wichtigen Aspekte: 1) Eine Aussage kann nur den Wahrheitswert w oder f besitzen. Für eine Aussage ist kein weiterer Wahrheitswert zugelassen (Prinzip der Zweiwertigkeit). 2) Eine Aussage kann nicht sowohl den Wahrheitswert w als auch den Wahrheitswert f haben (Prinzip vom ausgeschlossenen Widerspruch). Eine Aussage ist somit formal ein grammatikalisch korrekter Satz, der entweder wahr oder falsch ist. Zum Beispiel ist der Satz „Die Zahl 13 ist eine Primzahl“ eine wahre Aussage, während der Satz „Alle Zahlen sind ohne Rest durch 2 teilbar“ offensichtlich eine falsche Aussage darstellt. Der Wahrheitswert der Aussage „Morgen ist Freitag“ hängt dagegen davon ab, ob diese Feststellung an einem Donnerstag getroffen wurde oder nicht. Karikatur von A.-M. Legendre Bei einer Aussage ist es aber auch durchaus möglich, dass man zum gegenwärtigen Zeitpunkt noch nicht sagen kann, welchen Wahrheitswert sie besitzt. Dies ist z. B. bei ungelösten mathematischen Problemen der Fall. Die nach dem französischen Mathematiker Adrien-Marie Legendre (1752–1833) benannte Legendresche Vermutung „Zwischen n2 und (n+ 1)2 liegt für eine natürliche Zahl n stets mindestens eine Primzahl“ ist ein bekanntes Beispiel für solch eine Aussage. Zum Beispiel liegen zwischen 1 und 4 die Primzahlen 2 und 3, zwischen 4 und 9 die Primzahlen 5 und 7, usw. Einerseits hat noch kein Mensch eine natürliche Zahl n entdeckt, für die zwischen n2 und (n+ 1)2 keine Primzahl liegt; andererseits hat auch noch nie jemand beweisen können, dass die Aussage für alle natürlichen Zahlen n wahr ist. Noch berühmter als die Legendresche Vermutung ist die nach dem deutschen Mathematiker und Diplomaten Christian Goldbach (1690–1764) benannte Goldbachsche Vermutung „Jede gerade Zahl n größer als 2 kann als Summe zweier Primzahlen p und q geschrieben werden.“ C. Goldbach Goldbach formulierte diese Vermutung am 7. Juni 1742 in einem Brief an den schweizer Mathematiker Leonhard Euler (1707–1783). Mittlerweile gehört die Goldbachsche Vermutung zu den ältesten und bedeutendsten ungelösten mathematischen Problemen, und dies trotz der Tatsache, dass im Jahre 2000 ein britischer Verlag ein Preisgeld von einer Million Dollar auf den Beweis dieser Vermutung aussetzte. Im November 2011 wurde ihre Gültigkeit für alle Zahlen bis 26 · 1017 explizit nachgewiesen. Dies ist aber natürlich kein Beweis dafür, dass die Goldbachsche Vermutung für jede beliebig große gerade Zahl gültig ist. Brief von Goldbach an Euler Die beiden Feststellungen von Legendre und Goldbach haben somit gemeinsam, dass sie entweder wahr oder falsch sind, auch wenn die größten Mathematiker der letzten 250 Jahre nicht in der Lage waren, diese Vermutungen zu verifizieren oder zu widerlegen. Einer Person, der es gelingen sollte, eine dieser beiden Vermutungen zu beweisen oder zu widerlegen, wäre mit einem Schlag berühmt und würde sicherlich zahlreiche Angebote für Vorträge und Professuren an renommierten Universitäten erhalten. Üblicherweise werden Aussagen mit lateinischen Großbuchstaben aus dem vorderen Teil des Alphabets, also A, B, C usw., bezeichnet. Für eine wahre Aussage A sagt man auch: „A gilt“, „A ist richtig“ oder „A ist erfüllt“ 8 Kapitel 11.3 Aussagenlogik Entsprechend sagt man für eine falsche Aussage A auch: „A gilt nicht“, „A ist nicht richtig“ oder „A ist nicht erfüllt“ Durch Hinzufügen des Wortes „nicht“ kann also eine Aussage stets negiert, d. h. verneint werden. Aufgrund der Gültigkeit des Prinzips der Zweiwertigkeit spricht man auch von zweiwertiger Logik. Im Gegensatz hierzu kann in der mehrwertigen Logik und in der Fuzzy-Logik eine Aussage mehr als zwei Wahrheitswerte annehmen. Ein Blick in verschiedene Mathematikbücher zeigt, dass das Prinzip der Zweiwertigkeit oft mit dem auch innerhalb mehrwertiger Logiken gültigen Prinzip des ausgeschlossenen Dritten verwechselt wird. Das Prinzip des ausgeschlossenen Dritten besagt, dass für eine beliebige Aussage mindestens die Aussage selbst oder ihr Gegenteil gelten muss. Eine dritte Möglichkeit, die weder die Aussage ist, noch ihr Gegenteil, sondern eine Aussage irgendwo dazwischen, kann es nicht geben. Beispiel 1.3 (Aussagen) a) A= „Alle Studierenden lieben das Fach Mathematik.“ b) B = „Die Zahl 9 ist ohne Rest durch 3 teilbar.“ c) C = „Der HSV wird nächster Deutscher Fußballmeister.“ d) D = „In Hamburg scheint jeden Tag die Sonne.“ e) E = „Der gegenwärtige König von Deutschland ist kahl.“ Die Aussagen A und D sind (leider) falsch, während die Aussage B wahr ist. Ob jedoch die Aussage C wahr ist, kann derzeit nicht entschieden werden. Denn dies wird sich erst am Ende der laufenden Fußballsaison zeigen. Bei E handelt es sich hingegen um keine Aussage, da die Feststellung E gegen das Prinzip vom ausgeschlossenen Widerspruch verstößt (siehe hierzu Beispiel 1.5b)). Durch Verknüpfung von Elementaraussagen durch logische Operatoren, die sogenannten Junktoren (von lat. iungere „verknüpfen“, „verbinden“), können kompliziertere Aussagen gebildet werden. Dabei wird durch eine sogenannte Wahrheitstafel festgelegt, in welcher Weise der Wahrheitswert der zusammengesetzten Aussage durch die Wahrheitswerte der Elementaraussagen bestimmt ist (Prinzip der Extensionalität). In der klassischen Aussagenlogik sind die fünf Junktoren Negation, Konjunktion, Disjunktion, Implikation und Äquivalenz am gebräuchlichsten. Negationen Die Negation einer Aussage bezieht sich im Gegensatz zu den anderen vier Junktoren nur auf eine einzelne Aussage. Dennoch wird auch die Negation als eine Verknüpfung von Aussagen bezeichnet. Definition 1.4 (Negation) Die Negation ¬A der Aussage A (gelesen: „nicht A“) ist die Verneinung dieser Aussage A. Das heißt, ¬A ist wahr, wenn A falsch ist, und ¬A ist falsch, wenn A wahr ist. Die Negation ¬A ist festgelegt durch die Wahrheitstafel: A w f ¬A f w Neben ¬A ist auch A eine verbreitete Schreibweise für die Negation einer Aussage. Beispiel 1.5 (Negierte Aussagen) a) Die Aussage A = „Die Zahl 8 ist ohne Rest durch 3 teilbar“ besitzt die Negation ¬A = „Die Zahl 8 ist nicht ohne Rest durch 3 teilbar“ und entsprechend ist die Negation der Aussage B = „Die Zahl 9 ist ohne Rest durch 3 teilbar“ durch ¬B = „Die Zahl 9 ist nicht ohne Rest durch 3 teilbar“ gegeben. b) Die Feststellung E = „Der gegenwärtige König von Deutschland ist kahl“ verstößt gegen das Prinzip vom ausgeschlossenen Widerspruch und ist damit keine Aussage. Denn die Feststellung E ist falsch, da es gegenwärtig keinen König von Deutschland gibt. Aus demselben Grund ist auch die Negation ¬E = „Der gegenwärtige König von Deutschland ist nicht kahl“ falsch. Aus der Definition 1.4 und dem Gesetz der doppelten Verneinung (siehe den weiter unten folgenden Satz 1.17b)) folgt, dass die Feststellung E auch richtig ist. Das heißt die Feststellung E besitzt im Gegensatz zu einer Aussage sowohl den Wahrheitswert w als auch den Wahrheitswert f . 9 Kapitel 1 Aussagenlogik und mathematische Beweisführung c) Die Negation der Aussage A = „Alle Studierenden mögen das Fach Mathematik“ ist¬A = „Es gibt mindestens einen Studierenden, der das Fach Mathematik nicht mag.“ Hierbei ist zu beachten, dass die Aussage „Kein Studierender liebt das Fach Mathematik“ nicht die Negation von A ist. Konjunktionen Die Konjunktion zweier Aussagen A und B entspricht dem umgangssprachlichen Wort „und“ und ist wie folgt definiert: Definition 1.6 (Konjunktion) Die Konjunktion A ∧ B der beiden Aussagen A und B (gelesen: „A und B“) ist die aus den Aussagen A und B zusammengesetzte Aussage, die genau dann wahr ist, wenn sowohl die Aussage A als auch die Aussage B wahr ist. Ansonsten ist die Konjunktion A∧B falsch. Die Konjunktion A ∧ B ist festgelegt durch die Wahrheitstafel: A w w f f B w f w f A ∧ B w f f f Eine Konjunktion A∧B mit dem Wahrheitswert w entspricht somit einem „Es ist sowohl A als auch B wahr“. Eine Konjunktion ist falsch, wenn mindestens eine der beiden Aussagen A und B falsch ist. Die Wahrheitstafeln der beiden Konjunktionen A ∧ B und B ∧ A sind offensichtlich identisch. Beispiel 1.7 (Konjunktionen) Gegeben seien die beiden Aussagen A = „Die Bank 1 verkauft die Anleihe X“ und B = „Die Bank 1 verkauft die Anleihe Y “. Dann gilt: a) A∧B = „Die Bank 1 verkauft die Anleihen X und Y .“ b) ¬A ∧ B = „Die Bank 1 verkauft nicht die Anleihe X, aber die Anleihe Y .“ c) ¬A∧¬B = „Die Bank 1 verkauft weder die Anleihe X noch die Anleihe Y .“ Dabei wurde in Beispiel 1.7b) und c) stillschweigend die Konvention verwendet, dass die Negation vor der Konjunktion ausgeführt wird. Disjunktionen Die Disjunktion zweier Aussagen A und B entspricht dem umgangssprachlichen Wort „oder“ und ist wie folgt definiert: Definition 1.8 (Disjunktion) Die Disjunktion A∨B der beiden Aussagen A und B (gelesen: „A oder B“) ist die aus den Aussagen A und B zusammengesetzte Aussage, die genau dann wahr ist, wenn mindestens eine der beiden Aussagen A oder B wahr ist. Ansonsten ist die Disjunktion A∨B falsch. Die Disjunktion A ∨ B ist festgelegt durch die Wahrheitstafel: A w w f f B w f w f A ∨ B w w w f Eine Disjunktion A∨B mit dem Wahrheitswert w entspricht einem nicht ausschließenden „oder“ im Sinne von „Es ist A und/oderB wahr“. Eine Disjunktion ist somit nur dann falsch, wenn beide Aussagen A und B falsch sind. Das ausschlie- ßende „oder“ im Sinne von „Es ist entweder A oder B wahr“ wird durch die zusammengesetzte Aussage (A ∧ ¬B) ∨ (¬A ∧ B) ausgedrückt. Denn diese Aussage ist nur wahr, wenn A wahr und B falsch ist, oder wenn umgekehrt A falsch und B wahr ist. Dabei wurde stillschweigend die Konvention verwendet, dass die Negation vor der Konjunktion und der Disjunktion ausgeführt wird. Die Symbole ∨ und ∧ für Disjunktion bzw. Konjunktion können leicht dadurch unterschieden werden, dass das lateinische Wort „vel“ für das nicht ausschließende „oder“ mit dem Buchstaben „v“ anfängt. Die Wahrheitstafeln der beiden Disjunktionen A ∨ B und B ∨ A sind offensichtlich identisch. 10 Kapitel 11.3 Aussagenlogik Beispiel 1.9 (Disjunktionen) Durch A und B seien wieder die beiden Aussagen aus Beispiel 1.7 gegeben. Dann gilt: a) A ∨ B = „Die Bank 1 verkauft die Anleihe X und/oder die Anleihe Y .“ b) ¬A ∨ ¬B = „Die Bank 1 verkauft höchstens eine der beiden Anleihen X und Y .“ In Beispiel 1.9b) wurde stillschweigend die Konvention verwendet, dass die Negation vor der Disjunktion ausgeführt wird. Implikationen Die Implikation A ⇒ B ist die am wenigsten intuitive logische Operation. Sie ist wie folgt definiert: Definition 1.10 (Implikation) Die Implikation A ⇒ B (gelesen: „wenn A, dann B“) ist die aus den beiden Aussagen A und B zusammengesetzte Aussage, die genau dann falsch ist, wenn A wahr und B falsch ist. Sonst ist A ⇒ B wahr. Die Implikation ist festgelegt durch die Wahrheitstafel: A w w f f B w f w f A ⇒ B w f w w Die Aussage A wird dabei Voraussetzung oder Prämisse genannt und die Aussage B heißt Schlussfolgerung oder Konklusion. Anstelle von Implikation spricht man bei A ⇒ B auch von einer logischen Folgerung. Eine Implikation A ⇒ B ist bis auf den Fall einer wahren Voraussetzung A in Verbindung mit einer falschen Schlussfolgerung B stets wahr. Das heißt insbesondere, dass eine Implikation A ⇒ B, deren Voraussetzung A falsch ist, unabhängig vom Wahrheitswert der Schlussfolgerung B stets wahr ist. Somit kann man aus etwas Falschem alles folgern. Es existiert folglich ein großer Unterschied zwischen einer Implikation und der gängigen Vorstellung von einer „logischen Folgerung“, die man automatisch mit einer wahren Prämisse verbindet. Ist jedoch die Prämisse A wahr, dann hängt der Wahrheitsgehalt der Implikation A ⇒ B ausschließlich vom Wahrheitsgehalt der Aussage B ab: Ist B wahr, dann auch A ⇒ B. Ist B falsch, so auch A ⇒ B. Neben „wenn A, dann B“ sind für A ⇒ B auch die Sprechweisen „aus A folgt B“, „A impliziert B“, „A ist hinreichend für B“ und „B ist notwendig für A“ üblich. Für die Negation der ImplikationA ⇒ B schreibt man anstelle von¬(A ⇒ B) häufig auch A B. In Beispiel 1.14a) wird gezeigt, dass die Implikation A ⇒ B genau der Aussage ¬B ⇒ ¬A entspricht. Dieser Zusammenhang bildet die Grundlage sogenannter indirekter Beweise (Kontrapositionen), die bei der mathematischen Beweisführung eine wichtige Rolle spielen (siehe Abschnitt 1.6). Beispiel 1.11 (Implikationen) a) DurchA undB seien wieder die beiden Aussagen aus Beispiel 1.7 gegeben. Dann gilt: A ⇒ B = „Wenn die Bank 1 die Anleihe X verkauft, dann verkauft sie auch die Anleihe Y “ und A ⇒ ¬B = „Wenn die Bank 1 die Anleihe X verkauft, dann verkauft sie nicht die Anleihe Y “. b) Gegeben seien die beiden Aussagen A = „An meinem Standort regnet es in diesem Moment“ und B = „An meinem Standort ist die Straße in diesem Moment nass“. Dann ist die Aussage A ⇒ B wahr. c) Gegeben seien die beiden Aussagen A = „Die Zahl 3 teilt die Zahl n ohne Rest“ und B = „Die Zahl 9 teilt die Zahl n ohne Rest“. Dann ist die Aussage B ⇒ A stets wahr. Denn der Fall, dass die Prämisse B wahr und die Schlussfolgerung A falsch ist, kann nicht eintreten, da es keine Zahl n gibt, die ohne Rest durch 9, aber nicht ohne Rest durch 3 teilbar ist. d) Gegeben seien die Aussagen A = „Der Unternehmensgewinn ist gleich dem Umsatz abzüglich der Kosten“, B = „Die Kosten wachsen“, C = „Der Umsatz wächst“ und D = „Der Gewinn wächst“. Wird nun angenommen, dass A eine wahre Aussage ist, dann ist auch die Implikation C ∧ (¬B) ⇒ D = „Wenn der Umsatz wächst und die Kosten nicht steigen, dann wächst der Gewinn“ eine wahre Aussage. 11 Kapitel 1 Aussagenlogik und mathematische Beweisführung Dabei wurde in Beispiel 1.11a) stillschweigend die Konvention verwendet, dass die Negation vor der Implikation ausgeführt wird. Äquivalenzen Die Äquivalenz A ⇔ B ist wie folgt definiert: Definition 1.12 (Äquivalenz) Die Äquivalenz A ⇔ B (gelesen: „A ist äquivalent zu B“) ist die aus den beiden Aussagen A und B zusammengesetzte Aussage, die genau dann wahr ist, wenn sowohl die Aussage A als auch die Aussage B wahr ist, oder aber, wenn sowohl Aussage A als auch Aussage B falsch ist. Sonst ist A ⇔ B falsch. Die Äquivalenz A ⇔ B ist festgelegt durch die Wahrheitstafel: A w w f f B w f w f A ⇔ B w f f w Eine Äquivalenz A ⇔ B ist somit genau dann wahr, wenn die beiden Aussagen A und B den gleichen Wahrheitswert besitzen, und zwar unabhängig davon, ob dieser Wahrheitswert w oder f ist. In Beispiel 1.14b) wird gezeigt, dass die Äquivalenz A ⇔ B genau der Aussage (A ⇒ B)∧ (B ⇒ A) enspricht, d. h. die Äquivalenz (A ⇔ B) ⇐⇒ ((A ⇒ B) ∧ (B ⇒ A)) (1.2) wahr ist. Dabei wird in (1.2) die Konvention verwendet, dass die beiden Aussagen in Klammern auf der rechten Seite von (1.2) vor der Konjunktion ∧ ausgeführt werden. Somit ist bei einer wahren Äquivalenz A ⇔ B die Aussage A eine hinreichende Bedingung für B und die Aussage B ist eine hinreichende Bedingung für A. Dieser Zusammenhang ist bei der mathematischen Beweisführung sehr hilfreich (siehe hierzu die Abschnitte 1.5 und 1.6). Bei einer wahren Äquivalenz A ⇔ B sagt man, dass die Aussagen A und B logisch äquivalent sind. Neben „A ist äquivalent zu B“ sind für A ⇔ B auch die Sprechweisen „A ist gleichwertig zu B“, „A genau dann, wenn B“, „A dann und nur dann, wenn B“ und „A ist notwendig und hinreichend für B“ gebräuchlich. Für die Negation der Äquivalenz A ⇔ B schreibt man anstelle von ¬(A ⇔ B) häufig auch A B. Beispiel 1.13 (Äquivalenzen) a) Durch A und B seien wieder die beiden Aussagen aus Beispiel 1.7 gegeben. Dann gilt: A ⇔ B = „Die Bank 1 verkauft die Anleihe X genau dann, wenn sie auch die Anleihe Y verkauft“ und A ⇔ ¬B = „Die Bank 1 verkauft die Anleihe X genau dann, wenn sie die Anleihe Y nicht verkauft“. b) Gegeben seien die Aussagen A = „Die Zahl n ist ohne Rest durch die Zahl 6 teilbar“ undB = „Die Zahl n ist ohne Rest durch die Zahlen 2 und 3 teilbar“. Dann ist die Äquivalenz A ⇔ B eine wahre Aussage. c) Gegeben seien die beiden Aussagen A = „Heute ist Dienstag“ und B = „Morgen ist Mittwoch“. Dann ist die Äquivalenz A ⇔ B stets eine wahre Aussage, und zwar unabhängig davon, ob die Aussage A wahr oder falsch ist. d) Gegeben seien die beiden Aussagen A = „Das Versicherungsunternehmen X hat einen Marktanteil von 20%“ und B = „Die Konkurrenz des Versicherungsunternehmens X hat zusammen einen Marktanteil von 80%“. Dann ist A ⇔ B stets eine wahre Aussage, und zwar unabhängig davon, ob die Aussage A wahr oder falsch ist. In Beispiel 1.13a) wurde stillschweigend die Konvention verwendet, dass die Negation vor der Äquivalenz ausgeführt wird. In diesem Abschnitt wurden mit der Negation, Konjunktion, Disjunktion, Implikation und der Äquivalenz die fünf gebräuchlichsten Junktoren eingeführt. Dabei ist festzuhalten, dass einige dieser Junktoren redundant sind. Denn man kann zeigen, dass bereits zwei Junktoren ausreichend sind, wobei einer davon die Negation sein muss. Die anderen drei Junktoren können dann durch diese beiden Junktoren ausgedrückt werden. Zusammengesetzte Aussagen werden dann jedoch schnell sehr unübersichtlich und kompliziert, weshalb sich die Verwendung aller fünf Junktoren durchgesetzt hat. Das folgende Beispiel 1.14 zeigt, wie mit Hilfe dieser Junktoren problemlos auch mehr als zwei Aussagen zu neuen Aussagen verknüpft und deren Wahrheitswerte ermittelt werden können. Dabei ist die Reihenfolge, in welcher die einzelnen Teilaussagen ausgewertet werden, analog zur Arithmetik mit Hilfe von Klammern eindeutig festgelegt. Darüber hinaus werden zur Minimierung der dazu benötigten Anzahl 12 Kapitel 11.3 Aussagenlogik von Klammern üblicherweise die in Tabelle 1.1 angegebenen Konventionen bzgl. der Priorität der verschiedenen Junktoren getroffen. Priorität Junktor hoch Negation mittel Konjunktion, Disjunktion gering Implikation, Äquivalenz Tabelle 1.1: Konventionen bzgl. der Priorität der verschiedenen Junktoren (logische Operatoren) Beispiel 1.14 (Äquivalenzen) a) Die Aussagen A ⇒ B und ¬B ⇒ ¬A sind logisch äquivalent. Das heißt, es gilt (A ⇒ B) ⇐⇒ (¬B ⇒ ¬A). (1.3) Dies ist aus der folgenden Wahrheitstafel ersichtlich: A w w f f B w f w f A ⇒ B w f w w ¬B f w f w ¬A f f w w ¬B ⇒ ¬A w f w w Es ist zu erkennen, dass die beiden Teilaussagen A ⇒ B und ¬B ⇒ ¬A unabhängig von den Wahrheitswerten der Elementaraussagen A und B stets denselben Wahrheitswert besitzen. b) Die Aussagen A ⇔ B und (A ⇒ B) ∧ (B ⇒ A) sind ebenfalls logisch äquivalent. Das heißt, es gilt (A ⇔ B) ⇐⇒ ((A ⇒ B) ∧ (B ⇒ A)) . (1.4) Denn mit einer Wahrheitstafel erhält man: A w w f f B w f w f A ⇔ B w f f w A ⇒ B w f w w B ⇒ A w w f w (A ⇒ B) ∧ (B ⇒ A) w f f w Das heißt, die beiden Teilaussagen A ⇔ B und (A ⇒ B) ∧ (B ⇒ A) besitzen unabhängig von den Wahrheitswerten der Elementaraussagen A und B stets denselben Wahrheitswert. c) Die Aussagen A ⇒ B und (¬A) ∨ B sind logisch äquivalent. Das heißt, es gilt (A ⇒ B) ⇐⇒((¬A) ∨ B). (1.5) Dies ist aus der folgenden Wahrheitstafel ersichtlich: A w w f f B w f w f A ⇒ B w f w w ¬A f f w w (¬A) ∨ B w f w w Auch hier gilt, dass die beiden Teilaussagen A ⇒ B und (¬A) ∨ B unabhängig von den Wahrheitswerten der Elementaraussagen A und B stets denselben Wahrheitswert besitzen. d) Aus der folgenden Wahrheitstafel ist ersichtlich, dass auch die Aussagen ¬(A∧B) und (¬A)∨ (¬B) logisch äquivalent sind und somit (¬(A ∧ B)) ⇐⇒((¬A) ∨ (¬B)) (1.6) gilt. Dies zeigt die folgende Wahrheitstafel: A w w f f B w f w f A ∧ B w f f f ¬(A ∧ B) f w w w ¬A f f w w ¬B f w f w (¬A) ∨ (¬B) f w w w e) Zu guter Letzt erhält man, dass auch die Aussagen ¬(A∨B) und (¬A)∧ (¬B) logisch äquivalent sind und damit (¬(A ∨ B)) ⇐⇒((¬A) ∧ (¬B)) (1.7) gilt. Denn man erhält die folgende Wahrheitstafel: A w w f f B w f w f A ∨ B w w w f ¬(A ∨ B) f f f w ¬A f f w w ¬B f w f w (¬A) ∧ (¬B) f f f w 13 Kapitel 1 Aussagenlogik und mathematische Beweisführung Tautologien und Kontradiktionen Bei den zusammengesetzten Aussagen (1.3)–(1.7) handelt es sich somit um sogenannte Tautologien, d. h. Aussagen, die stets wahr sind. Ist das Gegenteil der Fall, d. h. ist eine Aussage stets falsch, dann spricht man von einer Kontradiktion: Definition 1.15 (Tautologie, Kontradiktion und Kontingenz) Eine (zusammengesetzte) Aussage heißt Tautologie oder Identität, wenn sie stets wahr ist. Im Gegensatz dazu wird eine Aussage als Kontradiktion oder Widerspruch bezeichnet, wenn sie stets falsch ist. Eine Aussage, die weder eine Tautologie, noch eine Kontradiktion ist, heißt Kontingenz oder Neutralität. Offensichtlich ist eine Aussage A genau dann eine Tautologie, wenn ihre Verneinung ¬A eine Kontradiktion ist. Umgekehrt ist eine Aussage A genau dann eine Kontradiktion, wenn ihre Verneinung ¬A eine Tautologie ist. Umgangssprachliche Tautologie Eine aus Teilaussagen zusammengesetzte AussageA ist eine Tautologie, wenn ihr Wahrheitswert unabhängig von den Wahrheitswerten der Teilaussagen stets w ist. Ist A dagegen eine Kontradiktion, dann ist der Wahrheitswert von A unabhängig von den Wahrheitswerten der Teilaussagen stets f . Der Wahrheitswert einer Kontingenz A ist dagegen abhängig von den Wahrheitswerten der Teilaussagen und kann w oder f sein. Zu beachten ist, dass umgangssprachlich Aussagen der Form „weißer Schimmel“, „schwarzer Rappe“, „unverheirateter Junggeselle“, „tote Leiche“ usw. ebenfalls als Tautologien bezeichnet werden. Eine Aussage heißt erfüllbar, wenn sie wahr werden kann, d. h. wenn sie keine Kontradiktion ist. Eine Aussage ist damit genau dann eine Tautologie, wenn ihre Verneinung nicht erfüllbar ist. Beispiel 1.16 (Tautologien und Kontradiktionen) a) Die Aussage A∨ (¬A) ist eine Tautologie. Dies ist aus der folgenden Wahrheitstafel ersichtlich: A w w f f ¬A f f w w A ∨ (¬A) w w w w Es ist zu erkennen, dass die Aussage A∨ (¬A) unabhängig vom Wahrheitswert der Elementaraussage A stets den Wahrheitswert w besitzt. b) Die Aussage A∧ (¬A) ist eine Kontradiktion. Dies ist aus der folgenden Wahrheitstafel ersichtlich: A w w f f ¬A f f w w A ∧ (¬A) f f f f Es ist zu erkennen, dass die Aussage A∧ (¬A) unabhängig vom Wahrheitswert der Elementaraussage A stets den Wahrheitswert f besitzt. c) Die Aussage A ⇔ (¬(¬A)) ist eine Tautologie. Dies ist aus der folgenden Wahrheitstafel ersichtlich: A w w f f ¬A f f w w (¬(¬A)) w w f f A ⇔ (¬(¬A)) w w w w Es ist zu erkennen, dass die Aussage A ⇔ (¬(¬A)) unabhängig vom Wahrheitswert der Elementaraussage A stets den Wahrheitswert w besitzt. d) Die Aussage A ∧ B ⇒ A ist eine Tautologie. Dies ist aus der folgenden Wahrheitstafel ersichtlich: A w w f f B w f w f A ∧ B w f f f A ∧ B ⇒ A w w w w Es ist zu erkennen, dass die Aussage A ∧ B ⇒ A unabhängig von den Wahrheitswerten der Elementaraussagen A und B stets den Wahrheitswert w besitzt. Völlig analog erhält man, dass auch A ⇒ A∨B eine Tautologie ist. 14 Kapitel 11.3 Aussagenlogik e) Die Aussage A ⇔ ¬A ist eine Kontradiktion. Dies ist aus der folgenden Wahrheitstafel ersichtlich: A w w f f ¬A f f w w A ⇔ ¬A f f f f Es ist zu erkennen, dass die Aussage A ⇔ ¬A unabhängig vom Wahrheitswert der Elementaraussage A stets den Wahrheitswert f besitzt. f) Die Aussage B = „Der Umsatz eines Unternehmens steigt oder er steigt nicht“ ist eine Tautologie. Dies folgt aus Teil a) dieses Beispiels. Denn die Aussage B ist von der Form A∨ (¬A) mit A = „Der Umsatz eines Unternehmens steigt“. g) Die Aussage C = „Eine natürliche Zahl n ist eine rationale Zahl“ ist eine Tautologie. Dies folgt aus Teil d) dieses Beispiels. Denn die Aussage C ist von der Form A∧B ⇒ A mit A = „Die Zahl n ist eine natürliche Zahl“ und B = „Die Zahl n ist eine rationale Zahl“. h) Die Aussage B = „Die Ungleichung xy > 1 ist genau dann erfüllt, wenn xy ≤ 1 gilt.“ ist eine Kontradiktion. Dies folgt aus Teil e) dieses Beispiels, denn die Aussage B ist von der Form A ⇔ ¬A mit A = „Die Ungleichung xy > 1 ist erfüllt“. Der folgende Satz fasst die wichtigsten Tautologien zusammen. Zum Teil wurden diese Identitäten schon in den vorhergehenden Beispielen nachgewiesen. Diese Tautologien bilden eine wichtige Grundlage für die Überlegungen zur mathematischen Beweisführung in Abschnitt 1.6 und damit auch für die Beweise aller mathematischen Aussagen in diesem Lehrbuch. Satz 1.17 (Wichtige Tautologien) Die folgenden Aussagen sind Tautologien: a) A ∨ ¬A (Gesetz vom ausgeschlossenen Dritten) b) A ⇔ (¬(¬A)) (Gesetz der doppelten Verneinung) c) Kommutativgesetze: A ∧ B ⇐⇒ B ∧ A A ∨ B ⇐⇒ B ∨ A (A ⇔ B) ⇐⇒ (B ⇔ A) d) Assoziativgesetze: A ∧ (B ∧ C) ⇐⇒ (A ∧ B) ∧ C A ∨ (B ∨ C) ⇐⇒ (A ∨ B) ∨ C (A ⇔ (B ⇔ C)) ⇐⇒ ((A ⇔ B) ⇔ C) e) Distributivgesetze: A ∧ (B ∨ C) ⇐⇒ (A ∧ B) ∨ (A ∧ C) A ∨ (B ∧ C) ⇐⇒ (A ∨ B) ∧ (A ∨ C) f) Regeln von De Morgan: ¬(A ∨ B) ⇐⇒ ¬A ∧ ¬B ¬(A ∧ B) ⇐⇒ ¬A ∨ ¬B g) (A ⇒ B) ⇐⇒ (¬B ⇒ ¬A) (Kontraposition) Beweis: Zu a) und b): Siehe Beispiel 1.16a) und c). Zu f) und g): Siehe Beispiel 1.14d) und e) bzw. Beispiel 1.14a). c), d) und e): Können analog zu den anderen Tautologien in Beispiel 1.14 und Beispiel 1.16 mit Hilfe von Wahrheitstafeln nachgewiesen werden. A. De Morgan Die beiden Tautologien in Satz 1.17f) sind nach dem englischen Mathematiker Augustus De Morgan (1806–1871) benannt. Sie besagen, dass die Verneinung einer Disjunktion logisch äquivalent zur Konjunktion der beiden verneinten Teilaussagen ist. Umgekehrt ist die Verneinung einer Konjunktion logisch äquivalent zur Disjunktion der beiden verneinten Teilaussagen. Wie sich in Abschnitt 2.3 zeigen wird, sind die Regeln von De Morgan nicht nur für die Aussagenlogik, sondern auch für die Mengenlehre bedeutsam. Das folgende etwas komplexere Beispiel demonstriert, wie sich durch Verknüpfung von Aussagen neue – auf den ersten Blick nicht offensichtliche – Erkenntnisse ergeben: 15 Kapitel 1 Aussagenlogik und mathematische Beweisführung Beispiel 1.18 (Drei Freunde im Gefängnis) In einem Gefängnis sitzen drei befreundete Häftlinge. Der erste sieht noch mit beiden Augen, der zweite sieht nur noch mit einem Auge und der dritte ist völlig blind. Der Gefängnisdirektor erklärt den drei Freunden, dass er fünf Hüte habe, von denen drei weiß und zwei schwarz seien. Anschließend setzt er jedem der Häftlinge einen der fünf Hüte auf, so dass die Häftlinge zwar die Farbe der Hüte der anderen beiden Häftlinge sehen können, aber nicht die Farbe des eigenen Hutes. Die beiden verbleibenden Hüte verwahrt er. Der Gefängnisdirektor verspricht nun dem normal sehenden Häftling die Freiheit, wenn er die Farbe seines Hutes nennen kann. Der normal sehende Häftling erklärt jedoch, dass er dies nicht könne. Der Gefängnisdirektor macht daher dem einäugigen Häftling dasselbe Angebot, worauf dieser jedoch antwortet, dass er auch nicht in der Lage sei, die Farbe seines Hutes zu nennen. Den blinden Häftling hingegen möchte der Gefängnisdirektor gar nicht erst fragen. Der blinde Häftling bittet jedoch darum, dieselbe Chance wie seine beiden Freunde zu erhalten. Der Gefängnisdirektor fragt daher auch den blinden Häftling nach der Farbe seines Hutes. Der blinde Häftling gibt auf diese Frage die korrekte Antwort: „Was ich von meinen Freunden weiß, das lässt mich sehen ganz genau auch ohne Augen: Mein Hut ist weiß!“ Anschließend erläutert der Blinde dem überraschten Gefängniswärter, dass sich mit Hilfe der drei Aussagen A = „Der Hut des normal sehenden Häftlings ist weiß“, B = „Der Hut des einäugigen Häftlings ist weiß“ und C = „Der Hut des blinden Häftlings ist weiß.“ die Aussagen des Gefängniswärters und seiner beiden Freunde wie folgt darstellen lassen: Die Aussage des Gefängniswärters ist A ∨ B ∨ C. Denn es gibt nur zwei schwarze Hüte. Die Aussage des normal sehenden Freundes istB∨C. Denn würden der einäugige Freund und der Blinde einen schwarzen Hut tragen, dann müsste aufgrund der Aussage des Gefängnisdirektors der Hut des normal sehenden Freundes weiß sein. Die Aussage des einäugigen Freundes ist C. Denn würde der Blinde einen schwarzen Hut tragen, dann müsste aufgrund der Aussage des normal sehenden Freundes der Hut des einäugigen Freundes weiß sein. Die Aussagen des Gefängniswärters, des normal sehenden Freundes und des einäugigen Freundes ergeben somit die zusammengesetzte Aussage (A ∨ B ∨ C) ∧ (B ∨ C) ∧ C. Da jedoch die Implikation (A ∨ B ∨ C) ∧ (B ∨ C) ∧ C ⇒ C offensichtlich eine Tautologie ist, folgt für den Blinden, dass sein Hut weiß sein muss. In Abschnitt 1.7 wird mit Hilfe der mathematischen Beweismethode der vollständigen Induktion ein ähnlich strukturiertes – aber komplizierteres – Problem gelöst (vgl. Beispiel 1.31). 1.4 Aussageformen und Quantoren In der Mathematik wird man sehr oft mit Formulierungen wie z. B. „x ist eine gerade Zahl“ konfrontiert. Bei dieser einfachen Feststellung handelt es sich jedoch um keine Aussage im Sinne der Definition 1.2. Denn aufgrund des „Platzhalters“ x lässt sich nicht entscheiden, ob diese Feststellung überhaupt sinnvoll ist, und falls sie Sinn ergibt, ob sie wahr oder falsch ist. Denn je nach Belegung von x erhält man einen Ausdruck, der keinen Sinn ergibt, z. B. „ √ 2 ist eine gerade Zahl“ ist eine wahre Aussage, z. B. „2 ist eine gerade Zahl“ oder eine falsche Aussage, z. B. „1 ist eine gerade Zahl.“ P. de Fermat Da jedoch die Formulierung „x ist eine gerade Zahl“ sprachlich die Form einer Aussage aufweist und man in der Mathematik z. B. sehr oft mit Ausdrücken der Form xn + yn = zn (1.8) konfrontiert wird, die von einem oder mehreren Platzhaltern abhängen, ist es sinnvoll, den Begriff der Aussage um diese Möglichkeit zu erweitern. 16 Kapitel 11.4 Aussageformen und Quantoren Zum Beispiel besagt eine vom französischen Mathematiker und Juristen Pierre de Fermat (ca. 1608–1665) vor ungefähr 400 Jahren aufgestellte Behauptung, dass die Gleichung (1.8) mit x, y, z ∈ N für keine natürliche Zahl n > 2 eine Lösung besitzt. Diese Behauptung ist unter der Bezeichnung der große Fermatsche Satz, Fermatsche Vermutung oder auch Jahrhundertproblem sehr berühmt geworden. A. Wiles Die Fermatsche Vermutung wurde erst im Jahre 1993 (publiziert 1995) – nach zahlreichen vergeblichen Versuchen bekannter und weniger bekannter Mathematiker – vom britischen Mathematiker Andrew Wiles (*1953) bewiesen. Aus Angst davor, von seinen Mathematik-Kollegen für seine Anstrengungen belächelt zu werden, hielt Wiles seine intensive und über sieben Jahre andauernde Arbeit an einem Beweis der Fermatschen Vermutung streng geheim. Briefmarke zum Beweis der Fermatschen Vermutung durch A. Wiles Für seine außergewöhnlichen mathematischen Leistungen wurde Wiles mit zahlreichen Wissenschaftspreisen ausgezeichnet. Darüber hinaus wurde er 2000 sogar mit einer eigenen Briefmarkenausgabe geehrt und zum Ritter geschlagen. Aussageformen Wird der Begriff der Aussage um die Möglichkeit der Existenz eines Platzhalters oder auch mehrerer Platzhalter erweitert, dann spricht man anstelle von Aussage von einer Aussageform: Definition 1.19 (Aussageform) Eine Aussageform A(x) oder A(x1, . . . , xn) ist ein Ausdruck, der einen oder mehrere Platzhalter x bzw. x1, . . . , xn enthält und durch Belegung der Platzhalter durch Objekte aus einem Bereich D in eine wahre oder falsche Aussage übergeht. Die Platzhalter x bzw. x1, . . . , xn werden dann als Variablen oder Veränderliche bezeichnet und der Bereich D heißt Definitionsbereich (Definitionsmenge) der Aussageform. Der Teilbereich L von D, für den die Aussageform in eine wahre Aussage übergeht, wird als Lösungsbereich (Lösungsmenge) der Aussageform bezeichnet. Analog zu Aussagen werden auch Aussageformen meistens mit lateinischen Großbuchstaben aus dem vorderen Teil des Alphabets, also A, B, C usw., bezeichnet. Zur Darstellung der Variablen benutzt man dagegen Kleinbuchstaben aus dem hinteren Teil des Alphabets, bspw. x, y, z oder x1, . . . , xn. Falls die Variablen für natürliche oder ganze Zahlen stehen, sind zur Darstellung der Variablen auch die Kleinbuchstaben k und n gebräuchlich. G. Frege Der Definitionsbereich D einer Aussageform A(x) ist in der Regel nicht eindeutig festgelegt. Oft verwendet man jedoch den größtmöglichen Bereich, für den die Aussageform in eine Aussage übergeht. Dabei ist zu beachten, dass der Lösungsbereich L in der Regel vom Definitionsbereich D abhängt. Nach Definition 1.19 hat eine Aussageform A(x) keinen bestimmbaren Wahrheitswert. Dieser resultiert erst nach Einsetzen eines Objekts aus dem Definitionsbereich D. Eine Aussageform A(x) kann daher als formale Vorschrift zur Gewinnung von Aussagen aufgefasst werden. Sie beschreibt eine Eigenschaft, die dem für die Variable x einzusetzendem Objekt gleichkommt. Das heißt, x erhält ein sogenanntes Prädikat. Aus diesem Grund wird die Theorie der Aussageformen als Prädikatenlogik oder Quantorenlogik bezeichnet. C. S. Peirce Die Prädikatenlogik stellt eine bedeutende Erweiterung der Aussagenlogik dar und wurde – unabhängig voneinander – von dem deutschen Mathematiker und Philosophen Gottlob Frege (1848–1925) und dem US-amerikanischen Mathematiker und Logiker Charles Sanders Peirce (1839–1914) entwickelt. Sie erlaubt es, komplexe Argumente 17 Kapitel 1 Aussagenlogik und mathematische Beweisführung und Sachverhalte zu formalisieren und auf ihre Gültigkeit hin zu überprüfen. Die Prädikatenlogik besitzt daher für viele Wissenschaften eine große Bedeutung. Werden die Variablen von Aussageformen durch konkrete Objekte aus dem jeweiligen Definitionsbereich ersetzt, dann resultieren Aussagen, die mit Hilfe der in Abschnitt 1.3 betrachteten Junktoren und Gesetze zu komplexeren Aussagen der Form ¬A(x), A(x) ∧ B(x), A(x) ∨ B(x), A(x) ⇒ B(x), A(x) ⇔ B(x) usw. zusammengesetzt und ausgewertet werden können. Häufig werden auch Aussageformen der Bauart 5x + 1 = b betrachtet, wobei b z. B. für eine beliebige reelle Zahl steht. Im Gegensatz zur Variablen x steht dann b stellvertretend für einen einmal ausgewählten und dann festgehaltenen Wert aus einem vorgegebenen Bereich, ohne dass man sich dabei auf einen speziellen Wert festlegt. Solche Größen werden als Konstanten oder Parameter bezeichnet. Für Parameter werden meistens lateinische Kleinbuchstaben aus dem vorderen Teil des Alphabets verwendet, wie z. B. a, b, c oder d. Beispiel 1.20 (Aussageformen) a) Die Aussageform A(x) = „x ist kleiner als 10“ besitze z. B. als Definitionsbereich D den Bereich der natürlichen Zahlen N. Der Lösungsbereich ist dann gegeben durch L = {1, 2, 3, 4, 5, 6, 7, 8, 9}. Dagegen besitzt A(x) für den Definitionsbereich D = {−3,−2,−1, 0, 1, 2, 3} den Lösungsbereich L = D. b) Die Aussageform A(n) = „n ist eine Primzahl“ besitzt als größtmöglichen Definitionsbereich N. Denn eine Primzahl ist gemäß Definition eine natürliche Zahl n, die größer als 1 und neben 1 nur noch durch sich selbst teilbar ist. Die Eigenschaft, eine Primzahl zu sein, ist somit nur für natürliche Zahlen definiert. Für D = N ist der Lösungsbereich gegeben durch L = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, . . . } . Das heißt, fürD=N ist der Lösungsbereich vonA(x) unbeschränkt, da es nach dem sogenannten Satz von Euklid (siehe Beispiel 1.27b)) unendlich viele Primzahlen gibt. Da jedoch bis heute kein Verfahren bekannt ist, mit dem auf effiziente Weise beliebig große Porträt von Euklid Primzahlen erzeugt werden können, existiert jeweils eine bis zum gegenwärtigen Zeitpunkt größte bekannte Primzahl. Am 23. August 2008 wurde an der University of California, Los Angeles mit 243112609 − 1 (1.9) die bis Ende 2011 größte bekannte Primzahl berechnet. Dies ist eine Zahl mit 12978189 Dezimalstellen. Das heißt, geht man davon aus, dass auf eine Buchseite ungefähr 50 Zeilen zu je 100 Ziffern passen, dann benötigt man 12978189/5000 ≈ 2596 Buchseiten, um alle diese Dezimalstellen aufzuschreiben. Ein solches Werk wäre bei weitem umfangreicher als dieses Lehrbuch. Poststempel mit der 1963 entdeckten 23. Mersenne-Primzahl Bei der Primzahl (1.9) handelt es sich um die größte sogenannte Mersenne-Zahl, von der bekannt ist, dass sie eine Primzahl ist. Bei einer Mersenne-Zahl handelt es sich um eine Zahl von der speziellen Form 2n − 1. Sie sind nach dem französischen Priester und Mathematiker Marin Mersenne (1588–1648) benannt und besitzen die schöne Eigenschaft, dass für sie ein Test existiert, mit dem auch für gewaltige Größenordnungen in überschaubarer Zeit überprüft werden kann, ob es sich um eine Primzahl handelt oder nicht. Mersenne-Zahlen, die auch Primzahlen sind, werden oft als Mersenne-Primzahlen bezeichnet. Bei der Primzahl (1.9) handelt es sich z. B. um die 48. bekannte Mersenne- Primzahl. Briefmarke mit der 2001 entdeckten 39. Mersenne-Primzahl Die ersten acht Mersenne- Primzahlen sind 22 − 1 = 3, 23 − 1 = 7, 25 − 1 = 31, 27 − 1 = 127, 213 − 1 = 8.191, 217 − 1 = 131.071, 219 − 1 = 524.287, 231 − 1 = 2.147.483.647. 18 Kapitel 11.4 Aussageformen und Quantoren Auf der Internetseite www.mersenne.org kann u. a. der jeweils aktuelle Stand aller bereits gefundenen Mersenne- Primzahlen eingesehen werden. Quantoren Neben dem Einsetzen von Objekten aus dem Definitionsbereich D können Aussageformen A(x) auch durch sogenannte Quantifizierungen in Aussagen überführt werden. Darunter versteht man den Einsatz von Quantoren wie „für alle x aus D“ und „es gibt ein x aus D“ zur Überführung einer Aussageform A(x) in eine Aussage. Die beiden gebräuchlichsten Quantoren sind der Allquantor und der Existenzquantor: Definition 1.21 (Quantoren) Es sei A(x) eine Aussageform mit Definitionsbereich D. a) Ist A(x) für alle x aus D eine wahre Aussage, dann sagt man „Für alle x giltA(x)“ oder auch „Für jedes x gilt A(x)“ und schreibt dafür ∀x : A(x) oder ∧ x A(x) (Allquantor). (1.10) b) Ist A(x) für mindestens ein x aus D eine wahre Aussage, dann sagt man „Für (mindestens) ein x gilt A(x)“ oder auch „Es gibt (mindestens) ein x mit A(x)“ und schreibt dafür ∃x : A(x) oder ∨ x A(x) (Existenzquantor). (1.11) c) Ist A(x) für genau ein x aus D eine wahre Aussage, dann sagt man „Für genau ein x gilt A(x)“ oder auch „Es gibt genau ein x mit A(x)“ und schreibt dafür ∃!x : A(x) oder •∨ x A(x) (Eindeutigkeitsquantor). (1.12) d) Ist A(x) für kein x aus D eine wahre Aussage, dann sagt man „Für kein x gilt A(x)“ oder auch „Es gibt kein x mit A(x)“ und schreibt dafür x : A(x) oder ¬∃x : A(x). (1.13) Wenn explizit auf den DefinitionsbereichD hingewiesen werden soll, dann werden auch die Schreibweisen ∀x ∈ D und ∃x ∈ D verwendet. Bei der Quantifizierung einer Aussageform A(x) durch einen der Quantoren ∀, ∃, ∃! und wird die ursprünglich freie Variable x gebunden. Das heißt, von außen betrachtet besitzen die Aussagen (1.10)–(1.13) keine freien Variablen mehr. Sie besitzen somit den Wahrheitswert w oder f und genügen folglich der Definition 1.2. Der Allquantor (1.10) und der Existenzquantor (1.11) können als eine Verallgemeinerung der Konjunktion bzw. Disjunktion von zwei Aussagen auf beliebig viele Aussagen aufgefasst werden. Dies soll auch durch die Verwendung der Symbole ∧ und ∨ zum Ausdruck kommen, die bis auf die Größe mit den Symbolen ∧ und ∨ für die Konjunktion bzw. Disjunktion übereinstimmen. Die Regeln von De Morgan gelten auch für die Konjunktion bzw. Disjunktion von beliebig vielen Aussagen. Sie lauten dann (vgl. Satz 1.17f)): ¬ ( ∧ x A(x) ) ⇐⇒ ∨ x ¬A(x) bzw. ¬ ( ∨ x A(x) ) ⇐⇒ ∧ x ¬A(x) Die Aussagen (1.10) und (1.11) werden als Allaussage bzw. Existenzaussage bezeichnet. Die Allaussage (1.10) ist falsch, wenn es auch nur ein einziges x aus D gibt, für welches die Aussage A(x) falsch ist. Die Negation von (1.10) ist somit ∃x : ¬A(x) bzw. ∨ x ¬A(x). Die Existenzaussage (1.11) ist dagegen falsch, wenn es kein (einziges) x aus D gibt, für welches die Aussage A(x) wahr ist. Das heißt, wenn für alle x aus D die Aussage ¬A(x) wahr ist. Die Negation von (1.11) ist somit ∀x : ¬A(x) bzw. ∧ x ¬A(x). Es lässt sich somit zusammenfassen, dass eine Aussage, in der die Quantoren ∀ und ∃ auftreten, verneint wird, indem durchgängig die Quantoren vertauscht werden (d. h. ∀ ↔ ∃) und jede Aussageform A(x) negiert wird (d. h. A(x) ↔ ¬A(x)). 19 Kapitel 1 Aussagenlogik und mathematische Beweisführung Beispiel 1.22 (Quantifizierung) a) Gegeben sei die Aussageform A(x) = „Der Studierende x besteht die Mathematik-Klausur“ und der Definitionsbereich D bestehe aus allen Studierenden. Dann gilt: ∀x : A(x) = „Alle Studierenden bestehen die Mathematik-Klausur“ ∃x : A(x) = „Mindestens ein Studierender besteht die Mathematik-Klausur“ ∃!x : A(x) = „Genau ein Studierender besteht die Mathematik-Klausur“ x : A(x) = „Kein Studierender besteht die Mathematik-Klausur“ b) Gegeben sei die Aussageform A(x) = „Der Kurs der Aktie x liegt über 100€“ und der Definitionsbereich D bestehe aus allen Aktien, die an der Wall Street gehandelt werden. Dann gilt: ∀x : A(x) = „Die Kurse aller Aktien liegen über 100€“ ∀x : ¬A(x) = „Der Kurs keiner Aktie liegt über 100€“ ¬ (∀x : A(x)) = „Es gibt Aktien mit einem Kurs nicht über 100€“ ¬ (∀x : ¬A(x)) = „Es gibt Aktien mit einem Kurs über 100€“ ∃x : A(x) = „Es gibt Aktien mit einem Kurs über 100€“ ∃x : ¬A(x) = „Es gibt Aktien mit einem Kurs nicht über 100€“ ¬ (∃x : A(x)) = „Es gibt keine Aktie mit einem Kurs über 100€“ ¬ (∃x : ¬A(x)) = „Es gibt keine Aktie mit einem Kurs nicht über 100€“ c) Gegeben sei die Aussageform A(x) = „x+ 4 = 15“ mit dem Definitionsbereich {1, 5, 8, 11}. Dann gilt: ∀x : A(x) ist eine falsche Aussage ∃x : A(x) ist eine wahre Aussage ∃!x : A(x) ist eine wahre Aussage x : A(x) ist eine falsche Aussage 1.5 Vermutung, Satz, Lemma, Folgerung und Beweis In Abschnitt 1.2 wurde bereits der grundsätzliche Unterschied zwischen Axiom, Definition und mathematischem Satz erläutert. Im Folgenden wird kurz auf die Unterscheidung zwischen Vermutung und mathematischem Satz eingegangen, sowie die übliche Differenzierung zwischen Satz, Lemma und Folgerung erläutert. Vermutungen und Sätze Im Gegensatz zu einer Vermutung, bei der es sich um eine Aussage handelt, von der (noch) nicht bekannt ist, ob sie wahr oder falsch ist (siehe hierzu z. B. die Legendresche Vermutung und Goldbachsche Vermutung in Abschnitt 1.3), handelt es sich bei einem mathematischen Satz stets um eine als wahr nachgewiesene mathematische Aussage. D. Hilbert Dabei bedient man sich beim Nachweis eines mathematischen Satzes eines sogenannten Beweises, der aus einer Folge von logischen und widerspruchsfreien Schlüssen besteht, die auf Axiomen und/oder bereits bekannten mathematischen Sätzen basieren. Das mathematische Teilgebiet, das sich speziell mit der Analyse von Beweisen beschäftigt, wird als Beweistheorie bezeichnet und wurde maßgeblich vom deutschen Mathematiker David Hilbert (1862–1943) geprägt. Mathematische Sätze werden je nach ihrer Rolle und Bedeutung weiter differenziert. In der Literatur sind für mathematische Sätze folgende Bezeichnungen gebräuchlich: a) Man spricht von Hilfssatz oder Lemma, falls die Aussage zur technischen Vorbereitung oder als Teilergebnis im Hinblick auf die Hauptaussage in einem darauf folgenden mathematischen Satz dient. Im Beweis dieses nachfolgenden Satzes wird dann die Aussage des Hilfssatzes (Lemmas) als mathematisches Hilfsmittel verwendet. Durch die Auslagerung von Teilen eines Beweises in Hilfssätze wird erreicht, dass kompliziertere Beweisschritte übersichtlicher werden und damit der gesamte Beweis letztendlich leichter verständlich ist. Ein Hilfssatz (Lemma) ist somit in der Regel ein vorbereitender mathematischer 20 Kapitel 11.6 Mathematische Beweisführung Satz, der oftmals nicht einfach zu beweisen ist. Das Wort Lemma stammt aus dem Griechischen und bedeutet soviel wie „Stichwort“ oder „Hauptgedanke“. Der Plural von Lemma ist Lemmata. Für ein Beispiel eines Hilfssatzes siehe den Hilfssatz in Beispiel 1.31. b) Die Bezeichnung Folgerung oder Korollar wird für einen mathematischen Satz verwendet, dessen Aussage sich aus einem vorhergehenden mathematischen Satz ohne großen Aufwand ergibt. Das Wort Korollar stammt von dem lateinischen Wort corollarium ab und bedeutet soviel wie „Kränzchen, das der Gastgeber dem Gast einfach so schenkt“. Für ein Beispiel einer Folgerung siehe Folgerung 3.24. c) Proposition ist das lateinische Wort für Satz und wird deshalb in der Mathematik als Synonym für Satz verwendet. Die Bezeichnung Proposition wird jedoch oftmals speziell für einen mathematischen Satz verwendet, der kein reiner Hilfssatz, aber auch kein bedeutender mathematischer Satz ist. In diesem Lehrbuch wird die Bezeichnung Proposition jedoch nicht verwendet. d) Ein wichtiger mathematischer Satz wird Theorem genannt, wenn er in der Regel nicht den Stellenwert eines Hauptsatzes oder Fundamentalsatzes besitzt. Das Wort Theorem stammt von dem griechischen Wort theorema ab und bedeutet soviel wie „Angeschautes“. Die Bezeichnung Theorem wird in diesem Lehrbuch ebenfalls nicht verwendet. e) Die Bezeichnung Hauptsatz ist für besonders bedeutende mathematische Sätze reserviert. Da in ihnen häufig ganze mathematische Teilgebiete gipfeln, gibt es nur relativ wenige Hauptsätze. Ein bereits aus der Schule bekanntes Beispiel für einen Hauptsatz ist der Hauptsatz der Differential- und Integralrechnung (siehe Abschnitt 19.6). f) Als Fundamentalsatz wird ein mathematischer Satz bezeichnet, dessen Aussage nicht nur für ein mathematisches Teilgebiet, sondern für die gesamte Mathematik von Bedeutung ist. Ein bekanntes Beispiel für einen Fundamentalsatz ist der Fundamentalsatz der Algebra (siehe Satz 4.2). In diesem Lehrbuch werden – wie auch sonst in der mathematischen Literatur oftmals üblich – alle mathematischen Sätze, Definitionen und Beispiele durchnummeriert. Darüber hinaus werden auch wichtige Formeln und Zwischenergebnisse mit einer fortlaufenden Nummer am rechten Rand versehen. Auf diese Weise kann an anderen Stellen im Text gezielt auf diese Ergebnisse verwiesen werden. 1.6 Mathematische Beweisführung Beweis für die globale Erderwärmung? In diesem Abschnitt werden wichtige mathematische Schlüsse, die zum Beweis oder zur Widerlegung einer mathematischen Aussage herangezogen werden können, vorgestellt und anhand von Beispielen erläutert. Die meisten Sätze werden aussagenlogisch als Implikation A ⇒ B oder als Äquivalenz A ⇔ B formuliert. Da jedoch die Aussage A ⇔ B äquivalent ist zu der aus zwei Implikationen zusammengesetzten Aussage (A ⇒ B) ∧ (B ⇒ A) (siehe Beispiel 1.14b)), genügt es, sich mit dem Beweis von Implikationen der Form A ⇒ B zu befassen. Die Aussage A wird dabei als Voraussetzung oder Prämisse bezeichnet und die Aussage B heißt – solange die Implikation A ⇒ B noch nicht bewiesen wurde – Behauptung. Nach dem Beweis wird B Schlussfolgerung oder Konklusion des Satzes genannt. Ein als Implikation A ⇒ B formulierter Satz gilt dann als bewiesen, wenn aus „A wahr“ auch „B wahr“ folgt (vgl. Definition 1.10). Ist jedoch „A“ wahr und „B“ falsch, dann ist die Negation ¬(A ⇒ B) der Implikation A ⇒ B wahr (vgl. Definition 1.4). In diesem Fall schreibt man dann A B (1.14) und sagt „wenn A, dann nicht notwendigerweise B“, „aus A folgt nicht allgemein B“, „A impliziert nicht B“ oder auch „A ist nicht hinreichend für B“. Beim Beweis eines Satzes ist stets akribisch darauf zu achten, dass der Nachweis der mathematischen Aussage in voller Allgemeinheit erfolgt. Andernfalls handelt es sich um keinen Beweis. Es ist auf keinen Fall ausreichend, die Gültigkeit eines Satzes nur anhand einiger Beispiele zu verifizieren. Der Beweis einer Aussage ist daher in den allermeisten Fällen nicht offensichtlich und oft genug ist eine vielversprechende Beweisidee nur mit großem Einfallsreichtum und einer gehörigen Portion Phantasie zu finden. Dieser Sachverhalt kommt auch sehr deutlich in dem folgenden Zitat des deutschen Mathematikers David Hilbert (1862–1943) zum Aus- 21 Kapitel 1 Aussagenlogik und mathematische Beweisführung druck, der auf die Frage nach dem Verbleib eines seiner früheren Assistenten antwortete: „Der ist Poet geworden. Für die Mathematik hatte er zu wenig Phantasie.“ Konstruktive und nicht-konstruktive Beweise Bei einem Beweis unterscheidet man ferner zwischen einem konstruktiven und einem nicht-konstruktiven Beweis. Bei einem konstruktiven Beweis einer mathematischen Aussage wird entweder die Lösung explizit angegeben oder ein Verfahren angegeben, mit dem die Lösung explizit ermittelt werden kann (d. h. es wird eine Lösung konstruiert). Dagegen spricht man von einem nicht-konstruktiven Beweis, wenn aus dem Beweis nur die Existenz einer Lösung hervorgeht, aber nicht, wie man zu dieser Lösung kommt. Aus Gründen der besseren Übersicht ist es oftmals üblich, das Ende des Beweises eines mathematischen Satzes durch das Symbol oder die Abkürzung „w.z.b.w.“ (für „was zu beweisen war“) bzw. deren lateinisches Pendant „q.e.d.“ (für „quod erat demonstrandum“) zu kennzeichnen. Beweise durch Nachrechnen Ist eine mathematische Aussage in Form einer Gleichung oder einer Ungleichung gegeben, dann kann man die Aussage oftmals durch einfaches Nachrechnen verifizieren. Dabei sind natürlich die für Gleichungen oder Ungleichungen geltenden Rechenregeln einzuhalten (siehe die Abschnitte 4.2 und 4.3). Beispiel 1.23 (Beweis durch Nachrechnen) a) Die Gleichung x − y u + (y − 2x)v uv + x u = 0 gilt für alle x aus R mit u, v = 0. Denn durch Umformung erhält man x − y u + (y − 2x)v uv + x u = xv − yv uv + yv − 2xv uv + xv uv = (xv − yv)+ (yv − 2xv)+ xv uv = 0. b) Die Ungleichung x6 + 3x4 + 4x2 − 40x + 95 ≥ −5 gilt für alle x aus R. Denn durch Umformung und Anwendung der binomischen Formel (a − b)2 = a2 − 2ab + b2 (siehe Abschnitt 5.3) erhält man x6 + 3x4 + 4x2 − 40x + 95 = x6 + 3x4 + 4(x2 − 10x + 25)− 5 = x6 + 3x4 + 4(x − 5)2 − 5 ≥ −5. Denn offensichtlich gilt x6 ≥ 0, 3x4 ≥ 0 und 4(x − 5)2 ≥ 0. Direkte Beweise Bei einem direkten Beweis einer Implikation A ⇒ B wird die Behauptung B unter der Voraussetzung A durch Anwendung von bereits bewiesenen Aussagen und durch logisches Schließen bewiesen. Ein direkter Beweis basiert auf der Tautologie A ∧ (A ⇒ B) ⇒ B, (1.15) der sogenannten Abtrennungsregel. Denn ist A ∧ (A ⇒ B) eine wahre Aussage (andernfalls ist (1.15) nach Definition 1.4 ohnehin wahr), dann sind sowohl A als auch A ⇒ B wahre Aussagen. Hieraus folgt, dass die Behauptung B wahr ist und damit insbesondere (1.15) eine Tautologie ist. In den meisten Fällen kann jedoch der Beweis einer Implikation A ⇒ B nur in mehreren Schritten erfolgen. Der Beweis basiert dann auf der Tautologie A ∧ (A ⇒ C1) ∧ ( n−1∧ k=1 (Ck ⇒ Ck+1) ) ∧ (Cn ⇒ B) ⇒ B, (1.16) wobei die Aussagen C1, . . . , Cn natürlich geeignet zu wählen sind. Die Tautologie (1.16) ist offensichtlich eine Verallgemeinerung der Abtrennungsregel und wird als Kettenschluss bezeichnet. Die Verwendung dieser Tautologie bietet sich immer dann an, wenn sich der Beweis der Implikation A ⇒ B durch Zerlegung in mehrere (einfachere) Implikationen A ⇒ C1, C1 ⇒ C2, . . . , Cn−1 ⇒ Cn und Cn ⇒ B stark vereinfachen lässt. 22 Kapitel 11.6 Mathematische Beweisführung In den folgenden drei Beispielen 1.24b), 1.25 und 1.26 treten zum ersten Mal Aussagen über die Eigenschaften der Menge R der reellen Zahlen auf. Für die Definition von R siehe Abschnitt 3.3. Beispiel 1.24 (Direkter Beweis von Implikationen) a) Die Aussage „Das Quadrat n2 einer ungeraden natürlichen Zahl n ist stets ungerade.“ lässt sich wie folgt direkt beweisen: Es sei n eine ungerade natürliche Zahl. Das heißt, es gibt ein k aus N, so dass n = 2k − 1 gilt. Mit der binomischen Formel (a− b)2 = a2 − 2ab+ b2 folgt daraus n2 = (2k − 1)2 = 4k2 − 4k + 1 = 2(2k2 − 2k)+ 1. Da 2(2k2 − 2k) offensichtlich stets eine gerade natürliche Zahl ist, folgt aus dieser Darstellung, dass n2 eine ungerade natürliche Zahl ist. b) Die Aussage „Es gilt a2 + b2 > 2ab für alle a, b aus R mit a = b.“ lässt sich mit Hilfe der binomischen Formel (a − b)2 = a2 − 2ab + b2 wie folgt in mehreren einfachen Schritten direkt beweisen: A ⇒C1 : ∀a, b : a = b ⇒ a − b = 0 C1 ⇒C2 : a − b = 0 ⇒ (a − b)2 >0 C2 ⇒C3 : (a − b)2 >0 ⇒ a2 − 2ab + b2 >0 C3 ⇒B : a2 − 2ab + b2 >0 ⇒ a2 + b2 >2ab. Dieser Beweis basiert somit auf der Tautologie A ∧ (A ⇒ C1) ∧ ((C1 ⇒ C2) ∧ (C2 ⇒ C3) ) ∧ (C3 ⇒ B) ⇒ B. In manchen Fällen ist es bei einem direkten Beweis zweckmä- ßig, eine sogenannte Fallunterscheidung vorzunehmen. Dies ist z. B. sehr häufig bei Ungleichungen der Fall, da sich bei der Multiplikation einer Ungleichung mit einer Zahl x < 0 das Ungleichheitszeichen umdreht. Das heißt, man hat im Falle der Multiplikation einer Ungleichung mit einer Variablen x die beiden Fälle x > 0 und x < 0 zu unterscheiden. Im ersten Fall bleibt das Ungleichheitszeichen erhalten, während es sich im zweiten Fall umdreht. Allgemein zerlegt man eine Aussage A beim Beweis der Implikation A ⇒ B mit Hilfe einer Fallunterscheidung in n restriktivere (einfachere) Aussagen A1, . . . , An, so dass A = n∨ k=1 Ak gilt. Anschließend beweist man dann die n (hoffentlich einfacheren) Implikationen A1 ⇒ B, A2 ⇒ B, . . . , An ⇒ B. Das heißt, der Beweis einer Implikation A ⇒ B mit einer Fallunterscheidung basiert auf der Tautologie A ∧ ( A ⇔ n∨ k=1 Ak ) ∧ ( n∧ k=1 (Ak ⇒ B) ) ⇒ B. Beispiel 1.25 (Direkter Beweis mittels Fallunterscheidung) Die Aussage „Es gilt x ≤ x2 + 1 für alle x aus R.“ lässt sich mit Hilfe der Fallunterscheidung x ≤ 1 und x > 1 direkt beweisen: A1 ⇒ B : x ≤ 1 ⇒ x ≤ x2 + 1 A2 ⇒ B : x > 1 ⇒ x · x > 1 · x ⇒ x2 + 1 ≥ x. Dieser Beweis basiert somit auf der Tautologie A∧(A ⇔ (A1 ∨ A2) )∧((A1 ⇒ B) ∧ (A2 ⇒ B) ) ⇒ B. Widerlegen einer Aussage Wenn dagegen eine Implikation A ⇒ B widerlegt werden soll, so ist zu zeigen, dass A B gilt. Das heißt, es ist nachzuweisen, dass die Negation ¬(A ⇒ B) wahr ist (vgl. (1.14)). Hierzu genügt es jedoch, ein Beispiel anzugeben, bei dem die Voraussetzung A erfüllt ist, aber die Behauptung B nicht wahr ist. 23 Kapitel 1 Aussagenlogik und mathematische Beweisführung Beispiel 1.26 (Widerlegen einer Aussage) Die Aussage „Es gilt x + 1 x > 2 für alle x aus R mit x > 0.“ lässt sich leicht widerlegen. Denn für x = 1 gilt z. B. x + 1 x = 2. Die Aussage ist damit widerlegt. Indirekte Beweise Bei einem indirekten Beweis, Widerspruchsbeweis oder auch einer Kontraposition einer Implikation A ⇒ B zeigt man, dass ein Widerspruch entstünde, wenn die zu beweisende Behauptung B falsch wäre. Dazu nimmt man an, dass die Behauptung B falsch ist, d. h. ¬B wahr ist, und wendet dann die gleichen mathematischen Schlüsse wie beim direkten Beweis an. Wenn daraus ein Widerspruch entsteht, dann kann die Behauptung B nicht falsch sein, also muss sie richtig sein. Ein indirekter Beweis basiert somit auf der Tautologie A ∧ (¬B ⇒ ¬A) ⇒ B, die sich unmittelbar aus Satz 1.17g) und der Tautologie (1.15) ergibt. Das heißt, ein indirekter Beweis ist ein direkter Beweis der Implikation ¬B ⇒ ¬A, der auf der Tautologie (A ⇒ B) ⇐⇒ (¬B ⇒ ¬A) basiert. Ein solcher indirekter Beweis bietet sich immer dann an, wenn es leichter erscheint, aus der Aussage ¬B logische Schlüsse zu ziehen als aus der Aussage A. Aufgrund der Tautologie (A ⇒ B) ⇐⇒ ¬(A ∧ (¬B)), Darstellung von Euklid die sich leicht analog zu den anderen Tautologien in den beiden Beispielen 1.14 und 1.16 mit Hilfe einer Wahrheitstafel beweisen lässt, kann ein indirekter Beweis der Implikation A ⇒ B auch dadurch erfolgen, dass die Aussage ¬(A∧(¬B)) als wahr nachgewiesen wird. Diese Vorgehensweise liegt dann nahe, wenn sich weder die Aussage A noch die Aussage ¬B allein eignen, um „leicht“ von A auf B (für die Implikation A⇒B) bzw. von ¬B auf ¬A (für die Implikation ¬B ⇒ ¬A) zu schließen. Das folgende Beispiel demonstriert das Vorgehen bei indirekten Beweisen anhand dreier konkreter Beispiele. In Teil b) wird die Gültigkeit des berühmten Satzes von Euklid nachgewiesen und in Teil c) die Tatsache, dass √ 2 keine rationale Zahl ist, d. h. √ 2 ∈ Q gilt. Für die Definition der Menge Q der rationalen Zahlen siehe Abschnitt 3.4. Sowohl der Satz von Euklid als auch die Irrationalität von √ 2 zählen zu den wichtigsten Sätzen der gesamten Mathematik. Beispiel 1.27 (Indirekte Beweise) a) Die Aussage „Ist n eine natürliche und n2 eine gerade Zahl, dann ist auch n gerade.“ lässt sich indirekt wie folgt beweisen: Es sei angenommen, dass n keine gerade Zahl ist. Dann ist n eine ungerade natürliche Zahl und mit Beispiel 1.24a) folgt somit, dass auch n2 ungerade ist. Dies ist jedoch ein Widerspruch zur Voraussetzung, dass n2 eine gerade Zahl ist. Die Zahl n muss somit gerade sein. b) Der berühmte Satz von Euklid „Es gibt unendlich viele Primzahlen.“ lässt sich indirekt wie folgt beweisen (zur Definition von Primzahlen siehe Beispiel 1.20b)): Angenommen, es gäbe nur endlich viele Primzahlen, die durch p1, p2, . . . , pn gegeben seien. Dann wäre die Zahl q = p1 · p2 · . . . · pn + 1 durch keine der Primzahlen p1, . . . , pn ohne Rest teilbar. Das heißt, die Primfaktoren der Zahl q gehören nicht zu den Primzahlen p1, p2, . . . , pn. Dies ist jedoch ein Widerspruch zu der Annahme, dass durch p1, p2, . . . , pn bereits alle existierenden Primzahlen gegeben sind. Bei diesem Beweis wurde der Fundamentalsatz der Arithmetik verwendet. Dieser besagt, dass sich jede natürliche Zahl n > 1 (bis auf die Reihenfolge) eindeutig als Produkt von Primzahlen darstellen lässt. Die Primzahlen dieses Produkts werden als Primfaktoren bezeichnet. Der Satz von Euklid geht auf den griechischen Mathematiker Euklid von Alexandria (ca. 360–280 v. Chr.) zurück. In seinem be- 24 Kapitel 11.7 Vollständige Induktion rühmtesten Werk „Die Elemente“ trug er das Wissen der griechischen Mathematik seiner Zeit zusammen. Dieses Werk diente mehr als 2000 Jahre lang als akademisches Lehrbuch und war noch bis in die zweite Hälfte des 19. Jahrhunderts nach der Bibel das meist verbreitete Werk der Weltliteratur. c) Die Aussage „ √ 2 ist keine rationale Zahl.“ lässt sich indirekt wie folgt beweisen: Es sei angenommen, dass √ 2 eine rationale Zahl ist. Dies impliziert dann, dass natürliche Zahlen p und q existieren mit q = 0, so dass √ 2 = p q (1.17) gilt (siehe hierzu Abschnitt 3.4). Dabei kann weiter angenommen werden, dass p und q keinen gemeinsamen Teiler größer als 1 besitzen (ansonsten kann der Bruch p q einfach um diesen Faktor gekürzt werden, so dass diese Annahme erfüllt ist). Aus (1.17) folgt dann durch Multiplizieren mit q und Quadrieren beider Seiten p2 = 2q2, (1.18) weshalb 2 ein Teiler von p2 ist. Damit ist aber neben p2 auch p eine gerade Zahl (siehe Teil a) dieses Beispiels). Es gilt daher p = 2r für eine geeignete natürliche Zahl r und damit insbesondere p2 = 4r2. Zusammen mit (1.18) impliziert dies 2q2 = 4r2 bzw. q2 = 2r2. Das heißt, q2 ist eine gerade Zahl und damit insbesondere auch q (folgt wieder mit Teil a) dieses Beispiels). Folglich ist 2 ein gemeinsamer Teiler von p und q. Dies ist jedoch ein Widerspruch zur Annahme, dass p und q keinen gemeinsamen Teiler größer als 1 besitzen. Das heißt, die Annahme, √ 2 sei eine rationale Zahl, ist falsch und es handelt sich somit bei √ 2 um eine irrationale Zahl. Dieser Beweis für die Irrationalität der Zahl √ 2 ist bereits in Euklids Werk „Die Elemente“ überliefert. Die Irrationalität der Zahl √ 2 zählt zu den wichtigsten mathematischen Entdeckungen, da es zu einer grundlegenden Veränderung der Mathematik im damaligen Griechenland geführt hat. Auf einer Liste der 100 wichtigsten mathematischen Sätze, die im Juli 1999 während einer Mathematiker-Tagung von Paul und Jack Abad vorgestellt wurde, befindet sich dieses Ergebnis auf Platz 1. Die Kriterien, welche diesem Ranking zugrunde gelegt wurden, waren „the place the theorem holds in the literature, the quality of the proof, and the unexpectedness of the result.“ 1.7 Vollständige Induktion F. Maurolicus Das Prinzip der vollständigen Induktion ist eine bedeutende und etablierte Beweismethode, auf die kein Zweig der Mathematik mehr verzichten kann. Sie wurde erstmals 1575 von dem bedeutenden griechischen Universalgelehrten Franciscus Maurolicus (1494–1575) eingesetzt, der mit ihrer Hilfe die Gültigkeit der Summenformel 1+3+5+7+. . .+(2n−1)=n2 für alle n ∈ N bewies. Da er jedoch dieses Beweisverfahren nicht weiter erläuterte, wird es in der Regel mit dem französischen Mathematiker Blaise Pascal (1623–1662) in Verbindung gebracht, der 1654 in seiner Schrift Traité du triangle arithmétique das Prinzip der vollständigen Induktion inklusive des sogenannten Induktionsanfangs und des Induktionsschritts thematisierte. Das Prinzip der vollständigen Induktion ist zum Beweis von Allaussagen der Form „Die Aussage A(n) gilt für alle natürlichen Zahlen n.“ bzw. formaler ∧ n A(n) (1.19) geeignet. 25 Kapitel 1 Aussagenlogik und mathematische Beweisführung B. Pascal Das Prinzip der vollständigen Induktion macht sich die Tautologie ∧ n A(n) ⇐⇒ A(1) ∧ ( ∧ n ( A(n) ⇒ A(n+ 1)) ) zu Nutze, die aus dem Peanoschen Axiom (P5) folgt (siehe Definition 1.1). Denn angewandt auf eine Allaussage der Form (1.19) besagt das Axiom (P5), dass, wenn A(1) wahr ist und aus „A(n) wahr“ auch „A(n+ 1) wahr“ folgt, die Aussage A(n) für alle n aus N gilt. Das Prinzip der vollständigen Induktion zum Beweis der Allaussage (1.19) verläuft daher in den folgenden zwei getrennten Schritten: 1) Induktionsanfang: Man weist nach, dass die Aussage A(1) wahr ist. 2) Induktionsschritt: Man wählt ein beliebiges n aus N und schließt aus der sogenannten Induktionsannahme A(n), dass auch A(n + 1) eine wahre Aussage ist. Auf diese Weise hat man dann gezeigt, dass ∧ n ( A(n) ⇒ A(n+ 1)) wahr ist. Dominoeffekt Das Beweisprinzip der vollständigen Induktion kann gut mit dem Dominoeffekt verglichen werden: Wenn der erste Dominostein fällt (entspricht dem Induktionsanfang, d. h. der Verankerung der Argumentation) und die Dominosteine so aufgestellt sind, dass durch jeden fallenden Dominostein der nächste umgesto- ßen wird (entspricht dem Induktionsschritt), dann wird schließlich jeder Dominostein irgendwann umfallen. Offensichtlich kann das Beweisprinzip der vollständigen Induktion in völlig analoger Weise auch zum Beweis von Allaussagen der Form „Die Aussage A(n) gilt für alle natürlichen Zahlen n ≥ k.“ bzw. formaler ∧ n≥k A(n) verwendet werden. Dabei kann k eine beliebige natürliche Zahl oder auch gleich 0 sein. In den meisten Fällen ist jedoch k = 0 oder k = 1 (siehe hierzu die nächsten Beispiele zur vollständigen Induktion). Bei der Durchführung des Beweisprinzips der vollständigen Induktion verändert sich dann lediglich der Induktionsanfang, indem nachgewiesen wird, dass die Aussage A(k) wahr ist. C. F. Gauß Die folgende Summenformel für die ersten n natürlichen Zahlen wird oftmals nach dem deutschen Mathematiker Carl Friedrich Gauß (1777–1855) als Gaußsche Summenformel oder auch als kleiner Gauß bezeichnet. Diese Summenformel war zwar bereits in der vorgriechischen Mathematik bekannt, sie wurde aber von dem 9-jährigen Gauß wiederentdeckt, als er von seinem Lehrer den Auftrag bekam, die ersten 100 natürlichen Zahlen aufzusummieren. Gauß löste diese Rechenaufgabe mit Hilfe seiner entdeckten Summenformel zum großen Erstaunen seines Lehrers innerhalb weniger Sekunden. Beispiel 1.28 (Gaußsche Summenformel) Die Gaußsche Summenformel ist gegeben durch n∑ i=1 i = 1 + 2 + 3 + . . .+ n = n(n+ 1) 2 (1.20) für alle n aus N. Für den Beweis der Gaußschen Summenformel mit Hilfe vollständiger Induktion bezeichnet A(n) im Folgenden die Aussage (1.20). Induktionsanfang: Die Aussage A(1) ist wahr. Denn durch Einsetzen von n = 1 in (1.20) erhält man 1 = 1·22 . Induktionsschritt: Es wird angenommen, dass die Aussage A(n) für ein beliebiges n aus N wahr ist. Für die Aussage A(n+1) folgt dann mit der Induktionsannahme n+1∑ i=1 i = 1 + 2 + . . .+ n+ (n+ 1) = n(n+ 1) 2 + (n+ 1) = (n+ 2)(n+ 1) 2 . Das heißt, die Aussage A(n+ 1) ist wahr. Damit ist gezeigt, dass die Gaußsche Summenformel (1.20) für alle n aus N gilt. 26 Kapitel 11.7 Vollständige Induktion Der Beweis der folgenden Summenformel für 3er-Potenzen ist sehr ähnlich: Beispiel 1.29 (Summenformel für 3er-Potenzen) Es gilt n∑ i=1 3i=3+32+33+. . .+3n = 1 2 ( 3n+1 − 3) (1.21) für alle n aus N. Für den Beweis dieser Summenformel mit Hilfe vollständiger Induktion bezeichnet A(n) im Folgenden die Aussage (1.21). Induktionsanfang: Die Aussage A(1) ist wahr. Denn durch Einsetzen von n = 1 in (1.21) erhält man 3 = 1 2 (3 2 − 3). Induktionsschritt: Es wird angenommen, dass die Aussage A(n) für ein beliebiges n aus N wahr ist. Für die Aussage A(n+1) folgt dann mit der Induktionsannahme n+1∑ i=1 3i = 3 + 32 + 33 + . . .+ 3n + 3n+1 = 1 2 ( 3n+1 − 3)+ 3n+1 = 1 2 ( 3n+2 − 3) . Das heißt, die Aussage A(n+ 1) ist wahr. Damit ist gezeigt, dass die Summenformel (1.21) für alle n aus N gilt. J. Bernoulli Das nächste Beispiel zeigt, wie mit Hilfe von vollständiger Induktion auch wichtige Ungleichungen bewiesen werden können. Es handelt sich dabei um die nach dem schweizerischen Mathematiker Jakob Bernoulli (1655–1705) benannte Ungleichung von Bernoulli. Mit ihrer Hilfe lassen sich in vielen Anwendungen Potenzfunktionen auf sehr einfache Weise nach unten abschätzen. Beispiel 1.30 (Ungleichung von Bernoulli) Die Ungleichung von Bernoulli ist gegeben durch (1 + x)n ≥ 1 + nx (1.22) für alle n aus N und jede reelle Zahl x > −1. Für den Beweis der Ungleichung von Bernoulli mit Hilfe vollständiger Induktion bezeichnet A(n) im Folgenden die Aussage (1.22). Induktionsanfang: Die Aussage A(1) ist wahr. Denn durch Einsetzen von n = 1 in (1.22) erhält man 1+ x ≥ 1 + x. Induktionsschritt: Es wird angenommen, dass die Aussage A(n) für ein beliebiges n aus N wahr ist. Für die Aussage A(n+1) folgt dann mit der Induktionsannahme und der Annahme x + 1 > 0 (1 + x)n+1 = (1 + x)(1 + x)n ≥ (1 + x)(1 + nx) = 1 + nx + x + nx2 ≥ 1 + (n+ 1)x. Das heißt, die Aussage A(n+ 1) ist wahr. Damit ist gezeigt, dass die Ungleichung von Bernoulli (1.22) für alle n aus N und x > −1 gilt. Eventuell auftretende Schwierigkeiten bei der konkreten Durchführung eines Induktionsbeweises liegen in der Regel darin begründet, dass es für den Induktionsschritt kein allgemeingültiges Rezept gibt. Je nach konkreter Aufgabenstellung kommt es darauf an, die Induktionsannahme „A(n) wahr“ in intelligenter Weise zum Nachweis der Gültigkeit der Implikation A(n) ⇒ A(n+1) für ein beliebiges n aus N auszunutzen. Darüber hinaus ist es bei Problemstellungen, die einem Beweis durch vollständige Induktion eigentlich grundsätzlich zugänglich sind, oftmals nicht offensichtlich, wie die Aussage A(n) geeignet zu formulieren ist. Das folgende Beispiel von „Anna und Bernd“ verdeutlicht dies. Es war im Jahre 1994 eine Aufgabe im Rahmen des Bundeswettbewerbs Mathematik und hat damals bei vielen Teilnehmern und Lehrern für großes Erstaunen gesorgt. Denn diese Aufgabe erscheint auf den ersten – und wahrscheinlich auch auf den zweiten – Blick erst einmal unlösbar. Darüber hinaus ist dieses Beispiel auch eine sehr gute Übung für indirekte Beweise und es zeigt, dass sich das Beweisprinzip der vollständigen Induktion auch zum Beweis von Aussagen verwenden lässt, die eine ganz andere Struktur aufweisen als die beiden Summenformeln (1.20) und (1.21) oder die Ungleichung (1.22). 27 Kapitel 1 Aussagenlogik und mathematische Beweisführung Beispiel 1.31 (Anna und Bernd) Ein Mathematik-Lehrer bittet seine Schülerin Anna eine natürliche Zahl a und seinen Schüler Bernd eine natürliche Zahl b jeweils auf einen Zettel zu schreiben, so dass es der Andere nicht sieht. Anschließend geben die beiden ihre Zettel ihrem Lehrer und dieser schreibt die Summe s = a+ b der beiden Zahlen von Anna und Bernd sowie eine weitere natürliche Zahl x an die Tafel. Das heißt, an der Tafel stehen dann die beiden natürlichen Zahlen s und x. Der Lehrer fragt anschließend Anna, ob sie ihm sagen könne, welche Zahl Bernd aufgeschrieben hat. Falls Anna mit „Nein“ antwortet, fragt er Bernd, ob er wisse, welche Zahl Anna aufgeschrieben hat. Falls auch Bernd mit „Nein“ antwortet, fragt er wieder Anna usw. Es gilt nun die folgende Behauptung: Behauptung: Nach endlich vielen Nein-Nein-Runden weiß Anna oder Bernd, welche Zahl der Andere aufgeschrieben hat. Zum Beweis dieser Behauptung wird zuerst mittels vollständiger Induktion der folgende Hilfssatz bewiesen: Hilfssatz: Anna und Bernd haben beide n-mal „Nein“ gesagt. Dann gilt: a) x ≥ a + n und b) b ≥ n+ 1. Beweis des Hilfssatzes: Für den Beweis des obigen Hilfssatzes mit Hilfe vollständiger Induktion bezeichneA(n) die Aussage „Anna und Bernd haben beide n-mal ‘Nein’ gesagt.“ Induktionsanfang: Die Aussage A(1) ist wahr. Denn zum einen gilt x ≥ a + 1 und somit a). Im Falle von x ≤ a hätte nämlich Anna gleich zu Beginn „Ja“ gesagt. Zum anderen gilt b ≥ 2 und somit b). Denn im Falle von b = 1 würde s = a + 1 und x mit x ≥ a+ 1 = s an der Tafel stehen. Aufgrund von Annas „Nein“ würde Bernd dann jedoch wissen, dass x > s gelten muss. Das heißt, Bernd würde wissen, dass die kleinere der beiden Zahlen an der Tafel die Summe s = a + 1 ist. Somit muss bei zweimal „Nein“ in der ersten Runde x ≥ a + 1 und b ≥ 2 gelten. Damit ist die Gültigkeit der Aussage A(1) nachgewiesen. Induktionsschritt: Es wird angenommen, dass A(n) wahr ist für ein beliebiges n aus N. Es ist nun zu zeigen, dass die Gültigkeit von A(n) auch die Gültigkeit von A(n+1) impliziert. Das heißt, es ist zu zeigen, dass bei n+1 Nein-Nein-Runden die beiden Ungleichungen a) x ≥ a + n+ 1 und b) b ≥ n+ 2 gelten. Zu a): Es gilt x ≥ a + n+ 1. Denn im Falle von x < a + n+ 1 würde aus dem ersten Teil der Induktionsannahme x ≥ a+n folgen, dass x = a+n gilt. An der Tafel würden somit x = a+n und s = a+ b stehen. Aus dem zweiten Teil der Induktionsannahme b ≥ n+ 1 folgt jedoch s = a+ b ≥ a+ n+ 1. Anna würde also in der (n+ 1)-ten Runde erkennen, dass die kleinere Zahl an der Tafel x = a + n sein muss und daher mit „Ja“ antworten. Zu b): Es gilt b ≥ n + 2. Denn im Falle von b < n + 2 würde aus dem zweiten Teil der Induktionsannahme b ≥ n+ 1 folgen, dass b = n+ 1 gilt. Wegen a) würde daraus weiter s = a+ b = a+ n+ 1 ≤ x folgen. Da Anna jedoch zuvor „Nein“ gesagt hat, gilt sogar s = a + b < x. Bernd würde also in der (n + 1)-ten Runde erkennen, dass die kleinere Zahl an der Tafel die Summe s = a + b sein muss und daher mit „Ja“ antworten. Mit Hilfe dieses Ergebnisses kann nun die Behauptung sehr einfach durch einen indirekten Beweis nachgewiesen werden: Angenommen, weder Anna noch Bernd würden jemals herausfinden, welche Zahl der Andere aufgeschrieben hat. Dann würde es unendlich viele Nein-Nein-Runden geben. Gemäß der Aussage des Hilfssatzes würde dies aber auch bedeuten, dass x ≥ a + n und b ≥ n+ 1 für alle n aus N gilt, insbesondere auch für n = b. Das heißt, es würde fälschlicherweise b ≥ b + 1 gelten. Die Annahme, dass es unendlich viele Nein-Nein-Runden gibt, muss somit falsch sein. Das heißt – ausreichend hohe Intelligenz bei Anna und Bernd vorausgesetzt – einer der beiden wird nach endlich vielen Runden „Ja“ sagen. Im Folgenden wird das Beispiel von Anna und Bernd anhand von zwei bewusst sehr einfach gewählten konkreten Zahlenbeispielen demonstriert: 1. Zahlenbeispiel: Anna, Bernd und der Lehrer schreiben die folgenden Zahlen auf: Anna Bernd Lehrer 10 35 30 −→ Tafel: 30 und 45 Dann sagt Anna in der ersten Runde „Nein“, da beide Zahlen an der Tafel größer als ihre Zahl sind. Bernd weiß jedoch anschließend, dass nur die Zahl 45 die Summe der Zahlen von Anna und ihm sein kann. Denn nur die Zahl 45 ist größer als seine eigene Zahl. Bernd sagt deshalb bereits in der ersten Runde „Ja“. 28 Kapitel 11.7 Vollständige Induktion 2. Zahlenbeispiel: Anna, Bernd und der Lehrer schreiben die folgenden Zahlen auf: Anna Bernd Lehrer 10 20 45 −→ Tafel: 30 und 45 Dann sagt Anna in der ersten Runde wieder „Nein“, da beide Zahlen an der Tafel größer als ihre Zahl sind. Bernd sagt aber jetzt in der ersten Runde auch „Nein“, da beide Zahlen an der Tafel größer als seine Zahl sind. Durch das „Nein“ von Anna in der ersten Runde, erhält er zwar die Information, dass ihre Zahl kleiner als min{30, 45} ist, doch diese Information hatte er schon vorher und sie besitzt somit keinen Wert für ihn. Durch das „Nein“ von Bernd in der ersten Runde, kann Anna jedoch in der zweiten Runde folgern, dass er die Zahl 20 aufgeschrieben hat. Denn bei der Zahl 35 hätte Bernd in der ersten Runde wissen müssen, dass die Zahl 30 an der Tafel nicht die Summe der Zahlen von Anna und ihm sein kann. Anna sagt somit in der zweiten Runde „Ja“. 29

Chapter Preview

References

Zusammenfassung

"uneingeschränkt zu empfehlen, [...] insbesondere als Einstiegslektüre im Bachelor-Studium". In: Studium, 2013.

So zentral die Rolle der Mathematik in der Ökonomie ist, so schwer tun sich die Studierenden mit mathematischen Methoden und Konzepten. Umso wichtiger ist es, die Studierenden bei ihrem aktuellen Wissensstand abzuholen und vorsichtig an den Stoff heranzuführen. Diesem Ziel verschreibt sich dieses Lehrbuch. Es führt mit vielen interessanten Beispielen aus der Ökonomie, kurzen Anekdoten und einem modernen mehrfarbigen Design in die zentralen mathematischen Methoden für ein erfolgreiches Wirtschaftsstudium ein, ohne dabei auf mathematische Klarheit sowie die notwendige Formalität und Stringenz zu verzichten. Auch nach dem Studium ist dieses Buch ein wertvoller Begleiter bei der mathematischen Lösung wirtschaftswissenschaftlicher Problemstellungen.

Aus dem Inhalt:

* Mathematische Grundlagen

* Lineare Algebra

* Matrizentheorie

* Folgen und Reihen

* Reellwertige Funktionen in einer und mehreren Variablen

* Differential- und Integralrechnung

* Optimierung mit und ohne Nebenbedingungen

* Numerische Verfahren

Dozenten finden auf der Website zum Buch unter www.vahlen.de zusätzliche Materialien zum Download.

"Indem Sie den Lehrstoff schrittweise aufbereiten und den Leser bei seinem aktuellen Wissenstand abholen, gelingt es ihnen [den Autoren], auch komplexe Zusammenhänge leicht nachvollziehbar zu vermitteln. Geschickt bauen sie immer wieder kurze Anekdoten, historische Ereignisse und überraschende Erkenntnisse in den Text ein". In: Studium, 2013.

Prof. Dr. Michael Merz ist Inhaber des Lehrstuhls für Mathematik und Statistik in den Wirtschaftswissenschaften an der Universität Hamburg. Prof. Dr. Mario V. Wüthrich forscht und lehrt am Department für Mathematik der ETH Zürich.