Automated reasoning (2017/2018)

Course code
Name of lecturer
Maria Paola Bonacina
Maria Paola Bonacina
Number of ECTS credits allocated
Academic sector
Language of instruction
I sem. dal Oct 2, 2017 al Jan 31, 2018.

Lesson timetable

Go to lesson schedule

Learning outcomes

The class presents problems, methods and systems in automated reasoning. The treatment combines theoretical foundations with algorithmic and practical issues, emphasizing mechanization throughout. The student learns how to design, apply, and evaluate methods and systems for automated reasoning, with attention to applications in fields such as analysis, verification, synthesis of systems, artificial intelligence, mathematics, robotics.


Foundations of automated reasoning: theorem proving and model building. The problem of propositional satisfiability (SAT): the DPLL and CDCL procedures. The problem of validity in first-order logic: inference systems and search plans. Herbrand theorem. Instance-based inference systems: hyper-linking. Ordering-based inference systems: resolution and paramodulation/superposition. Subgoal-reduction based inference systems: model elimination, tableaux. Search plans: the given-clause algorithm; depth-first search with iterative deepening. Decision procedures for satisfiability modulo theories (SMT). Constraint reasoning. Design and use of general-purpose or special-purpose reasoners.

Reference books
Author Title Publisher Year ISBN Note
Daniel Kroening, Ofer Strichman Decision Procedures. An algorithmic point of view Springer 2008 978-3-540-74104-6
Rolf Socher-Ambrosius, Patricia Johann Deduction Systems (Edizione 1) Springer Verlag 1997 0387948473
Raymond M. Smullyan First-order logic Dover Publications 1995 0486683702
Chin-Liang Chang, Richard Char-Tung Lee Symbolic Logic and Mechanical Theorem Proving (Edizione 1) Academic Press 1973 0121703509
Aaron R. Bradley, Zohar Manna The Calculus of Computation - Decision Procedures with Applications to Verification (Edizione 1) Springer 2007 9783540741
Alexander Leitsch The Resolution Calculus (Edizione 1) Springer 1997 3540618821
Martin Davis The Universal Computer. The Road from Leibniz to Turing. Turing Centenary Edition. Taylor and Francis Group 2012 978-1-4665-0519-3

Assessment methods and criteria

First round: the grade is given by 25% C1 + 25% C2 + 50% P, where C1 is the midterm exam, C2 is the final exam, and P is a project.
Later rounds: the grade is given by 100% E, where E is a written exam, as hard as midterm, final, and project combined.
Attending all classes is crucial, however the exam rules are the same regardless of whether one attends or not.