| Inhaltsverzeichnis?????????????????????????????????????????????????? | 5 |
| 1 Einleitung?????????????????????????????????????? | 11 |
| 1.1 Überblick???????????????????????????????????????? | 11 |
| 1.2 Methodische Schwerpunkte?????????????????????????????????????????????????????????????????????? | 12 |
| 1.3 Notation?????????????????????????????????????? | 13 |
| 1.4 Formalismus und Sicherheit?????????????????????????????????????????????????????????????????????????? | 14 |
| 1.5 Minimalismus?????????????????????????????????????????????? | 16 |
| 1.6 Danksagungen?????????????????????????????????????????????? | 16 |
| 2 Mengen?????????????????????????????? | 17 |
| 2.1 Mengen und Elemente???????????????????????????????????????????????????????????? | 17 |
| 2.1.1 Mengen, Elemente, Objekte???????????????????????????????????????????????????????????????????????????? | 17 |
| 2.1.2 Mengendefinition – Möglichkeiten und Fallstricke?????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????? | 18 |
| 2.2 Mengenrelationen und -operationen???????????????????????????????????????????????????????????????????????????????????????? | 22 |
| 2.3 Das Auswahlaxiom *?????????????????????????????????????????????????????????? | 27 |
| 2.4 Axiomatische Mengenlehre?????????????????????????????????????????????????????????????????????? | 28 |
| 2.4.1 Hauptrichtungen???????????????????????????????????????????????????????? | 28 |
| 2.4.2 ZFU als Beispiel einer Axiomatik *?????????????????????????????????????????????????????????????????????????????????????????????? | 29 |
| 2.4.3 Abseits der Axiomatik???????????????????????????????????????????????????????????????????? | 31 |
| 2.5 Übungsaufgaben?????????????????????????????????????????????????? | 31 |
| 3 Relationen und Funktionen???????????????????????????????????????????????????????????????????? | 35 |
| 3.1 Paare und Tupel???????????????????????????????????????????????????? | 35 |
| 3.2 Relationen?????????????????????????????????????????? | 36 |
| 3.3 Abbildungen (Funktionen)?????????????????????????????????????????????????????????????????????? | 39 |
| 3.4 Äquivalenzrelationen?????????????????????????????????????????????????????????????? | 43 |
| 3.5 Kongruenzrelationen???????????????????????????????????????????????????????????? | 45 |
| 3.6 Ordnungsrelationen?????????????????????????????????????????????????????????? | 46 |
| 3.6.1 Halb- und Totalordnungen?????????????????????????????????????????????????????????????????????????? | 46 |
| 3.6.2 Extremale und begrenzende Elemente?????????????????????????????????????????????????????????????????????????????????????????????? | 48 |
| 3.6.3 Ordnungen und das Auswahlaxiom *?????????????????????????????????????????????????????????????????????????????????????????? | 50 |
| 3.6.4 Verbände als spezielle Ordnungen *?????????????????????????????????????????????????????????????????????????????????????????????? | 51 |
| 3.7 Operationen auf Relationen?????????????????????????????????????????????????????????????????????????? | 52 |
| 3.8 Permutationen???????????????????????????????????????????????? | 54 |
| 3.9 Abbildungen von Relationen *?????????????????????????????????????????????????????????????????????????????? | 56 |
| 3.10 Induktion und Rekursion?????????????????????????????????????????????????????????????????????? | 57 |
| 3.10.1 Induktive Mengendefinitionen???????????????????????????????????????????????????????????????????????????????????? | 57 |
| 3.10.2 Induktionshistorie???????????????????????????????????????????????????????????????? | 60 |
| 3.10.3 Induktionsvarianten?????????????????????????????????????????????????????????????????? | 61 |
| 3.10.4 Induktionsbeweise?????????????????????????????????????????????????????????????? | 62 |
| 3.10.5 Rekursive Funktionsdefinitionen?????????????????????????????????????????????????????????????????????????????????????????? | 63 |
| 3.11 Hüllen und Erzeugendensysteme?????????????????????????????????????????????????????????????????????????????????? | 69 |
| 3.11.1 Transitive Hülle???????????????????????????????????????????????????????????? | 69 |
| 3.11.2 Andere Hüllen?????????????????????????????????????????????????????? | 70 |
| 3.12 Übungsaufgaben???????????????????????????????????????????????????? | 72 |
| 4 Logik???????????????????????????? | 77 |
| 4.1 Aussagenlogik???????????????????????????????????????????????? | 77 |
| 4.1.1 Die Syntax der Aussagenlogik?????????????????????????????????????????????????????????????????????????????????? | 77 |
| 4.1.2 Zwei wichtige Eigenschaften der Syntax der Aussagenlogik *?????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????? | 80 |
| 4.1.3 Die elementare Semantik der Aussagenlogik???????????????????????????????????????????????????????????????????????????????????????????????????????????? | 82 |
| 4.1.4 Semantische Begriffe rund ums Modell?????????????????????????????????????????????????????????????????????????????????????????????????? | 86 |
| 4.1.5 Substitution und Ersetzung?????????????????????????????????????????????????????????????????????????????? | 91 |
| 4.1.6 Assoziativitätsaspekte?????????????????????????????????????????????????????????????????????? | 95 |
| 4.1.7 Mehr über Junktoren *???????????????????????????????????????????????????????????????????? | 97 |
| 4.1.8 Reduzierbarkeit und Dualität *?????????????????????????????????????????????????????????????????????????????????????? | 100 |
| 4.1.9 Normalformen?????????????????????????????????????????????????? | 102 |
| 4.1.10 Beweisverfahren und Algorithmen?????????????????????????????????????????????????????????????????????????????????????????? | 106 |
| 4.2 Prädikatenlogik???????????????????????????????????????????????????? | 116 |
| 4.2.1 Die Syntax der Prädikatenlogik?????????????????????????????????????????????????????????????????????????????????????? | 117 |
| 4.2.2 Weitere syntaktische Begriffe???????????????????????????????????????????????????????????????????????????????????? | 118 |
| 4.2.3 Die elementare Semantik der Prädikatenlogik???????????????????????????????????????????????????????????????????????????????????????????????????????????????? | 120 |
| 4.2.4 Semantische Begriffe und Sätze der Prädikatenlogik?????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????? | 123 |
| 4.2.5 Substitution und Ersetzung in PL1???????????????????????????????????????????????????????????????????????????????????????????? | 125 |
| 4.2.6 Entscheidungsprobleme *???????????????????????????????????????????????????????????????????????? | 127 |
| 4.2.7 PL1-Beweisverfahren und -Algorithmen *?????????????????????????????????????????????????????????????????????????????????????????????????????? | 129 |
| 4.2.8 Prädikatenlogik mit Identität???????????????????????????????????????????????????????????????????????????????????? | 135 |
| 4.3 Übungsaufgaben?????????????????????????????????????????????????? | 137 |
| 5 Zahlen und Anzahlen???????????????????????????????????????????????????????? | 147 |
| 5.1 Zahlen?????????????????????????????????? | 148 |
| 5.1.1 Natürliche Zahlen und ihre Operationen?????????????????????????????????????????????????????????????????????????????????????????????????????? | 148 |
| 5.1.2 Ganze Zahlen?????????????????????????????????????????????????? | 152 |
| 5.1.3 Rationale Zahlen?????????????????????????????????????????????????????????? | 154 |
| 5.1.4 Reelle und komplexe Zahlen *?????????????????????????????????????????????????????????????????????????????????? | 157 |
| 5.2 Anzahlen?????????????????????????????????????? | 163 |
| 5.2.1 Mächtigkeit und endliche Anzahlen???????????????????????????????????????????????????????????????????????????????????????????? | 163 |
| 5.2.2 Abzählende Kombinatorik???????????????????????????????????????????????????????????????????????? | 166 |
| 5.2.3 Unendliche Anzahlen???????????????????????????????????????????????????????????????? | 174 |
| 5.3 Elementare Zahlentheorie *?????????????????????????????????????????????????????????????????????????? | 184 |
| 5.3.1 Teiler und Restklassenarithmetik?????????????????????????????????????????????????????????????????????????????????????????? | 184 |
| 5.3.2 Primzahlen, ggT und Restklassengleichungen?????????????????????????????????????????????????????????????????????????????????????????????????????????????? | 186 |
| 5.4 Übungsaufgaben?????????????????????????????????????????????????? | 194 |
| 6 Graphen???????????????????????????????? | 201 |
| 6.1 Einführende Beispiele???????????????????????????????????????????????????????????????? | 202 |
| 6.2 Definition, Grundbegriffe???????????????????????????????????????????????????????????????????????? | 204 |
| 6.3 Darstellungsfragen?????????????????????????????????????????????????????????? | 206 |
| 6.3.1 Zeichnerische Darstellung in der Ebene?????????????????????????????????????????????????????????????????????????????????????????????????????? | 206 |
| 6.3.2 Andere Darstellungen von Graphen?????????????????????????????????????????????????????????????????????????????????????????? | 208 |
| 6.4 Isomorphie?????????????????????????????????????????? | 209 |
| 6.5 Nachbarschaft, Wege???????????????????????????????????????????????????????????? | 210 |
| 6.5.1 … in ungerichteten Graphen?????????????????????????????????????????????????????????????????????????????? | 211 |
| 6.5.2 … in gerichteten Graphen?????????????????????????????????????????????????????????????????????????? | 211 |
| 6.5.3 … und in beiden???????????????????????????????????????????????????????? | 212 |
| 6.5.4 Zwei Hilfssätze für die theoretische Informatik???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????? | 212 |
| 6.5.5 Weglängen???????????????????????????????????????????? | 214 |
| 6.5.6 Zusammenhang?????????????????????????????????????????????????? | 216 |
| 6.5.7 Spezielle Wege?????????????????????????????????????????????????????? | 217 |
| 6.6 Bäume???????????????????????????????? | 219 |
| 6.6.1 Bäume – ein Thema mit Variationen???????????????????????????????????????????????????????????????????????????????????????????? | 219 |
| 6.6.2 Gerichtete ungeordnete Bäume?????????????????????????????????????????????????????????????????????????????????? | 221 |
| 6.6.3 Ungerichtete ungeordnete Bäume?????????????????????????????????????????????????????????????????????????????????????? | 222 |
| 6.6.4 Parallelen zwischen gerichteten und ungerichteten Bäumen?????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????? | 224 |
| 6.6.5 Geordnete Bäume???????????????????????????????????????????????????????? | 225 |
| 6.6.6 Spannbäume?????????????????????????????????????????????? | 226 |
| 6.6.7 Baumbezogene Graphenalgorithmen???????????????????????????????????????????????????????????????????????????????????????? | 227 |
| 6.6.8 Unendliche Bäume?????????????????????????????????????????????????????????? | 229 |
| 6.7 Beschriftete Graphen?????????????????????????????????????????????????????????????? | 230 |
| 6.7.1 Endliche Automaten?????????????????????????????????????????????????????????????? | 230 |
| 6.7.2 Termsyntax?????????????????????????????????????????????? | 232 |
| 6.7.3 Färbungen???????????????????????????????????????????? | 232 |
| 6.8 Einfache Algorithmen für endliche Graphen???????????????????????????????????????????????????????????????????????????????????????????????????????? | 233 |
| 6.8.1 Graphendurchläufe, Zusammenhang, Spannbäume???????????????????????????????????????????????????????????????????????????????????????????????????????????????? | 233 |
| 6.8.2 Besondere Wege: kürzeste, längste, Euler’sche und Hamilton’sche???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????? | 235 |
| 6.9 Übungsaufgaben?????????????????????????????????????????????????? | 238 |
| 7 Algebra???????????????????????????????? | 243 |
| 7.1 Gruppen???????????????????????????????????? | 243 |
| 7.1.1 Definition, Beispiele, Grundeigenschaften???????????????????????????????????????????????????????????????????????????????????????????????????????????? | 243 |
| 7.1.2 Gruppenhomomorphismen???????????????????????????????????????????????????????????????????? | 247 |
| 7.1.3 Untergruppen?????????????????????????????????????????????????? | 248 |
| 7.2 Ringe und Körper?????????????????????????????????????????????????????? | 253 |
| 7.2.1 Ringe???????????????????????????????????? | 253 |
| 7.2.2 Körper?????????????????????????????????????? | 258 |
| 7.3 Verbände *?????????????????????????????????????????? | 260 |
| 7.4 Vektorräume???????????????????????????????????????????? | 263 |
| 7.4.1 Definition und Beispiele?????????????????????????????????????????????????????????????????????????? | 263 |
| 7.4.2 Lineare Abhängigkeit, Basis und Dimension???????????????????????????????????????????????????????????????????????????????????????????????????????????? | 264 |
| 7.4.3 Untervektorräume?????????????????????????????????????????????????????????? | 270 |
| 7.4.4 Lineare Abbildungen und Matrizen?????????????????????????????????????????????????????????????????????????????????????????? | 272 |
| 7.4.5 Lineare Gleichungssysteme???????????????????????????????????????????????????????????????????????????? | 279 |
| 7.4.6 Räume linearer Abbildungen?????????????????????????????????????????????????????????????????????????????? | 283 |
| 7.4.7 Basistransformationen???????????????????????????????????????????????????????????????????? | 288 |
| 7.4.8 Determinanten???????????????????????????????????????????????????? | 290 |
| 7.4.9 Eigenwerte und Eigenvektoren?????????????????????????????????????????????????????????????????????????????????? | 296 |
| 7.5 Quotienten *?????????????????????????????????????????????? | 299 |
| 7.5.1 Normalteiler und Faktorgruppen?????????????????????????????????????????????????????????????????????????????????????? | 299 |
| 7.5.2 Ideale und Restklassenringe???????????????????????????????????????????????????????????????????????????????? | 302 |
| 7.5.3 Quotientenräume von Vektorräumen?????????????????????????????????????????????????????????????????????????????????????????? | 303 |
| 7.5.4 Isomorphiesätze bezüglich Produkten und Quotienten?????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????? | 304 |
| 7.6 Allgemeine Algebra *?????????????????????????????????????????????????????????????? | 305 |
| 7.6.1 Zwei Beispiele?????????????????????????????????????????????????????? | 305 |
| 7.6.2 Signaturen, Terme und Spezifikationen???????????????????????????????????????????????????????????????????????????????????????????????????? | 306 |
| 7.6.3 Algebren und Modelle?????????????????????????????????????????????????????????????????? | 307 |
| 7.6.4 Initiale Semantik???????????????????????????????????????????????????????????? | 308 |
| 7.7 Übungsaufgaben?????????????????????????????????????????????????? | 311 |
| 8 Diskrete Wahrscheinlichkeitstheorie???????????????????????????????????????????????????????????????????????????????????????? | 323 |
| 8.1 Markante Beispiele?????????????????????????????????????????????????????????? | 323 |
| 8.1.1 Die Verdoppelungsstrategie?????????????????????????????????????????????????????????????????????????????? | 323 |
| 8.1.2 Das Aufteilungsproblem?????????????????????????????????????????????????????????????????????? | 324 |
| 8.1.3 Das False-Positive-Problem?????????????????????????????????????????????????????????????????????????????? | 324 |
| 8.1.4 Das Geburtstagsphänomen???????????????????????????????????????????????????????????????????????? | 325 |
| 8.1.5 Das Ziegenproblem???????????????????????????????????????????????????????????? | 325 |
| 8.1.6 Serien beim Glücksspiel – der Spielerfehlschluss?????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????? | 326 |
| 8.2 Wahrscheinlichkeit und Wahrscheinlichkeitsmodelle???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????? | 326 |
| 8.2.1 Zufallsergebnisse???????????????????????????????????????????????????????????? | 326 |
| 8.2.2 Wahrscheinlichkeit und Ereignisse???????????????????????????????????????????????????????????????????????????????????????????? | 327 |
| 8.2.3 Wahrscheinlichkeitsräume?????????????????????????????????????????????????????????????????????????? | 328 |
| 8.2.4 Reiner Zufall???????????????????????????????????????????????????? | 332 |
| 8.3 Abgeleitete Begriffe?????????????????????????????????????????????????????????????? | 333 |
| 8.3.1 Unabhängigkeit und bedingte Wahrscheinlichkeit?????????????????????????????????????????????????????????????????????????????????????????????????????????????????????? | 333 |
| 8.3.2 Mehrstufige Zufallsexperimente?????????????????????????????????????????????????????????????????????????????????????? | 335 |
| 8.3.3 Zufallsvariablen, Verteilungsfunktionen, Erwartungswerte?????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????? | 339 |
| 8.3.4 Erwartungswerte als Entscheidungsgrundlage?????????????????????????????????????????????????????????????????????????????????????????????????????????????? | 342 |
| 8.3.5 Streuungsmaße???????????????????????????????????????????????????? | 343 |
| 8.4 Anwendungsbeispiele???????????????????????????????????????????????????????????? | 347 |
| 8.4.1 Wahrscheinlichkeitstheoretische Begriffe und Ergebnisse an einem Demonstrationsbeispiel???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????? | 347 |
| 8.4.2 Ernüchterung bei der Verdopplungsstrategie?????????????????????????????????????????????????????????????????????????????????????????????????????????????? | 349 |
| 8.4.3 Gerechtigkeit beim Aufteilungsproblem???????????????????????????????????????????????????????????????????????????????????????????????????? | 350 |
| 8.4.4 Erleichterung beim False Positive???????????????????????????????????????????????????????????????????????????????????????????? | 351 |
| 8.5 Prozesse?????????????????????????????????????? | 352 |
| 8.5.1 Definition und Beispiele?????????????????????????????????????????????????????????????????????????? | 352 |
| 8.5.2 Spezielle Bernoulli-Prozesse?????????????????????????????????????????????????????????????????????????????????? | 352 |
| 8.5.3 Die hypergeometrische Verteilung?????????????????????????????????????????????????????????????????????????????????????????? | 356 |
| 8.5.4 Markow-Ketten *???????????????????????????????????????????????????????? | 358 |
| 8.5.5 Zufallsbewegungen *???????????????????????????????????????????????????????????????? | 362 |
| 8.6 Übungsaufgaben?????????????????????????????????????????????????? | 364 |
| Literatur???????????????????????????????? | 371 |
| Stichwortverzeichnis?????????????????????????????????????????????????????? | 377 |
