Logik in der Informatik Prof. Dr. Nicole Schweikardt

Hier finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungsstunden und gelegentlich auch Korrekturen und sonstige ergänzende Bemerkungen.

1. Di, 16.04.2024 (9-11 Uhr):

   Kapitel 0: Einleitung und Grundbegriffe — heute: Einführung ins Thema, Organisatorisches, Vereinbarungen und Notationen bzgl. logischen Strukturen, Signaturen etc.; Definition von Syntax und Semantik der Logik FO+MOD; Beispiele; Einführung des Begriffs "Zählterm"

   Material: handschriftliche Notizen zu Kapitel 0: heute Seiten 0.1–0.5
   Weitere Lektüre: [KS17]

2. Di, 16.04.2024 (11-13 Uhr):

   Kapitel 0: Einleitung und Grundbegriffe — heute: Syntax und Semantik der Logik FO(P) (eine Erweiterung der Logik erster Stufe um unäre Zählquantoren); Beispiele; Syntax und Semantik der Logik FOC(P) (eine Erweiterung der Logik erster Stufe um Zählterme und numerische Prädikate); Beispiele

   Material: handschriftliche Notizen zu Kapitel 0: heute Seiten 0.6–0.8
   Weitere Lektüre: [KS17]

3. Do, 18.04.2024:

   Weiter mit Kapitel 0: Einleitung und Grundbegriffe — heute: weitere Grundbegriffe: der Gaifman-Graph, der Grad und die Zusammenhangskomponenten einer Struktur, die Distanz zwischen Elementen im Universum einer Struktur, induzierte Substrukturen, Nachbarschaften, r-Typen mit k Zentren über einer Signatur σ (und deren Beschreibung durch FO[σ]-Sätze), eine obere Schranke für die Anzahl der Elemente in der r-Nachbarschaft eines Elements im Universum einer Struktur vom Grad höchstens d; weitere einfache Beobachtungen zu Typen und Nachbarschaften.

   Material: handschriftliche Notizen zu Kapitel 0: heute Seiten 0.8–0.14
   Weitere Lektüre: [KS17]

4. Do, 25.04.2024:

   Abschluss von Kapitel 0: Einleitung und Grundbegriffe — heute: weitere einfache Beobachtungen zu Typen und Nachbarschaften.
   Start mit Kapitel 1: Hanf-Normalform und Hanf-Lokalität — heute: Definition der Begriffe Typen-1-Zählterm, einfacher-Zählterm, Hanf-Zählsatz und HNF-Formel für FO(P); Formulierung des Theorems zur "schwachen Hanf-Normalform für FO(P)" (Theorem 1.5); Diskussion zu Anwendungsmöglichkeiten des Theorems: Linearzeit-Auswertung von FO(P)-Sätzen auf Strukturen vom Grad höchstens d

   Material: handschriftliche Notizen zu Kapitel 0: heute Seite 0.15
   handschriftliche Notizen zu Kapitel 1: heute Seiten 1.1–1.3
   Weitere Lektüre: [KS17]

5. Di, 30.04.2024:

   Weiter mit Kapitel 1: Hanf-Normalform und Hanf-Lokalität — heute: Formulierung und Beweis des ersten technischen Lemmas, das für den Beweis von Theorem 1.5 gebraucht wird (Lemma 1.6)

   Material: handschriftliche Notizen zu Kapitel 1: heute Seiten 1.4–1.9
   Weitere Lektüre: [KS17]

6. Do, 02.05.2024:

   Weiter mit Kapitel 1: Hanf-Normalform und Hanf-Lokalität — heute: Formulierung und Beweis des zweiten technischen Lemmas, das für den Beweis von Theorem 1.5 gebraucht wird (Lemma 1.7); Beginn des Beweises von Theorem 1.5

   Material: handschriftliche Notizen zu Kapitel 1: heute Seiten 1.10–1.18
   Weitere Lektüre: [KS17]