Logic For Computer Science
Insegnamento: Logic For Computer Science
Titolo insegnamento in inglese: Logic For Computer Science
Lingua: italiano
Anno di corso: 1
Semestre: 2
CFU: 6
Insegnamenti propedeutici previsti: Nessuno.
Docenti:
- Luigi Sauro
Obiettivi Formativi
Lo studente acquisirà una conoscenza delle principali proprietà sintattiche e semantiche della logica classica proposizionale e della logica classica del primo ordine. Lo studente acquisirà inoltre familiarità con i principali sistemi deduttivi della logica classica che sono di interesse per le metodologie e i sistemi informatici. Lo studente acquisirà infine la capacità di formalizzare enunciati dichiarativi e problemi nel linguaggio della logica classica, nonché di controllare la correttezza di ragionamenti informali.
Programma
• Logica proposizionale classica. Nozioni sintattiche di base. Nozioni semantiche: soddisfacibilità, tautologie, conseguenza logica e insoddisfacibilità. Forme normali congiuntive e disgiuntive. Deduzione naturale. Calcolo dei sequenti. Tableaux analitici. Regola di risoluzione, procedura di Davis-Putnam, metodo refutazionale. Correttezza, completezza e compattezza della logica proposizionale. • Logica classica del primo ordine. Elementi di sintassi. Semantica tarskiana: soddisfacibilità, verità, validità, conseguenza logica. Tableaux analitici. Formalizzazione di ragionamenti informali. Clausole, universo di Herbrand, clausole ground e refutazioni di insiemi di clausole. Forma normale prenessa e skolemizzazione. Teorema di Skolem. Correttezza, completezza e compattezza della logica del primo ordine. Modelli nonstandard dell’aritmetica. Cenni al teorema di indecidibilità della logica del primo ordine e ai teoremi di incompletezza di Goedel. Dimostrabilità, verità e insiemi ricorsivamente enumerabili.
Modalità didattiche
Lezioni frontali. Esercitazioni.
Materiale didattico
Christos H. Papadimitriou, Computational complexity. Addison-Wesley 1994, ISBN 978-0-201-53082-7, pp. I-XV, 1-523
Modalità di esame
L'esame si articola in prova scritta ed orale.
La prova scritta consta di quesiti a risposta libera.