# LOGICS FOR INFORMATICS

## LOGICS FOR INFORMATICS

Docenti:
Giovanna D’agostino
Totale crediti: 6
Tipologia: Affine/Integrativa
Periodo didattico: Primo Periodo
Lingua insegnamento: INGLESE
Prerequisiti. A bachelor university course in elementary mathematics and logic.

## OBIETTIVI FORMATIVI

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.

## CONTENUTI

– 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

## TESTI DI RIFERIMENTO

Teaching material on the university elearning page

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