Automated Deduction (2007/2008)

Course partially running

Course code
Name of lecturer
Maria Paola Bonacina
Number of ECTS credits allocated
Other available courses
Academic sector
Language of instruction
2° Q dal Jan 10, 2008 al Mar 12, 2008.
Web page

Lesson timetable

2° Q
Day Time Type Place Note
Tuesday 10:30 AM - 11:30 AM lesson Lecture Hall I  
Thursday 10:30 AM - 12:30 PM lesson Lecture Hall I  
Friday 10:30 AM - 12:30 PM lesson Lecture Hall I  

Learning outcomes

The class presents the central problems in automated reasoning and a selection of the most important theoretical methods and state-of-the-art systems to approach them. The student learns how to design, apply and evaluate methods and systems for automated reasoning. After the course, the student is ready to work on an MS thesis in the area of automated reasoning. Pre-requisites: undergraduate-level knowledge of logic and algorithms.


Automated reasoning: proof procedures as semi-decision procedures for validity or theorem-proving strategies. Inference system + search plan = theorem-proving strategy. The Herbrand theorem. Ordering-based strategies. Expansion inference rules: resolution, paramodulation, superposition. Contraction inference rules: subsumption, simplification by rewriting. Search plans. Algorithmic reasoning: proof procedures as decision procedures for satisfiability. First-order theories and decidable problems in first-order theories. Decision procedures and their combination. When theorem-proving strategies are decision procedures. Design and use of automated reasoners.

Reference books
Author Title Publisher Year ISBN Note
Ricardo Caferra, Alexander Leitsch, Nicolas Peltier Automated Model Building (Edizione 1) Kluwer Academic Publishers 2004 1-4020-265 Altro libro di riferimento.
Rolf Socher-Ambrosius, Patricia Johann Deduction Systems (Edizione 1) Springer Verlag 1997 0387948473 Testo adottato.
Raymond M. Smullyan First-order logic Dover Publications 1995 0486683702 Altro libro di riferimento.
Allan Ramsay Formal Methods in Artificial Intelligence (Edizione 1) Cambridge University Press 1989 0521424216 Altro libro di riferimento.
Chin-Liang Chang, Richard Char-Tung Lee Symbolic Logic and Mechanical Theorem Proving (Edizione 1) Academic Press 1973 0121703509 Testo adottato.
Aaron R. Bradley, Zohar Manna The Calculus of Computation - Decision Procedures with Applications to Verification (Edizione 1) Springer 2007 9783540741 Testo adottato.
Alexander Leitsch The Resolution Calculus (Edizione 1) Springer 1997 3540618821 Altro libro di riferimento.

Assessment methods and criteria

Mode with partial tests:
this mode applies only to the exam right at the end of the class, that is for the exam session of March-April, since the class is scheduled in the II term. In this mode, the exam consists of a written 2h test (C) and an individual project (P) to be developed either at home or in the lab during the course. The project comprises writing a short project report (max 4 pages). The final grade is given by 50% C + 50% P. After the first exam session since the end of classes, P and C are no longer valid. Those who choose to take the exam in this mode are supposed to register for the March-April session.

Single-test mode:
in this mode, the exam consists of a single written test, whose difficulty is equivalent to that of C + P, and whose grade determines alone the final grade. This mode applies to all exam sessions. However, if a student takes test E, the grade given by 50% C + 50% P is lost.

the partial test C will be administered in the same date, time and place as test E of the March-April session (of course contents and duration of the two tests will be different).
Project P will be submitted electronically, except for the written report that will have to be handed-in before taking the partial test C.

for each session the date of the exam is given by the date of the written test (E); to register it is sufficient to register for the written test. Students are not allowed to "reject" grades and all grades will be registered. Students dissatisfied with their performance can withdraw: in order to withdraw it is sufficient not to hand-in C or E.