Mathematik für Informatiker I - Logik und Diskrete Mathematik

Dozent: Prof. Dr. Günter Rote

Inhalt

  • Aussagenlogik und mathematische Beweistechniken
  • Mengenlehre: Mengen, Relationen, Äquivalenz- und Ordnungsrelationen, Funktionen, Natürliche Zahlen und vollständige Induktion, Abzählbarkeit
  • Kombinatorik: Abzählprinzipien, Binomialkoeffizienten und Stirling-Zahlen, Rekursion, Schubfachprinzip
  • Graphentheorie: Graphen und ihre Darstellungen, Wege und Kreise in Graphen, Bäume
  • Boolesche Formeln und Boolesche Funktionen, DNF und KNF, Erfüllbarkeit, Resolutionskalkül
  • Prädikatenlogik und mathematische Strukturen

Vorlesung

Folgende Themen wurden in der Vorlesung behandelt:

  1. Aussagenlogik
    • Dienstag, 16. Oktober 2007:
      • Aussagen, Boole'sche Formeln, Junktoren
    • Donnerstag, 18. Oktober 2007:
      • Syntax und Semantik der Aussagenlogik
      • Vorrangregeln, Weglassen von Klammern
      • Baumstruktur Boole'scher Formeln
      • Wahrheitsbelegung, Wahrheitstafel
      • semantische Äquivalenz
      • Erfüllbarkeit, Tautologie, Kontradiktion
      • logische Gesetze, Umformungen
      • Das Leibniz'sche Ersetzungsprinzip
    • Dienstag, 23. Oktober 2007:
      • semantische Äquivalenz und Äquivalenzjunktor
      • Umformen von logischen Ausdrücken
      • konjunktive Normalform
      • Umwandlung in konjunktive Normalform durch Umformen
    • Donnerstag, 25. Oktober 2007:
      • Boole'sche Funktionen
      • Umwandeln einer Boole'schen Funktion in konjunktive Normalform
  2. Prädikatenlogik
    • Donnerstag, 25. Oktober 2007:
      • Variablen, Aussageformen, Funktionen, Prädikate, Quantoren
      • Präfix- und Infix-Schreibweise von Prädikaten und Funktionen
      • Gültigkeitsbereiche bei Quantoren
    • Dienstag, 30. Oktober 2007:
      • Syntax der Prädikatenlogik: Terme, Formeln
      • freie und gebundene Variablen
      • Semantik der Prädikatenlogik
      • Prädikatenlogische Gesetze: de Morgan'sche Regeln
    • Donnerstag, 1. November 2007:
      • Beispiele zur Formulierung mathematischer Aussagen mit Prädikatenlogik
  3. Mengen, Relationen, Funktionen
    • Donnerstag, 1. November 2007:
      • Mengenoperationen, Potenzmenge, geordnete Paare, kartesisches Produkt
    • Dienstag, 6. November 2007:
      • Relationen
      • Eigenschaften von Relationen, Verknüfung von Relationen, inverse Relation
    • Donnerstag, 8. November 2007:
      • Äquivalenzrelationen, Klasseneinteilungen (Partitionen)
      • Ordnungsrelationen (Halbordnungen): minimale und maximale Elemente, kleinstes und größtes Element, lineare Ordnung
    • Dienstag, 13. November 2007:
      • Halbordnungen: Ketten und Antiketten, Supremum und Infimum, Verbände
      • Funktionen. Darstellung von Funktionen
      • Injektive, surjektive, bijektive Funktionen; Verknüpfung und inverse Funktion
      • Anzahl von Funktionen
    • Donnerstag, 15. November 2007:
      • Der Graph einer Funktion
      • Anzahl von injektiven und bijektiven Funktionen
      • Das Schubfachprinzip
      • Permutationen: inverse Permutation, Zyklendarstellung, Transpositionen
    • Dienstag, 20. November 2007:
      • Gerade und ungerade Permutationen, Inversionen (Fehlstände)
      • Potenzen und inverse Permutationen in Zyklendarstellung
    • Donnerstag, 22. November 2007:
      • Endliche und unendliche Mengen, abzählbare und überabzählbare Mengen
      • Abzählbarkeit der rationalen Zahlen
      • Das Cantor'sche Diagonalargument
      • Folgen
      • Verallgemeinertes Schubfachprinzip
      • Anwendungen des Schubfachprinzips
  4. Beweistechniken
    • Dienstag, 27. November 2007:
      • Direkter Beweis, Kontraposition, Beweis durch Widerspruch (indirekter Beweis), Fallunterscheidung
      • Vollständige Induktion
    • Donnerstag, 29. November 2007:
      • Varianten der vollständigen Induktion
      • Strukturelle Induktion
      • Logische Basis von Junktoren (funktional vollständige Signaturen)
      • Induktive Definitionen
  5. Kombinatorik
    • Donnerstag, 29. November 2007:
      • Binomialkoeffizienten
    • Dienstag, 4. Dezember 2007:
    • Donnerstag, 6. Dezember 2007:
      • Elementare Zählprinzipien: Gleichheitsregel, Summenregel, Produktregel
      • Das Pascal'sche Dreieck
      • Der binomische Lehrsatz
    • Dienstag, 11. Dezember 2007:
      • Gitterpfade
      • Partitionen und Stirlingzahlen zweiter Art
      • Kombinationen mit Wiederholung (Multimengen)
    • Donnerstag, 13. Dezember 2007:
      • Inklusion-Exklusion (die Siebformel)
      • Doppeltes Abzählen
  6. Elementare Wahrscheinlichkeitstheorie
    • Donnerstag, 13. Dezember 2007:
      • Diskreter Wahrscheinlichkeitsraum, Elementarereignisse und Ereignisse, Gleichverteilung
    • Dienstag, 18. Dezember 2007:
      • Bedingte Wahrscheinlichkeit
      • Unabhängige Ereignisse
      • Formel von der totalen Wahrscheinlichkeit
    • Donnerstag, 20. Dezember 2007:
      • Zufallsvariablen und Erwartungwert
      • Linearität des Erwartungswertes
    • Dienstag, 8. Januar 2008:
      • Wahrscheinlichkeitsfunktion und Verteilungsfunktion von Zufallsvariablen
      • Einige diskrete Verteilungen von Zufallsvariablen: Gleichverteilung, Bernoulli-Verteilung, Binomialverteilung, geometrische Verteilung
      • Klebebildchensammler (Das coupon-collector-Problem)
      • Irrfahrten: einführendes Beispiel aus der Warteschlangentheorie
    • Donnerstag, 10. Januar 2008:
      • Symmetrische Irrfahrt als Beispiel einer Markoffkette
      • Bayes'sche Formel
  7. Algebraische Strukturen
    • Donnerstag, 10. Januar 2008:
      • Operationen, Verknüpfungstafel
      • Kommutative und assoziative Operationen, neutrales Element
      • Halbgruppen und Monoide
    • Dienstag, 15. Januar 2008:
      • Inverse Elemente
      • Gruppen, Permutationsgruppen
      • Homomorphismen
      • Isomorphie
    • Donnerstag, 17. Januar 2008:
      • Homomorphismen in der Informatik: Modellierung und Darstellung von Datenstrukturen
  8. Lineare Rekursionsgleichungen
    • Donnerstag, 17. Januar 2008:
      • Beispiele: Türme von Hanoi, Bitfolgen mit verbotenen Mustern
      • Verifikation durch vollständige Induktion
      • Superpositionsprinzip
    • Dienstag, 22. Januar 2008:
      • Homogene und inhomogene lineare Rekursionen mit konstanten Koeffizienten
      • Charakteristische Gleichung
  9. Graphentheorie
    • Dienstag, 22. Januar 2008:
      • Gerichtete und ungerichtete Graphen
      • Schleifen, Mehrfachkanten und Multigraphen; schlichte Graphen
      • Fragestellungen und Anwendungen: Färbung
    • Donnerstag, 24. Januar 2008:
      • Fragestellungen und Anwendungen: Euler'sche und Hamilton'sche Wege, das Rundreiseproblem, kürzeste Wege, planare Graphen, optimale Netzwerke
      • Grad eines Knotens, Untergraphen und induzierte Untergraphen
      • Spezielle Graphen: vollständiger Graph, vollständiger bipartiter Graph, Hyperwürfel, Kreis, Weg
      • Isomorphe Graphen
      • Erreichbarkeit und Zusammenhang, Zusammenhangskomponenten
      • Bäume und Spannbäume
    • Dienstag, 29. Januar 2008:
      • Charakterisierung von Bäumen
      • Existenz eines Spannbaumes
      • Charakterisierung von bipartiten Graphen
    • Donnerstag, 31. Januar 2008:
      • Darstellung von Graphen
      • Gerichtete und geordnete Bäume
      • Euler'sche Graphen
      • Planare Graphen und die Euler'sche Polyederformel
    • Dienstag, 5. Februar 2008:
      • Maximale Kantenzahl planarer Graphen
      • Polyeder, konvexe Mengen
      • Paarungen
      • Hall-Bedingung, Heiratssatz
      • Wegesuchprobleme in der künstlichen Intelligenz
  10. Logik: Resolution
    • Donnerstag, 7. Februar 2007:
      • Resolvent, Resolutionssatz für die Aussagenlogik
    • Dienstag, 12. Februar 2008:
      • Hornklauseln und 2-SAT
      • Der Satz von Schröder-Bernstein
    • Donnerstag, 14. Februar 2007:
      • Satz von Erdös und Szekeres über monotone Teilfolgen
      • Das 15er-Spiel
      • Zerlegung in Rechtecke mit einer ganzzahlige Seite

Übungsblätter

# Übungen Lösungen
1 Übungsblatt 1
2 Übungsblatt 2  
3 Übungsblatt 3  
4 Übungsblatt 4  
5 Übungsblatt 5  
6 Übungsblatt 6  
7 Übungsblatt 7  
8 Übungsblatt 8  
9 Übungsblatt 9  
10 Übungsblatt 10  
11 Übungsblatt 11  
12 Übungsblatt 12  
13 Übungsblatt 13  
14 Übungsblatt 14  
15 Übungsblatt 15  
  Probeklausur Musterlösung der Probeklausur
  Klausur Musterlösung der Klausur
  Nachklausur Musterlösung der Nachklausur