Corso di Laurea Triennale in   "Ingegneria Informatica"   a.a. 2020-2021   ALGEBRA e LOGICA   6 CFU   Docente:   Fabio Gavarini

Ultimo aggiornamento:   21 Febbraio 2022

---

CORSO CHIUSO

☆   ESAMI IN CORSO FINO ALLA SESSIONE DI GENNAIO-FEBBRAIO 2022   ☆

---

Il corso si svolge online sulla piattaforma Microsoft Teams, nella classe virtuale "Algebra e Logica (GAVARINI - 8039351 ALGEBRA E LOGICA)" - codice 3q04k52
Ci si può anche collegare da qui (per chi è già iscritto a Teams, necessariamente)
Le lezioni saranno trasmesse in diretta on-line su Teams (vedi sopra); chi non fosse (ancora) iscritto a Teams potrà seguire la diretta tramite questo link.
Le registrazioni delle lezioni saranno postate in rete, i link li trovate qui sotto e anche nel diario del corso

ORARIO delle LEZIONI: Lunedì 14:00-16:00 / Giovedì 14:00-16:00   -   Secondo semestre (01 Marzo 2021 - 12 Giugno 2021)
TUTORATO: Martedì 14:00-16:00 (a cura di Claudio Fabroni) N.B.: in linea di massima, ciascuna sessione di tutorato verterà su una lista di esercizi assegnata appositamente, volta per volta,
o anche sugli esercizi assegnati per la settimana in corso (o per le settimane precedenti),
o anche può essere dedicato a riprendere e chiarire argomenti trattati a lezione, secondo necessità.
RICEVIMENTO: per appuntamento:   tel. 06.7259.4606 / e-mail gavarini[at]mat.uniroma2.it

---

☆   PROGRAMMA   ☆

Versione Super-Sintetica:
Insiemi, corrispondenze, relazioni, funzioni. Equivalenze, partizioni relazioni d'ordine. Insiemi con operazioni.
Numeri naturali; il Principio di induzione. Divisione con resto; numerazione posizionale in base arbitraria.
Cardinalità di insiemi; ordinamento tra numeri cardinali. Insiemi infiniti.
Numeri interi. Divisione con resto; M.C.D., m.c.m., algoritmo euclideo per il M.C.D. Il Teorema Fondamentale dell'Aritmetica.
Equazioni diofantee. Relazioni di congruenza tra interi; equazioni congruenziali. Aritmetica modulare. Sistemi di equazioni congruenziali.
Insiemi ordinati; diagramma di Hasse, elementi speciali. Reticoli; algebre di Boole. Polinomi booleani; forma normale disgiuntiva, forme minimali.

NOTA: lo sviluppo del corso, in dettaglio, è descritto nel diario del corso,
che eventualmente può essere usato come guida alla studio del materiale oggetto del corso.

ESAMI

L'esame consiste in una prova scritta e una prova orale, entrambe obbligatorie;
condizione preliminare per essere ammessi alla prova orale è aver già superato una prova scritta (con un voto sufficiente, cioè almeno 18).
Si può sostenere la prova orale anche in un appello successivo o in una sessione successiva a quella in cui si sia superata la prova scritta.
☆       ☆     ☆   ☆☆☆   ☆     ☆       ☆
È possibile sostenere la prova scritta anche più di una volta: in tal caso, sarà considerato come rilevante il voto più alto ottenuto.
Se si sostiene una prova orale senza successo - perché respinti o ritirati - il voto con cui sia stata precedentemente superata la prova scritta resta valido
per presentarsi di nuovo alla prova orale; in altre parole, si deve rifare soltanto la prova orale, e non anche la prova scritta.
È possibile sostenere nuovamente la prova orale anche nella stessa sessione.
☆       ☆     ☆   ☆☆☆   ☆     ☆       ☆
Per partecipare a ciascuna prova (scritta o orale), *è necessario prenotarsi*, nei giorni precedenti, attraverso il sito Delphi.
In occasione di ciascuna prova (scritta e/o orale) è necessario portare con sé un documento di riconoscimento e (se lo avete) il libretto universitario.
☆       ☆     ☆   ☆☆☆   ☆     ☆       ☆
Durante le prove (scritte e/o orali) è vietato l'uso di libri, appunti, dispense, calcolatrici, telefoni cellulari, tablet, innesti cibernetici, e quant'altro:
in breve, è vietato l'uso di qualsiasi strumento di archiviazione/ricezione/trasmissione/elaborazione di dati,
salvo specifiche eccezioni motivate da esigenze fisiche debitamente comprovate secondo la normativa d'ateneo:
a tal fine gli studenti interessati devono preventivamente rivolgersi al CARIS prima dell'esame stesso (scritto o orale che sia).
Non è consentito uscire durante il compito (salvo emergenze).

