Logik und formale Sprachen (LFS)

Lasse Computer logisch schließen: Du lernst, Aussagen klar zu formulieren und mit Logik (Aussagen- und Prädikatenlogik) sowie Beweisverfahren neue Erkenntnisse abzuleiten. Außerdem beschäftigst du dich mit logischer Programmierung, regelbasierten Systemen und einfachen KI-Grundlagen. Ergänzend verstehst du, wie formale Sprachen und Automaten funktionieren und wie man Probleme nach ihrer Komplexität einordnet.

Inhalte

• Die Veranstaltung behandelt zum einen die Grundlagen der Aussagenlogik und der Prädikatenlogik erster Stufe, wie sie für die Informatik gebraucht werden. Formeln (z.B. Hornformeln), Quantoren und logische Operatoren werden eingeführt und besprochen. Normalformen (z.B. Die Skolemform), Modelle (z.B. Das Herbrand-Modell) sowie Markierungsalgorithmen und Resolutionsalgorithmen sollen erläutert und angewendet werden. Rückwertsverkettung (Beweisbäume, Backtracking), Vorwärtsverkettung, automatisches Beweisen und logische Programmiersprachen wie etwa PROLOG werden besprochen und es wird ein Ausblick auf regelbasierte Systeme und Künstliche Intelligenz gegeben.
• In einem zweiten Teil wird die Chomsky Hierachie der formalen Sprachen angesprochen. Reguläre Sprachen, kontextfreie Sprachen sowie Turing Maschinen werden erläutert und in diese Hierachie eingeordnet. Begriffe wie Turingentscheidbarkeit und die Gödelschen Sätze bilden eine Brücke zur Logik. Die Inhalte sollen durch entsprechende Übungsaufgaben illustriert und vertieft werden. Hier sind einige Stichpunkte:
• Finite Automaten und praktische Anwendungen
• Kellerautomaten und praktische AnwendungenBNF, EBNF
• Aussagenlogik
• Prädikatenlogik
• Hornklauseln
• Regelbasierte Systeme
• Rückwärtsverkettung
• Beweisbäume
• Backtracking
• Negation as Failure
• Vorwärtsverkettung
• reguläre, kontextfreie und kontextsensitive Sprachen
• Turing Maschinen
• Unentscheidbarkeitssätze von Gödel
• Ausblick: Künstliche Intelligenz

Lernziele/Kompetenzen

Die Studierenden sind in der Lage,

• logische Aussagen klar und präzise zu formulieren,
• grundlegende Beweistechniken zu verstehen und anzuwenden,
• Konzepte logischer Programmierung zu verstehen und anzuwenden,
• Grunprinzipien der künstlichen Intelligenz zu erläutern,
• Probleme in die Chomsky Hierachy einzuordnen und zentrale Konzepte der Theorie formaler Sprachen zu erklären und
• die gelernten Inhalte einem nicht eingearbeiteten Fachkollegen zu erklären und zu präsentieren.

Literatur

• Schöning: Theoretische Informatik – kurzgefaßt. Spektrum, 2008. (5. Auflage)
• Schöning: Logik für Informatiker, Spektrum, 2000.
• Rich: Automata, Computability, and Complexity, Pearson 2008.
• Vossen, Witt: Grundkurs Theoretische Informatik, vieweg, 2006.
• Asteroth, Baier: Theoretische Informatik, Pearson, 2003.
• Hollas, Boris: Grundkurs Theoretische Informatik, Spektrum Akademischer Verlag 2007
• Ebbinghaus, Flum, Thomas: Einführung in die mathematische Logik, Spektrum, 1996.
• Kreuzer, Kühling: Logik für Informatiker, Pearson 2006.
• Hölldobler u.a.: Logik für Logikprogrammierung, Synchron Wissenschaftsverlag, 2011.
• Staab: Logik und Algebra: Eine praxisbezogene Einführung für Informatiker und Wirtschaftsinformatiker, Oldenbourg Verlag, 2012.

Dozentinnen / Dozenten

• Prof. Dr. Lutz Strüngmann

Empfohlene Vorkenntnisse

• Mathematik 1
• Mathematik 2

Daten zum Modul

Semester	6/7
Unterrichtssprache	Deutsch
Häufigkeit	Unregelmäßig Im Durchscnitt alle 2 Semester
Kreditpunkte	5
Modulverantwortlich	Prof. Dr. Lutz Strüngmann
Dauer	1 Semester
Studienleistung	Keine
Prüfungsvorleistung	Pflichtübung (PU)
Prüfungsleistung	Klausur 90 Minuten (K90)

Semesterwochenstunden

Vorlesung	2 SWS
Übung	2 SWS
Summe	4 SWS

Arbeitsaufwand (work load)

Vorlesung	45 h
Selbststudium	60 h
Aufgaben	15 h
Prüfungsvorbereitung	30 h
Summe	150 h