Logic and Computability
Table of Content
Content
In this course, you will learn to understand logic formulas, to use concise mathematical notations, to formulate and solve problems in formal languages, and to reason with logics manually and algorithmically. We will teach logic proof systems, and you will gain the ability to construct logic proofs on your own and you will master common proof techniques of computer science. Finally, we discuss the fundamental limitations of the computing abilities of computers and discuss selected decision problems and the underlying algorithms.
The content of this lecture includes:
- Syntax and semantics of logic formulas in propositional logic and predicate logic (first-order logic)
- Basics of logical reasoning (natural deduction)
- Combinational equivalence checking
- Propositional satisfiability problem – DPLL algorithm – Resolution proofs
- Binary Decision Diagrams
- Decidability, Halteproblem
- First-Order Theories
- Satisfiability modulo Theories
Material
IMPORTANT-INFORMATION
- Previous course information: SS2020
Administrative Information
Pen and Paper Exercises and Programming Exercises, Oral Exercise Interviews (possibly virtual), and Written or Oral Exam (possibly virtual)
Lecture Dates
| Date | Begin | End | Location | Event | Type | Comment |
|---|---|---|---|---|---|---|
| 2021/03/05 | 10:00 | 12:00 | HS i13 | Abhaltung | VO | fix/ |
| 2021/03/12 | 10:00 | 12:00 | HS i13 | Abhaltung | VO | fix/ |
| 2021/03/19 | 10:00 | 12:00 | HS i13 | Abhaltung | VO | fix/ |
| 2021/03/19 | 13:00 | 14:00 | Seminarraum | Abhaltung | KU | fix/ |
| 2021/03/19 | 14:00 | 15:00 | Seminarraum | Abhaltung | KU | fix/ |
| 2021/03/26 | 10:00 | 12:00 | HS i13 | Abhaltung | VO | fix/ |
| 2021/03/26 | 13:00 | 14:00 | Seminarraum | Abhaltung | KU | fix/ |
| 2021/03/26 | 14:00 | 15:00 | Seminarraum | Abhaltung | KU | fix/ |
| 2021/04/16 | 10:00 | 12:00 | HS i13 | Abhaltung | VO | fix/ |
| 2021/04/16 | 13:00 | 14:00 | Seminarraum | Abhaltung | KU | fix/ |
| 2021/04/16 | 14:00 | 15:00 | Seminarraum | Abhaltung | KU | fix/ |
| 2021/04/23 | 10:00 | 12:00 | HS i13 | Abhaltung | VO | fix/ |
| 2021/04/23 | 10:00 | 12:00 | HS i13 | Abhaltung | VO | fix/ |
| 2021/04/23 | 13:00 | 14:00 | Seminarraum | Abhaltung | KU | fix/ |
| 2021/04/23 | 14:00 | 15:00 | Seminarraum | Abhaltung | KU | fix/ |
| 2021/04/30 | 10:00 | 12:00 | HS i13 | Abhaltung | VO | fix/ |
| 2021/04/30 | 13:00 | 14:00 | Seminarraum | Abhaltung | KU | fix/ |
| 2021/04/30 | 14:00 | 15:00 | Seminarraum | Abhaltung | KU | fix/ |
| 2021/05/21 | 10:00 | 12:00 | HS i13 | Abhaltung | VO | fix/ |
| 2021/05/21 | 13:00 | 14:00 | Seminarraum | Abhaltung | KU | fix/ |
| 2021/05/21 | 14:00 | 15:00 | Seminarraum | Abhaltung | KU | fix/ |
| 2021/05/28 | 10:00 | 12:00 | HS i13 | Abhaltung | VO | fix/ |
| 2021/05/28 | 13:00 | 14:00 | Seminarraum | Abhaltung | KU | fix/ |
| 2021/05/28 | 14:00 | 15:00 | Seminarraum | Abhaltung | KU | fix/ |
| 2021/06/04 | 10:00 | 12:00 | HS i13 | Abhaltung | VO | fix/ |
| 2021/06/04 | 13:00 | 14:00 | Seminarraum | Abhaltung | KU | fix/ |
| 2021/06/04 | 14:00 | 15:00 | Seminarraum | Abhaltung | KU | fix/ |
| 2021/06/11 | 10:00 | 12:00 | HS i13 | Abhaltung | VO | fix/ |
| 2021/06/11 | 13:00 | 14:00 | Seminarraum | Abhaltung | KU | fix/ |
| 2021/06/11 | 14:00 | 15:00 | Seminarraum | Abhaltung | KU | fix/ |
| 2021/06/18 | 10:00 | 12:00 | HS i13 | Abhaltung | VO | fix/ |
| 2021/06/18 | 13:00 | 14:00 | Seminarraum | Abhaltung | KU | fix/ |
| 2021/06/18 | 14:00 | 15:00 | Seminarraum | Abhaltung | KU | fix/ |
| 2021/06/25 | 13:00 | 15:00 | Seminarraum IGI | Abhaltung | KU | fix/Zweite Teilprüfung LuB Übung |
| 2021/06/25 | 13:00 | 15:00 | Seminarraum CGV | Abhaltung | KU | fix/Zweite Teilprüfung LuB Übung |
| 2021/06/25 | 13:00 | 14:00 | Seminarraum | Abhaltung | KU | fix/ |
| 2021/06/25 | 13:00 | 15:00 | Seminarraum IST | Abhaltung | KU | fix/Zweite Teilprüfung LuB Übung |
| 2021/06/25 | 14:00 | 15:00 | Seminarraum | Abhaltung | KU | fix/ |
| 2021/07/02 | 09:00 | 11:30 | HS i13 | Abhaltung | KU | fix/Ersatztermin für erste und zweite Übungsprüfung. (Teilnahme nur möglich bei entschuldigtem Fernbleiben einer Teilprüfung) |
Lecturers
Könighofer
PostDoc