# Logic

## News

• 19.09.: The repeat exam will take place as a written exam on 05.10.2017.
• 17.08.: In case only a small number of students register for the repeat exam, the written exam will be substituted by an oral exam. Dates for the oral exam: 25.09.–28.09.
• 28.07.: Exam review will be on Monday, 21.08., 14:00-16:00, in room MI 00.09.038.
• 24.07.: You are allowed to bring two hand-written cheat sheets (size DIN A4) to the exam. No other material is allowed, in particular printed sheets.
• 24.07.: There will be office hours (Sprechstunde) on Friday, 28.07., 14:00-16:00, in room MI 00.09.038. You can ask any question related to the lecture, exercises or homework.
• 27.06.: Two mistakes in the solution for sheets 7 (Exercise 7.1) and 8 (Exercise 8.3) have been fixed.
• 21.05.: Next tutorial on Tuesday, 23.05.2017, had to be moved to 14:00 because of SVV. Apologies for this inconvenience. Check your email inbox for information about the room.
• 15.05.: Next tutorial is Tuesday, 16.05.2017.
• 11.05.: Clarified bonus.
• 08.05.: The next tutorial is Wednesday, 10.05.2017, starting 14:30.
• 18.04.: Note the changed tutorial details. Due to the high number of class enrollments, we will reschedule the first four tutorials to Wednesday, 14:30–16:00, in Intermishörsaal 1. First tutorial: Wednesday, 26.04.
• Website created

## Excercises

### Homework Bonus

There will be graded homework assignments. Anyone who achieves more than 50% of the homework score gets awarded a bonus of 0.3 on the final exam's grade, provided the exam is passed.

### Submission

Typically before the tutorial in the week after (see sheet). Submission at the start of the tutorial or to the tutor's email address.

## Contents

The course assumes that you have had a basic introduction to logic already and are familiar with the following topics: syntax and semantics of both propositional and first-order logic; disjunctive and conjunctive normal forms; basic equivalences of propositional and first-order logic. These topics will only be refreshed briefly at the beginning of the course.

The main topics of the course:

• Proof theory: sequent calculus, natural deduction, resolution; their soundness and completeness; translations between proof systems.
• Meta-theory of first order logic: compactness, model theoy, undecidability, incompleteness of arithmetic.
• Decision procedures for fragments of logic and arithmetic.

## Slides

Propositional logic:
First-order predicate logic:

## Literature

• Ebbinghaus, Flum, Thomas. Einführung in die mathematische Logik (English: Mathematical Logic).
• Herbert Enderton. A Mathematical Introduction to Logic.
• Melvin Fitting. First-Order Logic and Automated Theorem Proving.
• Jean Gallier. Logic for Computer Science.
• John Harrison. Handbook of Practical Logic and Automated Reasoning.
• Uwe Schöning. Logik für Informatiker (English: Logic for Computer Scientists).
• A. Troelstra and H. Schwichtenberg. Basic Proof Theory.