LOGICS AND REASONING

Obiettivi formativi

Obiettivi generali: Il corso ha l'obiettivo di introdurre gli studenti ai risultati e ai metodi fondamentali della Logica Matematica con particolare attenzione alla loro applicazione nell'ambito dell'Informatica. Obiettivi specifici: L'obiettivo del corso è duplice. In primo luogo si intende dotare lo studente di una conoscenza rigorosa e di una capacità di applicare quei risultati e metodi della Logica Matematica che trovano applicazione in numerose aree dell'Informatica. D'altra parte si intende offrire allo studente una strumenti e conoscenze fondamentali per intraprendere un percorso di ricerca in Informatica Teorica. Conoscenze e comprensione: Il corso mira a dotare lo studente di una conoscenza rigorosa degli argomenti del corso attraverso lo studio delle dimostrazioni e la produzione di argomenti rigorosi nello svolgimento degli esercizi. Particolare attenzione è data alla motivazione concettuale, alla dimostrazione rigorosa e alla applicabilità dei risultati trattati nel corso. Applicare conoscenza e comprensione: I metodi della logica matematica hanno un ruolo fondamentale in diverse aree dell'Informatica quali la Teoria della Complessità, la Teoria delle Basi di Dati, l'Intelligenza Artificiale. Si mira a stimolare nello studente la capacità di applicare in vari contesti dell'informatica i metodi e i risultati studiati. Capacità di giudizio: Viene stimolata la partecipazione attiva alle lezioni ed esercitata l'autonomia di giudizio attraverso l'assegnazione di esercizi e problemi. Capacità di comunicazione: Lo studente può scegliere di dare l'esame finale in forma di presentazione seminariale davanti alla classe di un risultato concordato con il docente. Capacità di apprendimento: I metodi di analisi e formalizzazione acquisiti durante il corso trovano applicazione in diverse aree dell'Informatica. L'esercizio di formalizzazione e problem-solving durante il corso rinforza le capacità di apprendimento e acquisizione di nuove competenze.

Canale 1
GIUSEPPE PERELLI Scheda docente

Programmi - Frequenza - Esami

Programma
Parte 1 (Calcolo proposizionale e Logica del Primo Ordine) - Fondamenti: Logica predicativa, strutture e modelli. Teorie. Definibilità, completezza, decidibilità, esempi di teorie complete, eliminazione dei quantificatori, isomorfismo ed equivalenza elementare di strutture. - Teoria dei Modelli Finiti: esprimibilità di query in varie logiche. Metodi per dimostrare la non-esprimibilità di query, giochi di Ehrenfeucht-Fraissé, condizioni di back and forth, località di Gaifman, caratterizzazione logica di classi di complessità (Teorema di Fagin su NP). - Indecidibilità: indecidibilità della validità (Teoremi di Church e Trakhtenbrot), indecidibilità della verità aritmetica (Teoremi di Gödel), Gerarchia Aritmetica, computazione con oracoli, Teoremi di Post, teoremi con istanze calcolabili senza soluzioni calcolabili (Teoremi di König, Ramsey, Hindman). Parte 2 (Logica Modale) - Concetti di base: Strutture relazionali; Linguaggi modali; Modelli e frame; Frame generali; Relazioni di conseguenza modale; Logiche modali normali - Modelli: Risultati di invarianza; Bisimulazione; Modelli finiti; La traduzione standard - Frame: Definibilità dei frame; Definibilità dei frame e logica del secondo ordine: Proprietà definibili e indefinibili; Frame finiti; Corrispondenza automatica con la Logica del primo ordine
Prerequisiti
Elementi di Teoria degli Insiemi e Matematica Discreta.
Testi di riferimento
1. Introduction to Mathematical Logic, Elliot Mendelson (https://www.karlin.mff.cuni.cz/~krajicek/mendelson.pdf) 2. A concise introduction to Mathematical Logic, W. Rautenberg (Springer 2006) 3. Elements of Finite Model Theory, L. Libkin (https://homepages.inf.ed.ac.uk/libkin/fmt/fmt.pdf) 4. Modal Logic, P. Blackburn, M. de Rijke, Y. Venema (Cambridge University Press) 5. Reasoning about Knowledge, R. Fagin, J. Halpern, Y. Moses, M. Vardi (MIT Press)
Frequenza
Non obbligatoria ma fortemente consigliata, soprattutto per il superamento degli Homework.
Modalità di esame
La prova è composta da un set di "Homework" svolti durante il corso (40%) e da una presentazione di un argomento (60%) sugli stessi temi di quelli presentati al corso.
Modalità di erogazione
Didattica frontale.
LORENZO CARLUCCI Scheda docente
  • Codice insegnamento10620665
  • Anno accademico2025/2026
  • CorsoComputer Science - Informatica
  • CurriculumCurriculum unico
  • Anno1º anno
  • Semestre2º semestre
  • SSDINF/01
  • CFU6