Programma dell'insegnamento di
Logica Matematica
Docente: prof. Ruggero Ferro
Obiettivo:
L'esistenza stessa dell'informatica dipende dalla capacità di rappresentare adeguatamente nozioni ed elaborarle attraverso opportune trasformazioni delle loro rappresentazioni. Detto altrimenti l'informatica dipende dalle distinzioni e legami tra semantica e sintassi. Lo scopo di questo insegnamento è l'evidenziazione e lo studio del rapporto tra semantica e sintassi, mettendo in luce potenzialità e limiti dei linguaggi formali.
Contenuto:
Richiami a strutture, linguaggi formali del primo ordine, definizione base di verità in una realizzazione, soddisfacibilità, validita', conseguenza logica. Il problema del controllo sintattico della soddisfacibilita'. Alberi di confutazione per l'analisi delle formule a blocchi. Insiemi di Hintikka. Teoremi di validita', di completezza e di compattezza rispetto agli alberi di confutazione. Teoremi di Lowenheim Skolem. Categoricita' e alfa categoricita'. Paradosso di Skolem. Linguaggi numerabili e alberi per l'analisi delle formule una ad una. Cenni alla deduzione naturale. Deduzione alla Hilbert. Teorema di deduzione. Insiemi massimali consistenti. Insiemi di Henkin. Teoremi di validita' e completezza per la deduzione alla Hilbert.
Testi consigliati:
Bell, Machover: "A course in Mathematical Logic". North Holland.
Note del docente.