---

MATERIALE DIDATTICO
(libri, dispense, audio-video, ecc.)

  DIARIO del CORSO:   qui si registra in dettaglio, lezione per lezione, lo sviluppo del corso, indicando in particolare dove, nelle varie referenze citate (libri, dispense, videolezioni, ecc. ecc.) sono trattati i diversi argomenti oggetto delle lezioni (si può quindi usare come guida allo studio del corso stesso).


  TESTI consigliati (complessivamente contengono, sostanzialmente, tutto il materiale trattato nel corso, con numerosi esempi ed esercizi, anche svolti) :

• S. Lipschutz, M. Lipson, Matematica discreta, Etas Libri, Milano, 1985   (in italiano)
• S. Lipschutz, M. Lipson, Discrete Mathematics, Third Edition, Schaum's Outlines, McGraw-Hill, 2007   (in inglese)
• G. M. Piacentini Cattaneo, Algebra, ed. Decibel - Zanichelli, Padova, 1996
• G. Campanella, Appunti di Algebra 1 & 2 - scaricabile da qui
• L. Geatti, G. Pareschi, Dispense - che trovate qui sotto

  MATERIALE AUDIO-VIDEO:    

• registrazioni audiovideo delle lezioni del corso (dalla piattaforma Microsoft Stream - è necessario essere registrati):
• 1 Marzo 2021 (insiemi, sottoinsiemi, insieme delle parti, operazioni tra insiemi) - 2h:01'00"
• 4 Marzo 2021 (corrispondenze tra insiemi e costruzioni fondamentali su di esse) - 1h:57'58"
• 8 Marzo 2021 (funzioni; iniettività, suriettività, biiettività) - 2h:00'54"
• 11 Marzo 2021 (funzioni invertibili; funzioni caratteristiche in un insieme; sottoinsiemi vs. funzioni caratteristiche) - 1h:59'01"
• 15 Marzo 2021 (relazioni; ordini, equivalenze; partizioni) - 1h:54'31"
• 18 Marzo 2021 (corrispondenza tra equivalenze e quozienti di partizioni) - 1h:29'37"
• 22 Marzo 2021 (insiemi con operazioni) - 2h:01'29"
• 25 Marzo 2021 (Sistema dei Numeri Naturali e sue proprietà) - 2h:03'30"
• 29 Marzo 2021 (Principio di Induzione - Divisione con resto tra numeri naturali - Scrittura posizionale in base arbitraria) - 1h:58'24"
• 1 Aprile 2021 (Scrittura posizionale in base arbitraria - Cardinalità) - 1h:44'22"
• 8 Aprile 2021 (Cardinalità: relazione d'ordine tra numeri cardinali, proprietà dei cardinali infiniti) - 1h:46'24"
• 12 Aprile 2021 (Cardinalità: Primo e Secondo Teorema di Cantor (e loro conseguenze), cardinali infiniti superiori) - 1h:59'26"
• 15 Aprile 2021 (Numeri interi - divisibilità e elementi speciali - Teorema Fondamentale dell'Aritmetica [1^a parte: esistenza] - Teorema di Euclide - MCD e mcm di due interi) - 1h:59'26"
• 19 Aprile 2021 (Divisione euclidea tra interi - Esistenza e algoritmo di calcolo di MCD(a,b) e di una sua identità di Bézout - Teorema Fondamentale dell'Aritmetica [completo] - Forma "canonica" della fattorizzazione di un intero) - 1h:50'01"
• 22 Aprile 2021 (MCD e mcm in termini di fattorizzazioni - risoluzione di un'equazione diofantea - congruenze modulo n tra interi: proprietà fondamentali, descrizione delle classi e dell'insieme quoziente) - 1h:52'48"
• 26 Aprile 2021 (Operazioni tra numeri modulari: l'anello degli interi modulari - Equazioni congruenziali, equazioni modulari: discussione e risoluzione) - 2h:06'23"
• 29 Aprile 2021 (Interi modulari invertibili - Potenze di interi modulari - Criteri di divisibilità) - 2h:01'28"
• 3 Maggio 2021 (Sistemi di equazioni congruenziali - Teorema Cinese del Resto) - 2h:01'29"
• 6 Maggio 2021 (Insiemi ordinati - diagrammi di Hasse - elementi speciali) - 1h:52'58"
• 10 Maggio 2021 (Ordine prodotto, ordine lessicografico - Reticoli - esempi e controesempi) - 1h:50'02"
• 13 Maggio 2021 (Reticoli limitati - Complementi - Reticoli distributivi - ∨-fattorizzazione in un reticolo [generalità]) - 1h:55'11"
• 17 Maggio 2021 (∨-fattorizzazione in un reticolo [esistenza e unicità] - Sottoreticoli - Isomorfismi tra reticoli) - 1h:59'30"
• 20 Maggio 2021 (Algebre di Boole; presentazioni equivalenti - Isomorfismi tra algebre di Boole - Teorema di Rappresentazione di Stone [caso finito]) - 1h:54'32"
• 24 Maggio 2021 (Dimostrazione del Teorema di Rappresentazione di Stone [caso finito] - Sottoalgebre di Boole - Teorema di Rappresentazione di Stone [caso generale] - Funzioni booleane, polinomi booleani; equivalenza tra polinomi booleani) - 2h:08'33"
• 27 Maggio 2021 (Prodotti (booleani), somme di prodotti - Forma Normale Disgiuntiva di un polinomio booleano: esistenza e unicità) - 1h:59'17"
• 31 Maggio 2021 (Ogni funzione booleana è polinomiale - Forme Normali di un polinomio booleano: esistenza e non unicità - implicazione tra polinomi; implicanti primi) - 1h:47'31"
• 3 Giugno 2021 (Metodo del Consenso per il calcolo della s.t.i.p.(f) - metodo di calcolo delle forme minimali di un polinomio booleano - esempi di calcolo della s.t.i.p. e di forme minimali di un polinomio booleano) - 1h:52'19"
• 7 Giugno 2021 (esercizi varî sul calcolo della F.N.D., della s.t.i.p. e delle forme minimali di un polinomio booleano) - 3h:05'22"
• 11 Giugno 2021 (esercizi varî su: reticoli e algebre di Boole - scrittura posizionale - sistemi di congruenze - aritmetica modulare) - 2h:49'37"


• versioni scritte delle lezioni del corso (dalla piattaforma didattica d'ateneo):
  • 1 Marzo 2021 (insiemi, sottoinsiemi, insieme delle parti, operazioni tra insiemi) - 9,70 MB
  • 4 Marzo 2021 (corrispondenze tra insiemi e costruzioni fondamentali su di esse) - 4,20 MB
  • 8 Marzo 2021 (funzioni; iniettività, suriettività, biiettività) - 4,85 MB
  • 11 Marzo 2021 (funzioni invertibili; funzioni caratteristiche in un insieme; sottoinsiemi vs. funzioni caratteristiche) - 4,56 MB
  • 15 Marzo 2021 (relazioni; ordini, equivalenze; partizioni) - 4,30 MB
  • 18 Marzo 2021 (corrispondenza tra equivalenze e quozienti di partizioni) - 4,95 MB
  • 22 Marzo 2021 (insiemi con operazioni) - 6,66 MB
  • 25 Marzo 2021 (Sistema dei Numeri Naturali e sue proprietà) - 4,02 MB
  • 29 Marzo 2021 (Principio di Induzione - Divisione con resto tra numeri naturali - Scrittura posizionale in base arbitraria) - 4,85 MB
  • 1 Aprile 2021 (Scrittura posizionale in base arbitraria - Cardinalità) - 8,56 MB
  • 8 Aprile 2021 (Cardinalità: relazione d'ordine tra numeri cardinali, proprietà dei cardinali infiniti) - 4,96 MB
  • 12 Aprile 2021 (Cardinalità: Primo e Secondo Teorema di Cantor (e loro conseguenze), cardinali infiniti superiori) - 8,95 MB
  • 15 Aprile 2021 (Numeri interi - divisibilità e elementi speciali - Teorema Fondamentale dell'Aritmetica [1^a parte: esistenza] - Teorema di Euclide - MCD e mcm di due interi) - 7,05 MB
  • 19 Aprile 2021 (Divisione euclidea tra interi - Esistenza e algoritmo di calcolo di MCD(a,b) e di una sua identità di Bézout - Teorema Fondamentale dell'Aritmetica [completo] - Forma "canonica" della fattorizzazione di un intero) - 6,78 MB
  • 22 Aprile 2021 (MCD e mcm in termini di fattorizzazioni - risoluzione di un'equazione diofantea - congruenze modulo n tra interi: proprietà fondamentali, descrizione delle classi e dell'insieme quoziente) - 6,46 MB
  • 26 Aprile 2021 (Operazioni tra numeri modulari: l'anello degli interi modulari - equazioni congruenziali, equazioni modulari: discussione e risoluzione) - 5,50 MB
  • 29 Aprile 2021 (Interi modulari invertibili - Potenze di interi modulari - Criteri di divisibilità) - 7,64 MB
  • 3 Maggio 2021 (Sistemi di equazioni congruenziali - Teorema Cinese del Resto) - 6,85 MB
  • 6 Maggio 2021 (Insiemi ordinati - diagrammi di Hasse - elementi speciali) - 5,02 MB
  • 10 Maggio 2021 (Ordine prodotto, ordine lessicografico - Reticoli - esempi e controesempi) - 5,09 MB
  • 13 Maggio 2021 (Reticoli limitati - Complementi - Reticoli distributivi - ∨-fattorizzazione in un reticolo) - 5,17 MB
  • 17 Maggio 2021 (∨-fattorizzazione in un reticolo [esistenza e unicità] - Sottoreticoli - Isomorfismi tra reticoli) - 9,60 MB
  • 20 Maggio 2021 (Algebre di Boole; presentazioni equivalenti - Isomorfismi tra algebre di Boole - Teorema di Rappresentazione di Stone [caso finito]) - 8,02 MB
  • 24 Maggio 2021 (Dimostrazione del Teorema di Rappresentazione di Stone [caso finito] - Sottoalgebre di Boole - Teorema di Rappresentazione di Stone [caso generale] - Funzioni booleane, polinomi booleani; equivalenza tra polinomi booleani) - 10,4 MB
  • 27 Maggio 2021 (Prodotti (booleani), somme di prodotti - Forma Normale Disgiuntiva di un polinomio booleano: esistenza e unicità) - 9,41 MB
  • 31 Maggio 2021 (Ogni funzione booleana è polinomiale - Forme Minimali di un polinomio booleano: esistenza e non unicità - implicazione tra polinomi; implicanti primi) - 7,33 MB
  • 3 Giugno 2021 (Metodo del Consenso per il calcolo della s.t.i.p.(f) - metodo di calcolo delle forme minimali di un polinomio booleano - esempi di calcolo della s.t.i.p. e di forme minimali di un polinomio booleano) - 7,99 MB
  • 7 Giugno 2021 (esercizi varî sul calcolo della F.N.D., della s.t.i.p. e delle forme minimali di un polinomio booleano) - 3,87 MB
  • 11 Giugno 2021 - parte 1 (esercizi varî su: reticoli e algebre di Boole - scrittura posizionale - sistemi di congruenze - aritmetica modulare) - 3,08 MB
  • 11 Giugno 2021 - parte 2 (esercizi varî su: reticoli e algebre di Boole - scrittura posizionale - sistemi di congruenze - aritmetica modulare) - 8,35 MB


• videolezioni preregistrate (del prof. F. Gavarini)   -   in ordine progressivo, secondo lo svolgimento logico del corso:
  
• Insiemi   (insiemi, sottoinsiemi, insieme delle parti, operazioni tra insiemi)
• Corrispondenze   (corrispondenze tra insiemi e operazioni tra di esse)
• Funzioni 1   (funzioni; iniettività, suriettività, biiettività)
• Funzioni 2   (composizione di funzioni, funzioni invertibili)
• Funzioni caratteristiche   (funzioni caratteristiche in un insieme)
• Relazioni   (relazioni in un insieme: generalità, esempi)
• Equivalenze 1   (equivalenze e partizioni)
• Equivalenze 2   (equivalenze e funzioni)
• Operazioni 1   (operazioni in un insieme; insiemi con una operazione)
• Operazioni 2   (insiemi con più operazioni)
• Numeri naturali   (sistema dei numeri naturali: assiomi di Peano, ordine, operazioni)
• Induzione   (metodo di dimostrazione per induzione [semplice / forte / minimo])
• Divisione   (divisione con resto tra numeri naturali)
• Numerazione   (numerazione in base arbitraria / scrittura posizionale)
• Cardinalità 1   (insiemi equipotenti, cardinalità; Primo Teorema di Cantor)
• Cardinalità 2   (Secondo Teorema di Cantor)   -   N.B.: è lo sviluppo consecutivo (senza transizione) di Cardinalità 1
• Insiemi ordinati   (generalità, esempi, elementi speciali)
• Reticoli 1   (generalità, esempi; complementi in un reticolo; distributività)
• Reticoli 2   (v-fattorizzazione: v-irriducibili, atomi, esistenza/unicità di v-fattorizzazioni)
• Reticoli 3   (sottoreticoli; isomorfismi di reticoli, reticoli isomorfi)
• 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])

  COMPITI d'ESAME:     21 Febbraio 2022 (testo , voti)   -   7 Febbraio 2022 (testo , voti)   -   7 Settembre 2021 (testo , voti)   -   30 Agosto 2021 (testo , voti)   -   8 Luglio 2021 (testo , voti)   -   16 Giugno 2021 (testo , svolgimento , voti)


  ESERCIZI per il TUTORATO (C. Fabroni):   Polinomi booleani (8 Giugno 2021)   -   Algebre di Boole (1 Giugno 2021)   -   Reticoli, Algebre di Boole (25 Maggio 2021)   -   Reticoli (18 Maggio 2021)   -   Aritmetica modulare, Sistemi di equazioni congruenziali (11 Maggio 2021)   -   Equazioni congruenziali e modulari, Aritmetica modulare (4 Maggio 2021)   -   MCD, mcm, Equazioni diofantee (27 Aprile 2021)   -   Cardinalità, Numeri interi (20 Aprile 2021)   -   Induzione, Scrittura posizionale, Cardinalità (13 Aprile 2021)   -   Relazioni, Induzione, Scrittura posizionale (6 Aprile 2021)   -   Insiemi e corrispondenze (30 Marzo 2021)


  DISPENSE (a cura di L. Geatti e G. Pareschi):     Alfabeto greco   -   Insiemi   -   Funzioni e cardinalità   -   Induzione   -   Relazioni - 1   -   Relazioni - 2   -   Aritmetica sugli interi, congruenze, Teorema Cinese del Resto   -   Aritmetica sugli interi, etc. (complementi)   -   Gruppi, anelli, campi   -   Reticoli   -   Algebre di Boole   -   Funzioni booleane   -   Forme minimali di una funzione polinomiale


  COMPITI d'ESAME di a.a. passati:     22 Settembre 2017 (testo , svolgimento)   -   5 Settembre 2017 (testo , testo con soluzioni)   -   18 Luglio 2017 (testo , svolgimento)   -   5 Luglio 2017 (testo , svolgimento)   -   21 Febbraio 2017   -   2 Febbraio 2017 (testo , svolgimento)   -   18 Settembre 2015   -   4 Settembre 2015   -   15 Luglio 2015   -   3 Luglio 2015   -   23 Febbraio 2015 (con soluzioni)   -   9 Febbraio 2015 (con soluzioni)   -   18 Settembre 2014   -   2 Settembre 2014   -   16 Luglio 2014   -   4 Luglio 2014   -   18 Febbraio 2014   -   3 Febbraio 2014   -   13 Settembre 2013   -   5 Settembre 2013   -   19 Luglio 2013   -   5 Luglio 2013   -   14 Febbraio 2013   -   4 Febbraio 2013


  ESERCIZI (Gavarini):     Insiemi   -   Corrispondenze   -   Funzioni   -   Relazioni 1   -   Relazioni 2   -   Insiemi, funzioni, relazioni   -   Gruppoidi, morfismi   -   Induzione   -   Scrittura posizionale   -   Induzione, scrittura posizionale   -   Cardinalità   -   Scrittura posizionale, M.C.D., equazioni diofantee   -   M.C.D., equazioni diofantee   -   Equazioni congruenziali e equazioni modulari   -   Equazioni diofantee, congruenziali, modulari; aritmetica modulare   -   Aritmetica modulare   -   Insiemi ordinati, Reticoli   -   Reticoli, Algebre di Boole   -   Algebre di Boole   -   Polinomi booleani


  ESERCIZI (Geatti & Pareschi):     Insiemi, operazioni sugli insiemi, funzioni   -   Cardinalità, principio di induzione   -   Relazioni, relazioni di equivalenza   -   Relazioni, relazioni d'ordine   -   M.C.D., algoritmo di Euclide, equazioni lineari a coefficienti interi   -   Congruenze e sistemi di congruenze   -   Somma e prodotto in Z_n , aritmetica modulare   -   Gruppi e applicazioni   -   Mix su insiemi, relazioni, aritmetica modulare   -   Reticoli   -   Algebre di Boole   -   Espressioni booleane   -   Logica Matematica


  ESERCIZI SVOLTI (Geatti & Pareschi):     Insiemi, cardinalità, induzione, funzioni ricorsive (testo, soluzioni)   -   Relazioni (testo, soluzioni)   -   Aritmetica sugli interi, congruenze (testo, soluzioni)   -   Gruppi, anelli e campi (testo, soluzioni)   -   Reticoli (testo, soluzioni)   -   Algebre di Boole (testo, soluzioni)   -   Logica Matematica (testo, soluzioni)


  ALTRO MATERIALE disponibile in rete (per gentile concessione degli autori):     materiale didattico per il corso di "Matematica Discreta" (Gavarini)   -   dispense (Campanella)   -   esercizi (Campanella)   -   dispense (Caranti)   -   Numeri naturali (D'Andrea)   -   Cardinalità (D'Andrea)   -   Numeri interi (D'Andrea)   -   Congruenze, aritmetica modulare (D'Andrea)   -   lezioni, esercitazioni, prove di valutazione, ecc. (Fontana)   -   esercitazioni, prove d'esame, ecc. (Tartarone)

---

ALTRI SITI UTILI

• Algebra e Logica, anni passati:   2019-2020 (Pareschi)   -   2018-2019 (Pareschi)   -   2017-2018 (Schoof)   -   2016-2017 (Gavarini)   -   2015-2016 (Geatti)   -   2014-2015 (Gavarini)   -   2013-2014 (Gavarini)   -   2012-2013 (Gavarini)   -   2011-2012 (Geatti)
• Elementi di Algebra e Logica, anni passati:   2009-2010 (Geatti)   ,   2008-2009 (Geatti)   ,   2004-2005 (Schoof)   ,   2003-2004 (Geatti & Pareschi)   ,   2002-2003 (Schoof)   ,   2001-2002 (Schoof)
• Matematica Discreta (CdLT Informatica), anni passati:   materiale didattico per il corso (Gavarini)