Logical and Theoretical Foundations of CS


In this lecture the basics of mathematical logic and theory of computation are taught as well as the fundamental techniques of proving. The lecture starts with a profound introduction into propositional logic. This includes declarative sentences, natural deduction, propositional logic as a formal language, semantics of proposition logic, normal forms, and SAT solvers. This part is followed by a section in which the students learn how to apply these methods in theoretical computer science, namely in how to write a decent proof. This section covers not only different ways of proving a given claim but also shall give an intuition for proving - from the start to a nicely written proof. In the third part an introduction to predicate logic is given, namely predicate logic as a formal language, proof theory of predicate logic, and semantics of predicate logic. Afterwards again the students learn how to apply these formal methods to proofs they will have to write in their master's studies. In a fifth part this knowledge is deepened by an introduction to theory of computation. Here the Chomsky hierarchy builds the basis. With the knowledge about decidability, the last part of logic follows: the expressiveness of predicate logic. The last part contains the basics of complexity theory, namely the classes P, NP, and NPC. In all parts the main focus is on proving fundamental properties like associativity, commutativity, idempotency, etc. as well as soundness, completeness, and closure properties for getting a profound understanding of the connections between computability, decidability in computer science and the mathematical basis. Mathematical basics like sets, functions, relations including the main properties like injectivity, surjectivity, bijectivity, totality for functions, and symmetry, reflexivity, transitivity, (total) order for relations are assumed to be known. Literatur:

  • "Automata and Computability" by Dexter C. Kozen
  • "Logic in Computer Science, Second Edition" by Michael Huth, Mark Ryan
  • Voraussetzungen / Organisatorisches: Please register for the course at StudiDB and OLAT