Mathe I - fsi.uni- .Inhaltsverzeichnis 1 Logik 10 1.1 Aussagenlogik . . . . . . . . . . . . . .

  • View
    216

  • Download
    0

Embed Size (px)

Text of Mathe I - fsi.uni- .Inhaltsverzeichnis 1 Logik 10 1.1 Aussagenlogik . . . . . . . . . . . . . .

  • Mathe I

    Jan-Peter Hohloch

    WS 11/12

  • Inhaltsverzeichnis

    1 Logik 10 1.1 Aussagenlogik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2 Die wichtigsten Junktoren . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

    1.2.1 Negation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2.2 Konjunktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2.3 Disjunktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2.4 Exklusives Oder . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2.5 Implikation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2.6 Äquivalenz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

    1.3 Bemerkungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3.1 Sätze ber Implikationen . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3.2 Sätze ber Äquivalenzen . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3.3 Größe von Wahrheitstabellen . . . . . . . . . . . . . . . . . . . . . 12 1.3.4 Einfacherer Lösungsweg . . . . . . . . . . . . . . . . . . . . . . . . 13

    1.4 Logische Äquivalenz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.5 Tautologie und Kontradiktion . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.6 Wichtige log. Äquivalenzen . . . . . . . . . . . . . . . . . . . . . . . . . . 13

    1.6.1 Kommutativität . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.6.2 Doppelte Negation . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.6.3 De’Morgansche Regeln . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.6.4 Implikation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.6.5 Äquivalenz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.6.6 Assoziativität . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.6.7 Distributivität . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.6.8 Tautologie und Kontradiktion . . . . . . . . . . . . . . . . . . . . . 14

    1.7 Bemerkungen zu den logischen Äquivalenzen . . . . . . . . . . . . . . . . 14 1.8 Quantoren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

    1.8.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.8.2 Bemerkungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.8.3 Negation von Quantoren . . . . . . . . . . . . . . . . . . . . . . . . 15 1.8.4 Reihenfolge von Quantoren . . . . . . . . . . . . . . . . . . . . . . 16

    2 Mengen 17 2.1 Mengen allgemein . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

    2.1.1 Cantor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.1.2 Wie spezifiziert man eine Menge? . . . . . . . . . . . . . . . . . . . 17

    2

  • 2.1.3 Problematik in Cantors Definition . . . . . . . . . . . . . . . . . . 17 2.1.4 Leere Menge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.1.5 Kardinalität . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

    2.2 Def. Teilmenge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.2.1 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.2.2 Wichtiger Unterschied . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.2.3 Bemerkung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.2.4 Gleichheit von Mengen . . . . . . . . . . . . . . . . . . . . . . . . . 18

    2.3 Operationen auf Mengen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.3.1 Schnittmenge/Schnitt . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.3.2 Vereinigung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.3.3 Differenz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.3.4 Symmetrische Differenz . . . . . . . . . . . . . . . . . . . . . . . . 19

    2.4 Venn-Diagramme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.5 Satz über Mengenoperationen . . . . . . . . . . . . . . . . . . . . . . . . . 19

    2.5.1 Symmetrische Differenz . . . . . . . . . . . . . . . . . . . . . . . . 19 2.5.2 De’Morgansche Regel . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.5.3 Teilmengenbeziehungen . . . . . . . . . . . . . . . . . . . . . . . . 20 2.5.4 Distributivität . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

    2.6 Def.: Beliebige Vereinigungen und Schnitte . . . . . . . . . . . . . . . . . . 20 2.7 geordnete n-Tupel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

    2.7.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.7.2 Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

    2.8 Kartesisches Produkt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.8.1 Schreibweise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.8.2 Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

    3 Abbildungen 22 3.1 Def.: Abbildung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

    3.1.1 Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.1.2 Schreibweisen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

    3.2 Gleichheit von Abbildungen . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.3 Surjektiv, injektiv, bijektiv . . . . . . . . . . . . . . . . . . . . . . . . . . 24

    3.3.1 Surjektivität . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.3.2 Injektivität . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.3.3 Bijektivität . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.3.4 Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

    3.4 Endlichkeit von Mengen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.4.1 Abzählbar unendliche Mengen . . . . . . . . . . . . . . . . . . . . 25 3.4.2 Satz über endliche Mengen . . . . . . . . . . . . . . . . . . . . . . 26

    3.5 Hintereinanderausführung . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.5.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.5.2 Assoziativität . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.5.3 Beweis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

    3

  • 3.5.4 Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.5.5 Besondere Abbildungen . . . . . . . . . . . . . . . . . . . . . . . . 28

    3.6 Umkehrabbildung bijektiver Abb. . . . . . . . . . . . . . . . . . . . . . . . 28 3.6.1 Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.6.2 Beweis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

    4 Relationen 30 4.1 Def. Relation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

    4.1.1 Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 4.1.2 Anmerkung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

    4.2 Ordnungsrelationen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.2.1 Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

    4.3 Äquivalezrelation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.3.1 Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

    4.4 Def.: Äquivalenzklassen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.4.1 Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

    4.5 Gleichheit von Äquivalenzklassen . . . . . . . . . . . . . . . . . . . . . . . 33 4.5.1 Beweis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

    4.6 Zerlegung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4.6.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4.6.2 Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4.6.3 Satz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

    4.7 Repräsentantensystem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.7.1 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

    5 Natürliche Zahlen und Induktion 36 5.1 Vollständige Induktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

    5.1.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 5.1.2 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 5.1.3 Bemerkung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

    5.2 Verschärftes Induktionsprinzip . . . . . . . . . . . . . . . . . . . . . . . . 37 5.2.1 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

    5.3 Prinzip der rekursiven Definition . . . . . . . . . . . . . . . . . . . . . . . 38 5.3.1 informelle Definition . . . . . . . . . . . . . . . . . . . . . . . . . . 38 5.3.2 Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 5.3.3 Rekursive Definition mit mehreren Startwerten . . . . . . . . . . . 39

    5.4 Rechenregeln für Produkte und Summen . . . . . . . . . . . . . . . . . . . 40 5.4.1 Änderung der Summensequenzen . . . . . . . . . . . . . . . . . . . 40 5.4.2 Doppelsummen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 5.4.3 Koeffizienten vor Summen . . . . . . . . . . . . . . . . . . . . . . . 41

    5.5 Wohlordnungsprinzip . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 5