Insegnamento mutuato da: B012975 - LOGICA MATEMATICA Laurea Magistrale in MATEMATICA Curriculum GENERALE
Lingua Insegnamento
Italiano
Contenuto del corso
Logica booleana. Semantica herbrandiana e tarskiana. Deduzioni valide e non valide. Teorema di completezza di Goedel. Cenni di teoria dei numeri cardinali. Teorema di Loewenheim, compattezza della logica dei predicati con eguaglianza.
Test di Los-Vaught. Esempi di teorie complete: DLO, TFDAG (cenni)
Primo teorema di incompletezza di Goedel
P. Halmos, "Naive set theory", 1960
Gli appunti del prof. A. Berarducci per la parte sul teorema di incompletezza di Goedel
Boolos et al. "Computability and logic"
P.Smith "An introduction to Gödel's theorems" (CUP 2013) e le note di accompagnamento "Gödel without too many tears"
Obiettivi Formativi
Conoscenze: I teoremi fondamentali della logica
Competenze acquisite: la costruzione di refutazioni e domostrazioni formali nella logica proposizionale e predicativa
Capacità acquisite al termine del corso: L’uscita dall’analfabetismo logico, cosi’ comune tra i matematici. Capacita’di scrivere dimostrazioni formali, anche come oggetti grafici. Conoscenza dei teoremi di Goedel, di compattezza e completezza
CFU: 9
Numero di ore totali del corso: 225
Numero di ore per studio personale e altre attività formative di tipo individuale: 153
Numero di ore relative alle attività in aula: 72
Numero di ore relative ad attività di laboratorio (lezioni in laboratorio): 0
Numero di ore relative ad attività di esercitazioni (in laboratorio e in campo): 0
Numero di ore relative ad attività seminariali: 0
Numero di ore relative ad attività di stage: 0
Numero di ore per prove in itinere: 0
Altre Informazioni
Frequenza delle lezioni ed esercitazioni:
Non obbligatoria
Modalità di verifica apprendimento
Esame orale
Programma del corso
* * * Logica Proposizionale
* Sintassi e semantica
connettivi booleani e le tavole di verità
logica di Boole: sintassi
le formule booleane
non ambiguità della sintassi
definizione di valutazione booleana e proprietà: estensione unica alle L-formule proposizionali
tautologia, contraddizione, soddisfacibilita'
equivalenza tra le formule
conseguenza logica
L-teoria proposizionale
modelli di una teoria proposizionale
materiale preparatorio (lemma 1 e lemma 2 ) per il teorema di Compattezza
dimostrazione del Teorema di Compattezza:
caso numerabile e caso non numerabile utilizzando l'assioma della scelta
Lemma di Tukey e Zorn e la loro equivalenza
Applicazione al Teorema di compattezza (colorazione dei grafi)
proprietà dei connettivi booleani sotto equivalenza logica
Forme Normali
* Logica Booleana e logica delle clausole
* * * Logica dei Predicati
* Formule del primo ordine
sintassi: termini, formule atomiche, clausole, formule CNF
la semantica di Tarski: tipi e modelli
assiomi per l'eguaglianza
definizione di sottostruttura
sottoformule
semantica dei termini
sostituzione di termini al posto di variabili
chiusura deduttiva
formule equivalenti modulo teoria
espansione e restrizione del linguaggio
Universo di Herbrand
Teorema di Correttezza
Cenni di aritmetica dei numeri cardinali
Cardinalità dell'Universo di Herbrand
Teorema di completezza di Goedel
Teorema di compattezza
Teorema di Löwenheim-Skolem
* Esempi di teorie e strutture
Anelli, Gruppi, DLO, ACF
* teorie complete
definizione
esempi di teorie non complete:
Gruppi, Gruppi Abeliani
* teorie K-categoriche
Test di Los-Vaught
Enunciato del Teorema di Morley
* esempi di teorie K-categoriche per qualche K:
* classi elementari
* conseguenze del teorema di compattezza
* * * Teorema di incompletezza di Goedel
* Calcolabilità e ricorsione (cenni)
* insiemi aritmetici
* Tutti gli insiemi ricorsivi sono aritmetici
* Teorema di Tarski: la verità non è aritmetica
* La teoria Q di Robinson
* rappresentabilità di insiemi e funzioni
* Lemma di diagonalizzazione
* Primo teorema di incompletezza di Goedel