Formal Methods

Course objectives

General outcomes: The objective of the course is to study the most important quality of software: correctness. Such a study concerns bot the static aspects (data) and the dynamic aspects (processes) of software, considering both how to conceptualize and model such aspects and how to verify them. The main tools used for such study are various forms of logic: first-order logic and description logics for the static aspects, Hoare Logic and dynamic and temporal logics of programs for the dynamic aspects. After a successful completion of the course, the student will have acquired techniques and methods to model and verify programs, both wrt data and processes. Specific outcomes: Knowledge and understanding: Learn the fundamentals of formal methods. The use of strict and formal specifications and their verification. Founding principles of logic in computer science logic and formal verification of data and processes. Applying knowledge and understanding: Being able to apply the acquired knowledge to perform analysis of the correctness of programs through rigorous and formal methods, both in relation to aspects relating to data and processes. Making judgements: Being able to evaluate the rigor of a given argument of correctness of the programs. Being able to choose the conceptual tools provided by logic and formal methods for the verification of both static and dynamic properties. Communication: The group activities in the classroom as well as group projects make the students able to communicate / share the acquired knowledge and to compare himself with others on the topics of the course. Lifelong learning skills: In addition to the competences provided by the study of the teaching material, the course teaches the students to deepen their knowledge of some of topics presented in the course, while working in a group, and concretely apply the concepts and techniques learned to specific case studies.

Channel 1
GIUSEPPE DE GIACOMO Lecturers' profile

Program - Frequency - Exams

Course program
Introduction. Introduction to formal methods, formal guarantees, review of propositional and first-order logic, model checking/querying and reasoning (satisfiability, validity, and logical implication). Tableaux for propositional and first-order logic. Analysis and verification of static aspects. Syntax and semantics of class-based conceptual diagrams such as UML Class Diagrams and Entity Relationship Diagrams. Verification of static properties. Use of first-order logic for automated reasoning on such diagrams. Chase for full dependencies for completing UML Class Diagrams instances. Abstract operational semantics and partial correctness. Abstract operational semantics for programs: evaluation semantics (whole computation) and transition semantics (single step of the computation). Hoare Logics, weakest precondition, invariants of programs. Partial correctness, total correctness. Transition system and fixpoints. Reactive/interactive programs (finite state), transition systems, reachability, bisimulation. Fixpoints, Knaster-Tarski theorem on least and greatest fixpoint, approximates for least and greatest fixpoint. Verification of dynamic systems. Verification of dynamic and temporal properties on transition systems: Safeness, Liveness, Fairness, Strong Fairness. Temporal logic for verification: LTL, CTL, CTL*, mu-calculus. Model checking for mu-calculus. Model checking for CTL via translation to mu-calculus. Model checking for LTL via automata. LTL satisfiability via Tableaux Focusing on finite traces. Regular Automata, Linear Temporal Logics on finite traces, LTLf, LDLf, Pure Past LTL, connections to automata, computing DFAs, Manipulating DFAs, Reasoning on finite traces. Reactive synthesis. Automated program synthesis, synthesis from specifications in Linear Temporal Logic on finite traces, game-theoretic view, arena and objective, adversarial reachability.
Prerequisites
Students taking this course should have knowledge of software modeling and design, relational databases, and basic notions of propositional and first-order logic as acquired in previous years' courses.
Books
Course slides 2025/2026 and additional readings available on the course web page.
Frequency
Attendance is not mandatory, but it is strongly encouraged.
Exam mode
Written exam with exercises on all topics covered in the course program.
Lesson mode
The course is delivered through frontal lectures.
  • Lesson code1038133
  • Academic year2025/2026
  • CourseArtificial Intelligence
  • CurriculumSingle curriculum
  • Year2nd year
  • Semester1st semester
  • SSDING-INF/05
  • CFU6