20410451-1 - LM410 -TEOREMI SULLA LOGICA 1 - MODULO A

Obiettivi

Acquisire buona conoscenza dei principi della logica classica del primo ordine e del calcolo dei sequenti per essa, nonch‚ dei principali risultati che la concernono.

Risultati Apprendimento Attesi

Al termine del corso lo studente dovrà:

- conoscere i principali concetti sintattici e semantici della logica classica del primo ordine;
- comprendere e utilizzare il calcolo dei sequenti LK;
- saper costruire, leggere e verificare derivazioni formali;
- comprendere i principali risultati metateorici, in particolare correttezza, completezza, compattezza, teorema di Löwenheim–Skolem ed eliminazione del taglio;
- saper seguire e ricostruire dimostrazioni per induzione e analisi per casi;
- comprendere il rapporto tra semantica, derivabilità e normalizzazione delle dimostrazioni;
- acquisire autonomia nell’analisi di sistemi formali e nella valutazione della correttezza di una dimostrazione;
- utilizzare con precisione il linguaggio e la notazione della logica matematica.

Programma

Parte 1: Alcune nozioni preliminari.
Relazioni d'ordine e alberi, definizioni induttive, dimostrazioni per induzione, assioma di scelta e lemma di Kőnig.

Parte 2: Dimostrabilità e soddisfacibilità
Linguaggio formale del primo ordine: alfabeto, termini , formule, sequenti. Strutture per un linguaggio del primo ordine: strutture, termini e formule a parametri in una struttura, valutazione di termini, formule e sequenti. Calcolo dei sequenti per la logica del primo ordine: il calcolo dei sequenti LK di Gentzen. Sequenti derivabili e derivazioni. Correttezza delle regole di LK. Analisi canonica e teorema fondamentale: costruzione dellanalisi canonica (con e senza tagli) e dimostrazione del teorema fondamentale dellanalisi canonica. Conseguenze del teorema fondamentale dell'analisi canocica: teoremi di completezza, eliminabilit del taglio, compattezza, L"owenheim-Skolem.

Parte 3: Verso la teoria della dimostrazione: il teorema di eliminazione del taglio.
La procedura di eliminazione del taglio. Definizione dei passi elementari di eliminazione del taglio. Prima strategia dimostrativa (riduzione a grandi passi). Seconda strategia dimostrativa (rovesciamento delle derivazioni). Cenni sulla complessit\`a della procedura di eliminazione del taglio. Qualche conseguenza immediata del teorema di eliminazione del taglio.

Prerequisiti

nessun requisito specifico

Testi Adottati

V. Michele Abrusci e Lorenzo Tortora de Falco, Logica. Vol. 1 Dimostrazioni e modelli al primo ordine, Springer, 2014
https://sites.google.com/view/lm410/home

Bibliografia Di Riferimento

V. Michele Abrusci e Lorenzo Tortora de Falco, Logica. Vol. 1 Dimostrazioni e modelli al primo ordine, Springer, 2014 https://sites.google.com/view/lm410/home

Modalità Erogazione

Il corso prevede Didattica frontale; Discussioni con gli studenti e dibattiti sugli argomenti trattati; Esercitazioni; La frequenza non è obbligatoria ma è vivamente raccomandata. Nel caso di un prolungamento dell’emergenza sanitaria da COVID-19 verranno valutate le modalità di svolgimento delle attività didattiche. Si cercherà di limitare l’inevitabile danno agli studenti dovuto ad un’eventuale necessità di tenere il corso a distanza preservando, per quanto possibile, l’interattività durante le lezioni. E' presvisto lo streaming sincrono delle lezioni senza registrazione delle lezioni svolte in aula.

Modalità Frequenza

non obbligatoria ma fortemente raccomandata

Modalità Valutazione

Esame scritto e/o orale, di durata variabile, in media tra 45 e 60 minuti. Nel caso di misure restrittive dovute alla emergenza sanitaria da COVID-19 verranno valutate le modalità di svolgimento degli esami. Si cercherà di limitare l’inevitabile danno agli studenti dovuto ad un’eventuale necessità di tenere gli esami a distanza.

Esempi Domande

esempi di esercizi e domande sono disponibili nella pagina web online del libro di logica http://logica.uniroma3.it/tortora/Libro.html