Nota

Quello che segue è un elenco sintetico (e probabilmente non particolarmente utile) degli argomenti trattati nel corso, non necessariamente in ordine cronologico. È sicuramente utile, invece, consultare il più dettagliato registro delle lezioni, che propone anche un numero di esercizi che, pur non essendo generalmente intesi come parte integrante del corso, possono essere (interessanti di per sé e) di aiuto per la verifica della propria preparazione. Il registro è accessibile dalla pagina web del corso (), che contiene anche ulteriori materiali e informazioni, comprese quelle sui testi ed altre note utilizzabili per la preparazione.

Programma svolto nel corso

Logica intuitiva e linguaggio insiemistico.

Connettivi proposizionali e tavole di verità; tautologie e contraddizioni; iteratività, associatività, commutatività distributività e leggi di De Morgan per connettivi proposizionali. Tautologie relative all'implicazione. Cenni alla logica dei predicati: quantificatori e loro uso; negazione di formule universali o esistenziali.

Insiemi: nozione insiemistica di appartenenenza e principio di estensionalità. Cenni allo schema di assiomi di separazione. Inclusione tra insiemi. Le operazioni insiemistiche fondamentali: unione e intersezione di arbitrari insiemi, complemento e differenza simmetrica tra due insiemi. Legami tra operazioni insiemistiche e connettivi proposizionali. Diagrammi di Euler-Venn.

Corrispondenze, relazioni, applicazioni

Coppie ordinate; prodotto cartesiano tra due insiemi. Corrispondenze tra insiemi. Relazioni binarie in un insieme: proprietà riflessiva, antiriflessiva, simmetrica, antisimmetrica, transitiva; prodotto relazionale e sua associatività. Relazioni d'ordine (stretto o largo) e di equivalenza.

Applicazioni tra insiemi: famiglie; le applicazioni immagine e antiimmagine definite da un'applicazione; restrizioni e prolungamenti. Applicazioni iniettive, suriettive, biettive; il caso particolare delle applicazioni tra insiemi finiti della stessa cardinalità. Applicazioni componibili, composizione di applicazioni (prodotto operativo). Diagrammi commutativi di applicazioni. Sezioni e retrazioni. Rapporti tra iniettività, suriettività e composizione di applicazioni. Applicazioni invertibili, inversa di un'applicazione biettiva. Nozione di equipotenza tra insiemi.

Relazioni di equivalenza e partizioni di un insieme. Classi di equivalenza, insiemi quoziente, proiezioni canoniche. Il nucleo di equivalenza di (o equivalenza associata a) un'applicazione.

Insiemi ordinati: isomorfismi tra insiemi ordinati; ordinamento duale; insiemi totalmente ordinati (catene); minimo, massimo, elementi minimali, elementi massimali; minoranti, maggioranti, estremo inferiore, estremo superiore. Esistenza di elementi minimali e massimali in insiemi ordinati finiti non vuoti. Relazione di copertura e diagrammi di Hasse di insiemi ordinati finiti.

Calcolo combinatorio

Buon ordinamento dei naturali e principio di induzione (in due forme). Calcolo delle cardinalità per insiemi finiti: prodotti cartesiani; unioni tra insiemi (principio di inclusione-esclusione); insieme delle applicazioni ed insieme delle applicazioni iniettive tra due insiemi; fattoriali e fattoriali discendenti; insieme delle parti ed insieme delle $k$-parti di un insieme (per un numero naturale $k$), coefficienti binomiali e loro prime proprietà, il triangolo di Tartaglia-Pascal.

Operazioni e strutture algebriche

Operazioni nullarie, unarie, binarie (interne). Proprietà associativa e proprietà commutativa. Elementi neutri a destra o a sinistra, elementi neutri e loro unicità. Simmetrici destri e sinistri, elementi simmetrizzabili.

