Logica II (2004/2005)

Obiettivi formativi

Esame critico del ruolo dei linguaggi per effettuare controlli automatizzati e per determinarne i limiti.

Programma del corso
# ``Semantic tableaux'' e sistemi di Gentzen.
Parte Introduttiva: semantic tableaux per la logica classica proposizionale e predicativa (I ordine), per le logiche modali regolari (K, K4, GL, KD, T, S4, S5) e per la logic intuizionistica.
Argomenti avanzati PDL (propositional dynamic logic) e mu-calcolo (?).
Teorema di Goedel e logica GL (?).
# Teoria della dimostrazione.
Parte Introduttiva: calcoli dei sequenti per la logica classica LK, intuizionistica LJ e lineare LL. Deduzione naturale NJ, e corrispondenza con LJ. Teorema di normalizzazione debole, teorema di eliminazione del taglio. Reti di prova per la logica lineare moltiplicativa.
Argomenti avanzati Semantica dei giochi per la logica lineare polarizzata (?).
# Lambda calcolo tipato.
Parte Introduttiva: Definizioni fondamentali, proprieta` di Church-Rosser, algoritmi di tipabilita` con sistemi di tipi semplici e con tipi intersezione.
Argomenti avanzati teorema di normalizzazione forte (?).

L'ammissione all'esame di Logica II richiede il superamento di
# due prove scritte di due ore ciascuna sulla parte elementare dei tre moduli (semantic tableaux, teoria della dimostrazione, lambda calcolo tipato) e di
# una prova orale, consistente in una presentazione seminariale su un argomento piu` avanzato da concordare.

Le prova scritte si intendono superate se lo studente ottiene in entrambe una votazione di almento 18/30.

La prova orale si intende superata se la presentazione risulta soddisfacente per chiarezza e completezza dell'informazione (secondo criteri informali usuali, a giudizio del docente).

L'esame consiste in un breve colloqio orale, in cui i contenuti ed i risultati delle prove scritte ed il tema e la qualita` della presentazione orale vengono riconsiderati. Al termine, lo studente puo` decidere di accettare il voto proposto o concordare una ulteriore prova.

Gli studenti che abbiano sostenuto analoghe prove scritte sulla parte elementare dei moduli in occasione di esami precedenti hanno la facolta` di sostituire le prove scritte con una seconda presentazione orale.