Modulo A

Modulo A

Docente: Roberto Maieli (ricevimento: durante lo svolgimento del corso il Giovedì prima la lezione, ore 15-16 stanza 0.11, sede provvisoria uffici Via della Vasca Navale 84, Dip.to M&F, su prenotazione via email "maieli@uniroma3.it").

Scheda Modulo A: Insegnamento: LM410 -TEOREMI SULLA LOGICA 1. 

Caratteristiche: Ambito disciplinare: Formazione Teorica. Attività: Attività formative caratterizzanti Ore Aula: 32. Ore Esercitazioni: 16. CFU: 6. SSD: MAT/01

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

Prerequisiti: nessuno specifico

Programma dell'insegnamento:

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, Lowenheim-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à della procedura di eliminazione del taglio. Qualche conseguenza immediata del teorema di eliminazione del taglio.

Modalità di Svolgimento: 

Didattica  in presenza e in casi particoli anche in streaming sincrono (senza registrazione delle lezioni) 

La frequenza non è obbligatoria ma è vivamente raccomandata.

Modalità di valutazione: Esame scritto e/o orale. 

Testi adottati: Vito Michele Abrusci e Lorenzo Tortora de Falco,  Logica. Vol. 1 Dimostrazioni e modelli al primo ordine, Springer, 2014