Corso di Logica Matematica II

Prof. Silvio Ghilardi

Laurea Magistrale in Matematica - a.a. 2014/2015


AVVISI:

Il programma qui riportato è valido fino all'a.a 2014/2015. Nell'a.a. 2015/2016 il corso sarà tenuto dal prof. Marra e verrà contemporaneamente attivato nel secondo semestre un altro corso di area logica ("Metodi per il ragionamento Automatico") tenuto dal prof. Ghilardi.


Caratteristiche del corso | Programma del corso | Orari | Modalità d'esame | Materiali didattici | Appelli d'esame

  1. Caratteristiche del corso
  2. Il corso si propone di studiare i fenomeni di decidibilità e di indecidibilità che emergono sia nei domini matematici familiari che nelle applicazioni informatiche. A tale scopo si prenderanno in esame da un lato i risultati limitativi classici (derivanti dai teoremi di Goedel) e dall'altro le recenti e meno recenti acquisizioni relative alle procedure di decisione nelle teorie elementari.


  3. Programma del corso
  4. Gli argomenti svolti nella parte finale del corso sono soggetti a modifiche da definire nel corso delle lezioni.
    1. Elementi di teoria della calcolabilità. Rappresentabilità delle funzioni ricorsive nei sistemi formali.
    2. Goedelizzazione. Teoremi di Goedel, teorema di Church.
    3. Procedure di decisione per frammenti senza quantificatori in teorie di uso corrente (array, liste, ecc).
    4. Procedure di decisione tramite eliminazione dei quantificatori in domini numerici: l'algoritmo di Fourier-Motzkin per l'aritmetica lineare reale, l'aritmetica di Presburger. Decidibilità dell'aritmetica reale tramite il metodo di Muchnik; cenni sulla decomposizione algebrica cilindrica.
    5. Gli SMT-solvers e il progetto SMT-LIB. Applicazioni al model checking per sistemi a stati infiniti.


  5. Orari delle lezioni
  6. L'orario di ricevimento del prof. Ghilardi è il venerdì mattina alle ore 11.30.


  7. Modalità d'esame
  8. L'esame sarà costitutito da un colloquio. Sarà possibile concordare in tutto o in parte un programma specifico a fronte di esigenze particolari.


  9. Materiali didattici
  10. Si veda il sito ARIEL a questo indirizzo.


  11. Appelli d'esame
  12. Su appuntamento, con iscrizione al SIFA.

    Ultimo aggiornamento: 23/2/2015