• Organisatorisches
• Einführung Boolesche Aussagenlogik: elementare Aussagen, Junktoren und deren Stelligkeit, induktive Definition Boolescher Terme bei gegebener Signatur (Syntax), Baumdarstellung Boolescher Terme                                         

• Rangfunktion für Boolesche Terme
• Boolesche Algebra: Rechnen mit Wahrheitswerten
• Interpretation eines Booleschen Terms bezüglich gegebener Belegung der Variablen, vom Booleschen Term zur Booleschen Funktion als Semantik des Terms, Begriffe: Erfüllbarer Term, Tautologie, Kontradiktion und semantische Äquivalenz

• Wie hängen algorithmische Tests auf Erfüllbarkeit/Tautologie/Kontradiktion zusammen?
• Boolesche Gesetze, Beispiele, das Substitutionsprinzip bei der Anwendung von Booleschen Gesetzen
• Anzahl n-stelliger Boolescher Funktionen
• von Boolescher Funktion zu Booleschem Term mit dieser Semantik (Aufgabenstellung)

• Herleitung der kanonischen DNF und der kanonischen KNF als zwei Terme die eine gegebene Boolesche Funktion bei semantischer Interpretation liefern
• Begriffe: Literal, Minterm, Maxterm, vollständige Min- bzw. Maxterme
• Geometrische Interpretation von DNF und KNF im 0-1-Hyperwürfel
• Vereinfachung von kanonischer KNF bzw. DNF durch Zusammenfassung vollständiger Max bzw Minterme zu Unterwürfeln

• Funktionale Vollständigkeit einer Signatur: Definition + Beispiele
• Wie weist man Vollständigkeit/Unvollständigkeit  nach? Erstens per Definition oder man benutzt folgendes Konzept der "Simulation": Wenn Signatur I eine Signatur II simulieren kann und II ist funktional vollständig, so ist auch I vollständig. Die Kontraposition davon liefert ein Mittel, um Unvollständigkeit nachzuweisen
• Quantoren und der Umgang damit

• Einführung in Mengenlehre, grundlegende Definitionen: Mengen, Elemente, Teilmengen, Mächtigkeit
• Arten der Darstellung: Auflistung und Abstraktionsprinzip
• Operatoren: Vereinigung, Schnitt, (symmetrische) Differenz, Komplement
• Wichtige Identitäten: Kommutativität, Assoziativität, Distributivität, usw.
  • Nachweis durch Zurückführen auf entsprechende Boolesche Gesetze
• Definition Mengenfamilien

• Beispiel zu Mengenfamilien
• Beweistechnik: Fallunterscheidung
• Definition und Mächtigkeit der Potenzmenge
• Einführung Relationen, grundlegende Definitionen: Tupel, Kartesisches Produkt, Relation
• Darstellung von Relationen
• Schnitt, Vereinigung und Komplement von Relationen

• Inverse Relation und Verkettung von Relationen
• Eigenschaften von Relationen: Reflexivität, Symmetrie, Transitivität, Asymmetrie, Antisymmetrie
• Definition von Äquivalenzrelationen und Äquivalenzklassen
• Ganzzahlige Division und Kongruenzen

• Kongruenz modulo m als Beispiel einer Äquivalenzrelation
• Definition Zerlegung/Partition
• Die Äquivalenzklassen einer Äquivalenzrelation auf A partitionieren A. Umgekehrt existiert für jede Partition von A eine Äquivalenzrelation deren Äquivalenzklassen der Partition entsprechen.
• Der Schnitt zweier Äquivalenzrelationen ist wieder eine Äquivalenzrelation. Für die Vereinigung gilt dies nicht.

• Definition von Halbordnungsrelationen, halbgeordneten Mengen (posets) und totalen Odnungsrelationen
• Hasse Diagramme
• Lexikographische Ordnung
• maximal/minimale Elemente, obere/untere Schranken, Supremum/Infimum, Maximum/Minimum
• Existenz minimaler Elemente in endlichen Teilmengen einer halbgeordneten Menge
• Widerspruchsbeweise

• Definition von lineare Erweiterungen
• Existenz linearer Erweiterungen für jede endliche halbgeordnete Menge (topologisches Sortieren)
• Abschluss von Relationen bezüglich Reflexivität, Symmetrie, Transitivität
• Einführung Funktionen, grundlegende Definitionen: Bild, Urbild, surjektiv, injektiv, bijektiv
• Komposition von Funktionen
• Schnitt und Vereinigung von Bildern bzw. Urbildern

