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

I semestre
Giorno Ora Tipo Luogo Note
lunedì 11.30 - 13.30 lezione Aula A  
mercoledì 8.30 - 10.30 lezione Aula D  

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.