Academic Year 2019-2020


Giovanna D’agostino
Total Course Credits: 6
Teaching Period: First Period
Teaching Language: Inglese
Prerequisites. A bachelor university course in elementary mathematics and logic.


This course aims to provide a landascape of the role of Logic in Computer Science.

The course is divided into three parts. In the first part Ehrenfeucht games are analized. The objective here is to get the student acquainted with game theory and to the concept of winning strategy, and to show the applications of game theory to the expressive power of first order logic. In the second part, finite state automata reading infinite words are introduced and used to prove some classical results on monadic second order logic. The objective here is to get the student acquainted with automata reading infinite words and with their expressive power. In the last part, non monotone logics are introduced and studied. The objective here is to show that there are settings where classical logic is not adequate and can be replaced by non monotone logic. 


– LOGIC AND GAMES. Mathematical definition of games. Strategies. Determinacy. Ehrenfeucht games and expressivity of First Order Logic.

-LOGIC AND VERIFICATION Beyond First Order Logic: S1S, Buchi automata and games. Temporal Logics.

-LOGIC AND ARTIFICIAL INTELLIGENCE Description Logics and non monotone reasoning


Teaching material on the university elearning page

(slides used in class, notes, interactive exercises, articles in english)