Corso di Laurea in Ingegneria Informatica
a.a 2025-2026 - primo semestre
Diario delle lezioni del corso (6 CFU) di
ALGEBRA E LOGICA
Canale 2 (M-Z)
Docente: Fabio GAVARINI
( pagina web del corso )
PROGRAMMA
(versione preliminare)
BIBLIOGRAFIA:
[AaVv] - Autori Varî,
Materiale vario disponibile in rete (per gentile concessione degli autori)
[Ca] - G. Campanella,
Appunti di Algebra 1 (per gentile concessione dell'autore)
[G-P] - L. Geatti, G. Pareschi,
Dispense varîe (per gentile concessione degli autori)
[L-L] - S. Lipschutz, M. Lipson, Discrete Mathematics,
Third Edition, Schaum's Outlines, McGraw-Hill, 2007
[PC] - G. M. Piacentini Cattaneo, Algebra - un approccio algoritmico, ed. Decibel/Zanichelli, Padova, 1996
DODICESIMA LEZIONE - 3 Novembre 2025:
Caratterizzazione degli insiemi infiniti: Per ogni insieme X, le seguenti proprietà sono a due a due equivalenti:
- X è infinito,
- esiste una funzione iniettiva dall'insieme N dei numeri naturali ad X,
- esiste un sottoinsieme proprio X' di X che è equipotente ad X stesso.
Proposizione: N × N è equipotente a N.
1o Teorema di Cantor: L'unione di una famiglia finita (non vuota) o numerabile di insiemi numerabili è numerabile.
Applicazioni del Primo Teorema di Cantor: Z e Q sono numerabili.
2o Teorema di Cantor: Per ogni insieme X, la cardinalità dell'insieme P(X) delle parti di X e la cardinalit` dell'insieme 2X delle funzioni caratteristiche su X sono (uguali tra loro e) strettamente maggiori della cardinalità dell'insieme X stesso.
Bibliografia: [AaVv] file Cardinalità (D'Andrea) - [Ca] Capitolo I, paragrafo 6 - [G-P] file Funzioni e cardinalità, paragrafo 5 - [L-L] Chapter 3, section 7 - [PC] Capitolo 1, paragrafo 5
Esercizi: Cardinalità (N.B.: in linea di massima, questi esercizi sono un po' più difficili della media)
Videolezioni: Cardinalità 1 (insiemi equipotenti, cardinalità; Primo Teorema di Cantor) - Cardinalità 2 (Secondo Teorema di Cantor)
Lezioni analoghe del corso 2020/2021:
Cardinalità: relazione d'ordine tra numeri cardinali, proprietà dei cardinali infiniti (8 Aprile 2021)
(videoregistrazione [1h:46'24"] / versione scritta [4,96 MB])
-
Cardinalità: Primo e Secondo Teorema di Cantor (e loro conseguenze), cardinali infiniti superiori (12 Aprile 2021)
(videoregistrazione [1h:59'26"] / versione scritta [8,95 MB])
UNDICESIMA LEZIONE - 30 Ottobre 2025:
Relazione d'ordine (buono) tra numeri cardinali; il Teorema di Schroeder-Bernstein (senza dimostrazione della transitività e dell'essere buono).
Lemma: Siano A e B due insiemi finiti. Allora:
(a) se |A|<|B|, allora non esistono funzioni suriettive da A a B né funzioni iniettive da B ad A;
(b) se |A|=|B| e f è una funzione da A a B, allora f è iniettiva ⇔ f è suriettiva.
Corollario: L'insieme N dei numeri naturali è infinito numerabile è infinito (e quindi anche ogni insieme numerabile è infinito).
La relazione d'ordine tra cardinali finiti ristretta ai numeri naturali coincide con l'ordine standard.
Proposizione:
(a) Ogni insieme infinito contiene un sottoinsieme numerabile.
(b) Ogni sottoinsieme di un insieme numerabile o è finito oppure è numerabile.
Bibliografia: [AaVv] file Cardinalità (D'Andrea) - [Ca] Capitolo I, paragrafo 6 - [G-P] file Funzioni e cardinalità, paragrafo 5 - [L-L] Chapter 3, section 7 - [PC] Capitolo 1, paragrafo 5
Esercizi: Cardinalità (N.B.: in linea di massima, questi esercizi sono un po' più difficili della media)
Videolezioni: Cardinalità 1 (insiemi equipotenti, cardinalità; Primo Teorema di Cantor)
Lezioni analoghe del corso 2020/2021:
Cardinalità: relazione d'ordine tra numeri cardinali, proprietà dei cardinali infiniti (8 Aprile 2021)
(videoregistrazione [1h:46'24"] / versione scritta [4,96 MB])
DECIMA LEZIONE - 27 Ottobre 2025:
Teorema di Esistenza e Unicità per la scrittura posizionale di un numero naturale in base b (>1) arbitraria.
Algoritmo effettivo per il calcolo della scrittura posizionale di un numero naturale (in base arbitraria).
Esempi espliciti di calcolo della scrittura posizionale di un numero dato.
Esempi espliciti di calcolo di somma e prodotto con scrittura posizionale in base arbitraria (cenni).
La relazione di equipotenza tra insiemi; l'equipotenza è una equivalenza.
La cardinalità (o "potenza") di un insieme come classe di equipotenza dell'insieme stesso; i numeri cardinali.
Insiemi finiti e insiemi infiniti. La cardinalità del numerabile ℵ0 ; gli insiemi numerabili.
Bibliografia: [Ca] Capitolo II, paragrafo 2 - [PC] Capitolo 1, paragrafo 5; Capitolo 2, paragrafo 10
Esercizi: Scrittura posizionale
Videolezioni: Numerazione (numerazione in base arbitraria / scrittura posizionale) - Cardinalità 1 (insiemi equipotenti, cardinalità; Primo Teorema di Cantor)
Lezioni analoghe del corso 2020/2021:
Principio di Induzione; Divisione con resto tra numeri naturali; Scrittura posizionale in base arbitraria (29 Marzo 2021)
(videoregistrazione [1h:58'24"] / versione scritta [4,85 MB])
-
Scrittura posizionale in base arbitraria; Cardinalità (29 Marzo 2021)
(videoregistrazione [1h:44'22"] / versione scritta [8,56 MB])
NONA LEZIONE - 23 Ottobre 2025:
Esistenza e unicità di un S.N.N.: l'esistenza si postula (Assioma dell'Infinito), l'unicità si dimostra (cenni).
Il Principio di Induzione Forte (=Pr.I.F.), il Principio del Minimo (=Pr.M.); l'equivalenza tra Pr.I.D., Pr.I.F. e Pr. M. (senza dimostrazione)
Il metodo di dimostrazione per induzione (debole o forte o mediante principio del minimo): idea, strategia - base, passo induttivo (con ipotesi induttiva), ecc.
Divisione (euclidea) con resto tra numeri naturali. Esistenza e unicità di quoziente e resto nella divisione: dimostrazione dell'unicità, dimostrazione dell'esistenza per induzione in tre modi diversi (col Pr.I.D., col Pr.I.F. e col Pr.M.).
Scrittura posizionale (di un numero naturale) in base b (>1) arbitraria: idee e definizioni preliminari.
Bibliografia: [Ca] Capitolo II, paragrafi 1 e 2 - [G-P] files Induzione e Aritmetica sugli interi, etc. (complementi), paragrafo 1 - [L-L] Chapter 1, section 8; Chapter 11, section 3 - [PC] Capitolo 2, paragrafo 10
Esercizi: Principio di Induzione
- Induzione, scrittura posizionale
- Scrittura posizionale
Videolezioni: Induzione (metodo di dimostrazione per induzione [semplice / forte / minimo]) - Divisione (divisione con resto tra numeri naturali) - Numerazione (numerazione in base arbitraria / scrittura posizionale)
Lezioni analoghe del corso 2020/2021:
Principio di Induzione; Divisione con resto tra numeri naturali; Scrittura posizionale in base arbitraria (29 Marzo 2021)
(videoregistrazione [1h:58'24"] / versione scritta [4,85 MB])
OTTAVA LEZIONE - 20 Ottobre 2025:
Sistema dei numeri naturali (=S.N.N.): definizione tramite gli assiomi di Peano; il Principio di Induzione Debole, o Semplice (=Pr.I.D./S.).
Relazioni d'ordine buone - Esercizio: ogni ordine buono è (anche) totale.
La relazione d'ordine in un S.N.N. (definizione tramite il Pr.I.D.).
Le operazioni di somma e prodotto in un S.N.N. (definizione ricorsiva, tramite il Pr.I.D.).
Teorema: In un S.N.N., la relazione d'ordine è buona (quindi totale). Inoltre, un S.N.N. con somma e prodotto è un semianello commutativo unitario, e tali operazioni sono compatibili con la relazione d'ordine (senza dimostrazione).
Esempio: l'insieme dei numeri interi è un S.N.N. rispetto a un'opportuna scelta della funzione "successivo".
Bibliografia: [AaVv] file Numeri naturali (D'Andrea) - [Ca] Capitolo I, paragrafo 5 - [PC] Capitolo 1, paragrafo 4
Esercizi: Principio di Induzione
Videolezione: Naturali (sistema dei numeri naturali: assiomi di Peano, ordine, operazioni)
Lezioni analoghe del corso 2020/2021:
Sistema dei Numeri Naturali e sue proprietà (25 Marzo 2021)
(videoregistrazione [2h:03'30"] / versione scritta [4,02 MB])
SETTIMA LEZIONE - 13 Ottobre 2025:
Operazioni (binarie) in un insieme; proprietà speciali possibili. Elementi speciali: elemento neutro, elemento assassino.
Elementi invertibili in un monoide: l'inverso di un elemento invertibile.
Unicità di elemento neutro/assassino (se esiste); unicità dell'elemento inverso (se esiste).
Semigruppi, monoidi, gruppi; definizione, esempi e controesempi. Il gruppo degli invertibili in un monoide.
Il monoide EE delle endofunzioni di un insieme E (per l'operazione di composizione); il suo gruppo degli invertibili è il gruppo S(E) delle permutazioni di E.
Insiemi con due operazioni (binarie); casi speciali (semianelli, anelli, campi); esempi e
controesempi.
L'insieme delle parti (di un insieme) è un anello commutativo unitario - ma non un campo - per la differenza simmetrica e l'intersezione.
Bibliografia: [Ca] Capitolo I, paragrafo 4 - [G-P] file Gruppi, anelli, campi - [L-L] Appendix B - [PC] Capitolo 5, paragrafo 1; Capitolo 4, paragrafo 1
Esercizi: Gruppoidi e morfismi (N.B.: soltanto alcuni di questi esercizi sono pertinenti al programma svolto)
Videolezioni: Operazioni 1 (operazioni in un insieme; insiemi con una operazione) - Operazioni 2 (insiemi con più operazioni)
Lezioni analoghe del corso 2020/2021:
Insiemi con operazioni (22 Marzo 2021) (videoregistrazione [2h:01'29"] / versione scritta [6,66 MB])
SESTA LEZIONE - 9 Ottobre 2025:
Esercizio: la congruenza modulo n tra i numeri interi è una relazione di equivalenza.
La relazione in E associata all'insieme quoziente di una partizione di E (e quindi alla partizione stessa).
Classi di equivalenza e loro proprietà fondamentali.
Teorema: (a) La relazione in E associata al quoziente di una partizione di E è un'equivalenza.
(b) La famiglia delle classi di equivalenza (per una qualsiasi equivalenza data) in E è una partizione dell'insieme E.
(c) Le due costruzioni precedenti sono una l'inversa dell'altra.
Nota: ogni equivalenza in un insieme A è l'equivalenza indotta (canonicamente) da una qualche funzione il cui dominio è A stesso.
Bibliografia: [Ca] Capitolo I, paragrafo 3 - [G-P] file Relazioni 1 - [L-L] Chapter 2 - [PC] Capitolo 1, paragrafo 2
Esercizi: Relazioni 1 - Relazioni 2
Videolezioni: Equivalenze 1 (equivalenze e partizioni) - Equivalenze 2 (equivalenze e funzioni)
Lezioni analoghe del corso 2020/2021:
Corrispondenza tra equivalenze e quozienti di partizioni (18 Marzo 2021) (videoregistrazione [1h:29'37"] / versione scritta [4,95 MB])
Lezioni analoghe per altri corsi (un po' più in dettaglio):
prima parte (videoregistrazione [1h:52'23" - su Stream] /
versione scritta [4,14 MB])
-
seconda parte (videoregistrazione [1h:46'03" - su Stream] /
versione scritta [3,90 MB])
QUINTA LEZIONE - 6 Ottobre 2025:
Insiemi disgiunti.
Relazioni (binarie) in un insieme; operazioni insiemistiche tra relazioni, inversa, composizione e potenze di relazioni (in uno stesso insieme).
Proprietà notevoli per una relazione: riflessività, transitività, simmetricità, antisimmetricità.
Relazioni di preordine; relazioni d'ordine, relazioni d'ordine totale; relazioni di equivalenza. Esempi e controesempi.
In ogni insieme, la relazione identità è un ordine e un'equivalenza.
La divisibilità tra numeri naturali è un ordine, ma non è totale; la divisibilità tra numeri interi è un preordine, ma non un ordine. Nell'insieme delle parti (di un insieme X qualunque), l'inclusione è un ordine, che è totale se e soltanto se X ha meno di due elementi.
Teorema: Ad ogni funzione f da X a Y è associata in modo canonico una relazione in X che è una equivalenza.
Partizioni in un insieme; l'insieme quoziente e la proiezione canonica associati ad una partizione.
Esercizio: La proiezione canonica (definita come corrispondenza) è una funzione suriettiva.
Bibliografia: [Ca] Capitolo I, paragrafo 3 - [G-P] file Relazioni 1 - [L-L] Chapter 2 - [PC] Capitolo 1, paragrafo 2
Esercizi: Insiemi, funzioni, relazioni - Relazioni 1 - Relazioni 2
Videolezioni: Relazioni (relazioni in un insieme: generalità, esempi)
Lezioni analoghe del corso 2020/2021:
Relazioni; ordini, equivalenze; partizioni (15 Marzo 2021) (videoregistrazione [1h:54'31"] / versione scritta [4,30 MB])
QUARTA LEZIONE - 2 Ottobre 2025:
Funzioni invertibili: definizione, unicità (quando esista) della funzione "inversa".
Esercizio: Siano h una funzione da X a Y e k una funzione da Y a Z. Allora si ha:
(1) se h e k sono iniettive, allora la loro composizione k ○ h è iniettiva;
(2) se h e k sono suriettive, allora la loro composizione k ○ h è suriettiva;
(3) se la composizione k ○ h è iniettiva, allora h è iniettiva;
(4) se la composizione k ○ h è suriettiva, allora k è suriettiva;
(5) (applicazione di (3) e (4)) Se h è una funzione da X a Y e k una funzione da Y a X tali che k ○ h = idX , allora h è iniettiva e k è suriettiva.
Teorema: Per una data funzione f, le seguenti proprietà sono equivalenti:
(a) f è invertibile;
(b) f è biiettiva;
(c) la corrispondenza inversa f -1 è una funzione.
Permutazioni in un insieme. L'insieme 2E delle funzioni caratteristiche su un insieme E. La funzione caratteristica χF di un sottoinsieme F di un insieme E.
Teorema: Dato un insieme E, la funzione
Φ : P(E) ⟶ 2E, F ↦ χF ,
e la funzione
Ψ : 2E ⟶ P(E) , η ↦ η -1(1) , sono l'una l'inversa dell'altra. In particolare, entrambe le funzioni Φ e Ψ sono invertibili, e quindi sono biiettive.
Bibliografia: [Ca] Capitolo I, paragrafo 2 - [G-P] file Funzioni e cardinalità - [L-L] Chapter 3, sections 3.1-3 - [PC] Capitolo 1, paragrafo 3
Esercizi: Funzioni
Videolezioni: Funzioni 2 (composizione di funzioni, funzioni invertibili) - Funzioni caratteristiche (funzioni caratteristiche in un insieme)
Lezioni analoghe del corso 2020/2021:
Funzioni invertibili; funzioni caratteristiche in un insieme; sottoinsiemi vs. funzioni caratteristiche (11 Marzo 2021) (videoregistrazione [1h:59'01"] / versione scritta [4,56 MB])
TERZA LEZIONE - 29 Settembre 2025:
La composizione - o prodotto (operatorio) - di due corrispondenze.
Proprietà notevoli di inversione e composizione: associatività, esistenza di "elementi neutri" (le corrispondenze identità), non commutatività (in generale); la formula per l' inversa di una composizione. La composizione di due funzioni è a sua volta una funzione.
Proposizione: Ogni corrispondenza da A a B equivale ad una ben precisa funzione (univocamente determinata) da A a P(B), l'insieme delle parti di B, dalla quale si può ricostruire la corrisopndenza di partenza.
Famiglie (vs. "insiemi") - di oggetti in un insieme E indicizzati da elementi di un insieme I - come funzioni da I a E.
Funzioni iniettive (o "iniezioni"), funzioni suriettive (o "suriezioni"), funzioni biiettive (o "biiezioni", o "corrispondenze biunivoche"): definizioni, esempi e controesempi.
Proposizione: (caratterizzazione delle funzioni biiettivite tramite la corrispondenza inversa) Una funzione f è biiettiva se e soltanto se la sua corrispondenza inversa f-1 è a sua volta una funzione.
Bibliografia: [Ca] Capitolo I, paragrafo 2 - [G-P] file Funzioni e cardinalità - [L-L] Chapter 2; Chapter 3, sections 3.1-5 - [PC] Capitolo 1, paragrafi 1-3
Esercizi: Corrispondenze - Funzioni
Videolezioni: Corrispondenze (corrispondenze
tra insiemi e operazioni tra di esse) - Funzioni 1 (funzioni; iniettività, suriettività, biiettività)
Lezioni analoghe del corso 2020/2021:
Corrispondenze tra insiemi e costruzioni fondamentali su di esse (4 Marzo 2021) (videoregistrazione [1h:57'58"] / versione scritta [4,20 MB]) -
Funzioni; iniettività, suriettività, biiettività (8 Marzo 2021) (videoregistrazione [1h:57'58"] / versione scritta [4,85 MB])
SECONDA LEZIONE - 25 Settembre 2025:
Operazioni tra insiemi: intersezione, unione, differenza, complementare, differenza simmetrica, prodotto cartesiano.
Proprietà notevoli delle operazioni tra insiemi:
(1) commutatività e associatività di intersezione, unione e differenza simmetrica;
(2) esistenza di elementi speciali;
(3) distributività e leggi di De Morgan.
Corrispondenze tra insiemi: definizione, notazione. Casi speciali: relazioni e funzioni.
Esempi e controesempi: la corrispondenza vuota, la corrispondenza totale, la corrispondenza "identità" (che è una relazione e una funzione) idA su un insieme A; la corrispondenza "sorella" (che non è una funzione), la corrispondenza "madre"(che è una funzione).
Costruzioni sulle corrispondenze: operazioni insiemistiche tra corrispondenze, la corrispondenza inversa (di una corrispondenza data).
Bibliografia: [Ca] Capitolo I, paragrafo 2 - [L-L] Chapter 2 - [PC] Capitolo 1, paragrafo 2
Esercizi: Insiemi - Corrispondenze
Videolezioni: Insiemi (insiemi, sottoinsiemi, insieme delle parti, operazioni tra insiemi) - Corrispondenze (corrispondenze
tra insiemi e operazioni tra di esse)
Lezioni analoghe del corso 2020/2021:
Insiemi, sottoinsiemi, insieme delle parti, operazioni tra insiemi (1 Marzo 2021) (videoregistrazione [2h:01'00"] / versione scritta [9,70 MB]) -
Corrispondenze tra insiemi e costruzioni fondamentali su di esse (4 Marzo 2021) (videoregistrazione [1h:57'58"] / versione scritta [4,20 MB])
PRIMA LEZIONE - 24 Settembre 2025:
Presentazione generale del corso e spiegazione delle modalità d'esame.
Insiemi: definizione (naturale, o "ingenua"), descrizioni possibili; appartenenza e non appartenenza di elementi. Famiglie (di oggetti in un insieme): definizione "ingenua".
Il Paradosso di Russel e i limiti della teoria "ingenua" degli insiemi.
Inclusione tra insiemi; sottoinsiemi, sovrainsiemi. L'uguaglianza tra insiemi come doppia inclusione.
L'insieme vuoto. L'insieme delle parti di un insieme: definizione, esempi.
Bibliografia: [Ca] Capitolo I, paragrafo 1 - [G-P] file Insiemi - [L-L] Chapter 1 - [PC] Capitolo 1, paragrafo 1
Esercizi: Insiemi
Videolezione: Insiemi (insiemi, sottoinsiemi, insieme delle parti, operazioni tra insiemi)
Lezioni analoghe del corso 2020/2021:
Insiemi, sottoinsiemi, insieme delle parti, operazioni tra insiemi (1 Marzo 2021) (videoregistrazione [2h:01'00"] / versione scritta [9,70 MB])