Marco Benini

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.
Un eserciziario sulla dimostrazione in calcolo naturale.
Il corso di Mathematical Logic nel corso di Laurea magistrale in Matematica mette a disposizione materiale che viene in parte riutilizzato in questo corso. Si consiglia di guardare la pagina dei video di quel corso.

I temi d’esame:

Data Testo Soluzione
Esempio pdf pdf