Titel |
2 |
Vorwort | 4 |
Inhaltsverzeichnis | 5 |
1 Mathematische Notationen und Grundbegriffe | 7 |
1.1 Definition-Satz-Beweis, mathematische Terminologie | 8 |
1.2 Mengen | 10 |
1.3 Mengensysteme, Potenzmenge | 14 |
1.4 Folgen | 15 |
1.5 Kartesisches Produkt | 19 |
1.6 Summen und Produkte | 20 |
1.7 Matrizen und Skalarprodukt | 22 |
1.8 Algebraische Strukturen, axiomatische Definitionen | 25 |
1.9 Induktive Definitionen | 29 |
1.10 Relationen | 31 |
1.11 Funktionen | 35 |
1.12 Strukturerhaltende Abbildungen | 40 |
1.13 Abzählbar, überabzählbar | 41 |
1.14 Wahrscheinlichkeit | 43 |
1.15 Logische Operationen | 51 |
1.16 Quantoren | 55 |
1.17 Normalformen | 59 |
1.18 Fast alle, unendlich viele, O-Notation | 60 |
1.19 Gleichmäßig, nicht-gleichmäßig | 61 |
2 Über den Umgang mit mathematischen |
63 |
2.1 Infix, Präfix, Postfix | 63 |
2.2 Funktionswert vs. Funktion, .-Notation | 65 |
2.3 Syntax und Semantik, Metasprache und Objektsprache | 67 |
2.4 Paradoxien, Gödel und Russell | 69 |
3 Grundlegende Beweistechniken | 73 |
3.1 Axiome, Kalküle, Beweise | 74 |
3.2 Direkter Beweis, "Definition Chasing" | 75 |
3.3 Fallunterscheidungen | 77 |
3.4 Implikation, Äquivalenz, Ringschluss | 78 |
3.5 Indirekter Beweis, Beweis durchWiderspruch | 80 |
3.6 "Es genügt zu zeigen", Verschärfung und |
86 |
3.7 "Ohne Beschränkung der Allgemeinheit" | 87 |
3.8 Existenz und Eindeutigkeit | 88 |
3.9 Effizient und effektiv | 89 |
3.10 Induktion | 90 |
3.11 Strukturelle Induktion | 95 |
3.12 Induktion als Konstruktionsprinzip | 96 |
3.13 Beweistechnischer Umgang mit Quantoren, Skolem-Funktionen | 99 |
4 Fortgeschrittene Beweistechniken | 103 |
4.1 Korrektheitsbeweise von Algorithmen, Schleifeninvariante | 103 |
4.2 Terminationsbeweise | 106 |
4.3 Schubfachprinzip und Anzahlargumente | 112 |
4.4 Inklusion - Exklusion | 114 |
4.5 Doppeltes Zählen | 116 |
4.6 Diagonalisierung | 118 |
4.7 Beweis durch Lineare Algebra | 120 |
4.8 Beweismethode "Polynomifizierung" | 121 |
4.9 Informationstheoretische Argumente | 124 |
4.10 Erzeugende Funktionen, Funktionaltransformationen | 127 |
4.11 Indikator-Zufallsvariablen | 133 |
4.12 Probabilistische Existenzbeweise | 136 |
4.13 NP-Vollständigkeitsbeweise und Unentscheidbarkeitsbeweise mittels Reduktion | 140 |
Symbolverzeichnis | 145 |
Griechische, hebräische und altdeutsche Buchstaben | 146 |
Literatur | 147 |
Index | 152 |