Hasso-Plattner-Institut
  
    • de
 

Inhaltsverzeichnis

Mathematisches Denken und Beweisen
Eine Einführung

Inhalt

 

Teil I: Grundlagen

1 Aussagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

1.1 Definition und Beispiele

1.2 Verknüpfungen von Aussagen

1.3 Tautologie und Kontradiktion

1.4 Aussageformen

1.5 Aussagen mit Quantoren

2 Mengen und Mengenoperationen . . . . . . . . . . . . . . . . . . . . 36

2.1 Mengen

2.2 Gleichheit von Mengen

2.3 Komplementäre Mengen

2.4 Die leere Menge

2.5 Teilmenge und Obermenge

2.6 Potenzmenge und Mengenfamilien

2.7 Vereinigung, Durchschnitt und Differenz von Mengen

2.8 Produkt von Mengen

2.9 Weitere Rechenregeln für Mengenoperationen

3 Mathematisches Beweisen . . . . . . . . . . . . . . . . . . . . . . 58

4 Relationen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

4.1 Definition und erste Beispiele

4.2 Operationen auf Relationen

4.3 Wichtige Eigenschaften von Relationen

4.4 Äquivalenzrelationen und Klasseneinteilung

4.5 Rechnen mit Äquivalenzrelationen

4.6 Halbordnungsrelationen

5 Abbildungen und Funktionen . . . . . . . . . . . . . . . . . . . . . 89

5.1 Definition und erste Beispiele

5.2 Surjektive, injektive und bijektive Abbildungen

5.3 Folgen und Mengenfamilien

5.4 Kardinalität von Mengen

Quellen und weiterführende Literatur

 

Teil II: Techniken

6 Grundlegende Beweisstrategien . . . . . . . . . . . . . . . . . . . 111

6.1 Direkter Beweis

6.2 Beweis durch Kontraposition

6.3 Widerspruchs-Beweis

6.4 Äquivalenzbeweis

6.5 Beweis durch Fallunterscheidung

6.6 Beweis atomarer Aussagen

6.7 Beweis von Aussagen mit Quantoren

6.8 Kombinatorischer Beweis

7 Vollständige Induktion . . . . . . . . . . . . . . . . . . . . . . 127

7.1 Idee der vollständigen Induktion

7.2 Beispiele für Induktionsbeweise

7.3 Struktur von Induktionsbeweisen

7.4 Verallgemeinerte vollständige Induktion

7.5 Induktive Definitionen

8 Zählen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143

8.1 Grundlegende Zählprinzipien

8.2 Kombinationen, Permutationen und Binomialkoeffizienten

8.3 Rechnen mit Binomialkoeffizienten

 

9 Diskrete Stochastik . . . . . . . . . . . . . . . . . . . . . . . . 164

9.1 Zufallsexperimente und Wahrscheinlichkeiten

9.2 Bedingte Wahrscheinlichkeit

9.3 Zufallsvariablen

9.4 Binomial-Verteilung und geometrische Verteilung

Quellen und weiterführende Literatur

 

Teil III: Strukturen

10 Boole'sche Algebra . . . . . . . . . . . . . . . . . . . . . . . . 189

10.1 Schaltfunktionen und Ausdrücke

10.2 Definition der Boole'schen Algebra

10.3 Beispiele Boole'scher Algebren

10.4 Eigenschaften Boole'scher Algebren

10.5 Halbordnungen in einer Boole'schen Algebra

10.6 Atome

10.7 Normalformen für Boole'sche Ausdrücke

10.8 Minimierung Boole'scher Ausdrücke

10.9 Der Isomorphie-Satz

10.10 Schaltkreis-Algebra

11 Graphen und Bäume . . . . . . . . . . . . . . . . . . . . . . . . 231

11.1 Grundbegriffe

11.2 Wege und Kreise in Graphen

11.3 Graphen und Matrizen

11.4 Isomorphismen auf Graphen

11.5 Bäume

12 Aussagenlogik . . . . . . . . . . . . . . . . . . . . . . . . . . 262

12.1 Boole'sche Algebra und Aussagenlogik

12.2 Normalformen

12.3 Erfüllbarkeitsäquivalente Formeln

12.4 Unerfüllbare Klauselmengen

12.5 Erfüllbarkeit von Hornklauseln

12.6 Resolution

12.7 Klauselmengen in 2KNF

Quellen und weiterführende Literatur

Index