B027820 - LOGICA MATEMATICA

Italiano

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

D.Mundici, Logica: Metodo Breve, Springer 2011

Altri testi consigliati:

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"

Conoscenze: I teoremi fondamentali della logica
Competenze acquisite: la costruzione di refutazioni e dimostrazioni formali nella logica proposizionale e predicativa
Capacità acquisite al termine del corso: Capacita' di scrivere dimostrazioni formali, anche come oggetti grafici. Conoscenza dei teoremi di Goedel, di compattezza, completezza, e incompletezza

Insegnamenti contenenti i prerequisiti (vincolanti e/o consigliati)
Corsi vincolanti: Nessuno
Corsi raccomandati: conoscenze di base di algebra e di programmazione

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

Frequenza delle lezioni ed esercitazioni:
Non obbligatoria

Esame orale

* * * 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