Kompendium der diskreten Mathematik (eBook)

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