Corso di Laurea in Ingegneria Informatica
a.a 2016-2017 - primo semestre
Diario delle lezioni del corso - da 6 CFU - di
ALGEBRA E LOGICA
(elencate in ordine cronologico inverso)
Docente: Fabio Gavarini
( pagina web del corso )
PROGRAMMA:
versione preliminare
(al termine del corso sarà disponibile una versione definitiva)
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 (soltanto esercitazioni) - 26 Gennaio 2017:
Esercizi varî su:
- 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;
- analisi dell'invertibilità, e calcolo dell'inverso (quando esista), per una classe in Zn;
- equazioni diofantee, equazioni congruenziali, equazioni modulari; calcolo del M.C.D. e di un'identità di Bézout per esso;
- relazioni di equivalenza, classi di equivalenza.
- atomi, v-irriducibili, fattorizzazione in v-irriducibili in un reticolo; algebre di Boole.
VENTOTTESIMA LEZIONE - 25 Gennaio 2017:
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 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.
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
VENTISETTESIMA LEZIONE - 19 Gennaio 2017:
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.
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.
Bibliografia: [G-P] file Forme minimali di una funzione polinomiale - [L-L] Chapter 15, section 9
VENTISEIESIMA LEZIONE - 18 Gennaio 2017:
Lemma: Ogni somma di prodotti è equivalente ad una somma di prodotti fondamentali e 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 "tavole di verità", o tramite manipolazioni successive).
Fn(2) = Pn(2) , cioè ogni funzione booleana su 2 è polinomiale.
Bibliografia: [G-P] file Funzioni booleane - [L-L] Chapter 15, section 8
VENTICINQUESIMA LEZIONE - 12 Gennaio 2017:
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).
L'insieme Fn(B) delle funzioni booleane in n variabili su un'algebra di Boole B; struttura di algebra di Boole.
L'insieme Pn dei polinomi booleani in n variabili; funzioni booleane indotte da un polinomio booleano. L'insieme Pn(B) delle funzioni polinomiali su B; Pn(B) è sottoalgebra di Boole di Fn(B).
Equivalenza tra polinomi booleani (quando inducono la stessa funzione booleana su 2:={0,1}).
Teorema: Due polinomi booleani inducono la stessa funzione booleana su qualsiasi algebra di Boole se e soltanto se sono equivalenti.
Prodotti, prodotti fondamentali, prodotti completi in Pn. Somme di prodotti; somme di prodotti fondamentali, complete, ridondanti / non ridondanti.
Bibliografia: [G-P] file Algebre di Boole; file Funzioni booleane - [L-L] Chapter 15, sections 7 and 8
Videolezione: Algebre di Boole 2 (isomorfismi tra algebre di Boole, sottoalgebre di Boole; Teorema di Rappresentazione di Stone [caso finito, caso generale])
VENTIQUATTRESIMA LEZIONE - 11 Gennaio 2017:
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; prodotti di algebre di Boole; i prodotti {0,1}n.
Insiemi totalmente ordinati e reticoli di divisori Dn: criteri perché siano algebre di Boole.
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 {0,1}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.
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
Videolezione: Algebre di Boole 2 (isomorfismi tra algebre di Boole, sottoalgebre di Boole; Teorema di Rappresentazione di Stone [caso finito, caso generale])
VENTITREESIMA LEZIONE - 22 Dicembre 2016:
Proposizione: In un reticolo distributivo, una v-fattorizzazione non ridondante in fattori v-irriducibili - se esiste - è unica, a meno dell'ordine dei fattori.
Teorema di v-Fattorizzazione Unica (in v-irriducibili) per reticoli finiti distributivi.
Proposizione: In un reticolo finito unicamente complementato, ogni elemento v-irriducibile è un atomo.
Teorema di v-Fattorizzazione Unica (in atomi) per reticoli finiti distributivi complementati.
Isomorfismi tra reticoli, proprietà fondamentali. Reticoli isomorfi; l'essere isomorfi è una relazione di equivalenza tra reticoli.
Criterio di isomorfismo tra un reticolo Dr e un reticolo Ds .
Sottoreticoli di un reticolo.
Teorema (caratterizzazione dei reticoli distributivi): Un reticolo è distributivo se e soltanto se non contiene sottoreticoli isomorfi a N5 oppure a M5 (cenni).
Algebre di Boole: definizione come reticoli, definizione come insiemi con due operazioni; equivalenza delle due definizioni (senza dimostrazione).
Bibliografia: [G-P] file Reticoli, paragrafi da 5 a 7; file Algebre di Boole - [L-L] Chapter 14, sections 8 to 11; Chapter 15, sections 1, 2, 4 and 5
Videolezioni: Reticoli 3 (sottoreticoli; isomorfismi di reticoli, reticoli isomorfi) - Algebre di Boole 1 (definizioni; esempi, controesempi; Teorema di Equivalenza [con anelli booleani unitari])
VENTIDUESIMA LEZIONE - 21 Dicembre 2016:
Il reticolo L1 x ... x Lk prodotto diretto dei reticoli L1, ... , Lk ; il reticolo LX delle funzioni da un insieme X ad un reticolo L.
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 N5 e M5 sono complementati.
Reticoli distributivi. Esempi e controesempi: P(X) e Dn sono distributivi, N5 e M5 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 inf(x,y) e di sup(x,y).
v-Fattorizzazione in un reticolo; elementi v-riducibili o v-irriducibili. Atomi (in un reticolo limitato inferiormente). Esempi e controesempi di v-riducibili, di v-irriducibili e di atomi.
Proposizione: In un reticolo finito, ogni v-irriducibile copre al più un atomo, e ogni atomo è v-irriducibile.
Teorema: In un reticolo finito, ogni elemento ha una v-fattorizzazione in fattori v-irriducibili non ridondante (cioè i fattori sono a due a due non comparabili).
Bibliografia: [G-P] file Reticoli, paragrafi 3 e 4 - [L-L] Chapter 14, sections from 9 to 11
Videolezioni: Reticoli 1 (generalità, esempi; complementi in un reticolo; distributività)
- Reticoli 2 (v-fattorizzazione: v-irriducibili, atomi, esistenza/unicità di v-fattorizzazioni)
VENTUNESIMA LEZIONE - 15 Dicembre 2016:
L'ordine prodotto e l'ordine lessicografico in un prodotto cartesiano di insiemi ordinati.
Intervalli (chiusi, aperti, semi-chiusi/aperti, limitati o illimitati) in un insieme ordinato.
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. 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
Videolezioni: Insiemi ordinati (generalità, esempi, elementi speciali) - Reticoli 1 (generalità, esempi; complementi in un reticolo; distributività)
VENTESIMA LEZIONE - 14 Dicembre 2016:
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. Insiemi ordinati limitati.
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.
L'ordine indotto in un sottoinsieme E' di un insieme ordinato E. L'ordine indotto nell'insieme ES da un insieme qualsiasi S a un insieme ordinato E.
Bibliografia: [Ca] Capitolo 1, paragrafo 3(B) - [G-P] file Relazioni - 2 - [L-L] Chapter 14, sections 1, 2, 3, 5 and 7
Videolezione: Insiemi ordinati (generalità, esempi, elementi speciali)
DICIANNOVESIMA LEZIONE - 7 Dicembre 2016:
Esercizi varî su:
- M.C.D. tra interi, identità di Bézout;
- equazioni diofantee, equazioni congruenziali, equazioni modulari;
- sistemi di equazioni congruenziali;
- scrittura posizionale in base arbitraria, svolgimento di operazioni tramite scrittura posizionale in base (arbitraria) fissata;
- criteri di divisibilità in termini di scrittura posizionale in base (arbitraria) fissata;
- calcolo di inversi in Zn , calcolo di potenze in Zn .
DICIOTTESIMA LEZIONE - 1 Dicembre 2016:
Metodo di calcolo esplicito di potenze in Zn. Applicazione: il metodo crittografico R.S.A.
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.
Bibliografia: [Ca] Capitolo II, paragrafo 4, 5 e 6 - [G-P] file Aritmetica sugli interi, congruenze, Teorema Cinese del Resto - [L-L] Chapter 11, section 9 - [PC] Capitolo 2, paragrafi 7, 8 e 9
DICIASSETTESIMA LEZIONE - 30 Novembre 2016:
Connessione tra equazioni congruenziali o equazioni modulari e equazioni diofantee (in Z).
Equazioni congruenziali in Z: criterio di esistenza di soluzioni, algoritmo per il calcolo di una soluzione, insieme completo di soluzioni.
Equazioni modulari in Zn: criterio di esistenza di soluzioni, algoritmo per il calcolo di una soluzione, insieme completo di soluzioni.
Elementi invertibili in Zn: criterio di invertibilità, calcolo dell'inverso mediante risoluzione di una equazione congruenziale.
Formula esplicita della soluzione di un'equazione modulare in caso di esistenza e unicità.
La funzione di Eulero: definizione, formula esplicita.
Ripetitività delle potenze in Zn: generalità, il Piccolo Teorema di Fermat (senza dimostrazione), il Teorema di Eulero (senza dimostrazione).
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, 7 e 8
SEDICESIMA LEZIONE - 24 Novembre 2016:
Congruenze in Z (richiami). Ogni congruenza è una equivalenza; descrizione delle classi di congruenza e dell'insieme quoziente Zn.
Compatibilità di somma e prodotto con ogni congruenza modulo n. Aritmetica modulare: somma e prodotto in Zn.
Teorema: Zn è un anello commutativo unitario (esercizio - cenni di dimostrazione).
Esercizio: Zn è privo di divisori di zero <=> n è irriducibile (=primo) <=> Zn è un campo.
Criteri di divisibilità in Z: strategia generale - calcolo di una classe in Zn - esempi specifici.
Equazioni congruenziali in Z: definizione, connessione con le equazioni modulari equazioni (cioè equazioni in Zn).
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
QUINDICESIMA LEZIONE - 23 Novembre 2016:
Teorema Fondamentale dell'Aritmetica: esistenza e unicità di una fattorizzazione in irriducibili per interi (non nulli) non invertibili (cenni di dimostrazione dell'unicità).
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) .
Fattorizzazione in un monoide: esempi di monoidi in cui vale l'esistenza ma non l'unicità.
Equazioni diofantee: definizione, criterio per l'esistenza di soluzioni, procedura per il calcolo esplicito di una soluzione.
Bibliografia: [AaVv] file Numeri interi (D'Andrea), paragrafo 4 - [Ca] Capitolo II, paragrafi 3, 4 - [G-P] file Aritmetica sugli interi, congruenze, Teorema Cinese del Resto - [L-L] Chapter 11, section 7 - [PC] Capitolo 2, paragrafi 2 e 3
QUATTORDICESIMA LEZIONE - 17 Novembre 2016:
Teorema di Euclide: Esistono infiniti interi irriducibili a due a due non associati (cenni di dimostrazione).
Massimo comun divisore (=M.C.D.) e minimo comun multiplo (=m.c.m.). Elementi primi tra loro (o "coprimi").
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: calcolo con l'algoritmo euclideo delle divisioni successive. Esempi di calcolo esplicito.
Proposizione: In Z, ogni irriducibile è primo.
Bibliografia: [AaVv] file Numeri interi (D'Andrea), paragrafo 4 - [Ca] Capitolo II, paragrafi 1, 2 e 3 - [G-P] file Aritmetica sugli interi, congruenze, Teorema Cinese del Resto - [L-L] Chapter 11, sections 4, 5, 6, 7 - [PC] Capitolo 2, paragrafi 2 e 3
TREDICESIMA LEZIONE - 16 Novembre 2016:
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.
Divisibilità, multipli e divisori in Z. Elementi unità (=invertibili) in Z; elementi associati. Elementi riducibili, irriducibili, primi.
Proposizione: Ogni primo è irriducibile.
Il problema generale della fattorizzazione in un monoide. Fattorizzazioni banali, fattorizzazioni equivalenti; esempi e controesempi varî (di esistenza e/o unicità).
Teorema Fondamentale dell'Aritmetica: Esistenza e unicità di una fattorizzazione in irriducibili per interi (non nulli) non invertibili (dimostrazione dell'esistenza).
Bibliografia: [AaVv] file Numeri interi (D'Andrea), paragrafo 1 - [Ca] Capitolo II, paragrafi 2 e 3 - [G-P] file Aritmetica sugli interi, congruenze, Teorema Cinese del Resto - [L-L] Chapter 11, sections 1, 2, 3, 5, 6, 7 - [PC] Capitolo 2, paragrafi da 1 a 3
DODICESIMA LEZIONE - 10 Novembre 2016:
1o 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, Q e NxN sono numerabili.
2o Teorema di Cantor: La cardinalità dell'insieme delle parti di un insieme è strettamente maggiore della cardinalità dell'insieme stesso.
I numeri cardinali infiniti superiori "Alephn" (per ogni n in N). La cardinalità del continuo: |R| = |P(N)| (senza dimostrazione). L'ipotesi del continuo generalizzata (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
Videolezioni: Cardinalità 1 (insiemi equipotenti, cardinalità; Primo Teorema di Cantor) - Cardinalità 2 (Secondo Teorema di Cantor)
UNDICESIMA LEZIONE - 9 Novembre 2016:
Esercizio: i numeri descrivibili con al più N cifre nella scrittura posizionale in base b sono tutti quelli da 0 fino a bN - 1 .
Equipotenza tra insiemi; l'equipotenza è riflessiva, simmetrica, transitiva. Cardinalità di un insieme, numeri cardinali. Insiemi finiti, infiniti numerabili o infiniti non numerabili.
Relazione d'ordine tra numeri cardinali; il Teorema di Schroeder-Bernstein (senza dimostrazione della transitività).
Proposizione: Ogni insieme infinito contiene un sottoinsieme numerabile; ogni sottoinsieme di un insieme numerabile o è finito oppure è numerabile.
Caratterizzazione degli insiemi infiniti: per un insieme X le seguenti proprietà sono equivalenti:
- X è infinito,
- esiste una funzione iniettiva dall'insieme dei numeri naturali ad X,
- esiste un sottoinsieme proprio 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
Videolezione: Cardinalità 1 (insiemi equipotenti, cardinalità; Primo Teorema di Cantor)
DECIMA LEZIONE - 3 Novembre 2016:
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.)
Numerazione in base arbitraria. Scrittura posizionale (di un numero naturale) in base b (>1) arbitraria: esistenza e unicità di tale scrittura (dimostrazione per induzione forte).
La procedura operativa per il calcolo della scrittura posizionale di un numero naturale in una base data: strategia generale, esempi.
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
Videolezioni: Induzione (metodo di dimostrazione per induzione [semplice / forte / minimo]) - Divisione (divisione con resto tra numeri naturali) - Numerazione (numerazione in base arbitraria / scrittura posizionale)
NONA LEZIONE - 2 Novembre 2016:
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". Relazione d'ordine tra numeri naturali: definizione tramite il Pr.I.D.; tale relazione è un buon ordinamento.
Operazioni di somma e prodotto tra numeri naturali (definizione ricorsiva, tramite il Pr.I.D.).
Teorema: Un S.N.N. con somma e prodotto è un semianello commutativo unitario, e le operazioni sono compatibili con la relazione d'ordine.
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. (cenni).
Bibliografia: [AaVv] file Numeri naturali (D'Andrea) - [Ca] Capitolo I, paragrafo 5 - [PC] Capitolo 1, paragrafo 4
Videolezione: Naturali (sistema dei numeri naturali: assiomi di Peano, ordine, operazioni)
OTTAVA LEZIONE - 27 Ottobre 2016:
Operazioni (binarie) in un insieme; proprietà speciali possibili. Unicità di elemento neutro (se esiste) e di elemento inverso (se esiste, nel caso associativo) di un elemento dato.
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
Videolezioni: Operazioni 1 (operazioni in un insieme; insiemi con una operazione) - Operazioni 2 (insiemi con più operazioni)
SETTIMA LEZIONE - 26 Ottobre 2016:
Classi di equivalenza; rappresentante di una classe di equivalenza. L'insieme quoziente di un insieme X modulo un'equivalenza; la proiezione canonica da X all'insieme quoziente.
L'equivalenza associata alla proiezione canonica è l'equivalenza iniziale.
Teorema: (a) La famiglia delle classi di equivalenza (per una qualsiasi equivalenza data) in X è una partizione dell'insieme X.
(b) La relazione in X associata ad una partizione di X è un'equivalenza.
(c) Le due costruzioni precedenti sono una l'inversa dell'altra.
Nota: ogni equivalenza in un insieme X è l'equivalenza indotta (canonicamente) da una qualche funzione il cui dominio è X stesso.
Esempi di equivalenze, classi di equivalenza, insiemi quozienti.
Bibliografia: [Ca] Capitolo I, paragrafo 3 - [G-P] file Relazioni 1 - [L-L] Chapter 2 - [PC] Capitolo 1, paragrafo 2
Videolezioni: Equivalenze 1 (equivalenze e partizioni) - Equivalenze 2 (equivalenze e funzioni)
SESTA LEZIONE - 20 Ottobre 2016:
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.
La congruenza modulo n tra numeri interi è una equivalenza. La relazione in X associata ad una funzione f da X a Y è una equivalenza.
Partizioni in un insieme: esempi e controesempi.
Bibliografia: [Ca] Capitolo I, paragrafo 3 - [G-P] file Relazioni 1 - [L-L] Chapter 2 - [PC] Capitolo 1, paragrafo 2
Videolezioni: Relazioni (relazioni in un insieme: generalità, esempi)
QUINTA LEZIONE - 19 Ottobre 2016:
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.
La corrispondenza naturale tra l'insieme delle parti di un insieme X e l'insieme delle funzioni caratteristiche in X è una funzione, e tale funzione è invertibile; 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
Videolezioni: Funzioni 2 (composizione di funzioni, funzioni invertibili) - Funzioni caratteristiche (funzioni caratteristiche in un insieme)
QUARTA LEZIONE - 13 Ottobre 2016:
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.
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).
Famiglie (vs. "insiemi") - di oggetti in un insieme E indicizzati da elementi di un insieme I - come funzioni da I a E. Partizioni di un insieme.
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
Videolezione: Funzioni 1 (funzioni; iniettività, suriettività, biiettività)
TERZA LEZIONE - 12 Ottobre 2016:
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: corrispondenza vuota, corrispondenza totale; corrispondenza identica (o "identità") su un insieme.
Corrispondenza complementare; corrispondenza inversa. Operazioni insiemistiche tra corrispondenze.
Composizione - o prodotto (operatorio) - di due corrispondenze. Proprietà notevoli di inversione e composizione: associatività, esistenza di "elementi neutri", potenze di relazioni.
Bibliografia: [Ca] Capitolo I, paragrafo 2 - [L-L] Chapter 2 - [PC] Capitolo 1, paragrafo 2
Videolezione: Corrispondenze (corrispondenze
tra insiemi e operazioni tra di esse)
SECONDA LEZIONE - 6 Ottobre 2016:
Insiemi: definizione (naturale, o "ingenua"), descrizioni possibili; appartenenza e non appartenenza di elementi.
Sottoinsiemi, sovrainsiemi. Inclusione tra insiemi; inclusione stretta. 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) associatività e commutatività di intersezione, unione e differenza simmetrica;
(2) 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
Videolezione: Insiemi (insiemi, sottoinsiemi, insieme delle parti, operazioni tra insiemi)
PRIMA LEZIONE - 5 Ottobre 2016 (soltanto un'ora):
Presentazione generale del corso.