# Formal Logic

## Where und When:

• Lecture: Tuesday 14:15-15:45 in T2-205
• Problem classes:
• Tuesday 16-18 in E0-180, tutor: Jonas Kalinski, or
• Wednesday 8-10 in U2-135, tutor: Oliver Tautz
• Written exam: Monday 10. February 2020 at 10:00 in H14
• Duration: 100 min
• Allowed tools: Pen, brain (no own paper, no cheat sheet)
• Typical problems would look like exercises 1, 5, 6, 9a, (10), 11, (12), 13, 14, 16, 18, (19), (22), 23, (26), 28, 30, 33, 34, (41), 44, 45, 48, 49, (50), 51.
• Second exam: oral exams, date can be negotiated, just write an email.
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 formulas) 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.

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