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.