Kompendium der diskreten Mathematik (eBook)

Bernd Baumgarten (Autor)

eBook Download: PDF | EPUB

2014
388 Seiten
De Gruyter (Verlag)
978-3-486-78132-8 (ISBN)

Infos

Das Kompendium präsentiert die für ein Mathematik- oder Informatikstudium benötigten Grundlagen der diskreten Mathematik in kompakter Form. Alle wichtigen Themen wie Mengen, Relationen und Funktionen, Logik, Graphen, abstrakte und lineare Algebra sowie diskrete Wahrscheinlichkeitstheorie werden abgedeckt. Damit erweist sich das Buch als nützlicher Begleiter für viele Vorlesungen im Studium.


Bernd Baumgarten, Hochschule Darmstadt.

Inhalt

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

Produkt-Details

• Erscheint lt. Verlag: 15.10.2014
• Reihe/Serie: De Gruyter Studium
• Zusatzinfo: 127 b/w ill., 27 b/w tbl.
• Sprache: deutsch
• Themenwelt: Mathematik / Informatik ► Mathematik ► Graphentheorie
• Themenwelt: Technik
• Schlagworte: Discrete Mathematics • discrete probability theory • Diskrete Mathematik • Diskrete Wahrscheinlichkeitstheorie • Nachschlagewerk • reference work
• ISBN-10: 3-486-78132-4 / 3486781324
• ISBN-13: 978-3-486-78132-8 / 9783486781328