Syllabus di logica matematica

Una proposta per l’insegnamento della logica matematica

1. Corsi di laurea in Matematica

L’AILA ha svolto un’indagine sull’insegnamento della Logica Matematica nei corsi di laurea triennale e magistrale delle classi di Matematica (32 e 45/S) nelle Università italiane per l’anno accademico 2004-05. Si nota una forte disomogeneità tra le varie sedi: in alcune Università Logica è completamente assente, in altre si prevedono fino a 10 crediti per la laurea triennale. Anche la presenza di docenti del settore MAT/01 (Logica Matematica) pare assai irregolare. D’altra parte l’esperienza didattica degli ultimi anni mostra quanto sia importante introdurre gli studenti che si iscrivono ai corsi di laurea in Matematica al linguaggio matematico e al corretto svolgimento delle dimostrazioni formali. La Logica Matematica ha poi crescenti interazioni e applicazioni a vari rami della Matematica Pura e Applicata e dell’Informatica, e la conoscenza dei suoi punti fondamentali è da tempo elemento essenziale del patrimonio culturale di un matematico.

In questa fase di ulteriore riorganizzazione della struttura delle nuove lauree, in particolare di quella magistrale, l’AILA ha ritenuto allora utile presentare alla comunità matematica una proposta su possibili corsi di Logica Matematica per la laurea triennale e per quella magistrale e sui loro contenuti di base. Nel rispetto della libertà, dell’autonomia e della sensibilità di ogni docente e delle finalità formative dei vari corsi di studio, la proposta presenta un orientamento largamente condiviso nell’ambito dell’associazione e in questo senso può essere un utile punto di riferimento, certamente aperto a eventuali approfondimenti e discussioni.

Primo corso di logica matematica(5 CFU)

Riguarda la laurea triennale in Matematica. Può essere svolto nel primo biennio, preferibilmente già al primo anno.

1. Teoria degli Insiemi Cardinalità di un insieme. Il continuo e il numerabile. Gli assiomi di Peano-Dedekind per i numeri naturali. Numeri cardinali e numeri ordinali. Paradosso di Russell. Altri esempi di paradossi. Necessità di un sistema di assiomi che superi i paradossi. Un esempio di assiomatizzazione. Teorema di Cantor-Schroeder-Bernstein. L’assioma della scelta. L’ipotesi del continuo.
2. Logica proposizionale Alfabeto, formule, valutazioni, verità. Semantica e sintassi: conseguenze logiche e dimostrazioni. Cenni sui teoremi di correttezza e di completezza. Metodi formali di dimostrazione (ad esempio, deduzione naturale). Problema della soddisfacibilità. Le tavole di verità. Riduzione in forma normale congiuntiva o disgiuntiva. Il problema SAT. Metodo di risoluzione. Introduzione al problema P = NP.
3. Logica del primo ordine Alfabeto, formule, strutture, verità. Semantica e sintassi: conseguenze logiche e dimostrazioni. Cenni sui teoremi di Correttezza e di Completezza. Metodi formali di dimostrazione (come sopra). Cenni sul teorema di Compattezza e discussione delle limitazioni espressive della logica del primo ordine. Problema della soddisfacibilità nello logica del primo ordine: riduzione di una formula in forma normale prenessa, procedimento di Skolem, teorema di Herbrand, ricorso agli algoritmi della logica proposizionale. Cenni sul metodo di risoluzione e unificazione e sul teorema di J. A. Robinson. (Se possibile: cenni su logiche non classiche, introduzione alla logica intuizionistica).

Ulteriori commenti. Come detto, il corso si propone di avviare lo studente al ragionamento matematico. Presenta quindi anzitutto alcuni punti chiave della teoria degli insiemi e dei fondamenti della matematica. Si cerca poi di accostare lo studente all’uso dei connettivi e dei quantificatori e alle norme che lo regolano e permettono di “riscrivere” gli enunciati matematici nella forma più “ordinata” possibile. Sono prevedibili collegamenti ad analisi, algebra e geometria (nel punto 1) e con temi attuali di informatica teorica e matematica applicata (ad esempio nel problema del millennio P = NP).

Secondo corso di logica matematica (4-6 CFU)

Si può prevedere per studenti del terzo anno della laurea triennale o del successivo biennio magistrale, soprattutto in lauree e indirizzi di Matematica Pura.

