Obiettivi formativi
Nozioni di base di logica del primo ordine
Prerequisiti
Nozioni di bse di algebra e di programmazione
Contenuti dell'insegnamento
Corso isitituzionale di Logica Matematica.
Calcolo proposizionale, logica del primo ordine, ricorsivita' e calcolabilita', teoremi di incompletezza.
Programma esteso
1) Calcolo proposizionale:
Formule proposizionali, valutazioni Booleane; teorema di compattezza, forme
normali, formule come funzioni Booleane.
2)Logica del Primo Ordine:
Strutture, termini, formule, modelli; omomorfismi; espansioni del linguaggio,
sostituzione; esempi di teorie; insiemi definibili.
3) Deduzione e completezza:
Regole di deduzione; teorema di completezza (lemma di Lindembaum, costanti di
Henkin); teoremi di compattezza e di Lowenheim-Skolem; esempi di teorie complete; classi elementari
4) Ricorsione
Funzioni e insiemi ricorsivi; codifiche di tuple; insiemi ricorsivamente enumerabili; teorema di Post; quantificatori limitati; insiemi aritmetici
5) Computabilità
Macchine di Turing (cenni);
macchine a registri di memoria; tesi di Church per MRM; MRM universale;
6) Decidibilità
Codifiche di formule, chiusura deduttiva di una teoria, teorie decidibili; esempi di teorie decidibili
7) Indecidibilità
Teorema di Tarski sulla non-definibilità della verità aritmetica; teoria Q di Robinson; rappresentabilità in Q; primo teorema di Godel;
assiomi di Peano al primo ordine; secondo teorema di Godel.
Bibliografia
Note del corso
Note del corso di A. Berarducci
Toffalori-Cintioli "Logica Matematica" McGraw-Hill (2000)