Edizione 2025-2026

Calendario didattico a.a. 2025/2026 - I semestre

• Lezioni: Lunedì 16-19 aula M3; Mercoledì 16-19, aula F; Venerdì 16-19 aula M3

• 22/09/2025: inizio lezioni del I semestre

• dal 10/11 al 15/11/2025: periodo riservato agli esoneri – interruzione lezioni (data Primo esonero LM410: Venerdì 15 Novembre)

• 17/11/2025: ripresa lezioni 

• 23/12/2025: inizio vacanze di Natale

• 07/01/2026: ripresa dell’attività didattica

• dal 12/01 al 17/01/2026: eriodo riservato agli esoneri per i soli Corsi di laurea e di laurea magistrale in Matematica e in Scienze Computazionali

• dal 19/01 al 21/02/2026: sessioni appelli d’esame

1. lunedì 22/9 (LTdF+RM): presentazione e avvio del corso; Discussione generale su dimostrazioni e refutazioni logiche. Esempi di dimostrazioni, ed in particolare di dimostrazioni matematiche.  

Modulo A (R. Maieli)

2. Mercoledì 24/9 : I concetti di Proposizione del Primo Ordine, Formula Logica del Primo Ordine (chiusa) e Proposizioni Puramente Logiche. I concetti di dimostrazione (logica) e refutazione (logica), falsificabilità e soddisfacibilità di una formula del primo ordine chiusa. Gli enunciati dei Teoremi di Corretta e Completezza per la Logica del Primo Ordine. Riferimenti: Capitolo 1 (Introduzione) del libro Logica. Vol. 1 Dimostrazioni e modelli al primo ordine, Springer, 2014.  Nozioni preliminari: ordini parziali ed ordini totali, relazioni ben fondate, buoni ordini. Esempi. Definizione di albero e prime proprietà degli alberi. Riferimenti: Capitolo 2, pagg. 36 - 41 del libro Logica. Vol. 1.

3. Venerdì 2/9: Definizioni induttive di un insieme. Dimostrazioni per induzione. Induzione sull’ordine lessicografico. Dimostrazione che l'ordine lessicogafico è un buon ordine. Assioma di scelta e sua applicazione per dimostrare il lemma di König. Dimostrazione del Lemma di König numerabile senza Assioma di Scelta.  Capitolo 2, pagg. 41 - 48 del libro Logica. Vol. 1. Esercizio: dimostrare che le due formulazioni del principio di induzione di pagina 45 (sezione 2.3.2) del libro di Logica vol. 1 sono equivalenti (vedi traccia dello svolgimento dell'esercizio e le altre formulazioni del principi di induzione ).

4. Lunedì 39/09: Linguaggio del primo ordine: alfabeto. Due formulazioni diverse di un alfabeto del primo ordine. Definizione induttiva di termine su di un linguaggio del primo ordine. Definizione induttiva di formula su di un linguaggio del primo ordine. Occorrenze libere e vincolate di variabili in una formula. Sostituzione di un termine in una formula: il "problema della cattura di una variabile". Una relazione di equivalenza sulle formule del primo ordine. Riferimenti: Capitolo 3, pagg. 49 - 61 del libro Logica. Vol. 1. Sottoformule. Grado e altezza di una formula. Osservazioni sulla cardinalità del linguaggio.

5. Mercoledì 1/10: Strutture per un linguaggio del primo ordine. Termini e formule a parametri (chiusi) in una struttura. Valutazione di termini e formule in una struttura. Modelli e Contromodelli per formule chiuse del primo ordine. Soddisfacibilità di Teorie del primo ordine e di Sequenti del primo ordine. Riferimenti: Capitolo 3, pagg. 62 - 69 del libro Logica. Vol. 1.  Esempi. Esercitazione sul principio di induzione: l’induzione sui multinsiemi finiti di numeri naturali ed il taglio delle teste dell’Idra  (scarica i file EserciziLogicaCap2.pdf).

6. Venerdì 3/10: Esercitazione sul principio di induzione: dimostrazione "sintattica" o "diretta" della equivalenza delle due definzione del principio di induzione "debole" e "forte" su i Naturali e dimostrazione come conseguenza del fatto che le due formulazioni sono consegeunza del Buon Ordine dei numeri naturali dotati della relazione d'ordine "<" (vedi traccia dello svolgimento dell'esercizio). Esercitazione sulla nozione di soddisfacibilità, da parte di una struttura, di una formula chiusa del primo ordine Prima discussione sull’assiomatizzazione al primo ordine della nozione di insieme finito e della nozione di insieme infinito. Esercizi sulla soddisfacibilità al primo ordine. Scarica il testo degli EserciziLogicaCap3-1.pdf. 

7. Lunedì 6/10: Presentazione del calcolo dei sequenti LK di Gentzen per la logica del primo ordine: lista delle regole, commenti e discussione. Formulazioni moltiplicativa e additiva delle regole del calcolo dei sequenti Definizione di derivabilità di una formula (e di un sequente) e di derivabilità di una formula (e di un sequente) da un insieme di formule. Esempi. Riferimenti: Capitolo 3, pagg. 70 - 73 del libro Logica. Vol. 1. Esempi. Definizione di Analisi di un sequente da un insieme di formule come generalizzazione della nozione di derivazione di un sequente da un insieme di formule. 

