B012975 - LOGICA MATEMATICA

Italiano

Completezza della procedura di Davis-Putnam per la logica booleana. Semantica herbrandiana e tarskiana. Skolemizzazione. Metodo refutazionale. 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.

D.Mundici, Logica: Metodo Breve, Springer 2011

Altri testi consigliati:
P. Halmos, "Naive set theory", 1960
M. Curzio, P. Longobardi, M. Maj "Lezioni di algebra" (cap. 1)

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

Insegnamenti contenenti i prerequisiti (vincolanti e/o consigliati)
Corsi vincolanti: Nessuno
Corsi raccomandati: Nessuno

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
Strumenti a supporto della didattica: dispense aggiuntive sul “passo di calcolo”

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
La Risoluzione
Clausole e formule come insiemi finiti
Risoluzione
Procedura di Davis-Putnam DPP
Teorema di completezza di Robinson}
Teorema di Completezza ( la procedura DPP funziona )
definizione di refutazione

* Classi fulminee per DPP
Clausole Krom
Clausole Horn

* * * Logica dei Predicati

* Formule senza quantificatori
sintassi: termini, formule atomiche, clausole, formule CNF
la semantica di Tarski: tipi e modelli
semantica dei termini
semantica di Tarski per le clausole
sostituzione di termini al posto di variabili
lemma 13.5
Universo di Herbrand e risoluzione
correttezza dell'istanziazione ground
Teorema di Correttezza
refutazione
Cenni di aritmetica dei numeri cardinali
Cardinalità dell'Universo di Herbrand
Teorema di Completezza per le formule senza quantificatori
Teorema di Compattezza
assiomi per l'eguaglianza
definizione di sottostruttura

* La logica del primo ordine
sintassi e semantica
Forma normale prenessa
sottoformule
chiusura deduttiva
formule equivalenti modulo teoria
espansione e restrizione del linguaggio
Skolemizzazione
Teorema di completezza di Goedel
Teorema di compattezza

calcolo della cardinalità della skolemizzazione.
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:
DLO+
Teorema di Cantor (DLO+ è omega-categorica)
operazioni sugli ordini lineari: somma, prodotto
DLO+ non è K-categorica per ogni K non numerabile
insiemi puri
DTFAG e spazi vettoriali su Q
assiomatizzazione di Z col succesore; studio delle orbite

* classi elementari
classi elementari finitamente assiomatizzabili e loro caratterizzazione

* conseguenze del teorema di compattezza
{campi di char 0} non e' finitamente assiomatizzabile
Lemma: Se T ha modelli finiti di cardinalita' arbitrariamente alta. allora T ha modelli infiniti.
Teorema di Erdös-Bruijin
Principio di Robinson