Algebra.
Insiemi. Relazioni. Relazioni d'ordine. Relazioni di equivalenza. Classi di equivalenza. Insiemi quoziente. La relazione di congruenza modulo n nell'insieme Z dei numeri interi. L'insieme Z/nZ.
Funzioni. Funzioni iniettive, suriettive, biiettive. La cardinalità di un insieme. Cardinali finiti e infiniti.
Gruppi: definizione e esempi. Sottogruppi. Sottogruppi generati da n elementi. Sottogruppi ciclici. Struttura dei sottogruppi additivi di Z.
L'algoritmo della divisione con resto. Numeri primi e fattorizzazione unica. Massimo comune divisore e minimo comune multiplo. L'algoritmo di Euclide per il calcolo del M.C.D. di due numeri interi. Studio degli elementi invertibili di Z/nZ. La funzione φ di Eulero.
Relazione di congruenza modulo un sottogruppo H di un gruppo G. Classi laterali destre. Alcuni risultati relativi all'ordine di un sottogruppo (l'ordine di un sottogruppo divide l'ordine del gruppo, l'ordine di un elemento divide l'ordine del gruppo). Il piccolo teorema di Fermat. Il teorema di Eulero.
Applicazioni alla crittografia: la procedura di scambio di chiavi di Diffie-Hellman, crittografia a chiavi pubblica e privata RSA.
Sottogruppi invarianti e gruppi quoziente. Omomorfismi di gruppi. Nucleo e immagine. Primo teorema di omomorfismo di gruppi.
Definizioni di anello, corpo e campo.
Logica.
Logica proposizionale. Linguaggi formali: sintassi e semantica. I connettivi di negazione, congiunzione, disgiunzione, implicazione e le loro tavole di verità.
Interpretazioni e modelli. Formule soddisfacibili, insoddisfacibili e tautologie. Conseguenza semantica. Deduzione semantica. Il teorema di compattezza. Equivalenza semantica. Il teorema di sostituzione. Completezza funzionale. Forme normali: forma normale congiuntiva e forma normale disgiuntiva.
Sistemi deduttivi. La deduzione naturale di Gentzen. Teoremi di correttezza e completezza.
Logica dei predicati. Linguaggi del primo ordine: sintassi e semantica. Equivalenza semantica. Forma normale prenessa. Forma di Skolem.
La deduzione naturale per il calcolo del primo ordine. Correttezza e completezza.
Il problema della decisione: Teorema di Church. I teoremi di incompletezza di Gödel.
