Logic and Computability

Course Number IND04033UF and IND05034UF | Sommersemester 2020

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
  • Craig Interpolation
  • Binary Decision Diagrams
  • Decidability, Halteproblem
  • First-Order Theories
  • Satisfiability modulo Theories

Material

Here you find all information and material about the lecture and the practicals: Teaching Wiki. We will upate the slides and the tasks for the practicals during the semester and they are not considered to be complete until the end of the semester.

Administrative Information

Previous Knowledge

basic programming skills (understanding pseudo-code) definition and working principle of Turing machines basic knowledge in complexity theory

Prerequisites Curriculum

See position in the curriculum

Objective

Understanding the construction, interpretation, and representation of logic formulas, understanding logic proof systems, ability to construct logic proofs, understanding the fundamental limitations of the computing abilities of digitial computers, mastering common proof techniques of computer science, understanding selected decision problems and the underlying algorithms

Language

English

Teaching Method

Lecture, partially supported by PowerPoint presentations and blackboard (exercises and examples)

How to get a grade

Default: written exam. Oral exams are possible at the candidates discretion. If less than four candidates are registered for a particular exam date, this exam will be conducted orally.

Registration

https://online.tugraz.at/tug_online/sa.gruppen_einteilung?clvnr=228545&corg=983

Lecture Dates

Date Begin End Location Event Type Comment
2020/03/20 13:00 14:00 Seminarraum Abhaltung KU fix/
2020/03/20 14:00 15:00 Seminarraum Abhaltung KU fix/
2020/03/27 13:00 14:00 Seminarraum Abhaltung KU fix/
2020/03/27 14:00 15:00 Seminarraum Abhaltung KU fix/
2020/04/03 13:00 14:00 Seminarraum Abhaltung KU fix/
2020/04/03 14:00 15:00 Seminarraum Abhaltung KU fix/
2020/04/24 13:00 14:00 Seminarraum Abhaltung KU fix/
2020/04/24 14:00 15:00 Seminarraum Abhaltung KU fix/
2020/05/08 13:00 14:00 Seminarraum Abhaltung KU fix/
2020/05/08 14:00 15:00 Seminarraum Abhaltung KU fix/
2020/05/15 13:00 14:00 Seminarraum Abhaltung KU fix/
2020/05/15 14:00 15:00 Seminarraum Abhaltung KU fix/
2020/05/29 13:00 14:00 Seminarraum Abhaltung KU fix/
2020/05/29 14:00 15:00 Seminarraum Abhaltung KU fix/
2020/06/05 13:00 14:00 Seminarraum Abhaltung KU fix/
2020/06/05 14:00 15:00 Seminarraum Abhaltung KU fix/
2020/06/12 13:00 14:00 Seminarraum Abhaltung KU fix/
2020/06/12 14:00 15:00 Seminarraum Abhaltung KU fix/
2020/06/19 13:00 14:00 Abhaltung KU fix/
2020/06/19 14:00 15:00 Abhaltung KU fix/
2020/06/26 13:00 14:00 Seminarraum Abhaltung KU fix/
2020/06/26 14:00 15:00 Seminarraum Abhaltung KU fix/

Lecturers

Bettina Könighofer
Bettina
Könighofer

PhD Candidate

View more
Erwin Heiner Peterlin
Erwin Heiner
Peterlin


View more