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.
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. |
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.
Notes:
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.
Registration:
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.
******** CSS e script comuni siti DOL - frase 9957 ********p>