Algebra E Logica 2011/2012

Insiemi e operazioni sugli insiemi. Funzioni iniettive, suriettive, invertibili. Cardinalita'. Induzione matematica.  Relazioni. Grafo associato ad una relazione. Relazioni di equivalenza su un insieme, classi di equivalenza, insieme quoziente. Relazioni di ordine parziale, diagramma di Hasse di un insieme finito parzialmente ordinato, elementi massimali e minimali, massimo e minimo assoluto. Maggioranti, minoranti, estremo superiore e inferiore di un sottoinsieme. Insiemi bene ordinati. Aritmetica sui numeri interi: divisione con resto, massimo comun divisore, algoritmo euclideo. Numeri primi, Teorema Fondamentale dell'Aritmetica. Congruenze e sistemi di congruenze. Teorema cinese del resto. Aritmetica modulare. Gruppi, anelli, campi. Teorema di Lagrange, piccolo teorema di Fermat. Applicazioni: test di primalita' di Miller Rabin, sistema crittografico a chiave pubblica RSA. Reticoli, ordinamento parziale su un reticolo. Isomorfismi di reticoli. Reticoli limitati, distributivi, complementati, booleani. Algebre di Boole. Espressioni booleane: forma normale disgiuntiva, forma normale disgiuntiva completa, implicanti primi e forme minimali. Metodo del consenso. Quantificatori. Successioni ricorsive ed equazioni risorsive lineari a coefficienti costanti.