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