# 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

- Sheet 1 from 16
^{th} Oct 2018
- Sheet 2 from 23
^{rd} Oct 2018 (corrected version as of Oct 24^{th} 17:15)
- Sheet 3 from 30
^{th} Oct 2018
- Sheet 4 from 6
^{th} Nov 2018 (corrected version as of Nov 6^{th} 16:45)

## Lecture notes

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

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

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