Stud.IP Uni Oldenburg
University of Oldenburg
16.06.2021 04:27:29
inf400 - Theoretical Computer Science: Logic (Complete module description)
Original version English PDF Download
Module label Theoretical Computer Science: Logic
Modulkürzel inf400
Credit points 6.0 KP
Workload 180 h
Institute directory Department of Computing Science
Verwendbarkeit des Moduls
  • Bachelor's Programme Computing Science (Bachelor) > Basismodule
  • Dual-Subject Bachelor's Programme Computing Science (Bachelor) > Wahlpflicht Theoretische Informatik (30 KP)
Zuständige Personen
Habel, Annegret (Prüfungsberechtigt)
Olderog, Ernst-Rüdiger (Prüfungsberechtigt)
Lehrenden, Die im Modul (Prüfungsberechtigt)
Prerequisites
Skills to be acquired in this module
Introduction to propositional logic, predicate logic, logic programming, and temporal logic

Professional competence
The students:
  • Know syntax, semantics and applications of propositional logic, predicate logic, logic programming, and temporal logic
  • Specify problems by using logical formulas
  • Solve questions concerning propositional formulas with truth tables
  • Draw conclusions in the field of propositional logic and predicate logic by means of natural deduction
  • Answer queries to logic programs by using SLD resolution
  • Perform model checking of Kripke structures with regard to CTL formulas algorithmically

Methodological competence
The students:
  • Recognize logic as a versatile tool in computer science

Social competence
The students:
  • Work together in small groups to solve problems
  • Present solutions to problems to groups of other students

Self-competence
The students:
  • Learn persistence in pursuing difficult tasks
  • Learn precision in writing down solutions
Module contents
The course introduces propositional, predicate and temporal logic. In computer science it is essential to have a good understanding of logic because the language of logical formulas is widely used in the field of computer science. For example, Boolean expressions appear in every programming language and in circuit design; Horn clauses are used in knowledge representation; predicate logic and temporal logic are used for specifying software and hardware. More recent applications such as interactive and automatic proving as well as the logic programming language PROLOG emphasize the tool character of logic in computer science.

The course introduces syntax, semantics, procedures, and calculi to prove the validity of formulas of propositional, predicate, and temporal logic. This is illustrated by many examples.
Central is the concept of logical consequence.

Topics:
  • Propositional logic: syntax and semantics, truth tables, natural deduction
  • Predicate logic: syntax and semantics, natural deduction
  • Logic programming: declarative and procedural semantics, unification algorithm (Robinson), SLD resolution, PROLOG
-Temporal logic CTL: syntax and semantics of Kripke structures, CTL model checking algorithm
Literaturempfehlungen
Essential:
  • Script "Logik" (in German), in its current edition

Recommended:
  • D. van Dalen: "Logic and Structure", Fourth Edition. Springer-Verlag, 2004.

Good secondary reading:
  • U. Schöning: "Logic for Computer Scientists“, Birkhäuser, 1994.
Links
Language of instruction German
Duration (semesters) 1 Semester
Module frequency jährlich
Module capacity unlimited
Modullevel / module level BC (Basiscurriculum / Base curriculum)
Modulart / typ of module Pflicht / Mandatory
Lehr-/Lernform / Teaching/Learning method V & Ü
Vorkenntnisse / Previous knowledge
Form of teaching Comment SWS Frequency Workload of compulsory attendance
Lecture
3.00 SoSe 42
Exercise or tutorial
1.00 SoSe 14
Präsenzzeit Modul insgesamt 56 h
Examination Prüfungszeiten Type of examination
Final exam of module
At the end of the lecture period
written exam or oral exam