1. Verso i teoremi di incompletezza di Goedel. Un’introduzione storica: il programma di Hilbert. Richiami della logica del primo ordine: il concetto di modello. Teorema di compattezza. Discussione sulle limitazioni espressive della logica del primo ordine. Classi elementari e non elementari di strutture. Teorie, teorie coerenti, teorie complete. Insiemi definibili: cenni sulla loro caratterizzazione in determinate classi di strutture (insiemi costruibili, insiemi semialgebrici).
2. Computabilità Il problema della comp utabilità. Macchine di Turing. Tesi di Church-Turing. Problemi non risolubili e funzioni non computabili. Codifiche con numeri naturali. Il problema dell’arresto. Cenni ad altri problemi matematici non risolubili algoritmicamente: il Decimo problema di Hilbert. (EVENTUALMENTE: Cenni di complessità computazionale. Complessità di un algoritmo. Confronto asintotico delle funzioni di complessità, la relazione O. La classe P: rapido = polinomiale? La classe NP. Il problema P = NP).
3. I teoremi di Goedel. La struttura (N, +, .). Insiemi di naturali decidibili, semidecidibili, definibili. Teorie decidibili e indecidibili. Esempi di teorie decidibili. Indecidibilità della teoria di (N, +, .). Primo teorema di incompletezza di Goedel (in forma debole: incapacità di assiomatizzare in modo semidecidibile al primo ordine la teoria di (N, +, .)). Cenni sui teoremi di incompletezza di Goedel. Vero e dimostrabile. Discussione delle loro conseguenze. Applicazioni: impossibilità di assiomatizzare la validità nella logica del secondo ordine.

Commento. Il corso propone argomenti – come i teoremi di Goedel e di Tarski e l’analisi della computabilità di Turing – che sono punti fondamentali del patrimonio matematico dell’ultimo secolo ma non possono rientrare nei limiti e nelle finalità del primo corso di Logica.

2. Corsi di laurea in Informatica

L’AILA ha svolto un’indagine sull’insegnamento della Logica Matematica nei corsi di Laurea Triennale e Magistrale in Informatica (classi 26 e 23/S) delle Università italiane per l’anno accademico 2004-05. Si nota che un corso di Logica Matematica (di 5-6 CFU) è presente nella quasi totalità dei corsi di Laurea Triennale di Informatica e che i contenuti dei relativi programmi sono in genere abbastanza omogenei e condivisi. Del resto l’esperienza didattica degli ultimi anni mostra quanto sia importante e delicato introdurre gli studenti che si iscrivono ai corsi di laurea in Informatica al linguaggio matematico e al corretto svolgimento delle dimostrazioni formali. La Logica Matematica ha poi significative connessioni e applicazioni all’Informatica, da quelle classiche sui temi della computabilità e della complessità a quelle di programmazione, verifica di hardware, software e protocolli, nonché rappresentazione della conoscenza e intelligenza artificiale. Dunque un corso di Logica Matematica si presenta come necessario supporto agli ambiti teorici e applicativi dell’Informatica. L’AILA ritiene quindi utile ribadire l’importanza di un corso di Logica Matematica e proporre alla comunità informatica una serie di argomenti fondamentali per il suo contenuto. Nel rispetto della libertà, dell’autonomia e della sensibilità di ogni docente e delle finalità formative dei vari corsi di studio, la proposta che segue presenta un orientamento largamente condiviso nell’ambito dell’associazione e in questo senso può essere un utile punto di riferimento, certamente aperto a eventuali approfondimenti e discussioni.

Corso di logica matematica (6 CFU)

Riguarda un corso di nel primo biennio della Laurea Triennale, da svolgere possibilmente già nel primo anno.

1. Logica proposizionale Alfabeto, formule, valutazioni, verità. Semantica e sintassi, conseguenze logiche e valutazioni. Cenni sui teoremi di correttezza e di completezza. Problema della soddisfacibilità. Tavole di verità. Metodi formali di dimostrazione (deduzione naturale, eventualmente calcolo dei sequenti, alberi, tableaux semantici). Regole di Davis -Putnam. Algoritmo di risoluzione. Riferimento al problema P = NP.
2. Logica del primo ordine Alfabeto, formule, strutture, verità. Semantica e sintassi: conseguenze logiche e dimostrazioni. Cenni sui teoremi di Correttezza e di Completezza. Cenni sul Teorema di Compattezza. Metodi formali di dimostrazione (come sopra). Riduzione di un enunciato in forma normale prenessa, skolemizzazione, teorema di Herbrand, algoritmo di risoluzione e unificazione, teorema di J. A. Robinson.
3. Breve introduzione ai teoremi di incompletezza di Goedel. È auspicabile che al corso sia poi associata una significativa attività di laboratorio che permetta la sperimentazione con alcuni strumenti di proof-checking, o con SAT-solvers, o con strumenti di dimostrazione automatica di ultima generazione, e accompagni e sostenga -ma non sostituisca- l’educazione al ragionamento. In ragione delle finalità didattiche del corso di studi, altri corsi di carattere Logico (o comunque collegati alla Logica Matematica) accompagneranno il corso fondamentale sopra descritto.