• Beweiskonzepte: Kontraposition und Ringschluss
• Charakterisierungen der surjektiven, injektive und bijektiven Funktionen
• Beweis von Bijektivität durch Angabe einer Umkehrabbildung
• Einführung Abzählbarkeit, grundlegende Definition: endliche und unendliche Mengen, Gleichmächtigkeit zweier Mengen, abzählbar (unendliche) Mengen
• Abzähbarkeit der natürlichen und ganzen Zahlen

• Abzählbarkeit der rationalen Zahlen
• Die endlichen Teilmengen der natürlichen Zahlen sind abzählbar ...
• ... aber die Potenzmenge der natürlichen Zahlen ist nicht abzählbar (überabzählbar)
• Die reellen Zahlen sind nicht abzählbar

• Schubfachprinzip
• Einführende Beispiele
• Satz von Erdös-Szekeres über Existenz aufsteigender / absteigender Teilfolgen mit gewisser Mindestlänge

• Weitere Beispiele zum Schubfachprinzip
• Peano Axiome
• Rekursiv definierte Addition für natürliche Zahlen
• Prinzip der vollständigen Induktion
• Schema eines Beweises per vollständiger Induktion

• Beispiele zu Beweisen per vollständiger Induktion
• Varianten der vollständigen Induktion (jeweils mit Beispielen):
  • Induktionsanker > 0
  • verallgemeinerte vollständige Induktion
  • "breiter" Induktionsanker
• Zusammenhang zwischen vollständiger Induktion und rekursiven Algorithmen

• Ausblick: Strukturelle vollständige Induktion als Beweisprinzip     

KOMBINATORIK/ Abzählen

• Gleichheits-,Summen- und Produktregel
• Mächtigkeit der Potenzmenge einer n-Menge
• Inklusions- Exklusionsprinzip
• Anzahl Permutationen einer n-Menge
• Definition Binomialkoeffizienten, einfache Eigenschaften

In diesem Zeitraum wurden die Kapitel 5.1, 5.2 und 5,6 aus dem Skript behandelt.

• Einführung diskrete Wahrscheinlichkeitsrechnung, grundlegende Definitionen und Beispiele
  • Diskreter Wahrscheinlichkeitsraum, Ereignisse, Wahrscheinlichkeit
  • Gleichverteilung
• Grundlegende Fakten zur Berechnung von Wahrscheinlichkeiten
• Geburstagsparadoxon
• Bedingte Wahrscheinlichkeit

• Rechnen mit bedingten Wahrscheinlichkeiten, Beispiel eines Baumdiagrams
• Satz von Bayes
• Satz der totalen Wahrscheinlichkeit
• Unabhängigkeit von zwei und mehr Ereignisse, unabhängige Familien von Ereignissen
• Zufallsvariablen und deren induzierte Wahrscheinlichkeitsverteilungen

• Definition des Erwartungswerts einer Zufallsvariable
• Verschiedene Ansätze / Identitäten zu Berechnung des Erwartungswerts, jeweils mit Beispielen
• Geometrische Reihe
• Linearität des Erwartungswerts
• Bernoulli Experimente und Bernoulli Verteilung

• Bionomialverteilung
• Geometrische Verteilung
• Einführung Graphentheorie, grundlegende Definitionen: gerichtete und ungerichtetete Graphen, Knoten, Kanten, Nachbarschaft, Adjazenz und Inzidenz
• Anwendungsbeispiele

• Handschlag Lemma
• Teilgraphen und induzierte Teilgraphen
• Isomorphie
• Wichtige Graphklassen: vollständige (bipartite) Graphen, Hyperwürfel, Wege und Kreise, azyklische Graphen, planare Graphen

• Definitionen: Zusammenhang, Zusammenhangskomponenten, Bäume, aufspannende Bäume
• Existenz von mindestens zwei Blättern in Bäumen mit mindestens zwei Knoten
• Charakterisierung von Bäumen
• Charakterisierung von bipartiten Graphen

• Planare Graphen und Zeichnung, Jordanscher Kurvensatz (ohne Beweis)
• Eulerformel
• Folgerungen aus der Euler Formel:
  • ein planar Graph mit n > 2 Knoten hat höchstens 3n-6 Kanten
  • jeder planare Graph enthält einen Knoten mit Grad < 6
• Landkartenfärben: jeder planare Graph kann mit 5 Farben gefärbt werden
  • es geht sogar mit 4 Farben (ohne Beweis)
• Definition: Unterteilung eines Graphen
• Satz von Kuratowski (ohne Beweis)

• Klauseldarstellung von KNF-Termen
• Definition: Resolventen, reflexiv-transitiver Abschluss der Resolventenbildung
• Resolutionslemma: Hinzufügen von Resolventen zur Klauselmenge erhält deren Erfüllbarkeit
• Resolutionssatz: Klauselmenge ist nicht erfüllbar genau dann, wenn man die leere Klausel herleiten kann