Algebra E Logica 2022/2023

INSIEMI, FUNZIONI, RELAZIONI Insiemi, sottoinsiemi e operazioni tra di essi. Corrispondenze tra insiemi; relazioni, funzioni, composizione.  Iniettività, suriettività, biiettività, invertibilità di funzioni. Insieme delle parti di un insieme; funzione caratteristica di un sottoinsieme.  Partizioni. Relazioni d’'ordine. Relazioni di equivalenza; classi, quozienti, legame con le partizioni. Insiemi con operazioni. Classi particolari: esempi e controesempi.   NUMERI NATURALI Il sistema dei numeri naturali; il Principio di Induzione (in tre formulazioni). Dimostrazioni per induzione. Ordine e operazioni nei numeri naturali; divisione con resto. Numerazione (scrittura posizionale) in base arbitraria.   CARDINALITÀ, NUMERI CARDINALI Insiemi finiti e insiemi infiniti. Cardinalità di un insieme, numeri cardinali.  Ordinamento tra numeri cardinali; Teorema di Bernstein. Insiemi numerabili, insiemi non numerabili. Primo e Secondo Teorema di Cantor. Cardinalità del continuo (cenni).   NUMERI INTERI, NUMERI RAZIONALI Costruzione dei numeri interi (a partire dai naturali); valore assoluto, operazioni, ordinamento; divisibilità; M.C.D. e m.c.m. Divisione con resto tra numeri interi.  Esistenza del M.C.D.: l’'algoritmo di Euclide; identità di Bézout.  Fattorizzazione nell'anello dei numeri interi: il Teorema Fondamentale dell’'Aritmetica. Equazioni diofantee. Relazioni di congruenza tra numeri interi. Equazioni congruenziali; sistemi di equazioni congruenziali. Anelli di classi resto (=interi modulari). Aritmetica modulare; equazioni congruenziali.   RETICOLI, ALGEBRE DI BOOLE, CALCOLO BOOLEANO Insiemi ordinati; relazione di copertura, diagramma di Hasse; elementi speciali in un (sotto)insieme ordinato. Reticoli; classi speciali di reticoli; v-fattorizzazione nei reticoli. Algebre di Boole, come reticoli e come anelli booleani unitari; il Teorema di Equivalenza (Stone).  Algebre di Boole e insiemi delle parti: il Teorema di Rappresentazione (Stone) per il caso finito (e cenni per il caso infinito). Funzioni booleane; polinomi booleani; equivalenza tra polinomi booleani. Forma Normale Disgiuntiva di un polinomio booleano. Forme Minimali di un polinomio booleano.  Implicanti primi; il Metodo del Consenso per il calcolo delle forme minimali di un polinomio booleano.