VVZ API is not affiliated with ETH Zurich. Data might be outdated or incorrect. Please view the official ETHZ Vorlesungsverzeichnis for binding information.

252-0007-00L 4 Credits BSC D-INFK

Logic

Logik

Lecturers: Dr. Stefan Wolf
Examiners: Prof. em. Dr. Ueli Maurer
VVZ CR n/a

Last Updated: 2026-02-05 15:14:28

Abstract

Introduction to propositional logic, predicate logic and logic programming (Prolog).

Objective

Understanding the basic notions of logic. Learning how to translate natural language sentences into logical formulas. Learning how to read logical formulas and how to draw the right conclusions. Learning how to use first-order logic as a universal specification language. Lay the foundations for applications of logic in Computer Science. Examples are hardware design (Boolean functions), complexity theory (SAT/NP), theory of computation (decidability problem), data bases (logic as a query language), software engineering (logic as a specification language).

Content

Part I. Propositional logic: propositions, logical operators, syntax of propositional logic, formulas, semantics of propositional logic, truth tables, satisfiability, validity, logical consequence, deductive systems, axioms, proof rules, formal derivations, Boolean functions, truth functional completeness, normal forms, negation normal form, disjunctive normal forms, conjunctive normal form, clause sets, automatic proof procedures. Part II. Predicate logic: predicates, quantifiers, equality, syntax of first-order logic, semantics of first-order logic, structures, models, isomorphic structures, finite structures, quantifier rules, deductive systems, logical calculi, undecidability of first-order logic, Peano arithmetic, induction. Part III. Logic programming: Horn clauses, Datalog, queries, unification, substitutions, most general unifiers, SLD-resolution, Prolog, syntax of lists, list predicates, back-tracking, declarative programming.

Resources

Lecture Notes

ja

Literature

K. R. Apt: From Logic Programming to Prolog. International Series in Computer Science. Prentice Hall, 1996. [Introduction to the foundations of logic programming and its applications to Prolog.] J. Barwise and J. Etchemendy: Language Proof and Logic. CSLI Publications, 2000. [Introduction to first-order logic for students of philosophy, computer science and mathematics. Includes the learning software Tarki's World, Fitch, Bool.] D. van Dalen: Logic and Structure. Springer-Verlag, 3rd edition, 1994. [Thorough introduction to elementary classical logic with connections of logic to other parts of mathematics.] H.-D. Ebbinghaus, J. Flum, and W. Thomas: Mathematical Logic. Springer-Verlag, 2nd edition, 1996. [Introduction to mathematical logic and model theory for students of mathematics.] U. Schönig: Logik für Informatiker. Spektrum Akademischer Verlag, 5. Auflage, 2000. [A classical introduction to logic for computer science students. Unfortunately the book is based too much on resolution.] R. Stärk: Logik. ETH Zürich, 2002. [Lecture notes for Logik]

General Information

Language
German
Levels
BSC
Frequency
Yearly recurring

Examination

Type
session examination
Mode
written 120 minutes
Aids
Keine. In der Prüfung wird eine Zusammenfassung des Skriptes verteilt, die schon zu Beginn der Vorlesung bekannt gegeben wird.

Course Components

Type Title Time & Place Hours
lecture Logik
  • Wed 10:15-12:00 (HG F 5)
2 h weekly
exercise Logik
  • Wed 12:15-13:00 (IFW A 32.1)
  • Wed 13:15-14:00 (CAB G 52)
  • Wed 13:15-14:00 (CLA E 4)
  • Wed 13:15-14:00 (IFW A 32.1)
  • Wed 13:15-14:00 (IFW C 42)
  • Wed 13:15-14:00 (ML F 34)
  • Wed 13:15-14:00 (ML H 37.1)
  • Wed 13:15-14:00 (ML J 34.3)
1 h weekly

Offered In