Logica

This course is in Italian, so this webpage is in Italiano.

Programma

1. Introduzione
   1. aspetti burocratici e amministrativi
      storia della logica
      relazione con l’informatica
2. Logica Proposizionale
   1. concetto di induzione strutturale
      sintassi
      deduzione naturale
   2. esempi di dimostrazione formale
   3. semantica a tavole di verità
      insiemi minimali di connettivi
      forme normali disgiuntive e congiuntive
      soddisfacibilità
   4. algebre di Boole
   5. teorema di correttezza
      schema della dimostrazione e correttezza di semplici programmi
   6. completezza
3. Logica al Primo Ordine
   1. sintassi
      sostituzione
      calcolo naturale
   2. esempi di deduzione
      esempi di formalizzazione
   3. semantica alla Tarski
      teorema di correttezza
   4. risoluzione
      unificazione
      programmazione logica mediante esempi
4. Teoria dei Tipi Semplici
   1. λ-calcolo
      sintassi
      riduzioni
   2. esempi: tipi di dati in λ-calcolo
      esempi: programmazione funzionale
   3. teoria dei tipi semplici
      sintassi
      riduzioni
   4. logica proposizionale intuizionista
      sintassi
      potenza espressiva
   5. isomorfismo Curry-Howard
      dimostrazioni come programmi
      correttezza per costruzione
   6. normalizzazione forte
      terminazione di programmi
5. Risultati limitativi
   1. teorema di compattezza
      esempi di modelli non standard
   2. aritmetica di Peano
      codifica
   3. lemma di punto fisso
      teorema di incompletezza di Gödel
   4. funzioni calcolabili
      tesi di Church-Turing
      teorema di Cantor
      esistenza di funzioni incalcolabili
   5. incalcolabilità e incompletezza
      esempi: minori di grafi

Materiale didattico

Le slides delle lezioni:

2022/23

2021/22

2020/21

Un eserciziario sulla dimostrazione in calcolo naturale.

Il corso dell’anno accademico 2020/21 è anche disponibile online.

Il corso di Mathematical Logic nel corso di Laurea magistrale in Matematica mette a disposizione materiale che viene in parte riutilizzato in questo corso.

I temi d’esame:

Data	Testo	Soluzione
Esempio	pdf	pdf
10 giugno 2021	pdf	pdf
22 giugno 2021	pdf	pdf
22 luglio 2021	pdf	pdf
7 settembre 2021	pdf	pdf
3 febbraio 2022	pdf	pdf
18 febbraio 2022	pdf	pdf
10 giugno 2022	pdf	pdf
1 luglio 2022	pdf	pdf
22 luglio 2022	pdf	pdf
2 settembre 2022	pdf	pdf
27 gennaio 2023	pdf	pdf
17 febbraio 2023	pdf	pdf

Calendario degli esami

• 15 giugno 2023
• 5 luglio 2023
• 21 luglio 2023
• 4 settembre 2023