# Formal Logic

## Where und When:

- Lecture: Tuesday 14:15-15:45 in room T2-204
- Problem class: Tuesday 16-18 in room T2-204 Tutor: Oliver Tautz

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 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 formula) as
well as concepts and questions about (un-)decidabilty.

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. 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

## Lecture notes

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

## 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 17.8.2018
Dirk Frettlöh
*