Vorlesung Berechenbarkeit und Logik (WS 2025/26)

 

Organisatorisches

• Veranstalter: Prof. Dr. Markus Lohrey (Raum H-A 7103, Tel. 0271-740-2826)
• Vorlesungstermin:
  • Freitag 12:15-13:45 in H-C 8326
  • Freitag 14:15-15:45 (erste Hälfte des Semesters) in H-C 8326
• Übungstermin:
  • Dienstag 08:15-09:45 in H-C 3302
  • Mittwoch 08:15-09:45 in H-C 3302
  • Mittwoch 10:15-11:45 in H-C 3302
  • Donnerstag 12:15-13:45 in H-C 7327
  Organisation der Übungen: Alexander Thumm (Raum H-A 7105)

  Die Übungen beginnen in der Woche 20.10-24.10.

 

Einige Themen

• Berechenbarkeit
• • Berechnungsmodelle
  • berechenbare Funktionen
  • Churche These
  • Entscheidbarkeit und Unentscheibarkeit
  • Halteproblem
  • Satz von Rice
  • Komplexitätstheorie
• Aussagenlogik
• • Äquivalenz und Normalformen
  • Hornformeln
  • Endlichkeitssatz
  • Resolution
• Prädikatenlogik
• • Pränexnormalform
  • Herbrand-Theorie
  • Resolution

 

Lehrmaterial

• Deutsche Version der Folien
• English version of the slides

 

Übungsblätter Berechenbarkeit

• Blatt 1
• Blatt 2
• Blatt 3

 

Übungsblätter Logik

 

Klausuren

Logik I

• Klausur SoSe 22 (Lösung)
• Klausur SoSe 21 (Lösung)
• Klausur WiSe 20/21 (Lösung)
• Klausur SoSe 20 (Lösung)

 

Lehrbücher

• Uwe Schöning, Theoretische Informatik - kurz gefasst, Spektrum Akademischer Verlag
• Lutz Priese, Katrin Erk, Theoretische Informatik: Eine umfassende Einführung, Springer
• Alexander Asteroth, Christel Baier, Theoretische Informatik, Pearson Studium
• Uwe Schöning: Logik für Informatiker, Spektrum Akademischer Verlag

 

Impressum