Logica Matematica B

(Corso di Laurea in Informatica (quinquennale))

Codice:

4I010

Crediti:

Semestre:

Sigla:

Docente

Francesca Levi

Tel. 0502212770

Prerequisiti

Nessuno

Obiettivi di apprendimento

Fornire la capacità di
i) esprimere correttamente tramite formule, entro modelli o teorie, proprietà, relazioni e proposizioni vertenti su numeri, sequenze e tipi di dati;
ii) utilizzare regole di inferenza formali per costruire semplici deduzioni logiche.

Descrizione

Il corso ha lo scopo di fornire le basi della logica matematica: alcuni sistemi dimostrativi di logica proposizionale e predicativa, alcune importanti teorie e modelli, i risultati fondamentali basati sulla compattezza e completezza della logica predicativa, le nozioni di rappresentabilità logica ed i fondamentali teoremi limitativi delle formalizzazioni logiche.

Programma

Fondamenti Logico-matematici : Nozioni e notazioni matematiche fondamentali. Principi di induzione.
Logica proposizionale : Connettivi, tavole di verità, tautologie, dualità, algebra di Boole. Forme normali. Compattezza proposizionale.
Logica dei predicati : Modelli e validità logica, regole Tableaux per quantificatori e uguaglianza. Completezza predicativa. Compattezza predicativa, forme di Skolem, universi di Herbrand. Formalizzazioni predicative entro modelli e teorie. Altri calcoli logici (deduzione naturale, risoluzione).
Limiti della logica del primo ordine : Teoremi di Loewenheim-Skolem. Teorie complete e incomplete. Indecidibilità predicativa e cenni al teorema di incompletezza di Goedel.

Ore lezione:

Ore esercitazione:

Bibliografia

Asperti A., Ciabattoni A., Logica ad Informatica, McGraw-Hill, Milano, 1998.
Crossley J. N.et al., Cosa è la logica Matematica?, Boringhieri, 1976.
Manca V., Formal Logic, Encyclopedia of Electrical and Electronics Engineering, John Wiley & Sons, Inc., New York, 1999.
Manca V., Logica Matematica: Strutture, Rappresentazioni, Deduzioni, Bollati-Boringhieri, Torino 2001.

Modalità di esame

Scritto e orale