| | | |  corso | | | |
Logica Matematica A
(Corso di Laurea in Informatica (quinquennale))
| Codice: | 4I010 | Crediti: | 6 | Semestre: | 2 | Sigla: | LM | |
Docente
Vincenzo Manca
Prerequisiti
Notazioni e concetti di base della teoria degli insiemi.
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.
English Description
This course intends to provide the basis of Mathematical Logic: some
important proof systems in propositional and predicative logic, some
important models and theories, the basic results related to the compactness
and completeness of predicate logic, the notions of logical
representability, and the fundamental limitative results in logical
formalization.
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. Cenni ad
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: | 25 | Ore esercitazione: | 15 | | | |
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
Esame scritto ed orale con compitini di verifica intermedia, sostitutivi
dell'esame scritto finale.
