Design Patterns für mathematische Beweise: Ein Leitfaden insbesondere für Informatiker

Dieses Buch behandelt einfache Beweismuster wie Fallunterscheidung, Allbeweis, Implikationsbeweis, komplexe Beweismuster wie Kontraposition, Widerspruchsbeweis, Diagonalisierung sowie die verschiedenen Varianten der vollständigen Induktion bis hin zur transfiniten Induktion. Damit gibt es Antworten auf Fragen wie Was genau ist eigentlich ein Widerspruchsbeweis? Oder eine Widerlegung? Und wie hängen sie miteinander zusammen? Die Autoren versuchen, derartige fragen zu erörtern, indem sie verbreitete Beweismuster und anhand von allgemein verständlichen Beispielen aus dem Alltag, der Mathematik und der Informatik zu verdeutlichen. Vorwort 5 Inhaltsverzeichnis 8 Teil I. Einfache und komplexe Beweismuster 11 Kapitel 1.Einleitung 12 Kapitel 2. Vorbereitung: Arten des Schließens 14 2.1. Deduktives Schließen (Deduktion) 14 2.2. Induktives Schließen (Induktion) 15 2.3. Abduktives Schließen (Abduktion) 17 2.4. Andere Arten des Schließens im Alltag 18 2.5. Schließen in mathematischen Beweisen 19 2.5.1. Vorwärtsschließen 20 2.5.2. Rückwärtsschließen 20 2.5.3. Bidirektionales Schließen 20 Kapitel 3. Vorbereitung: Schreibweisen der Logik 22 3.1. Logische Symbole 22 3.1.1. Junktoren 22 3.1.2. Quantoren 23 3.1.2.1. Kurzschreibweisen für beschränkte Quantifizierung 24 3.2. Anwendungsspezifische Symbole 24 3.3. Formeln und Terme 26 3.4. Präfix, Infix, Postfix 26 3.5. Rechenregeln 27 Kapitel 4. Einfache Beweismuster 29 4.1. Deduktive Kette: Beweis durch „Ausrechnen“ 29 4.1.1. Beweis aus Beispiel 10: Beweispräsentation vs. Beweissuche 31 4.2. Beweis durch Fallunterscheidung 34 4.3. Allbeweis 34 4.4. Implikationsbeweis 36 4.5. Existenzbeweis 37 4.5.1. Konstruktiver Existenzbeweis 37 4.5.2. Nicht-konstruktiver Existenzbeweis 41 4.5.3. Exkurs: „Unangenehme“ Existenzbeweise 42 4.5.4. Exkurs: Existenzbeweise und Programmsynthese 46 4.5.4.1 Skolem-Funktionen 46 4.5.4.2 Deduktive Programmsynthese 47 Kapitel 5. Komplexe Beweismuster 50 5.1. Deduktives Netz: Beweis durchVernetzung deduktiver Ketten 50 5.2. Beweis durch Kontraposition 51 5.3. Äquivalenzbeweis 54 5.4. Widerspruchsbeweis 55 5.4.1. Widerspruchsbeweis durch Transformation (Reduktion) 59 5.4.2. Widerspruchsbeweis durch Diagonalisierung 62 5.5. Widerlegung 67 5.5.1. Widerlegung durch Gegenbeispiel 67 5.5.2. Widerlegung durch Spezialisierung 69 Kapitel 6. Vollständige Induktion 71 6.1. Beweis durch vollständige Induktion über natürliche Zahlen 72 6.1.1. Grundmuster 73 6.1.1.1. Variationen des Grundmusters 78 6.1.2. Starke Induktion 80 6.1.2.1. Variationen der starken Induktion 80 6.1.3. k-Induktion 87 6.2. Allgemeinere Charakterisierung der vollständigen Induktion 89 6.3. Beweis durch Noethersche Induktion 91 6.3.1. Terminierungsbeweis durch Noethersche Induktion 98 6.4. Bauminduktion 104 6.4.1. Rekursive Definition einer Menge 106 6.4.1.1. Top-down-Lesart 108 6.4.1.2. Bottom-up-Lesart 109 6.4.1.3. Ableitungsbaum vs. Strukturbaum 110 6.4.2. Beweis durch Top-down-Bauminduktion 111 6.4.3. Bottom-up-Bauminduktion: Beweis durch strukturelle Induktion 113 6.5. Exkurs: Beweis durch transfinite Induktion 117 Teil II. Transfinite Ordinalzahlen und transfinite Induktion 119 Kapitel 7. Einleitung zu Teil II 120 Kapitel 8. Vollständige Induktion und Grenzwertbildung 121 8.1. Folgen, Reihen und Grenzwerte 121 8.2. Vollständige Induktion mit Limesfall 123 8.3. Bedeutung und Notation von „unendlich“ 124 Kapitel 9. Transfinite Ordinalzahlen 125 9.1. Cantors Hotel(s) 125 9.1.1. Graphische Veranschaulichung zu Cantors Hotels 132 9.1.2. Anzahl der Zimmer in den ω-Hotels 134 9.1.3. Auf- und Absteigen in den ω Hotels 135 9.2. Die von-Neumann-Ordinalzahlen 135 9.3. Transfinite Ordinalzahlen: Hydra-Bekämpfung und Terminierung 138 9.4. Ordinalzahlen bis einschließlich ω 143 9.4.1. Ordinalzahlen und Wiederholungsschleifen 143 9.4.2. ω-Automaten (Datenstrom-Automaten) 146 Kapitel 10. Transfinite Induktion 148 10.1. Transfinite Induktion: Fixpunktsemantik 150 10.2. Transfinite Induktion: Zimmerhöhen im ω-Hotel 152 10.2.1. Höhen der Obergeschosse 152 10.2.2. Gesamthöhen der Zimmer 154 10.3. Transfinite Induktion bis einschließlich ω mit dem Kompaktheitssatz 161 Kapitel 11. Exkurs: Mathematisches Arbeiten 165 11.1. Entwicklungsprozess zu den Ergebnissen in Abschnitt 10.2 165 11.2. Mathematisches Arbeiten und Pizzabacken 167 11.2.1. Präsentationsebene 167 11.2.2. Analyseebene 168 11.2.3. Entwicklungsebene 170 Anhang 171 Danksagung und Schlusswort 172 Literaturverzeichnis 173 Verzeichnis mathematischer Symbole und Bezeichnungen 175 Verzeichnis der Beweisschemata und Beispiele 177 Stichwortverzeichnis 180 Dieses Buch behandelt einfache Beweismuster wie Fallunterscheidung, Allbeweis, Implikationsbeweis und komplexe Beweismuster wie Kontraposition, Widerspruchsbeweis, Diagonalisierung sowie die verschiedenen Varianten der vollständigen Induktion bis hin zur transfiniten Induktion. Damit gibt es Antworten auf Fragen wie: Was genau ist eigentlich ein Widerspruchsbeweis? Was ist eine Widerlegung? Und wie hängen sie zusammen? Dazu erörtern die Autoren verbreitete Beweismuster anhand von allgemein verständlichen Beispielen aus dem Alltag, der Mathematik und der Informatik. Der Inhalt Arten des Schließens Schreibweisen der Logik Einfache Beweismuster Komplexe Beweismuster Vollständige Induktion Vollständige Induktion und Grenzwertbildung Transfinite Ordinalzahlen Transfinite Induktion Exkurs: mathematisches Arbeiten Die Zielgruppen Studierende der Informatik und anderer Fächer, bei denen mathematische Beweise eine Rolle spielen Dozenten, die Material und Beispiele für Beweistechniken benötigen Die Autoren Professor Dr. Hans Jürgen Ohlbach arbeitete nach seinem Studium der Physik und Mathematik an der Universität Mainz auf dem Gebiet Künstliche Intelligenz und Automatisches Beweisen. Er promovierte an der Technischen Universität Kaiserslautern zu einem Thema der nichtklassischen Logik. Anschließend war er stellvertretender Direktor am Max-Planck Institut für Informatik in Saarbrücken und arbeitete in London am Imperial College und am King's College, bis er an das Institut für Informatik der Ludwig-Maximilians Universität in München berufen wurde. Dort war er als Studiendekan maßgeblich an der Einführung und Gestaltung der Bachelor- und Masterstudiengänge beteiligt. Dr. Norbert Eisinger studierte Informatik (Diplom) an der Universität Karlsruhe und promovierte im Fachbereich Infor matik der Universität Kaiserslautern. Nach einigen Jahren an einem industriellen Forschungszentrum arbeitete er seit 1993 als wissenschaftlicher Angestellter am I Dieses Buch behandelt einfache Beweismuster wie Fallunterscheidung, Allbeweis, Implikationsbeweis und komplexe Beweismuster wie Kontraposition, Widerspruchsbeweis, Diagonalisierung sowie die verschiedenen Varianten der vollständigen Induktion bis hin zur transfiniten Induktion. Damit gibt es Antworten auf Fragen wie: Was genau ist eigentlich ein Widerspruchsbeweis? Was ist eine Widerlegung? Und wie hängen sie zusammen? Dazu erörtern die Autoren verbreitete Beweismuster anhand von allgemein verständlichen Beispielen aus dem Alltag, der Mathematik und der Informatik. Der Inhalt Arten des Schließens Schreibweisen der Logik Einfache Beweismuster Komplexe Beweismuster Vollständige Induktion Vollständige Induktion und Grenzwertbildung Transfinite Ordinalzahlen Transfinite Induktion Exkurs: mathematisches Arbeiten Die Zielgruppen Studierende der Informatik und anderer Fächer, bei denen mathematische Beweise eine Rolle spielen Dozenten, die Material und Beispiele für Beweistechniken benötigen Die Autoren Professor Dr. Hans Jürgen Ohlbach arbeitete nach seinem Studium der Physik und Mathematik an der Universität Mainz auf dem Gebiet Künstliche Intelligenz und Automatisches Beweisen. Er promovierte an der Technischen Universität Kaiserslautern zu einem Thema der nichtklassischen Logik. Anschließend war er stellvertretender Direktor am Max-Planck Institut für Informatik in Saarbrücken und arbeitete in London am Imperial College und am King's College, bis er an das Institut für Informatik der Ludwig-Maximilians Universität in München berufen wurde. Dort war er als Studiendekan maßgeblich an der Einführung und Gestaltung der Bachelor- und Masterstudiengänge beteiligt. Dr. Norbert Eisinger studierte Informatik (Diplom) an der Universität Karlsruhe und promovierte im Fachbereich Informatik der Universität Kaiserslautern. Nach einigen Jahren an einem industriellen Forschungszentrum arbeitete er seit 1993 als wissenschaftlicher Angestellter am In Front Matter ....Pages i-xi Front Matter ....Pages 1-1 Einleitung (Hans Jürgen Ohlbach, Norbert Eisinger)....Pages 3-4 Vorbereitung: Arten des Schließens (Hans Jürgen Ohlbach, Norbert Eisinger)....Pages 5-12 Vorbereitung: Schreibweisen der Logik (Hans Jürgen Ohlbach, Norbert Eisinger)....Pages 13-19 Einfache Beweismuster (Hans Jürgen Ohlbach, Norbert Eisinger)....Pages 21-41 Komplexe Beweismuster (Hans Jürgen Ohlbach, Norbert Eisinger)....Pages 43-63 Vollständige Induktion (Hans Jürgen Ohlbach, Norbert Eisinger)....Pages 65-112 Front Matter ....Pages 113-113 Einleitung zu Teil II (Hans Jürgen Ohlbach, Norbert Eisinger)....Pages 115-115 Vollständige Induktion und Grenzwertbildung (Hans Jürgen Ohlbach, Norbert Eisinger)....Pages 117-120 Transfinite Ordinalzahlen (Hans Jürgen Ohlbach, Norbert Eisinger)....Pages 121-143 Transfinite Induktion (Hans Jürgen Ohlbach, Norbert Eisinger)....Pages 145-161 Exkurs: Mathematisches Arbeiten (Hans Jürgen Ohlbach, Norbert Eisinger)....Pages 163-168 Back Matter ....Pages 169-184