LOGICA MATEMATICA

Crediti: 
6
Settore scientifico disciplinare: 
LOGICA MATEMATICA (MAT/01)
Anno accademico di offerta: 
2016/2017
Semestre dell'insegnamento: 
Secondo Semestre
Lingua di insegnamento: 

Italiano

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)

Metodi didattici

Lezioni frontali

Modalità verifica apprendimento

Esame orale