Mathematische Grundlagen der Informatik: Mathematisches Denken und Beweisen

Buchcover......Page 1
Mathematische Grundlagen der Informatik: Mathematisches Denken
und Beweisen - Eine Einführung, 3. Auflage......Page 4
ISBN: 978-3-8351-0049-7......Page 5
Vorwort......Page 6
Inhaltsverzeichnis......Page 8
Einleitung......Page 12
Teil I - Grundlagen......Page 18
1.1 Definition und Beispiele......Page 20
1.2 Verknüpfungen von Aussagen......Page 22
1.3 Tautologie und Kontradiktion......Page 28
1.4 Aussageformen......Page 32
1.5 Aussagen mit Quantoren......Page 33
2.1 Mengen......Page 37
2.2 Gleichheit von Mengen......Page 40
2.3 Komplementäre Mengen......Page 42
2.4 Die leere Menge......Page 43
2.5 Teilmenge und Obermenge......Page 44
2.6 Potenzmenge und Mengenfamilien......Page 46
2.7 Vereinigung, Durchschnitt und Differenz von Mengen......Page 48
2.8 Produkt von Mengen......Page 53
2.9 Weitere Rechenregeln für Mengenoperationen......Page 56
3 Mathematisches Beweisen......Page 59
4.1 Definition und erste Beispiele......Page 64
4.2 Operationen auf Relationen......Page 68
4.3 Wichtige Eigenschaften von Relationen......Page 72
4.4 Äquivalenzrelationen und Klasseneinteilung......Page 75
4.5 Rechnen mit Äquivalenzrelationen......Page 81
4.6 Halbordnungsrelationen......Page 84
5.1 Definition und erste Beispiele......Page 90
5.2 Surjektive, injektive und bijektive Abbildungen......Page 95
5.3 Folgen und Mengenfamilien......Page 101
5.4 Kardinalität von Mengen......Page 104
Quellen und weiterführende Literatur......Page 109
Teil II - Techniken......Page 110
6 Grundlegende Beweisstrategien......Page 112
6.1 Direkter Beweis......Page 113
6.2 Beweis durch Kontraposition......Page 115
6.3 Widerspruchs-Beweis......Page 116
6.4 Äquivalenzbeweis......Page 117
6.5 Beweis atomarer Aussagen......Page 118
6.6 Beweis durch Fallunterscheidung......Page 120
6.7 Beweis von Aussagen mit Quantoren......Page 122
6.8 Kombinatorischer Beweis......Page 125
7 Vollständige Induktion......Page 129
7.1 Idee der vollständigen Induktion......Page 130
7.2 Beispiele fÜr Induktionsbeweise......Page 131
7.3 Struktur von Induktionsbeweisen......Page 134
7.4 Verallgemeinerte vollständige Induktion......Page 136
7.5 Induktive Definitionen......Page 137
8.1 Grundlegende Zählprinzipien......Page 148
8.2 Permutationen und Binomialkoeffizienten......Page 153
8.3 Rechnen mit Binomialkoeffizienten......Page 158
9.1 Zufallsexperimente und Wahrscheinlichkeiten......Page 167
9.2 Bedingte Wahrscheinlichkeit......Page 175
9.3 Zufallsvariablen......Page 177
9.4 Binomial-Verteilung und geometrische Verteilung......Page 183
Quellen und weiterführende Literatur......Page 188
Teil III - Strukturen......Page 190
10.1 Schaltfunktionen und Ausdrücke......Page 192
10.2 Definition der Boole’schen Algebra......Page 198
10.3 Beispiele Boole’scher Algebren......Page 201
10.4 Eigenschaften Boole’scher Algebren......Page 207
10.5 Halbordnungen in einer Boole’schen Algebra......Page 211
10.6 Atome......Page 214
10.7 Normalformen für Boole’sche Ausdrücke......Page 217
10.8 Minimierung Boole’scher Ausdrücke......Page 220
10.9 Der Isomorphie-Satz......Page 222
10.10 Schaltkreis-Algebra......Page 226
11 Graphen und Bäume......Page 234
11.1 Grundbegriffe......Page 235
11.2 Wege und Kreise in Graphen......Page 242
11.3 Graphen und Matrizen......Page 248
11.4 Isomorphismen auf Graphen......Page 255
11.5 Bäume......Page 259
12.1 Boole’sche Algebra und Aussagenlogik......Page 265
12.2 Normalformen......Page 270
12.3 Erfüllbarkeitsäquivalente Formeln......Page 272
12.4 Unerfüllbare Klauselmengen......Page 277
12.5 Erfüllbarkeit von Hornklauseln......Page 281
12.6 Resolution......Page 284
12.7 Klauselmengen in 2KNF......Page 292
13 Modulare Arithmetik......Page 296
13.1 Die Teilbarkeitsrelation......Page 297
13.2 Modulare Addition und Multiplikation......Page 301
13.3 Modulares Rechnen......Page 305
13.4 Der größte gemeinsame Teiler und der Algorithmus von Euklid......Page 309
13.5 Der kleine Satz von Fermat......Page 313
13.6 Verschlüsselung mit dem kleinen Satz von Fermat......Page 317
13.7 Das RSA-Verfahren......Page 323
Quellen und weiterführende Literatur......Page 325
Index......Page 328