Logica per informatica (2009/2010)

Codice insegnamento
4S02848
Docente
Luca Vigano'
Coordinatore
Luca Vigano'
crediti
6
Altri corsi di studio in cui è offerto
Settore disciplinare
MAT/01 - LOGICA MATEMATICA
Lingua di erogazione
Italiano
Periodo
I semestre dal 1-ott-2009 al 31-gen-2010.

Orario lezioni

Obiettivi formativi

L'esistenza stessa dell'informatica dipende dalla capacità di rappresentare adeguatamente nozioni ed elaborarle attraverso opportune trasformazioni delle loro rappresentazioni. Detto altrimenti, l'elaborazione delle conoscenze si appoggia sulle distinzioni e legami tra semantica e sintassi.

Lo scopo principale di questo insegnamento è dunque introdurre le nozioni fondamentali della logica simbolica: sintassi, semantica, linguaggio e metalinguaggio, sistemi deduttivi, stutture e rappresentabilità.

Programma

La logica proposizionale: sintassi e semantica; sistemi deduttivi (almeno uno dei seguenti sistemi: deduzione naturale, calcolo dei sequenti, tableaux); correttezza e completezza; completezza funzionale.

La logica dei predicati: i quantificatori; le strutture e la semantica del linguaggio del primo ordine; l'uguaglianza; estensione dei sistemi deduttivi per trattare i quantificatori e l'uguaglianza; teorie matematiche del primo ordine; teoremi di correttezza e completezza; teoremi di compattezza e di Lowenheim-Skolem; formalizzazione di strutture matematiche e rappresentabilità; l'aritmetica di Peano; enunciato del teorema di incompletezza.

Modalità d'esame

La verifica del profitto avviene mediante una prova scritta, che deve essere svolta senza l'ausilio di appunti, libri o altro. È facoltà del docente sostituire la prova scritta con una prova orale.