Formal Logic
Recent annoucements:
The second exam will be an oral exam (mündliche Prüfung).
It takes place Tuesday 4. April in U4-135. Please send me an email with
your desired time slot (see also below).
In case you need an earlier exam just let me know.
The first exam took place on 16. Februrary 2023. Results should
be visible in your Leistungsübersicht in the Prüfungsverwaltung.
Where und When:
- Lecture: Tuesday 14:15-15:45 in H11
- Problem classes:
- Tue 16-18 in U2-232 (Constantin Lefeld)
- Tue 16-18 in T2-233 (Jakob Niermann)
- Wed 8-10 in U2-232 (Frederic Alberti)
- Wed 16-18 in U2-147 (Hannah Schweizer)
- Thu 12-14 in C01-136 (Luigi Esercito and Enrico di Gaspero, in English)
- Written exam: Thursday 16th February 2022 at 10:00 in H1
- Duration: 90 min
- Allowed tools: Pen, brain (no own paper, no cheat sheet)
- Typical problems would look like exercises 1, 5, 6, 9, 10, 14, 17,
18, 19, 22, 26, 27, 29, 31, 33, 34, 35, 39, 42, 43, 45, 46, 47, 48.
- Second exam: 4. April. Free slots: 10:00, 10:30, 11:30,
17:00, 17:30.
Here the
link
to the ekvv-entry.
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
well-posed problems that cannot be solved algorithmically in general.
Propositional and first-order logic, as well as temporal
logic and higher-order logic are used in the verification and validation
of computer algorithms.
This one-semester course offers an introduction to advanced topics of formal
logic. After setting the ground by delving into propositional logic, this
course covers first-order logic and modal logic (with some
focus on normal forms and the algorithmic treatment of logic formulas) as
well as concepts and questions about (un-)decidabilty, like the Gödel
theorems and un-computable problems.
Exercise Sheets
The 2h lectures are accompanied by problem sheets. Solutions to the problem
sheets will be handed in by the students (single, or groups of two) and
discussed in the problem classes. In any case it is important that all
students worked on all exercises, otherwise you will not learn enough.
Any student who presents his/her solution to a problem class gets
one point bonus for the written exam (at most two).
Lecture notes
The lecture notes. Please
let me know if you find any errors, including typos.
If you know Anki Flashcards:
here are sets of those that can be used to memorize the lecture or
prepare for the exams (thanks to Constantin).
...or all in one.
Assessment: 5 Credit points for solving 50% of the exercises on the
problem sheets, and passing the written exam at the end of the course.
- NWI Bachelor: strukturierte Ergänzung
- BIG Bachelor: Wahlpflicht Bioinformatik (benotet oder unbenotet),
oder strukturierte Ergänzung
- KOI Bachelor: Wahlpflicht Intelligente Systeme, oder
strukturierte Ergänzung
- Informatik Bachelor: Wahlpflicht Informatik, oder
strukturierte Ergänzung
- NWI Master: Grundlagen Ergänzung
- BIG Master: Grundlagen Ergänzung
- ISY Master: Grundlagen Ergänzung
Videos:
One can find a lot of misleading, false or superficial information
in the web. But there are exceptions:
Literature:
- Uwe Schöning: Logic for Computer Scientists
- H.-D. Ebbinghaus, J. Flum, W. Thomas: Mathematical Logic
- Wolfgang Rautenberg: A Concise Introduction to Mathematical Logic
- Uwe Schöning: Logik für Informatiker (German)
- Martin Kreuzer, Stefan Kühling: Logik für Informatiker (German)
Last change 20.2.2023
Dirk Frettlöh