Programma Definitivo

Logica matematica a.a.2006/2007
Docente: Borzacchini Luigi

PROGRAMMA DI ''LOGICA MATEMATICA'' 
CORSO DI LAUREA SPECIALISTICA IN INFORMATICA
A.A. 2006/2007 - PROF. LUIGI BORZACCHINI


1.Introduzione. La rappresentazione e il pensiero formale. Linguaggio e 
metalinguaggio. Sintassi e semantica. Dimostrazione e verità. Rappresentazione come 
linguaggio e come calcolo. Rappresentazione ed Interpretazione. 

2. Richiami di teoria dei linguaggi formali. Alfabeti ed Espressioni. Gerarchia di 
Chomskij: i linguaggi e le macchine (membership e parsing). Decidibilità e 
complessità.

3. Calcolo delle proposizioni. Proposizioni, Connettivi e Tavole di verità. Forme 
normali. Diagrammi di Venn. Calcolo alla Hilbert e Deduzione naturale. Teorema di 
deduzione. Correttezza, completezza, compattezza, consistenza, decidibilità. Forme 
normali. Linguaggio logico e linguaggio insiemistico. Intensione ed Estensione.

4. Calcolo dei predicati. Formule, Variabili, Predicati e Quantificatori. Calcolo 
alla Hilbert e Deduzione Naturale. Interpretazioni e modelli: semantica di Tarski. 
Teorie assiomatizzate. Teoria dell’infinito di Cantor. Universo di Herbrand. 
Teorema di completezza di Gödel. Teorema di Löwenheim-Skolem. Teorema di 
Compattezza. Calcolo dei predicati con uguaglianza.

5. Problema della decisione e risoluzione. General theorem prover e general problem 
solver. Metodo delle tavole semantiche. Correttezza e completezza del metodo. 
Decidibilità del metodo. Teorema di Skolem-Herbrand. Clausole e risoluzione. 

6. Logica e filosofia della matematica. I paradossi. Filosofia della matematica nel 
XX secolo: il dibattito tra Frege ed Hilbert. Logicismo, formalismo, intuizionismo. 
Il programma di Hilbert e la nascita della computer science.

7. Funzioni ricorsive. Il calcolo dei predicati con uguaglianza. Calcolo delle 
equazioni. Ricorsività primitiva, totale, parziale. Funzioni ricorsive e macchine 
di Turing. Insiemi ricorsivi e ricorsivamente enumerabili.

8. Teoremi limitativi. Problema dell’alt. Semidecidibilità del calcolo dei 
predicati. Altri problemi semidecidibili e indecidibili. Assiomatizzazione della 
aritmetica: teoria del successore e aritmetica di Peano. Rappresentabilità. Teoremi 
di incompletezza di Gödel. Cenni sulle teorie del second’ordine.


TESTI CONSIGLIATI

G. LOLLI. Introduzione alla logica formale. Il Mulino
Dispense su “La teoria degli insiemi di Cantor e la filosofia della matematica”
Torna su Torna