8. Mercoledì 8/10:Enunciato e dimostrazione del Teorema di Correttezza per la logica del primo ordine LK (Vedi Errata-Corrige Volume 1). Esercitazione: La nozione di reversibilità di una regola logica unaria e binaria.  Elenco delle regole reversibili ed irreversibili del calcolo dei sequenti. Dimostrazione della reversibilità ed irrevesribilità delle regole. Esercitazione sulla derivabilità delle regole moltiplicative da quelle additive e vice-versa mediante l’uso delle regole strutturali (weakening e contraction).

9. Venerdì 10/10: Esercizio sulla permutabilità delle regole logiche. Elementi neutri ed elementi assorbenti della congiunzione e della disgiunzione. Esercizi sulla nozione di derivabilità in LK senza Quantificatori (calcolo proposizionale) ed in presenza di Quantificatori. Il Teorema dell’Ubriaco e la necessità della regola di Contrazione per la nozione di derivabilità nel calcolo dei predicati del primo ordine. (Esercizi 3.8.1, 3.9.1 e 3.10 del file EserciziLogicaCap3-2.pdf). 

10. Lunedì 13/10: Ordine Ciclico. Costruzione dell’Analisi Canonica Senza Tagli di una formula del primo ordine. Proprietà dell'A.C.S.T di una formula chiusa del primo ordine. Esempi e discussione. Riferimenti: Capitolo 3, pagg. 80 -  88 del libro Logica. Vol. 1.

11. Mercoledì 15/10: Costruzione dell’Analisi Canonica Con Tagli di una formula chiusa A da una Teoria T del primo ordine. Proprietà dell'A.C.C.T. Esempi e discussione. Prime Proprietà dei rami scorretti dell'Analisi Canonica con e senza tagli: Lemmi 0,1 e 2. Riferimenti: Capitolo 3, pagg. 88 - 97 del libro Logica. Vol. 1.

12. Venerdì 17/10: Proprietà dei rami scorretti dell'Analisi Canonica con e senza tagli: Lemmi 3,4 e 5 e 6. Teorema fondamentale dell’Analisi Canonica con la dimostrazione completa. Corollario: Completezza di LK. (Scarica il file con la dimostrazione) Commenti ed esempi. Riferimenti: Capitolo 3, pagg. 97 - 108 del libro Logica. Vol. 1. Esercizio 3.5 sulla Indipendenza dell'assioma della Coppia dall'assioma dell'Estensionalità della Teoria degli Insiemi di Zermelo.

13. Lunedì 20/10:  Esercitazione: sulla nozione di derivabilità in LK in presenza di quantificatori + analisi canonica con e senza tagli. (Eserizio 3.10, Riferimenti:   file EserciziLogicaCap3-2.pdf). 

14. Mercoledì 22/10: Conseguenze del teorema fondamentale dell'Analisi Canonica: teorema di completezza, teorema di eliminabilità del taglio. Corollario della non-contraddittorietà di LK. Ulteriori conseguenze del teorema fondamentale dell’analisi canonica: teorema di compattezza, teorema di Löwenheim-Skolem. Osservazioni conclusive sul teorema fondamentale dell’analisi canonica e sulle estensioni delle sue conseguenze al caso dei linguaggi più che numerabili (verso la Teoria dei Modelli).  Esercitazione: su soddisfacibilità, dimostrabilità, analisi canonica (Eserizio 3.11, Riferimenti:   file EserciziLogicaCap3-2.pdf). 

15. Venerdì 24/10: La questione dell’eliminazione del taglio di Gentzen. Enunciato del teorema di eliminazione del taglio e suo raffinamento. Strategia generale della dimostrazione. Le trasformazioni elementari definite da Gentzen (i casi-chiave). I casi dell’indebolimento e della contrazione. Le trasformazioni elementari definite da Gentzen: il caso dei quantificatori e le difficoltà ad esso connesse. Riferimenti: Capitolo 4, pagg. 109 - 125 del libro Logica. Vol. 1.

16. Lunedì 27/10: Prima dimostrazione del teorema di eliminazione del taglio applicando la procedura T_glob ottenuta componendo opportunamente tra loro i passi elementari di riduzione T e distinguendo i passi logici (L) da i passi strutturali (S). Discussione ed esempi. Riferimenti: Capitolo 4, pagg. 125 - 133 del libro Logica. Vol. 1. 

17. Mercoledì 29/10: Esercitazione: es. 3.9.2 ed es. 3.12. Esercizi sulla eliminazione del taglio nel caso proposizionale.

18. Venerdì 31/10: Lemma di Reversibilità. Seconda dimostrazione del teorema di eliminazione del taglio applicando la procedura T_rev, ottenuta sfruttando il Lemma di Reversibilità. Discussione ed esempi. Riferimenti: Capitolo 4, pagg. 125 - 133 del libro Logica. Vol. 1. Esercizio sulla eliminazione dei tagli da dimostrazioni con quantificatori (eliminazione del taglio dal "Teorema dell'Ubriaco").

19. Mercoledì 5/11: Esercitazione sulla soddisfacibilità e dimostrabilità di formule del primo ordine. Eliminazione delle regole del taglio mediante induzione sull'Idra (il multiinsieme) delle complessità logiche delle cut formule di una derivazione logica di LK (Esercizio 4.3).

20. 14/11/2025 ore 11:00-14:00 - Aula M5 - Primo esonero : 

21.  24/11/2025 ore 16:00-19:00 - correzione primo esonero

22.  12/01/2026 ore 11-13, esercitazione

23. 14/01/2026 ore 10-13 Secondo Esonero

24. 27/01/2026 ore 14-17 aula M2 correzione Secondo Esonero