Mathematische Grundlagen der Informatik: Mathematisches Denken und Beweisen, 5. Auflage

Cover......Page 1
Mathematische
Grundlagen
der Informatik,
5. Auflage......Page 4
ISBN 9783834815200......Page 5
Vorwort......Page 6
Vorwort zur f¨unften Auflage......Page 7
Inhaltsverzeichnis......Page 8
Einleitung......Page 12
Teil I: Grundlagen......Page 18
1.1 Definition und Beispiele......Page 20
1.2 Verkn¨upfungen 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¨are 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 Di.erenz von Mengen......Page 48
2.8 Produkt von Mengen......Page 53
2.9 Weitere Rechenregeln fur¨ Mengenoperationen......Page 57
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 A¨quivalenzrelationen und Klasseneinteilung......Page 75
4.5 Rechnen mit A¨quivalenzrelationen......Page 81
4.6 Halbordnungsrelationen......Page 85
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 Kardinalita¨t von Mengen......Page 104
Quellen und weiterf¨uhrende 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 A¨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¨andigen Induktion......Page 130
7.2 Beispiele fur¨ Induktionsbeweise......Page 131
7.3 Struktur von Induktionsbeweisen......Page 134
7.4 Verallgemeinerte vollst¨andige Induktion......Page 136
7.5 Induktive De.nitionen......Page 137
8.1 Grundlegende Za¨hlprinzipien......Page 148
8.2 Permutationen und Binomialkoe.zienten......Page 153
8.3 Rechnen mit Binomialkoe.zienten......Page 158
9.1 Zufallsexperimente und Wahrscheinlichkeiten......Page 168
9.2 Bedingte Wahrscheinlichkeit......Page 176
9.3 Zufallsvariablen......Page 178
9.4 Binomial-Verteilung und geometrische Verteilung......Page 184
Binomial-Verteilung......Page 185
Geometrische Verteilung......Page 187
Quellen und weiterf¨uhrende Literatur......Page 189
Teil III: Strukturen......Page 192
10.1 Schaltfunktionen und Ausdru¨cke......Page 194
10.2 Definition der Boole’schen Algebra......Page 200
10.3 Beispiele Boole’scher Algebren......Page 203
10.4 Eigenschaften Boole’scher Algebren......Page 209
10.5 Halbordnungen in einer Boole’schen Algebra......Page 213
10.6 Atome......Page 216
10.7 Normalformen fur¨ Boole’sche Ausdruc¨ ke......Page 219
10.8 Minimierung Boole’scher Ausdru¨cke......Page 222
10.9 Der Isomorphie-Satz......Page 224
10.10 Schaltkreis-Algebra......Page 229
11 Graphen und Ba¨ume......Page 237
11.1 Grundbegriffe......Page 238
11.2 Wege und Kreise in Graphen......Page 245
11.3 Graphen und Matrizen......Page 251
11.4 Isomorphismen auf Graphen......Page 258
11.5 Ba¨ume......Page 262
12.1 Boole’sche Algebra und Aussagenlogik......Page 268
12.2 Normalformen......Page 273
12.3 Erf¨ullbarkeits¨aquivalente Formeln......Page 276
12.4 Unerf¨ullbare Klauselmengen......Page 280
12.5 Erf¨ullbarkeit von Hornklauseln......Page 285
12.6 Resolution......Page 287
12.7 Klauselmengen in 2KNF......Page 295
13 Modulare Arithmetik......Page 299
13.1 Die Teilbarkeitsrelation......Page 300
13.2 Modulare Addition und Multiplikation......Page 304
13.3 Modulares Rechnen......Page 308
13.4 Der gr¨oßte gemeinsame Teiler undder Algorithmus von Euklid......Page 312
13.5 Der kleine Satz von Fermat......Page 316
13.6 Verschl¨usselung mit dem kleinen Satz von Fermat......Page 320
13.7 Das RSA-Verfahren......Page 326
Quellen und weiterf¨uhrende Literatur......Page 328
Index......Page 330