Definizioni delle strutture algebriche fondamentali: semigruppi, monoidi, gruppi (e gruppi abeliani), anelli, corpi, campi. Regole di calcolo nelle diverse strutture; multipli e potenze secondo interi. Parti chiuse (o stabili), strutture indotte. Sottostrutture generate. Gruppi ciclici. Omomorfismi, omomorfismi suriettivi ed isomorfismi. Equivalenze compatibili (anche a sinistra o a destra) con un'operazione binaria, congruenze in una struttura algebrica, strutture quoziente e corrispondenti proiezioni canoniche.

Traslazioni destre e sinistre determinate da un elemento in un semigruppo; cancellabilità. Il gruppo degli invertibili in un monoide e in un anello unitario. Il monoide delle trasformazioni ed il gruppo simmetrico su un insieme.

Proprietà degli anelli. Anelli commutativi, anelli unitari e loro elementi invertibili. Elementi cancellabili e divisori dello zero in un anello. Anelli integri e domini di integrità.

Aritmetica e polinomi

Fattorizzazione nei monoidi commutativi. Relazione di divisibilità, in un monoide commutativo ed in un anello commutativo; elementi irriducibili, elementi tra loro associati. Nozioni di monoide fattoriale e di anello fattoriale. Massimi comuni divisori e minimi comuni multipli.

L'anello $\Z$ degli interi. Aritmetica in $\Z$: teorema fondamentale dell'aritmetica (fattorialità di $\Z$), interi primi, invertibili ed interi tra loro associati, interi coprimi; divisione aritmetica (con resto). Congruenze in $\Z$ e quozienti di $\Z$, aritmetica modulare.

L'anello dei polinomi ad una indeterminata su un anello commutativo unitario. Proprietà universale e omomorfismo di sostituzione. Grado di un polinomio. Grado del prodotto tra due polinomi; regola di addizione dei gradi per polinomi, in particolare su domini di integrità, e sue conseguenze. Polinomi monici. Divisione tra polinomi in un anello commutativo unitario. Applicazioni polinomiali e radici di un polinomio. Teorema del resto e teorema di Ruffini. Teorema di Ruffini generalizzato in domini di integrità e sue applicazioni: numero delle radici di un polinomio, principio di identità per polinomi su domini di integrità infiniti.

Algoritmo euclideo per la ricerca di un massimo comun divisore, in $\Z$ e nell'anello dei polinomi ad una indeterminata su un campo; teorema di Bézout (in entrambi i casi). Equazioni congruenziali (di primo grado, ad una incognita) ed equazioni diofantee (di primo grado, a due incognite) in $\Z$, elementi cancellabili ed invertibili nei quozienti di $\Z$; struttura di questi ultimi.

Fattorialità di anelli di polinomi (su campi e su $\Z$, senza dimostrazione). Caratterizzazione dei polinomi irriducibili su un campo; irriducibilità e radici. Descrizione dei polinomi irriducibili sul campo complesso e sul campo reale, criterio di Eisenstein per polinomi a coefficienti interi considerati sul campo razionale (senza dimostrazioni), radici razionali di polinomi a coefficienti interi.

Reticoli, algebre di Boole, anelli booleani

Reticoli come particolari insiemi ordinati e come strutture algebriche; equivalenza tra le nozioni. Principio di dualità per reticoli. Isomorfismi tra reticoli. Reticoli limitati, reticoli completi. Intervalli e sottoreticoli. Complementi e reticoli complementati, reticoli distributivi. Enunciato del criterio di distributività di Birkhoff. Anelli booleani, reticoli booleani, algebre di Boole; equivalenza tra queste nozioni (con dimostrazioni solo parziali). Enunciato del teorema di Stone e descrizione delle strutture booleane finite; loro occorrenza in informatica.

Grafi

Definizione di grafo (semplice) e di multigrafo. Relazione di adiacenza; incidenza. Grado di un vertice. Isomorfismi tra grafi. Sottografi. Relazioni aritmetiche fra numero dei lati, numero e grado dei vertici. Vertici pari e vertici dispari. Grafi completi. Grafi planari (o piani). Cammini, circuiti, connessione, componenti connesse. Cammini e circuiti euleriani (non sono richieste dimostrazioni). Alberi, foreste e loro caratterizzazioni. Alberi con radice. Sottoalbero massimale (o albero di supporto) di un multigrafo finito connesso.