Corso di Laurea in Ingegneria Informatica
a.a 2020-2021 - secondo semestre

Diario delle lezioni del corso - da 6 CFU (60 ore) - di

ALGEBRA E LOGICA

(elencate in ordine cronologico inverso)

Docente:   Fabio Gavarini

( pagina web del corso )

PROGRAMMA

                                       

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

  VENTINOVESIMA LEZIONE (tre ore - ripasso ed esercizi) - 10 Giugno 2021:   trasmissione in diretta (via Teams).
    Contenuto della lezione:
      Esercizi varî su:
        -   atomi, ∨-irriducibili, fattorizzazione non ridondante in ∨-irriducibili in un reticolo, algebre di Boole;
        -   scrittura posizionale di un numero naturale in base arbitraria;
        -   sistemi di equazioni congruenziali;
        -   aritmetica modulare: elementi invertibili, risoluzione di equazioni lineari, calcolo di potenze.
      FINE del CORSO
    Registrazione della lezione:   versione originale Teams (2h:49'37" - su Stream)   -   parte scritta 1 (3,87 MB) / parte scritta 2 (8,35 MB)

  VENTOTTESIMA LEZIONE (tre ore - ripasso ed esercizi) - 7 Giugno 2021:   trasmissione in diretta (via Teams).
    Contenuto della lezione:
      Esercizi varî sul calcolo della forma normale disgiuntiva (=F.N.D.), della somma di tutti gli implicanti primi (=s.t.i.p.) e di una forma minimale (=f.m.) per un polinomio booleano.
    Bibliografia:   [G-P] file Funzioni booleane; file Forme minimali di una funzione polinomiale - [L-L] Chapter 15, sections 7, 8, 9 and 11
    Registrazione della lezione:   versione originale Teams (3h:05'22" - su Stream)   -   solo parte scritta (3,87 MB)
    Esercizi:   Polinomi booleani
    Esercizi per il tutorato (8 Giugno 2021):   Polinomi booleani

  VENTISETTESIMA LEZIONE - 3 Giugno 2021:   trasmissione in diretta (via Teams).
    Contenuto della lezione:
      Proposizione: Ogni forma minimale di un polinomio booleano f è una somma di (alcuni) implicanti primi di f dalla quale non si può cancellare nessun termine.
      La nozione di consenso tra due prodotti (fondamentali).
      Lemma: La somma di due polinomi in consenso tra loro è equivalente alla loro somma con il loro consenso.
      Il Metodo del Consenso: algoritmo di calcolo della somma di tutti gli implicanti primi di un polinomio booleano in n variabili.
      Algoritmo di selezione di una forma minimale di un polinomio booleano a partire dalla somma di tutti gli implicanti primi del polinomio stesso.
      Esempi espliciti di calcolo della della somma di tutti gli implicanti primi (=s.t.i.p.) e di una forma minimale (=f.m.) per un polinomio booleano.
      Esempi espliciti di polinomi booleani che hanno diverse forme minimali.
      FINE del PROGRAMMA (seguono sole esercitazioni)
    Bibliografia:   [G-P] file Forme minimali di una funzione polinomiale - [L-L] Chapter 15, section 9
    Registrazione della lezione:   versione originale Teams (1h:52'19" - su Stream)   -   solo parte scritta (7,99 MB)
    Esercizi:   Polinomi booleani
    Esercizi per il tutorato (8 Giugno 2021):   Polinomi booleani

  VENTISEIESIMA LEZIONE - 31 Maggio 2021:   trasmissione in diretta (via Teams).
    Contenuto della lezione:
      F_n(2) = P_n(2) , cioè ogni funzione booleana su 2 è polinomiale.
      Esempi di calcolo della F.N.D. di un polinomio booleano.
      Misura della "grandezza" di una somma di prodotti; la relazione di "maggior semplicità" tra somme di prodotti.
      Forme minimali di un polinomio booleano: definizione, esistenza e (in generale) non unicità.
      La relazione di "implicazione" tra polinomi booleani; il legame tra la relazione di implicazione e quella di equivalenza. Gli implicanti primi di un polinomio booleano.
      Proposizione: Ogni somma di prodotti è equivalente alla somma di tutti i suoi implicanti primi (soltanto l'idea della dimostrazione).
    Bibliografia:   [G-P] file Funzioni booleane; file Forme minimali di una funzione polinomiale - [L-L] Chapter 15, sections 8, 9 and 11
    Registrazione della lezione:   versione originale Teams (1h:47'31" - su Stream)   -   solo parte scritta (7,33 MB)
    Esercizi:   Polinomi booleani
    Esercizi per il tutorato (8 Giugno 2021):   Polinomi booleani

  VENTICINQUESIMA LEZIONE - 27 Maggio 2021:   trasmissione in diretta (via Teams).
    Contenuto della lezione:
      Prodotti, prodotti fondamentali, prodotti completi in P_n.
      Lemma: Ogni prodotto in P_n è equivalente a un prodotto fondamentale oppure a 0.
      Somme di prodotti; somme di prodotti fondamentali, complete, ridondanti / non ridondanti.
      Lemma: Ogni somma di prodotti è equivalente ad una somma di prodotti fondamentali completi non ridondante.
      La Forma Normale Disgiuntiva di un polinomio booleano (=F.N.D.).
      Esistenza e unicità della F.N.D., metodi operativi per il calcolo (tramite manipolazioni successive o tramite "tavole di verità").
    Bibliografia:   [G-P] file Funzioni booleane - [L-L] Chapter 15, sections 7, 8 and 11
    Registrazione della lezione:   versione originale Teams (1h:59'17" - su Stream)   -   solo parte scritta (9,41 MB)
    Esercizi:   Polinomi booleani   -   Algebre di Boole
    Esercizi per il tutorato (1 Giugno 2021):   Algebre di Boole

  VENTIQUATTRESIMA LEZIONE - 24 Maggio 2021:   trasmissione in diretta (via Teams).
    Contenuto della lezione:
      Dimostrazione del Teorema di Rappresentazione (Stone - caso finito).
      Sottoalgebre di Boole di un'algebra di Boole; esempi, controesempi.
      Teorema di Rappresentazione (Stone - caso generale): Ogni algebra di Boole è isomorfa ad una sottoalgebra di Boole dell'insieme delle parti di un opportuno insieme (senza dimostrazione).
      Prodotti di algebre di Boole; i prodotti {0,1}ⁿ.
      L'insieme F_n(B) delle funzioni booleane in n variabili su un'algebra di Boole B; struttura di algebra di Boole.
      L'insieme P_n dei polinomi booleani in n variabili; funzioni booleane indotte da un polinomio booleano. L'insieme P_n(B) delle funzioni polinomiali su B; P_n(B) è sottoalgebra di Boole di F_n(B).
      Equivalenza tra polinomi booleani (quando inducono la stessa funzione booleana su 2:={0,1}).
      Teorema: Due polinomi booleani sono equivalenti se e soltanto se inducono la stessa funzione booleana su qualsiasi algebra di Boole.
    Bibliografia:   [G-P] file Algebre di Boole; file Funzioni booleane - [L-L] Chapter 15, sections 6, 7 and 8
    Registrazione della lezione:   versione originale Teams (2h:08'33" - su Stream)   -   solo parte scritta (10,4 MB)
    Videolezione:   Algebre di Boole 2 (isomorfismi tra algebre di Boole, sottoalgebre di Boole; Teorema di Rappresentazione di Stone [caso finito, caso generale])
    Esercizi:   Algebre di Boole   -   Reticoli, Algebre di Boole
    Esercizi per il tutorato (25 Maggio 2021):   Reticoli, algebre di Boole

  VENTITREESIMA LEZIONE - 20 Maggio 2021:   trasmissione in diretta (via Teams).
    Contenuto della lezione:
      Algebre di Boole: definizione come reticoli, definizione come insiemi con due operazioni; equivalenza delle due definizioni (idea della dimostrazione).
      Il Principio di Dualità per algebre di Boole.
      Esempi di algebre di Boole: l'insieme delle parti P(X); le funzioni a valori in un'algebra di Boole. Il caso degli insiemi totalmente ordinati.
      Anelli booleani. Teorema di Equivalenza (Stone): Ogni algebra di Boole corrisponde a un anello booleano unitario, e viceversa (forma esplicita della corrispondenza e idea della dimostrazione). L'esempio fondamentale: P(X) come anello booleano unitario con la "differenza simmetrica" come somma.
      Isomorfismi tra algebre di Boole, algebre di Boole isomorfe; la relazione di "essere isomorfe" tra algebre di Boole è un'equivalenza.
      Esempio: la biiezione canonica da P(X) a 2^X - per ogni insieme X - è un isomorfismo di algebre di Boole.
      Teorema di Rappresentazione (Stone - caso finito): Ogni algebra di Boole finita è isomorfa all'insieme delle parti dell'insieme dei suoi atomi, tramite un isomorfismo canonico esplicito.
      Corollario: Ogni algebra di Boole finita è isomorfa all'insieme delle funzioni caratteristiche dell'insieme dei suoi atomi. In particolare, la cardinalità di un'algebra di Boole è sempre una potenza di 2.
      Controesempio al Teorema di Stone: l'algebra di Boole dei sottoinsiemi finiti o cofiniti di N non è isomorfa a nessuna algebra di Boole della forma P(X).
    Bibliografia:   [G-P] file Algebre di Boole - [L-L] Chapter 15, sections 1 to 6
    Registrazione della lezione:   versione originale Teams (1h:54'32" - su Stream)   -   solo parte scritta (8,02 MB)
    Videolezioni:   Algebre di Boole 1 (definizioni; esempi, controesempi; Teorema di Equivalenza [con anelli booleani unitari])   -   Algebre di Boole 2 (isomorfismi tra algebre di Boole, sottoalgebre di Boole; Teorema di Rappresentazione di Stone [caso finito, caso generale])
    Esercizi:   Reticoli, Algebre di Boole
    Esercizi per il tutorato (25 Maggio 2021):   Reticoli, Algebre di Boole

  VENTIDUESIMA LEZIONE - 17 Maggio 2021:   trasmissione in diretta (via Teams).
    Contenuto della lezione:
      Teorema: In un reticolo finito, ogni elemento ha una ∨-fattorizzazione in fattori ∨-irriducibili non ridondante (cioè i fattori sono a due a due non comparabili).
      Proposizione: In un reticolo distributivo, una ∨-fattorizzazione non ridondante in fattori ∨-irriducibili - se esiste - è unica, a meno dell'ordine dei fattori.
      Teorema di ∨-Fattorizzazione Unica (in ∨-irriducibili, non ridondante) per reticoli finiti distributivi.
      Proposizione: In un reticolo finito unicamente complementato, ogni elemento ∨-irriducibile è un atomo.
      Teorema di ∨-Fattorizzazione Unica (in atomi a due a due distinti) per reticoli finiti distributivi complementati.
      Sottoreticoli in un reticolo; ogni sottoreticolo è a sua volta un reticolo.
      Isomorfismi tra reticoli, proprietà fondamentali. Reticoli isomorfi; l'essere isomorfi è una relazione di equivalenza tra reticoli.
      La "forma" di un reticolo D_n (n > 0). Criterio di isomorfismo tra un reticolo D_r e un reticolo D_s .
      Teorema (caratterizzazione dei reticoli distributivi): Un reticolo è distributivo se e soltanto se non contiene sottoreticoli isomorfi a 𝔑₅ oppure a 𝔐₅ (cenni).
    Bibliografia:   [G-P] file Reticoli, paragrafi da 4 a 6 - [L-L] Chapter 14, sections 8 to 11; Chapter 15, sections 1, 2, 4 and 5
    Registrazione della lezione:   versione originale Teams (1h:59'30" - su Stream)   -   solo parte scritta (9,60 MB)
    Videolezioni:   Reticoli 2 (∨-fattorizzazione: ∨-irriducibili, atomi, esistenza/unicità di ∨-fattorizzazioni)   -   Reticoli 3 (sottoreticoli; isomorfismi di reticoli, reticoli isomorfi)
    Esercizi:   Reticoli, Algebre di Boole
    Esercizi per il tutorato (18 Maggio 2021):   Reticoli

  VENTUNESIMA LEZIONE - 13 Maggio 2021:   trasmissione in diretta (via Teams).
    Contenuto della lezione:
      Proposizione: Ogni reticolo finito è limitato.   -   Controesempi alla proposizione.
      Complementi in un reticolo limitato; reticoli complementati. Questioni di esistenza e unicità del complemento, esempi e controesempi. I reticoli 𝔑₅ e 𝔐₅ sono complementati.
      Reticoli distributivi. Esempi e controesempi: P(X) e D_n sono distributivi, 𝔑₅ e 𝔐₅ non sono distributivi. Complementazione e distributività sono preservate dalla dualità.
      Proposizione: In un reticolo distributivo, il complemento - se esiste - è unico, e valgono le Leggi di De Morgan per il complemento di x∨y e di x∧y .
      ∨-Fattorizzazione in un reticolo; elementi ∨-riducibili o ∨-irriducibili. Atomi (in un reticolo limitato inferiormente). Esempi e controesempi di ∨-riducibili, di ∨-irriducibili e di atomi.
      Proposizione: In un reticolo finito, (a) un elemento è ∨-irriducibile ⇔ copre al più un atomo, e (b) ogni atomo è ∨-irriducibile.
    Bibliografia:   [G-P] file Reticoli, paragrafi 3 e 4 - [L-L] Chapter 14, sections from 8 to 11
    Registrazione della lezione:   versione originale Teams (1h:55'11" - su Stream)   -   solo parte scritta (5,17 MB)
    Videolezioni:   Reticoli 1 (generalità, esempi; complementi in un reticolo; distributività)   -   Reticoli 2 (∨-fattorizzazione: ∨-irriducibili, atomi, esistenza/unicità di ∨-fattorizzazioni)
    Esercizi:   Reticoli, Algebre di Boole
    Esercizi per il tutorato (18 Maggio 2021):   Reticoli

  VENTESIMA LEZIONE - 10 Maggio 2021:   trasmissione in diretta (via Teams).
    Contenuto della lezione:
      Sottoinsiemi (semi)limitati in un insieme ordinato.
      L'ordine indotto in un sottoinsieme E' di un insieme ordinato E. L'ordine indotto nell'insieme E^S da un insieme qualsiasi S a un insieme ordinato E.
      L'ordine prodotto e l'ordine lessicografico in un prodotto cartesiano di insiemi ordinati.
      Reticoli: definizione come insiemi ordinati e definizione come insiemi con due operazioni binarie.
      Teorema di Corrispondenza (per reticoli): Le due definizioni di reticolo sono equivalenti (con cenni di dimostrazione).
      Il Principio di Dualità per reticoli (in termini di relazione d'ordine e in termini di operazioni).
      Esempi di reticoli: gli insiemi con ordinamento totale, l'insieme delle parti di un insieme, N e N₊ con la divisibilità, ogni intervallo in un reticolo, il reticolo dei divisori di n. Prodotti diretti di reticoli; reticoli di funzioni.
      Controesempi: insiemi ordinati che non sono reticoli.
    Bibliografia:   [G-P] file Relazioni - 2; file Reticoli, paragrafi 1 e 2 - [L-L] Chapter 14, section 8
    Registrazione della lezione:   versione originale Teams (1h:50'02" - su Stream)   -   solo parte scritta (5,09 MB)
    Videolezioni:   Reticoli 1 (generalità, esempi; complementi in un reticolo; distributività)   -   Insiemi ordinati (generalità, esempi, elementi speciali)
    Esercizi:   Reticoli, Algebre di Boole   -   Insiemi ordinati, Reticoli
    Esercizi per il tutorato (11 Maggio 2021):   Aritmetica modulare, Sistemi di equazioni congruenziali

  DICIANNOVESIMA LEZIONE - 6 Maggio 2021:   trasmissione in diretta (via Teams).
    Contenuto della lezione:
      Relazioni d'ordine, insiemi ordinati. Ordini totali, ordini buoni: ogni ordine buono è totale. Il Principio di Dualità per insiemi ordinati.
      Relazione di copertura e diagramma di Hasse per un insieme ordinato.
      Elementi minimali - risp. massimali - minimo min(E') - risp. massimo max(E') - per un sottoinsieme E' in un insieme ordinato E; unicità di min(E') - risp. di max(E') - se esiste.
      Minoranti - risp. maggioranti - estremo inferiore inf(E') - risp. estremo superiore sup(E') - per un sottoinsieme E' in un insieme ordinato E; unicità di inf(E') - risp. di sup(E') - se esiste.
      Intervalli - chiusi, aperti, semi-chiusi/aperti, limitati o illimitati - in un insieme ordinato qualsiasi.
    Bibliografia:   [Ca] Capitolo 1, paragrafo 3(B) - [G-P] file Relazioni - 2 - [L-L] Chapter 14, sections 1, 2, 3, 5 and 7
    Registrazione della lezione:   versione originale Teams (1h:52'58" - su Stream)   -   solo parte scritta (5,02 MB)
    Videolezione:   Insiemi ordinati (generalità, esempi, elementi speciali)
    Esercizi:   Insiemi ordinati, Reticoli
    Esercizi per il tutorato (11 Maggio 2021):   Aritmetica modulare, Sistemi di equazioni congruenziali

  DICIOTTESIMA LEZIONE - 3 Maggio 2021:   trasmissione in diretta (via Teams).
    Contenuto della lezione:
      Sistemi di equazioni congruenziali: discussione, sistemi in forma risolta, sistemi in forma cinese (o "sistemi cinesi").
      Il Teorema Cinese del Resto (senza dimostrazione) per sistemi in forma cinese.
      Metodo di risoluzione di un sistema tramite sostituzioni successive oppure - sotto le ipotesi del caso - tramite la procedura fornita dal Teorema Cinese del Resto. Esempi di risoluzione di un sistema di equazioni congruenziali.
    Bibliografia:   [Ca] Capitolo II, paragrafo 5 - [G-P] file Aritmetica sugli interi, congruenze, Teorema Cinese del Resto - [L-L] Chapter 11, section 9 - [PC] Capitolo 2, paragrafo 7
    Registrazione della lezione:   versione originale Teams (2h:01'29" - su Stream)   -   solo parte scritta (6,85 MB)
    Esercizi:   Equazioni congruenziali e modulari   -   Aritmetica modulare   -   MCD tra interi, Equazioni diofantee
    Esercizi per il tutorato (4 Maggio 2021):   Equazioni congruenziali e modulari, Aritmetica modulare

  DICIASSETTESIMA LEZIONE - 29 Aprile 2021:   trasmissione in diretta (via Teams).
    Contenuto della lezione:
      Il gruppo U(Z_n) degli elementi invertibili in Z_n: criterio di invertibilità, calcolo dell'inverso mediante risoluzione di una equazione modulare (dunque congruenziale, dunque diofantea).
      Corollario: Z_n è un campo ⇔ n è irriducibile.
      La funzione φ di Eulero: definizione, proprietà, formula esplicita.
      Ripetitività delle potenze in Z_n: generalità, caratterizzazione del caso delle potenze con base una classe invertibile;
      Il Teorema di Eulero (senza dimostrazione).
      L'algoritmo di riduzione dell'esponente di una potenza in Z_n .
      Criteri di divisibilità in Z: strategia generale (calcolo di una classe in Z_n) esempi specifici.
    Bibliografia:   [Ca] Capitolo II, paragrafi 4, 5 e 6 - [G-P] file Aritmetica sugli interi, congruenze, Teorema Cinese del Resto; file Aritmetica sugli interi, etc. (complementi) - [L-L] Chapter 11, sections 8 and 9 - [PC] Capitolo 2, paragrafi 6-9
    Registrazione della lezione:   versione originale Teams (2h:01'28" - su Stream)   -   solo parte scritta (7,64 MB)
    Esercizi:   Aritmetica modulare   -   MCD tra interi, Equazioni diofantee
    Esercizi per il tutorato (4 Maggio 2021):   Equazioni congruenziali e modulari, Aritmetica modulare

  SEDICESIMA LEZIONE - 26 Aprile 2021:   trasmissione in diretta (via Teams).
    Contenuto della lezione:
      Compatibilità di somma e prodotto con ogni congruenza modulo n. Aritmetica modulare: somma e prodotto in Z_n.
      Teorema: Z_n è un anello commutativo unitario (esercizio - cenni di dimostrazione).
      Esercizio:   (a) non esistono divisori di zero in Z_n ⇔ n è primo;   (b) non esistono divisori di zero in Z_n ⇔ Z_n è un campo;   (c) Z_n è un campo ⇔ n è irriducibile.
      Equazioni congruenziali, equazioni modulari, equazioni diofantee: connessioni tra le une e le altre.
      Criterio di esistenza di soluzioni, algoritmo per il calcolo di una soluzione, insieme completo di soluzioni per equazioni congruenziali e per equazioni modulari.
      Elementi invertibili in Z_n; formula esplicita della soluzione di un'equazione modulare in caso di esistenza e unicità.
    Bibliografia:   [Ca] Capitolo II, paragrafi 4 e 5 - [G-P] file Aritmetica sugli interi, congruenze, Teorema Cinese del Resto; file Aritmetica sugli interi, etc. (complementi) - [L-L] Chapter 11, sections 8 and 9 - [PC] Capitolo 2, paragrafi 6 e 7
    Registrazione della lezione:   versione originale Teams (2h:06'23" - su Stream)   -   solo parte scritta (5,60 MB)
    Esercizi:   MCD tra interi, Equazioni diofantee   -   Equazioni congruenziali, Equazioni modulari
    Esercizi per il tutorato (27 Aprile 2021):   MCD, mcm, Equazioni diofantee

  QUINDICESIMA LEZIONE - 22 Aprile 2021:   trasmissione in diretta (via Teams).
    Contenuto della lezione:
      Forma esplicita di MCD(a,b) e di mcm(a,b) in termini di fattorizzazioni di a e di b ; la relazione   MCD(a,b) mcm(a,b) = a b
      Calcolo di mcm(a,b) tramite il calcolo di MCD(a,b) - con l'algoritmo euclideo delle divisioni successive - e la formula   mcm(a,b) = a b / MCD(a,b)
      Equazioni diofantee: definizione, criterio per l'esistenza di soluzioni, procedura per il calcolo esplicito di una soluzione. Esempi.
      Congruenze ≡_n in Z (richiami). Ogni congruenza è una equivalenza; descrizione delle classi di congruenza e dell'insieme quoziente   Z_n := Z / ≡_n   .
    Bibliografia:   [Ca] Capitolo II, paragrafi 2-4 - [G-P] file Aritmetica sugli interi, congruenze, Teorema Cinese del Resto - [L-L] Chapter 11, sections 6-8 - [PC] Capitolo 2, paragrafi 2-3, 6-7
    Registrazione della lezione:   versione originale Teams (1h:52'48" - su Stream)   -   solo parte scritta (6,46 MB)
    Esercizi:   Scrittura posizionale, MCD, Equazioni diofantee   -   MCD tra interi, Equazioni diofantee
    Esercizi per il tutorato (27 Aprile 2021):   MCD, mcm, Equazioni diofantee

  QUATTORDICESIMA LEZIONE - 19 Aprile 2021:   trasmissione in diretta (via Teams).
    Contenuto della lezione:
      Divisione con resto tra numeri interi: esistenza e unicità di quoziente e resto (positivo).
      Esistenza del MCD in Z, e identità di Bézout per esso: dimostrazione e calcolo mediante l'algoritmo euclideo delle divisioni successive. Esempi di calcolo esplicito.
      Proposizione: In Z, ogni irriducibile è primo (senza dimostrazione).
      Teorema Fondamentale dell'Aritmetica: esistenza e unicità di una fattorizzazione in irriducibili per interi (non nulli) non invertibili (cenni di dimostrazione dell'unicità).
      La fattorizzazione "canonica" di un intero. La relazione tra la fattorizzazione "canonica" di un intero e quella di un suo qualunque divisore o multiplo.
    Bibliografia:   [AaVv] file Numeri interi (D'Andrea), paragrafo 4 - [Ca] Capitolo II, paragrafi 1-3 - [G-P] file Aritmetica sugli interi, congruenze, Teorema Cinese del Resto - [L-L] Chapter 11, sections 4-7 - [PC] Capitolo 2, paragrafi 2-3
    Registrazione della lezione:   versione originale Teams (1h:50'01" - su Stream)   -   solo parte scritta (6,78 MB)
    Esercizi:   MCD tra interi, Equazioni diofantee
    Esercizi per il tutorato (20 Aprile 2021):   Cardinalità, Numeri interi

  TREDICESIMA LEZIONE - 15 Aprile 2021:   trasmissione in diretta (via Teams).
    Contenuto della lezione:
      L'insieme Z dei numeri interi: relazione coi numeri naturali, operazioni (somma e prodotto), ordinamento, valore assoluto.
      Z è un anello commutativo unitario senza divisori di zero, e la relazione d'ordine in esso è totale.
      Divisibilità, multipli e divisori in Z. Elementi unità (=invertibili) in Z; elementi associati. Elementi riducibili, irriducibili, primi.
      Lemma: Ogni primo è irriducibile.
      Fattorizzazioni di un elemento, fattorizzazioni banali.
      Teorema Fondamentale dell'Aritmetica - 1^a parte (esistenza): Per ogni intero non nullo e non invertibile esiste una fattorizzazione in prodotto di interi irriducibili.
      Teorema di Euclide: Esistono infiniti interi irriducibili.
      Massimo comun divisore (=M.C.D.) e minimo comun multiplo (=m.c.m.). Interi primi tra loro (o "coprimi").
    Bibliografia:   [Ca] Capitolo II, paragrafi 2 e 3 - [G-P] file Aritmetica sugli interi, congruenze, Teorema Cinese del Resto - [L-L] Chapter 11, sections 1-3, 5-7 - [PC] Capitolo 2, paragrafi 1-3
    Registrazione della lezione:   versione originale Teams (1h:49'34" - su Stream)   -   solo parte scritta (7,05 MB)
    Esercizi:   Numeri Interi
    Esercizi per il tutorato (20 Aprile 2021):   Cardinalità, Numeri interi

  DODICESIMA LEZIONE - 12 Aprile 2021:   trasmissione in diretta (via Teams).
    Contenuto della lezione:
      Proposizione: N è equipotente a N × N.
      1^o Teorema di Cantor: L'unione di una famiglia finita (non vuota) o numerabile di insiemi numerabili è numerabile.
      Generalizzazioni del Primo Teorema di Cantor (cenni)   -   Applicazioni: Z, ZxZ e Q sono numerabili.
      2^o Teorema di Cantor: La cardinalità dell'insieme delle parti di un insieme è strettamente maggiore della cardinalità dell'insieme stesso.
      I numeri cardinali infiniti superiori ℵ_n (per ogni n in N). La cardinalità del continuo: |R| = |P(N)| (senza dimostrazione).
      L'ipotesi del continuo generalizzata e l'ipotesi del continuo generalizzata (cenni).
      La "distribuzione" dei numeri cardinali rispetto alla relazione d'ordine (cenni).
    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
    Registrazione della lezione:   versione originale Teams (1h:59'26" - su Stream)   -   solo parte scritta (8,95 MB)
    Videolezioni:   Cardinalità 1 (insiemi equipotenti, cardinalità; Primo Teorema di Cantor)   -   Cardinalità 2 (Secondo Teorema di Cantor)
    Esercizi:   Cardinalità (N.B.: in linea di massima, questi esercizi sono un po' più difficili della media)
    Esercizi per il tutorato (13 Aprile 2021):   Induzione, Scrittura posizionale, Cardinalità

  UNDICESIMA LEZIONE - 8 Aprile 2021:   trasmissione in diretta (via Teams).
    Contenuto della lezione:
      Insiemi numerabili. Ogni insieme numerabile è infinito.
      Relazione d'ordine (buono) tra numeri cardinali; il Teorema di Schroeder-Bernstein (senza dimostrazione della transitività e dell'essere buono).
      Proposizione: Ogni insieme infinito contiene un sottoinsieme numerabile; ogni sottoinsieme di un insieme numerabile o è finito oppure è numerabile.
      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.
    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
    Registrazione della lezione:   versione originale Teams (1h:46'24" - su Stream)   -   solo parte scritta (4,96 MB)
    Videolezioni:   Cardinalità 1 (insiemi equipotenti, cardinalità; Primo Teorema di Cantor)
    Esercizi:   Cardinalità (N.B.: in linea di massima, questi esercizi sono un po' più difficili della media)
    Esercizi per il tutorato (13 Aprile 2021):   Induzione, Scrittura posizionale, Cardinalità

  DECIMA LEZIONE - 1 Aprile 2021:   trasmissione in diretta (via Teams).
    Contenuto della lezione:
      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. La cardinalità (o "potenza") di un insieme; numeri cardinali. Insiemi finiti e insiemi infiniti.
    Bibliografia:   [Ca] Capitolo II, paragrafo 2 - [PC] Capitolo 1, paragrafo 5; Capitolo 2, paragrafo 10
    Registrazione della lezione:   versione originale Teams (1h:44'22" - su Stream)   -   solo parte scritta (8,56 MB)
    Videolezioni:   Numerazione (numerazione in base arbitraria / scrittura posizionale)   -   Cardinalità 1 (insiemi equipotenti, cardinalità; Primo Teorema di Cantor)
    Esercizi:   Scrittura posizionale
    Esercizi per il tutorato (6 Aprile 2021):   Relazioni, Induzione, Scrittura posizionale

  NONA LEZIONE - 29 Marzo 2021:   trasmissione in diretta (via Teams).
    Contenuto della lezione:
      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.
      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 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
    Registrazione della lezione:   versione originale Teams (1h:58'24" - su Stream)   -   solo parte scritta (4,85 MB)
    Registrazione di lezioni analoghe (un po' più in dettaglio):   versione audiovideo: prima parte [1h:44'36" - su Stream] / seconda parte [1h:32'33" - su Stream] / terza parte [1h:43'25" - su Stream]   -   solo parte scritta: prima parte [3,90 MB] / seconda e terza parte [7,46 MB]
    Videolezioni:   Induzione (metodo di dimostrazione per induzione [semplice / forte / minimo])   -   Divisione (divisione con resto tra numeri naturali)   -   Numerazione (numerazione in base arbitraria / scrittura posizionale)
    Esercizi:   Principio di Induzione   -   Scrittura posizionale
    Esercizi per il tutorato (30 Marzo 2021):   Insiemi e corrispondenze

  OTTAVA LEZIONE - 25 Marzo 2021:   trasmissione in diretta (via Teams).
    Contenuto della lezione:
      Sistema dei numeri naturali (=S.N.N.): definizione tramite gli assiomi di Peano; il Principio di Induzione Debole, o Semplice (=Pr.I.D./S.). Esistenza e unicità di un S.N.N. (cenni).
      Ordinamenti buoni: definizione, proprietà "buono" implica "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 (qiundi 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).
    Bibliografia:   [AaVv] file Numeri naturali (D'Andrea) - [Ca] Capitolo I, paragrafo 5 - [PC] Capitolo 1, paragrafo 4
    Registrazione della lezione:   versione originale Teams (2h:03'30" - su Stream)   -   solo parte scritta (4,02 MB)
    Registrazione di lezioni analoghe (un po' più in dettaglio):   versione audiovideo: prima parte [1h:44'36" - su Stream] / seconda parte [1h:32'33" - su Stream] / terza parte [1h:43'25" - su Stream]   -   solo parte scritta: prima parte [3,90 MB] / seconda e terza parte [7,46 MB]
    Videolezione:   Naturali (sistema dei numeri naturali: assiomi di Peano, ordine, operazioni)
    Esercizi:   Principio di Induzione
    Esercizi per il tutorato (30 Marzo 2021):   Insiemi e corrispondenze

  SETTIMA LEZIONE - 22 Marzo 2021:   trasmissione in diretta (via Teams).
    Contenuto della lezione:
      Operazioni (binarie) in un insieme; proprietà speciali possibili. Elementi speciali: elemento neutro, elemento assassino.
      Unicità di elemento neutro/assassino (se esiste); unicità dell'elemento inverso (se esiste, nel caso associativo).
      Semigruppi, monoidi, gruppi; definizione, esempi e controesempi. Il gruppo degli invertibili in un monoide.
      Il monoide E^E 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
    Registrazione della lezione:   versione originale Teams (2h:01'29" - su Stream)   -   solo parte scritta (6,66 MB)
    Videolezioni:   Operazioni 1 (operazioni in un insieme; insiemi con una operazione)   -   Operazioni 2 (insiemi con più operazioni)
    Esercizi:   Gruppoidi e morfismi (N.B.: soltanto alcuni di questi esercizi sono pertinenti al programma svolto)

  SESTA LEZIONE - 18 Marzo 2021:   trasmissione in diretta (via Teams).
    Contenuto della lezione:
      La relazione associata all'insieme quoziente di una partizione.
      La congruenza modulo n tra i numeri interi è una relazione di equivalenza (esercizio).
      Classi di equivalenza e loro proprietà fondamentali.
      Teorema: (a) La relazione in E associata ad 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
    Registrazione della lezione:   versione originale Teams (1h:29'37" - su Stream)   -   solo parte scritta (4,95 MB)
    Registrazione di lezioni analoghe (un po' più in dettaglio):   prima parte (versione audiovideo [1h:52'23" - su Stream] / solo parte scritta [4,14 MB])   -   seconda parte (versione audiovideo [1h:46'03" - su Stream] / solo parte scritta [3,90 MB])
    Videolezioni:   Equivalenze 1 (equivalenze e partizioni)   -   Equivalenze 2 (equivalenze e funzioni)
    Esercizi:   Relazioni 1   -   Relazioni 2

  QUINTA LEZIONE - 15 Marzo 2021:   trasmissione in diretta (via Teams).
    Contenuto della lezione:
      Relazioni (binarie) in un insieme; operazioni insiemistiche tra relazioni, composizione, inversa 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 interi è un preordine, ma non un ordine; la divisibilità tra numeri naturali è un ordine, ma non è totale. 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; insieme quoziente e proiezione canonica associati ad una partizione.
    Bibliografia:   [Ca] Capitolo I, paragrafo 3 - [G-P] file Relazioni 1 - [L-L] Chapter 2 - [PC] Capitolo 1, paragrafo 2
    Registrazione della lezione:   versione originale Teams (1h:54'31" - su Stream)   -   solo parte scritta (4,30 MB)
    Videolezioni:   Relazioni (relazioni in un insieme: generalità, esempi)
    Esercizi:   Insiemi, funzioni, relazioni   -   Relazioni 1   -   Relazioni 2

  QUARTA LEZIONE - 11 Marzo 2021:   trasmissione in diretta (via Teams).
    Contenuto della lezione:
      Composizione di funzioni: la composizione di due funzioni è ancora una funzione.
      Funzioni invertibili (definizione). Caratterizzazione delle funzioni invertibili in termini intrinseci (biiettività) e in termini della corrispondenza inversa (dev'essere a sua volta una funzione).
      Permutazioni in un insieme. Funzioni caratteristiche in un insieme.
      Esiste una funzione biiettiva esplicita tra l'insieme delle parti di un insieme E e l'insieme delle funzioni caratteristiche in E; descrizione esplicita della funzione inversa.
    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
    Registrazione della lezione:   versione originale Teams (1h:59'01" - su Stream)   -   solo parte scritta (4,56 MB)
    Videolezioni:   Funzioni 2 (composizione di funzioni, funzioni invertibili)   -   Funzioni caratteristiche (funzioni caratteristiche in un insieme)
    Esercizi:   Funzioni

  TERZA LEZIONE - 8 Marzo 2021:   trasmissione in diretta (via Teams).
    Contenuto della lezione:
      Funzioni (o "applicazioni"): definizione, esempi, controesempi. Immagine - tramite una funzione - di un elemento del dominio; l'immagine di una funzione.
      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.
      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.
      Caratterizzazione della biiettività di una funzione tramite la corrispondenza inversa (che deve essere a sua volta una funzione).
      Esercizi varî su identità notevoli tra insiemi.
    Bibliografia:   [Ca] Capitolo I, paragrafo 2 - [G-P] file Funzioni e cardinalità - [L-L] Chapter 3, sections 3.1-5 - [PC] Capitolo 1, paragrafo 3
    Registrazione della lezione:   versione originale Teams (2h:00'54" - su Stream)   -   solo parte scritta (4,85 MB)
    Videolezione:   Funzioni 1 (funzioni; iniettività, suriettività, biiettività)
    Esercizi:   Corrispondenze   -   Funzioni

  SECONDA LEZIONE - 4 Marzo 2021:   trasmissione in diretta (via Teams).
    Contenuto della lezione:
      Corrispondenze tra insiemi: definizione, notazione.
      Immagine - tramite una corrispondenza data - di un sottoinsieme del dominio; controimmagine - tramite una corrispondenza data - di un sottoinsieme del codominio.
      Esempi, casi speciali: relazioni, funzioni; la corrispondenza vuota, la corrispondenza totale; la corrispondenza identica (o "identità") su un insieme.
      Costruzioni sulle corrispondenze: operazioni insiemistiche tra corrispondenze, la corrispondenza inversa, 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.
    Bibliografia:   [Ca] Capitolo I, paragrafo 2 - [L-L] Chapter 2 - [PC] Capitolo 1, paragrafo 2
    Registrazione della lezione:   versione originale Teams (1h:57'58" - su Stream)   -   solo parte scritta (4,20 MB)
    Videolezione:   Corrispondenze (corrispondenze tra insiemi e operazioni tra di esse)
    Esercizi:   Insiemi   -   Corrispondenze

  PRIMA LEZIONE - 1 Marzo 2021:   trasmissione in diretta (via Teams).
    Contenuto della lezione:
      Presentazione generale del corso.
      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.
      Sottoinsiemi, sovrainsiemi. Inclusione tra insiemi; l'uguaglianza tra insiemi come doppia inclusione. Insiemi disgiunti.
      L'insieme vuoto. L'insieme delle parti di un insieme: definizione, esempi.
      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.
    Bibliografia:   [Ca] Capitolo I, paragrafo 1 - [G-P] file Insiemi - [L-L] Chapter 1 - [PC] Capitolo 1, paragrafo 1
    Registrazione della lezione:   versione originale Teams (2h:01'00" - su Stream)   -   solo parte scritta (9,70 MB)
    Videolezione:   Insiemi (insiemi, sottoinsiemi, insieme delle parti, operazioni tra insiemi)
    Esercizi:   Insiemi