Formal Logic

Current News

Where und When:

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!

AI policy: You are not allowed to use AI for solving the problems. However, you may use AI to translate text, correct text etc. We will make partial checks whether you can explain your solutions. If you cannot, we assume you used AI and will give no points. Let us know in this case whether you contradict our suspicion.
This is in concordance with the yellow tier of the current guideline of the Techfak.

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.

Lecture notes

The lecture notes. Please let me know if you find any errors, including typos.

Literature:

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:
Last change 13.10.2026       Dirk Frettlöh