Logic For Computer Science

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.