MLU
INF.01117.03 - Logik und Berechenbarkeit (Complete module description)
Original version English
INF.01117.03 5 CP
Module label Logik und Berechenbarkeit
Module code INF.01117.03
Semester of first implementation
Faculty/Institute Institut für Informatik
Module used in courses of study / semesters
  • Informatik (MA120 LP) (Master) > Informatik InformatikMA120, Version of accreditation (WS 2006/07 - SS 2013) > Primärmodule
  • Informatik (MA120 LP) (Master) > Informatik InformatikMA120, Version of accreditation (WS 2006/07 - SS 2013) > Sekundärmodule
  • Informatik (MA120 LP) (Master) > Informatik InformatikMA120, Version of accreditation (WS 2006/07 - SS 2013) > Sekundärmodule
  • Mathematik (MA120 LP) (Master) > Mathematik MathematikMA120, Version of accreditation (WS 2006/07 - SS 2013) > Anwendungsfach Informatik
  • Mathematik (MA120 LP) (Master) > Mathematik MathematikMA120, Version of accreditation (WS 2013/14 - SoSe 2023) > Anwendungsfach Informatik
Responsible person for this module
Further responsible persons
Prof. Dr. Ludwig Staiger
Prerequisites
Skills to be acquired in this module
  • Ein wesentliches Ziel dieses Moduls ist es, die Fähigkeiten der Teilnehmenden, eigene Gedankengänge logisch zu analysieren, kausale Zusammenhänge zu erkennen und zur Abstraktion, weiterzuentwickeln. Zu diesem Zwecke hat das Modul die Beziehung zwischen mathematischer Logik und Berechenbarkeit zum Inhalt.
Module contents
  • Abstrakte Spezifikation und Verifikation, grundlegende intellektuelle Fähigkeiten eines Informatikers, haben ihre Wurzeln in der formalen Logik. In der Vorlesung werden die Beziehung zwischen Syntax und Semantik der klassischen Prädikatenlogik, insbesondere Beziehungen zwischen Erfüllbarkeit und Widerspruchsfreiheit, Vollständigkeit, Axiomatisierbarkeit, Unentscheidbarkeit etc studiert.
  • Weiter wird gezeigt, dass die Entscheidbarkeit der eingeschränkten monadischen Arithmetik der zweiten Stufe Grundlage für verschiedene automatische Verifikationsverfahren ist. Dazu wird die Beziehung zwischen der Arthmetik und der Theorie der endlichen Automaten entwickelt.
  • Der Aufbau der Vorlesung orientiert sich an den folgenden Punkten.
  • 1. Syntax und Semantik der Prädikatenlogik
  • 2. Modellbeziehung
3. Axiomatisierbarkeit und Berechenbarkeit
4. Entscheidbarkeit und Unentscheidbarkeit
5. Entscheidbarkeit der monadischen Arithmetik der zweiten Stufe und Automatentheorie
Forms of instruction Course (3 SWS)
Course (2 SWS)
Course
Languages of instruction German, English
Duration (semesters) 1 Semester Semester
Module frequency nicht festlegbar
Module capacity unlimited
Time of examination
Credit points 5 CP
Share on module final degree Course 1: %; Course 2: %; Course 3: %.
Share of module grade on the course of study's final grade 1
Reference text
Angebotsturnus: Alle 2 bis 3 Semester, normalerweise im Wintersemester, Primärmodul für Vertiefungsrichtungen: Theoretische Informatik, Sekundärmodul für Vertiefungsrichtungen: Algorithmen und Datenstrukturen, Softwaretechnik und Übersetzerbau, Datenbanken und Informationssysteme
Module course label Course type Course title SWS Workload of compulsory attendance Workload of preparation / homework etc Workload of independent learning Workload (examination and preparation) Sum workload
Course 1 Course Vorlesung 3 0
Course 2 Course Übung 2 0
Course 3 Course Bearbeiten der Übungsaufgaben 0
Workload by module 150 150
Total module workload 150
Examination Exam prerequisites Type of examination
Course 1
Course 2
Course 3
Final exam of module
Korrekte Bearbeitung der theoretischen Übungsaufgaben in Höhe von mindes-tens 60% der maximal erreichbaren Punkte, 3 Kurzvorträge über Lösungen von Übungsaufgaben, aktive Teilnahme an den Übungen und Bearbeitung der Übungsaufgaben
mündl./schriftl. Prüfung
Exam repetition information
Prerequisites and conditions Prerequisites Frequency Compulsory attendance Share on module grade in percent
Course 1 Winter semester No %
Course 2 Winter semester No %
Course 3 Winter semester No %