Logica
This course is in Italian, so this webpage is in Italiano.
Programma
Il syllabus è disponibile.
- Introduzione
- aspetti burocratici e amministrativi
storia della logica
relazione con l’informatica
- aspetti burocratici e amministrativi
- Logica Proposizionale
- concetto di induzione strutturale
sintassi
deduzione naturale - esempi di dimostrazione formale
- semantica a tavole di verità
insiemi minimali di connettivi
forme normali disgiuntive e congiuntive
soddisfacibilità - algebre di Boole
- teorema di correttezza
schema della dimostrazione e correttezza di semplici programmi - completezza
- concetto di induzione strutturale
- Logica al Primo Ordine
- sintassi
sostituzione
calcolo naturale - esempi di deduzione
esempi di formalizzazione - semantica alla Tarski
teorema di correttezza - risoluzione
unificazione
programmazione logica mediante esempi
- sintassi
- Teoria dei Tipi Semplici
- λ-calcolo
sintassi
riduzioni - esempi: tipi di dati in λ-calcolo
esempi: programmazione funzionale - teoria dei tipi semplici
sintassi
riduzioni - logica proposizionale intuizionista
sintassi
potenza espressiva - isomorfismo Curry-Howard
dimostrazioni come programmi
correttezza per costruzione - normalizzazione forte
terminazione di programmi
- λ-calcolo
- Risultati limitativi
- teorema di compattezza
esempi di modelli non standard - aritmetica di Peano
codifica - lemma di punto fisso
teorema di incompletezza di Gödel - funzioni calcolabili
tesi di Church-Turing
teorema di Cantor
esistenza di funzioni incalcolabili - incalcolabilità e incompletezza
esempi: minori di grafi
- teorema di compattezza
Materiale didattico
Le slides delle lezioni:
Un eserciziario sulla dimostrazione in calcolo naturale.
Il corso dell’anno accademico 2020/21 è anche disponibile online.
Il corso di Mathematical Logic nel corso di Laurea magistrale in Matematica mette a disposizione materiale che viene in parte riutilizzato in questo corso.
I temi d’esame:
L’esame è uno scritto diviso in tre parti. La prima vale 9 punti e contiene due domande (di 4 e 5 punti rispettivamente) riguardanti definizioni o esercizi illustrati nel corso. La seconda vale 9 punti e chiede di dimostrare un teorema tra quelli studiati a lezione. La terza vale 12 punti e contiene due domande (6 punti ciascuna) che richiedono lo svolgimento di esercizi sulla falsariga di quelli visti nel corso.
| Data | Testo | Soluzione |
|---|---|---|
| Esempio | ||
| 10 giugno 2021 | ||
| 22 giugno 2021 | ||
| 22 luglio 2021 | ||
| 7 settembre 2021 | ||
| 3 febbraio 2022 | ||
| 18 febbraio 2022 | ||
| 10 giugno 2022 | ||
| 1 luglio 2022 | ||
| 22 luglio 2022 | ||
| 2 settembre 2022 | ||
| 27 gennaio 2023 | ||
| 17 febbraio 2023 | ||
| 15 giugno 2023 | ||
| 5 luglio 2023 | ||
| 21 luglio 2023 | ||
| 4 settembre 2023 | ||
| 17 gennaio 2024 | ||
| 8 febbraio 2024 | ||
| 6 giugno 2024 | ||
| 27 giugno 2024 | ||
| 18 luglio 2024 | ||
| 3 settembre 2024 | ||
| 19 dicembre 2024 | ||
| 29 gennaio 2025 | ||
| 13 febbraio 2025 |
Calendario degli esami
Essendosi svolto l’ultimo appello relativo all’anno accademico 2023/24, non vi saranno altri appelli regolari dell’esame di Logica tenuto dal docente.
Marco Benini 