Prof. Alessandro Berarducci

Calcolo dei predicati, calcolabilità, complessità Richiami di teoria degli insiemi. Linguaggi formali. Il linguaggio del calcolo proposizionale e del calcolo dei predicati. Modelli di sistemi di assiomi. Il concetto semantico di conseguenza logica. Il concetto sintattico di dimostrazione formale: sistemi deduttivi. Teorema di completezza: equivalenza tra conseguenza logica e dimostrabilità formale. Conseguenze del teorema di completezza. Macchine di Turing e funzioni calcolabili. Insiemi decidibili e ricorsivamente enumerabili. Teorema di incompletezza di Godel. Problemi non risolubili algoritmicamente. Il problema della soddisfacibilità: primi cenni sul problema ``P = NP''. Classi di complessità computazionale.

Bibliografia: C. Toffalori e P. Cintioli, Logica Matematica, McGraw-Hill 2000.