Mathematical Logic

SS 2010

News

  • Die Ergebnisse der Klausur (2. Termin) sind nun im m(a)lo-Portal einsehbar. Sie haben am Montag den 18.10.2010 von 14:00 bis 15:00 die Möglichkeit, Ihre Klausur im Seminarraum des Lehrstuhls für Informatik 7 (Raum 4116, E1, Informatikzentrum) einzusehen. Falls Sie Einwände gegen die Bewertung Ihrer Klausur haben, so können Sie diese während der Einsicht schriftlich vorbringen. In diesem Fall werden die betroffenen Aufgaben noch einmal korrigiert. Bitte beachten Sie, dass zur Einsicht keinerlei eigenes Schreibmaterial oder sonstige Unterlagen mitgebracht werden dürfen.

Schedule

TypeDateLocation Organizer
V3Di11:4512:501420|001 (Gr)Beginn 13. AprilE. Grädel
Do11:4512:551420|001 (Gr)Beginn 15. AprilE. Grädel
Ü2Fr10:0011:302350|009 (AH I)Gruppe AT. Ganzow
Fr10:0011:301580|001 (SE 001)Gruppe BS. Siebertz
Fr11:4513:152356|054 (5054)Gruppe CS. Leßenich
Fr13:3015:001010|141 (IV)Gruppe DF. Abu Zaid
Mo11:4513:152350|009 (AH I)Gruppe EB. Puchala
Di08:1509:452356|055 (5055)Gruppe FD. Fischer
Di14:0015:301250|243 (E2)Gruppe GW. Pakusa

Übungsbetrieb

Die Übungsblätter stehen jeweils ab Mittwoch auf dieser Webseite zum Download bereit. Sie können Ihre Lösungen bis zum darauffolgenden Mittwoch um 13:00 am Lehrstuhl in den dafür vorgesehenen Kasten einwerfen. Die Rückgabe der Abgaben erfolgt im nachfolgenden Tutorium, die erzielten Punkte können Sie auch über das m(a)lo-Portal abrufen.

Geben Sie Ihre Lösungen in Gruppen von zwei oder (bevorzugt) drei Studierenden ab und beschriften Sie Ihre Abgabe mit der Nummer des Übungsblattes, dem Kennbuchstaben Ihrer Übungsgruppe sowie Namen und Matrikelnummern aller beteiligten Studierenden. Die Abgaben werden bevorzugt von Ihrem Tutor korrigiert.

Das erste Übungsblatt erscheint am Mittwoch, den 21.04., die Tutorien finden ab Freitag, 23.04. statt. In den Tutorien werden die Übungsaufgaben der vergangenen Woche vorgerechnet, sowie jeweils eine zusätzliche Aufgabe die eine Hilfestellung für das Lösen der Übungsaufgaben geben soll.

Für die Zulassung zur Klausur sind 50% der Punkte in den Übungen notwendig. Studierende, die im Sommersemester 2009 die Zulassung zur Prüfung durch erfolgreiche Teilnahme an den Übungen erworben haben, sind auch im Sommersemester 2010 zur Prüfung zugelassen.

Lecture Notes

  • Chapter 1: Aussagenlogik [pdf] [pdf-2up]
  • Chapter 2: Syntax und Semantik der Prädikatenlogik [pdf] [pdf-2up]
  • Chapter 3: Definierbarkeit in der Prädikatenlogik [pdf] [pdf-2up]
  • Chapter 4: Vollständigkeitssatz, Kompaktheitssatz und Unentscheidbarkeit der Prädikatenlogik [pdf] [pdf-2up]

Coursework

Content

  • Aussagenlogik (Grundlagen, algorithmische Fragen, Kompaktheit, Resolution, Sequenzenkalkül)
  • Strukturen, Syntax und Semantik der Prädikatenlogik
  • Einführung in weitere Logiken (modale und temporale Logiken, Logiken höherer Stufe)
  • Auswertungsspiele, Modellvergleichsspiele
  • Beweiskalküle, Termstrukturen, Vollständigkeitssatz
  • Kompaktheitssatz und Anwendungen
  • Entscheidbarkeit, Unentscheidbarkeit und Komplexität von logischen Spezifikationen

Lernziele

Die Studierenden sollen Sachverhalte in geeigneten logischen Systemen formalisieren und mit diesen Formalisierungen umgehen, Grundlegende Begriffe und Methoden der mathematischen Logik verstehen (Syntax und Semantik logischer Systeme, Folgerungsbeziehung, Erfüllbarkeit, Beweiskalküle, Definierbarkeit, etc.), die Ausdrucksstärke und Grenzen logischer Systeme beurteilen können sowie einige der fundamentalen Resultate der mathematischen Logik des 20. Jahrhunderts (z.B. Vollständigkeitssatz, Kompaktheitssatz, Unentscheidbarkeit der Prädikatenlogik) kennenlernen und ihre Bedeutung für Mathematik und Informatik verstehen.

Prüfungsleistung

Die Klausuren zum Erwerb des Leistungsnachweises für Diplom- und Lehramtsstudenten finden an den gleichen Terminen wie die Bachelorprüfungen statt. Für diese Studenten ist keine Anmeldung erforderlich.

In der Klausur darf jeder Teilnehmer ein (beidseitig beschriebenes) DIN-A4-Blatt mit eigenen Notizen benutzen. Darüber hinaus sind keine weiteren Hilfsmittel (Skripte, Bücher, Mitschriften etc.) zugelassen.

Literature

[1]S. Burris. Logic for Mathematics and Computer Science. Prentice Hall, 1998.
[2]R. Cori and D. Lascar. Logique mathématique. Masson, 1993.
[3]H. Ebbinghaus, J. Flum, and W. Thomas. Einführung in die mathematische Logik. Wissenschaftliche Buchgesellschaft, Darmstadt, 1986.
[4]M. Huth and M. Ryan. Logic in Computer Science. Modelling and reasoning about systems. Cambridge University Press, 2000.
[5]B. Heinemann and K. Weihrauch. Logik für Informatiker. Teubner, 1992.
[6]H. K. Büning and T. Lettman. Aussagenlogik: Deduktion und Algorithmen. Teubner, 1994.
[7]S. Popkorn. First Steps in Modal Logic. Cambridge University Press, 1994.
[8]W. Rautenberg. Einführung in die Mathematische Logik. Vieweg, 1996.
[9]U. Schöning. Logik für Informatiker. Spektrum Verlag, 1995.
[10]D. van Dalen. Logic and Structure. Springer, Berlin, Heidelberg, 1983.

Classification

  • Informatik (B.Sc.)/4. Semester
  • Mathematik (B.Sc.)/Mathematik (WS)/4. Semester
  • Mathematik (B.Sc.)/Mathematik (WS)/6. Semester
  • Mathematik (B.Sc.)/Mathematik (SS)/5. Semester
  • Informatik (D)/Grundstudium
  • Mathematik (D)/Hauptstudium/Reine Mathematik
  • Informatik (S II)
  • Mathematik (S II)/Hauptstudium/B: Algebra und Grundlagen der Mathematik

Prerequisites

  • Mathematische Grundkenntnisse aus den Vorlesungen Diskrete Strukturen und Lineare Algebra
  • Grundkenntnisse über Berechenbarkeit und Komplexität

Successive Courses

  • Algorithmische Modelltheorie
  • Mathematische Logik II
  • Komplexitätstheorie und Quantum Computing
  • Logik und Spiele
  • weitere Spezialvorlesungen zur Mathematischen Logik

Recurrence

Jedes Jahr im Sommersemester

Contact

Erich Grädel, Bernd Puchala