Attenzione: PROGRAMMA PROVVISORIO
Il programma per ora si riferisce all'a.a. 2006/07.
Per riferimenti dettagliati degli argomenti svolti a lezioni
si consulti anche il Diario delle Lezioni

Obiettivi del corso: Il corso si propone di familiarizzare lo studente con la formalizzazione matematica e con il metodo di deduzione.

TEORIA DEGLI INSIEMI
* Insiemi. Sottoinsiemi e inclusione.
* Operazioni con gli insiemi: unione, intersezione, differenza.
* Il complementare di un insieme in un altro.
* Prodotto cartesiano. Grafico.
* Corrispondenze, corrispondenza negata e inversa di una data.
* Relazioni su un insieme.
* Proprietà di una relazione: riflessiva, simmetrica, antisimmetrica, transitiva, totale.
* Relazioni d'ordine, parziali e totali.
* Insiemi parzialmente ordinati: diagramma di Hasse.
* Minimo, massimo, elementi minimali, massimali, minoranti, maggioranti,
estremo inferiore e superiore di un sottoinsieme di un insieme parzialmente ordinato.
* Catene di un insieme parzialmente ordinato. Catene massimali.
* Relazioni di equivalenza, classi di equivalenza, insieme quoziente.
* Teorema fondamentale sulle relazioni di equivalenza.
* La relazione di congruenza modulo un naturale sugli interi.
* Costruzione degli interi a partire dai naturali come quoziente
del loro prodotto cartesiano modulo una relazione di equivalenza.
* Costruzione dei razionali a partire dagli interi come quoziente
del loro prodotto cartesiano modulo una relazione di equivalenza.
* Funzioni: dominio, codominio, immagine, funzioni iniettive, suriettive, biiettive.
* Funzione composta. La funzione inversa.
* Operazioni unarie, binarie, n-arie.
* Assioma del buon ordinamento sui naturali
* Principio di induzione naturale (prima e seconda forma)
* Teorema: esistenza e unicità di quoziente e resto sugli interi.
* Teorema: ogni intero si esprime in modo unico (a meno dell'ordine) come prodotto di primi.
* Il coefficiente binomiale, relazione ricorsiva.
* Proposizione: se p è primo, allora in Z/pZ si ha
(x+y)^p= x^p+y^p.
* Il "Piccolo teorema di Fermat": se p è primo, allora in Z/pZ si ha a^p=a per ogni a.
* Massimo comune divisore sugli interi.
* L'algoritmo di Euclide per il calcolo del massimo comune divisore
* Identità di Bézout. Calcolo di inversi moltiplicativi e di potenze nel campo numerico Z/nZ
* Teorema: esistono infiniti numeri primi.
* Teoria della cardinalità. Equipotenza di insiemi
* Costruzione dei naturali. Insiemi finiti e infiniti, insiemi numerabili
* Confronto di cardinalità. La potenza del continuo.
* Teorema: Ogni insieme infinito contiene un sottoinsieme numerabile
* Teorema (metodo diagonale di Cantor): l'unione di numerabili è numerabile.
* L'insieme dei razionali è numerabile
* L'intervallo aperto (0,1) non è numerabile.
* L'insieme dei numeri reali non è numerabile.

LOGICA MATEMATICA

Calcolo proposizionale

* Formule proposizionali
* Interpretazione vero-funzionale: tavole di verità
* Equivalenza logica, soddisfacibilità, validità, tautologie e conseguenza logica
* Metodo dei tableaux semantici: costruzione, terminazione, teorema di correttezza e completezza (con dimostrazione)

Calcolo dei predicati

* Relazioni e predicati
* Formule predicative
* Interpretazioni. Soddisfacibilità, validità
* Tableaux semantici: costruzione sistematica, correttezza e completezza (indecidibilità)

TESTI CONSIGLIATI