Formal Logic
Current News
Where und When:
- Lecture: Tuesday 14:15-15:45 in H5
- Problem classes:
(will be held in German)
- Tuesday 16-18 in S1-501, tutor: Lisa Henetmayr, or
- Wednesday 12-14 in S1-501, tutor: Lisa Henetmayr
- Written exam: 18th February 2026, 10-12 in Y-0-111.
- Duration: 90 min
- Allowed tools: Pen, brain (no own paper, no cheat sheet)
- Solutions can be in German as well as in English as well as in Denglisch.
- Typical problems would look like exercises 1, (4), 5, 6, 7b, 7c, 9, 10,
(12), (13), 14, 16, 17, 19, (20), 21a, (22), (23), 24, 25, 26, 29, 30, 31, 34, 35, 36,
38, 39 and 40 via tableau calculus, 41, 42, 43, 45a, (45 b, 45c), 46a, (46b), (46c), 47, (49), (51).
(In brackets: if you want to achieve a good or very good grade)
- Second exam: (probably) oral exams, (probably) end of March, more info
to come.
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 problems that cannot be solved
algorithmically. 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 we will
cover 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.
5 credit points are obtained by solving more than 50%
of the problems on the problem sheets plus passing the written exam at
the end of the course.
Exercise Sheets
The 2h lectures are accompanied by problem sheets. Solutions to the problem
sheets will be handed in by the students and discussed in the problem
class. Solutions can be handed in in German as well as in English as well as
in Denglisch. Solutions can be handed in by groups of one or two. Anyway, you
need to try yourself on all exercises, otherwise you will face problems
in the final exam!
Please name your solution files techfakaccount-bln.xxx,
so for instance dfrettloeh-bl2.pdf, or in a group of two like
dfrettloeh+dmerkle-bl2.pdf.
If you present two solutions during the tutorials then you will get one
bonus point in the written exam.
The additional exercises ('Präsenzübungen'):
- Sheet 1 propositional logic: warmup.
- Sheet 2 propositional logic: resolution calculus.
- Sheet 3 first order logic: THE normal form.
- Sheet 4 first order logic: resolution calculus.
- Sheet 5 modal logic: tableau calculus.
Lecture notes
The lecture notes. Please
let me know if you find any errors, including typos.
Literature:
- Uwe Schöning: Logic for Computer Scientists
- Uwe Schöning: Logik für Informatiker (same in German)
- H.-D. Ebbinghaus, J. Flum, W. Thomas: Mathematical Logic
- Wolfgang Rautenberg: A Concise Introduction to Mathematical Logic
- Martin Kreuzer, Stefan Kühling: Logik für Informatiker.
The first one (resp., two) is my main source for the first part of the lecture
(Chapters 1 and 2). Number three is the standard textbook on formal
logic, first edition in 1978. Number four is a more recent textbook from 2009,
also very comprehensive, hence the latter two cover much, much more than our lecture.
Number 5 is not a good book, it contains several errors, but it is one
of the few sources for modal logic - the other books don't cover it.
Videos:
One can find a lot of misleading, false or superficial information
in the web. But there are exceptions:
- Many
excellent videos on several topics in logic, maths, computer science.
In particular,
A great video on Gödel's (in)completeness theorems.
- An explanation of
how many infinities are there (also the link at 1:25). The other videos of
PBS Infinite Series (on logic or else) are also good.
Last change 12.2.2026
Dirk Frettlöh