Corso di Laurea in Ingegneria Informatica
Anno Accademico 2009-2010 e Anno Accademico 2010-2011
Primo semestre (emisemestre 2)
ELEMENTI DI ALGEBRA E LOGICA (crediti 5)
Programma dettagliato & diario delle lezioni

PRIMA SETTIMANA:
- Insiemi ed operazioni sugli insiemi: unione, intersezione, differenza, complementare, prodotto cartesiano, insieme delle parti. Funzioni: definizione, composizione, funzioni iniettive, suriettive, biettive, funzione inversa.
- Cardinalita' di un insieme. Insiemi numerabili e non numerabili. Cardinalita' del continuo.
- Induzione matematica. Funzioni definite per ricorrenza.

Appunti: Preliminari. Funzioni e cardinalita'. Induzione.
Testo: L&L., Cap I, Sez.1,2,3,4,5,6,7,8,9,10. Cap III: Sez.1,2,3,5,6,7, Eserc. 3.13, 3.16, 3.28.
Esercizi 1 (con soluzioni), Esercizi 1- 2009

SECONDA SETTIMANA:
- Relazioni binarie fra insiemi: definizioni e proprieta'. Grafo diretto associato. Relazioni di equivalenza su un insieme. Classi di equivalenza e insieme quoziente. Relazioni di equivalenza e partizioni. Esempi.
- Relazioni di ordine parziale su un insieme. Diagramma di Hasse associato. Insiemi parzialmente ordinati: elementi massimali, massimo, elementi minimali, minimo. Insiemi totalmente ordinati.

Appunti: Relazioni 1. Relazioni 2.
Testo: L&L., Cap.II: Sez.1,2,3,4,6,8,9, Cap.XIV: Sez.3,5,7.
Esercizi 2 (con soluzioni), Esercizi 2- 2009

TERZA SETTIMANA:
- Maggioranti, estremo superiore, minoranti ed estremo inferiore di un sottoinsieme in un insieme parzialmente ordinato.
- Aritmetica sugli interi: numeri primi e Teorema Fondamentale dell'Aritmetica. Divisione con resto. Massimo comune divisore fra interi. L'algoritmo di Euclide.
- Equazioni lineari diofantee in due incognite. L'identita' di Bezout. L'algoritmo di Euclide esteso.
Congruenze modulo n.

Appunti: Relazioni 2. Testo: L&L., Cap.XIV: Sez.3,5,7.
Appunti: nota1, pag.1-8.
Esercizi 2 (con soluzioni), Esercizi 2- 2009
Esercizi 3 (con soluzioni), Esercizi 3- 2009

QUARTA SETTIMANA:
- Congruenze modulo n. Sistemi di congruenze. Il Teorema Cinese del Resto.
- Calcolo modulo $n$. Definizione di gruppo. Esempi. Il gruppo additivo Z_n, il gruppo moltiplicativo Z_n^*.

Appunti: nota1.
Esercizi 3 (con soluzioni), Esercizi 3- 2009
Appunti: Aritmetica sugli interi: complementi; nota2, pag.1-5.
Esercizi 4- 2009, Esercizi 4 (con soluzioni): i primi esercizi della lista.

QUINTA SETTIMANA:
- Il campo Z_p, con p primo. Il teorema di Lagrange. Il Piccolo Teorema di Fermat.
- Applicazioni al calcolo di potenze modulo n.
- Il criptosistema RSA.

R. Schoof, Fattorizzazione e criptosistemi a chiave pubblica.
Appunti: nota2 (fino a pag.14).
Esercizi 5- 2009, Esercizi 4 (con soluzioni): fino all'esercizio 14. Esercizi 5 (con soluzioni): solo n. 1, 2, 8, 9. Col computer: n. 10, 11,12.

SESTA SETTIMANA:
- Reticoli: assiomi di definizione, proprieta' delle operazioni su un reticolo. Esempi: (P(X), ⊆, ∪, ∩), (D_m, | , mcd, mcm).
- Reticoli limitati, reticoli distributivi, reticoli complementati, reticoli booleani. Esempi.
- Isomorfismi di reticoli.

Appunti: Reticoli (eccetto per il momento Sez. 4).
L&L., Cap.XIV: Sez. 8 (tranne dualita' e Teorema 14.2), 9, 10,11.
Esercizi 6 (con soluzioni), Esercizi 6- 2009.

SETTIMA SETTIMANA:
- Algebre di Boole: definizione, equivalenza fra algebre di Boole e reticoli booleani. Esempi.
- L'algebra di Boole del calcolo proposizionale.
- Espressioni booleane: forma normale disgiuntiva (somma di prodotti), forma normale disgiuntiva completa (somma di prodotti completa). Implicanti primi, forme minimali.

Appunti: Algebre di Boole.
Appunti: Funzioni booleane.
L&L., Cap.XV: Sez.1,2,4,5,6,7,8 ed esercizi: 15.1, 15.2, 15.3, 15.5 (cenni), 15.6 (cenni), 15.7 (cenni), 15.8 (cenni), 15.10 -- 15.14;
Esercizi 7, n.1--8 (con soluzioni in arrivo); Esercizi 8, n. 1--9 (con soluzioni); Esercizi 7- 2009.

OTTAVA SETTIMANA:
- Espressioni booleane: Metodo del consenso per la determinazione degli implicanti primi.
- Predicati e quantificatori.

Appunti: Funzioni booleane.
Appunti: Forme minimali di una funzione polinomiale.
L&L., Sez.9, esercizi: 15.15 -- 15.21, 15.53 -- 15.59. Cap.IV: Sez.11, 12, esercizi 4.3 -- 4.7, 4.10, 4.17 -- 4.20.
Esercizi 7, n. 9--13 (con soluzioni in arrivo); Esercizi 8, n. 10--11 (con soluzioni); Esercizi 8- 2009.