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, prolungamenti e ridotte. 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; dimostrazioni per controesempio minimo 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

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

L'anello $\Z$ degli interi. Equivalenze compatibili con un'operazione binaria ed operazioni quoziente; congruenze in $\Z$. L'operazione parziale mod in $\Z$ e divisione aritmetica (con resto). Algoritmo euclideo per la ricerca di un massimo comun divisore in $\Z$; teorema di Bézout. 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.

Interi primi, invertibili ed interi tra loro associati, interi coprimi e lemma di Euclide. Teorema fondamentale dell'aritmetica. Aritmetica modulare.

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.