Programma Definitivo
Matematica Discreta (Corso B) a.a.2002/2003
Docente: Farinola Angela
CENNI DI LOGICA
Logica proposizionale e logica predicativa. Tecniche di dimostrazione. 
Il 
principio di induzione completa.

I NUMERI INTERI
Massimo comune divisore tra due interi e identità di Bezout (*). Numeri 
primi e numeri irriducibili. Fattorizzazione di un intero (*): Il 
crivello 
di Eratostene. Il criterio di Fermat. La funzione di Eulero. Equazioni 
diofantee: compatibilità e soluzioni. Relazioni ricorsive ed esempi: Le 
torri di Hanoi e i numeri di Fibonacci come soluzione del problema delle 
coppie di conigli.

RELAZIONI, FUNZIONI, RETICOLI, GRAFI
a)	Relazioni binarie. Relazioni funzionali. Applicazioni, 
applicazioni ingettive, surgettive, bigettive, con particolare 
riferimento 
alle applicazioni tra insiemi finiti. Modelli dell’occupazione e delle 
parole. Operazione su un insieme e proprietà. Rappresentazione grafica 
(grafo orientato) di una relazione binaria su un insieme finito. 
Relazioni 
di equivalenza su un insieme. Insiemi quozienti. Relazioni di 
equivalenza 
compatibile con una operazione ed operazione indotta sul quoziente. 
Partizioni di un insieme. Legame tra partizioni e relazioni di 
equivalenza. Studio della relazione di congruenza “modulo n” e 
dell’insieme Zn delle classi resto. Il piccolo teorema di Fermat. 
Teorema 
di Eulero (*) e sua applicazione nel sistema R.S.A. nel campo della 
crittologia. Congruenze lineari. Compatibilità e soluzioni di una 
congruenza lineare. Risoluzione dei sistemi di congruenze lineari. Il 
teorema cinese del resto (*).
b)	Relazioni d’ordine su un insieme e relativa rappresentazione 
grafica (diagramma di Hasse) nel caso finito. Morfismo ed isomorfismo di 
insiemi ordinati. Elementi massimali  e minimali, massimo e minimo di un 
insieme ordinato. Maggioranti, minoranti, estremo superiore, estremo 
inferiore di un sottoinsieme di un insieme ordinato. Reticoli, 
sottoreticoli. Operazioni in un reticolo e loro proprietà. Reticoli 
distributivi. Caratterizzazione  dei reticoli distributivi (*). Morfismi 
e 
isomorfismi di reticoli. Reticoli limitati, complementati. Reticoli di 
Boole. Leggi di De Morgan. Morfismi e isomorfismi di reticoli di Boole. 
Principio di dualità nella teoria dei reticoli.
c)	Relazioni simultaneamente simmetriche e antiriflessive e 
relativa 
rappresentazione grafica (grafo non orientato) nel caso finito. Teoria 
elementare dei grafi. Definizione ed esempi di grafi regolari, completi, 
cammini e circuiti, grafi connessi, cammini e circuiti euleriani. Il 
problema dei ponti di Königsberg e il teorema di Eulero (*). Alberi e 
foreste, definizione ed esempi di grafi piani e planari.

STRUTTURE ALGEBRICHE
a)	Monoidi: definizione, potenze in un monoide e relative proprietà 
(*). Morfismi e isomorfismi tra monoidi. Il monoide delle parole e 
proprietà universale del monoide delle parole. Sottomonoide generato da 
un 
insieme e relativo teorema di struttura (*). Sottomonoidi ciclici e 
monoidi ciclici.
b)	Gruppi: definizione, esempi, potenze in un gruppo e loro 
proprietà 
(*). Il gruppo degli elementi invertibili di un monoide. Sottogruppi e 
loro caratterizzazione. Studio dei sottogruppi di (Z, +). Morfismi ed 
isomorfismi tra gruppi e relative proprietà. Sottogruppo generato da un 
insieme e relativo teorema di struttura (*). Sottogruppi ciclici e 
gruppi 
ciclici. Periodo di un elemento di un gruppo. Determinazione e numero 
dei 
generatori di un gruppo ciclico. Teorema di Lagrange (*) e suoi 
corollari. 
Il reticolo dei sottogruppi. Sottogruppi di gruppi ciclici (*). Gruppi 
quozienti di gruppi ciclici. Studio dei gruppi (Zn, +), (Zp*, •) con p 
primo, (GL (n, k) •) delle matrici non singolari, (Sn, •) delle 
permutazioni su n oggetti. Classificazione dei gruppi ciclici (*). I 
gruppi di ordine 4. Il gruppo prodotto diretto.
c)	Anelli, corpi, campi: definizione, esempi, divisori dello zero 
ed 
elementi unitari, l’anello prodotto diretto. Anelli di Boole e 
proprietà. 
L’anello di Boole (Z2n, +, •). Classificazione degli anelli di Boole 
finiti (*). Legame tra reticoli di Boole ed anelli di Boole (*). Studio 
degli anelli (Zn, +, •) delle classi resto modulo n, (k [x], +, •) dei 
polinomi, (Mn (k), +, •) delle matrici quadrate. Il campo (C, +, •) dei 
numeri complessi. Teorema di Ruffini e molteplicità di uno zero di un 
polinomio. Polinomi irriducibili e teorema di fattorizzazione (*). 
Ricerca 
degli zeri razionali di un polinomio a coefficienti interi, condizione 
sufficiente per l’irriducibilità in Q di polinomi primitivi. Polinomi 
irriducibili nel campo R dei numeri reali. Fattorizzazione di polinomi a 
coefficienti interi sul campo Q dei numeri razionali. Teorema di Gauss 
(*). Criterio di Eisenstein (*). C come campo algebricamente chiuso (*).

MATRICI E SISTEMI LINEARI
Rango di una matrice. Sistemi di equazioni lineari. Regole di Cramer e 
teorema di Rouchè-Capelli (*). Sistemi omogenei. Autovalori di una 
matrice 
e loro caratterizzazione come zeri del polinomio caratteristico. 
Diagonalizzazione di una matrice e criterio di diagonalizzabilità (*).


N.B.: dei teoremi contrassegnati con (*) non è richiesta la 
dimostrazione.


	TESTI CONSIGLIATI:

Ø	A. FACCHINI, Algebra e Matematica Discreta, Decibel Zanichelli.
Ø	PIACENTINI-CATTANEO, Algebra un approccio algoritmico, Decibel 
Zanichelli.