Christoph Meinel, Martin Mundhenk

Mathematisches Denken und Beweisen
Eine Einführung

Teubner Verlag, 2009

Inhalt

Teil I: Grundlagen

1 Aussagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .19
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 atomarer Aussagen
6.6 Beweis durch Fallunterscheidung
6.7 Beweis von Aussagen mit Quantoren
6.8 Kombinatorischer Beweis

7 Vollständige Induktion . . . . . . . . . . . . . . . . . . . . . . . . . .  128
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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
8.1 Grundlegende Zählprinzipien
8.2 Permutationen und Binomialkoeffizienten
8.3 Rechnen mit Binomialkoeffizienten

9 Diskrete Stochastik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
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 . . . . . . . . .  . . . . . . . . . . . . . . . . . . . 193
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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
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  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266
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

13 Modulare Arithmetik  . . . . . . . . . . . .  . . . . . . . . . . . . . . . 297
13.1 Die Teilbarkeitsrelation
13.2 Modulare Addition und Multiplikation
13.3 Modulares Rechnen
13.4 Der größte gemeinsame Teiler und der Algorithmus von Euklid
13.5 Der kleine Satz von Fermat
13.6 Verschlüsselung mit dem kleinen Satz von Fermat
13.7 Das RSA-Verfahren
Quellen und weiterführende Literatur Index