Formale Logik
Wann und Wo:
- Dienstag 14-16 (c.t.) in T2-228
Hier der
Link
zur ekvv-Seite.
Die Seminar-Vorträge finden
am 10.4.2017 und 11.4.2017 in Raum U2-232 statt. Die
Themenliste.
Inhalt:
Formale Logik ist an vielen Stellen mit Informatik verwoben: logische Schaltkreise sind Grundlage der Rechnerarchitektur. Beweise der NP-Schwierigkeit von Problemen bestehen oft in der Reduktion auf Erfüllbarkeit Boolescher Ausdrücke. Logik bietet ein Konzept von Berechenbarkeit und liefert etliche Probleme, die nicht algorithmisch entscheidbar sind. Aussagen- und Prädikatenlogik, temporale Logik und Logiken höherer Ordnung werden genutzt zum Nachweis der Korrektheit von Algorithmen.
Dieser Kurs hat zwei Teile: Im Wintersemester gibt es eine Vorlesung, die die verschiedenen Logiken (Aussagenlogik, Prädikatenlogik, Normalformen, modale Logik) und Modelle (Peanoarithmetik, Presburgerarithmetik,...) sowie Unvollständigkeitssätze und Beweisbarkeit im Detail behandelt; im Sommersemester stellen die Teilnehmer in Vorträgen ausgewählte Themen vor.
Topics:
Formal logic appears naturally in several places in computer science. Logic gates are the elementary building blocks of integrated circuits. Proofs of NP-hardness often use reductions to satisfiability of Boolean expressions. Logic provides a concept of computability, and a wealth of problems that cannot be solved algorithmically. Propositional and predicate logic, as well as temporal logic and higher-order logic are used in the verification and validation of computer algorithms.
This two-part course offers introduction in and advanced topics of formal logic. In the winter term the course takes place as a lecture, covering propositional logic, first-order logic, normal forms, modal logic, incompleteness theorems and more. In the summer term the course has the form of a seminar; the participants will give presentations of selected topics.
Literatur:
- Uwe Schöning: Logik für Informatiker (Kap 1 und 2)
- Martin Kreuzer, Stefan Kühling: Logik für Informatiker (Kap 1-4,6,7)
Zuletzt geändert am 20.12.2016
Dirk Frettlöh