Matematica Discreta

Programma del corso

Insiemi. Operazioni sugli insiemi: unione, intersezione, differenza, differenza simmetrica, prodotto cartesiano. Insieme delle parti di un insieme.

Corrispondenze e applicazioni. Immagini e antiimmagini. Applicazioni iniettive, suriettive e biiettive. Applicazioni composte. Inversa di una applicazione.

Elementi di Aritmetica. Il principio di induzione. Numeri naturali e numeri interi. Divisibilità tra numeri interi (la divisione con resto). Numeri primi. Teorema fondamentale dell'aritmetica. Teorema di Euclide sull'esistenza di infiniti numeri primi. Il massimo comun divisore e il minimo comune multiplo. L'algoritmo di Euclide per il calcolo del MCD di due numeri interi. Aritmetica modulo un intero m. Equazioni congruenziali lineari. Il teorema cinese del resto.

Elementi di calcolo combinatorio. Fattoriale di un numero naturale. Coefficienti binomiali. Disposizioni. Disposizioni con ripetizioni. Permutazioni. Permutazioni con ripetizioni. Combinazioni.

Relazioni di equivalenza. Classi di equivalenza. Insieme quoziente. Teorema fondamentale sulle relazioni di equivalenza.

Relazioni d'ordine. Elementi minimali e massimali. Minimo e massimo. Minoranti e maggioranti. Estremo inferiore ed estremo superiore. Diagrammi di Hasse. Insiemi totalmente ordinati. Insiemi bene ordinati. Sottoinsiemi di un insieme ordinato e ordine indotto. Reticoli. Reticolo delle parti di un insieme. Reticolo degli interi.

Strutture algebriche. Operazioni binarie su un insieme. Tavola di moltiplicazione. Sottoinsiemi stabili e operazione indotta. Operazioni associative. Operazioni commutative. Elemento neutro. Elementi invertibili. Relazioni di equivalenza compatibili con una operazione. Strutture quoziente. Omomorfismi. Semigruppi, sottosemigruppi, omomorfismi di semigruppi, semigruppo quoziente. Monoidi, sottomonoidi, omomorfismi di monoidi, monoide quoziente. Gruppi, sottogruppi, omomorfismi di gruppi, gruppo quoziente. Gruppo degli elementi invertibili di un monoide. Anelli, sottoanelli, omomorfismi di anelli, anello quoziente, anelli commutativi, anelli unitari, elementi invertibili, campi, divisori dello zero, domini di integrità, legge di annullamento del prodotto.

Matrici. Operazioni sulle matrici (somma, prodotto per uno scalare, prodotto righe per colonne, potenze). Matrice trasposta. Anello delle matrici quadrate su un campo. Matrici diagonali. Matrici invertibili. Determinante di una matrice quadrata e sue proprietà notevoli (senza dimostrazione). Teorema di Binet (senza dimostrazione). Calcolo della matrice inversa di una matrice invertibile. Rango di una matrice. Autovalori e autovettori di una matrice quadrata.

Sistemi di equazioni lineari. Teorema di Cramer (senza dimostrazione). Teorema di Rouché-Capelli (senza dimostrazione).

Testo consigliato: