Corso di Laurea in Ingegneria Informatica
a.a 2012-2013 - 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 sintetica     ☆     versione analitica

                                       

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, Appunti varî   (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

TRENTUNESIMA LEZIONE (soltanto esercitazioni) - 31 Gennaio 2013:     FINE del CORSO
  Esercizi varî su:
      -   relazioni d'ordine, ordinamento lessicografico;
      -   successioni ricorsive (di secondo grado, lineari omogenee a coefficienti a coefficienti costanti);
      -   descrizione di reticoli, isomorfismi tra reticoli;
      -   calcolo di potenze in anelli Z_n di classi resto modulo n.
  FINE del CORSO

TRENTESIMA LEZIONE (soltanto esercitazioni) - 30 Gennaio 2013:
  Esercizi varî su:
      -   equazioni congruenziali;
      -   sistemi di equazioni congruenziali (con il Teorema Cinese dei Resti, o per sostituzioni successive);
      -   radici quadrate in anelli Z_n di classi resto modulo n;
      -   risoluzione di equazioni di secondo grado in anelli Z_n di classi resto modulo n.

VENTINOVESIMA LEZIONE (soltanto esercitazioni) - 24 Gennaio 2013:
  Esercizi varî su:
      -   successioni ricorsive di secondo grado (lineari omogenee a coefficienti a coefficienti costanti);
      -   procedure di calcolo usando la scrittura posizionale, in varie basi;
      -   sistemi di equazioni congruenziali;
      -   atomi, v-irriducibili, fattorizzazione in v-irriducibili in un reticolo;
      -   polinomi booleani (forma normale disgiuntiva, forme minimali).

VENTOTTESIMA LEZIONE (soltanto esercitazioni) - 23 Gennaio 2013:
  Esercizi varî su:
      -   equazioni diofantee, M.C.D., identità di Bézout;
      -   scrittura posizionale in varie basi;
      -   criteri di divisibilità per numeri interi;
      -   polinomi booleani (forma normale disgiuntiva, forme minimali);
      -   atomi, v-irriducibili, fattorizzazione in v-irriducibili in un reticolo.

VENTISETTESIMA LEZIONE (soltanto esercitazioni) - 17 Gennaio 2013:
  Esercizi varî su:
      -   successioni ricorsive di secondo grado (lineari omogenee a coefficienti a coefficienti costanti);
      -   polinomi booleani (forma normale disgiuntiva, forme minimali).

VENTISEIESIMA LEZIONE - 16 Gennaio 2013:
  Lemma: Se a è una successione complessa che è soluzione di un'equazione ricorsiva lineare omogenea a coefficienti costanti reali, allora la successione dei suoi coniugati è a sua volta soluzione della stessa equazione ricorsiva.
  Calcolo esplicito di una base per lo spazio delle successioni ricorsive (omogenee a coefficienti costanti) di grado 2 reali nel caso in cui il polinomio caratteristico abbia (3) due radici complesse non reali (e dunque coniugate).
  Esempi espliciti.
  FINE del PROGRAMMA (seguono sole esercitazioni)
    Bibliografia:   [G-P] file Equazioni alle differenze finite (cenni)
    Videolezioni:   Funzioni ricorsive 3.1   (risoluzione di equazioni ricorsive lineari omogenee a coefficienti costanti di grado 2: caso di due radici distinte o di una sola radice)   -   Funzioni ricorsive 3.2   (risoluzione di equazioni ricorsive lineari omogenee a coefficienti costanti di grado 2: caso reale con due radici (distinte) complesse coniugate)   ☆   N.B.: la seconda videolezione è lo sviluppo consecutivo (senza transizione) della prima.

VENTICINQUESIMA LEZIONE - 10 Gennaio 2013:
  Polinomio caratteristico e equazione caratteristica associati ad una successione ricorsiva omogenea a coefficienti costanti.
  Lemma: Se r è una radice del polinomio caratteristico, allora la successione {rⁿ}_n delle potenze di r è una soluzione dell'equazione ricorsiva; se poi r è una radice doppia, allora anche la successione {n rⁿ}_n è soluzione dell'equazione ricorsiva.
  Calcolo esplicito di una base per lo spazio delle successioni ricorsive (omogenee a coefficienti costanti) di grado 1.
  Calcolo esplicito di una base per lo spazio delle successioni ricorsive (omogenee a coefficienti costanti) di grado 2 complesse.
  Calcolo esplicito di una base per lo spazio delle successioni ricorsive (omogenee a coefficienti costanti) di grado 2 reali nei casi in cui il polinomio caratteristico abbia (1) due radici reali distinte, oppure (2) una sola radice reale (doppia).
    Bibliografia:   [G-P] file Equazioni alle differenze finite (cenni) - [L-L] Chapter 3, section 6; Chapter 6, sections 7, 8 and 9
    Videolezioni:   Funzioni ricorsive 1   (funzioni ricorsive: generalità, casi particolari, esempi; Teorema di Ricorsione [di esistenza e unicità])   -   Funzioni ricorsive 2   (funzioni ricorsive lineari omogenee come spazio vettoriale; calcolo di una base, e di una successione specifica, per il caso a coefficienti costanti di grado 1)

VENTIQUATTRESIMA LEZIONE - 9 Gennaio 2013:
  Funzioni (o "successioni") ricorsive. Dati iniziali, equazione ricorsiva e grado (di ricorsività) di una funzione ricorsiva.
  Teorema di Ricorsione per l'esistenza e unicità di una funzione che abbia dati iniziali assegnati e soddisfi una data equazione ricorsiva.
  Casi particolari di funzioni ricorsive: lineari, lineari omogenee, lineari a coefficienti costanti - esempi e controesempi.
  Proposizione: L'insieme S delle successioni che sono soluzioni di un'equazione ricorsiva lineare omogenea di grado k è sottospazio vettoriale dello spazio di tutte le successioni, e ha dimensione k.
  Strategia di calcolo di una funzione ricorsiva lineare omogenea: (1) ricerca di una base dello spazio delle soluzioni dell'equazione ricorsiva associata, e (2) successiva imposizione delle condizioni iniziali.
    Bibliografia:   [G-P] file Equazioni alle differenze finite (cenni) - [L-L] Chapter 3, section 6; Chapter 6, sections 6 and 7
    Videolezioni:   Funzioni ricorsive 1   (funzioni ricorsive: generalità, casi particolari, esempi; Teorema di Ricorsione [di esistenza e unicità])   -   Funzioni ricorsive 2   (funzioni ricorsive lineari omogenee come spazio vettoriale; calcolo di una base, e di una successione specifica, per il caso a coefficienti costanti di grado 1)

VENTITREESIMA LEZIONE - 20 Dicembre 2012:
  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.
  Somme di prodotti irridondanti.
  Proposizione: Ogni forma minimale di un polinomio booleano f è somma irridondante di implicanti primi di f.
  Il consenso di due prodotti in P_n. Il Metodo del Consenso: algoritmo di calcolo della somma di tutti gli implicanti primi di un polinomio booleano in n variabili (senza dimostrazione).
    Bibliografia:   [G-P] file Forme minimali di una funzione polinomiale - [L-L] Chapter 15, section 9

VENTIDUESIMA LEZIONE - 19 Dicembre 2012:
  Esistenza e unicità della forma normale disgiuntiva (=F.N.D.) di un polinomio booleano. Metodi operativi per il calcolo della F.N.D. di un polinomio booleano: (1) tramite "tavole di verità", (2) tramite manipolazioni successive.
  Esempi di calcolo della F.N.D. (tramite i due metodi possibili).
  Misura della "grandezza" di una somma di prodotti; la relazione di "maggior semplicità" tra polinomi booleani equivalenti che siano somme di prodotti.
  Forme minimali di un polinomio booleano: definizione, esistenza e (in generale) non unicità.
    Bibliografia:   [G-P] file Funzioni booleane - [L-L] Chapter 15, sections 8 and 9

VENTUNESIMA LEZIONE - 13 Dicembre 2012:
  Esercizi vari sugli argomenti del programma svolti fino a questa data.

VENTESIMA LEZIONE - 12 Dicembre 2012:
  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).
  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 indotte da un polinomio booleano.
  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 inducono la stessa funzione booleana su qualsiasi algebra di Boole se e soltanto se sono equivalenti.
  Prodotti, prodotti fondamentali in (in P_n); somme di prodotti (ridondanti, non ridondanti, complete); passaggio da un oggetto (prodotto o somma non "buono" (fondamentale, o irridondante, o completo) ad uno "buono" equivalente.
  La forma normale disgiuntiva di un polinomio booleano.
    Bibliografia:   [G-P] file Algebre di Boole; file Funzioni booleane - [L-L] Chapter 15, sections 1 to 8
    Videolezione:   Algebre di Boole 2   (isomorfismi tra algebre di Boole, sottoalgebre di Boole; Teorema di Rappresentazione di Stone [caso finito, caso generale])

DICIANNOVESIMA LEZIONE - 6 Dicembre 2012:
  Sottoreticoli di un reticolo.   -   Teorema: Un reticolo è distributivo se e soltanto se non ha sottoreticoli isomorfi a N₅ o a M₅ (senza dimostrazione).
  Algebre di Boole: definizione come reticoli distributivi (limitati) complementati, definizione come insiemi con due operazioni particolari. Equivalenza delle due definizioni (senza dimostrazione).   -   Il Principio di Dualità per algebre di Boole.
  Controsempi: gli insiemi totalmente ordinati con più di due elementi, N₅ e M₅ non sono 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}ⁿ.
  Isomorfismi tra algebre di Boole, algebre di Boole isomorfe: gli isomorfismi tra algebre di Boole preservano il complemento.   -   Esempi: (1) la biiezione canonica da P(X) a {0,1}^X - per ogni insieme X - è un isomorfismo; (2) la biiezione canonica da B^{1,...,n} a Bⁿ - per ogni algebra di Boole B - è un isomorfismo.
  Teorema (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.   -   Esempi espliciti dell'isomorfismo fornito dal Teorema di Stone.
    Bibliografia:   [G-P] file Reticoli, paragrafi da 5 a 7; file Algebre di Boole - [L-L] Chapter 15, sections 1 to 6
    Videolezioni:   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])

DICIOTTESIMA LEZIONE - 5 Dicembre 2012:
  v-Fattorizzazione in un reticolo. Elementi v-riducibili o v-irriducibili; atomi. Esempi e controesempi.
  Proposizione: In un reticolo finito, ogni elemento ha una v-fattorizzazione non ridondante in fattori v-irriducibili.   -   Proposizione: In un reticolo distributivo, una v-fattorizzazione non ridondante in fattori v-irriducibili - se esiste - è unica.
  Teorema di v-Fattorizzazione Unica (in v-irriducibili) per reticoli finiti distributivi.
  Caratterizzazione degli elementi v-irriducibili in un reticolo finito.   -   Lemma: Ogni atomo è irriducibile.   -   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, reticoli isomorfi; proprietà degli isomorfismi.   -   Esercizio: D_r è isomorfo a D_s se e soltanto se r ed s hanno fattorizzazioni in primi distinti che coinvolgono gli stessi esponenti.
    Bibliografia:   [G-P] file Reticoli, paragrafi 4 e 6 - [L-L] Chapter 14, sections from 8 to 11
    Videolezioni:   Reticoli 2   (v-fattorizzazione: v-irriducibili, atomi, esistenza/unicità di v-fattorizzazioni)   -   Reticoli 3   (sottoreticoli; isomorfismi di reticoli, reticoli isomorfi)

DICIASSETTESIMA LEZIONE - 29 Novembre 2012:
  Reticoli: equivalenza delle due definizioni (cenni di dimostrazione).
  Principio di Dualità per reticoli.   -   Proposizione: Ogni reticolo finito è limitato.
  Esempi (e controesempi) di reticoli: gli insiemi con ordinamento totale, N e N₊ con la divisibilità, ogni intervallo in un reticolo, il reticolo dei divisori di n, l'insieme delle parti di un insieme, l'insieme L^X delle funzioni da un insieme X ad un reticolo L.
  Complementi in un reticolo; reticoli complementati. Reticoli distributivi. Esempi e controesempi.
  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).
    Bibliografia:   [G-P] file Relazioni - 2; file Reticoli, paragrafi da 1 a 3 - [L-L] Chapter 14, sections from 8 to 11
    Videolezione:   Reticoli 1   (generalità, esempi; complementi in un reticolo; distributività)

SEDICESIMA LEZIONE - 28 Novembre 2012:
  Sistemi di equazioni congruenziali: discussione, risoluzione - tramite il Teorema Cinese del Resto (senza dimostrazione) o tramite sostituzioni successive. Esempi espliciti di risoluzione di sistemi.
  Relazioni d'ordine, insiemi ordinati. Principio di Dualità per insiemi ordinati. Relazione di copertura e diagramma di Hasse per un insieme finito. Esempi.
  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.
  Reticoli: definizione come insiemi ordinati e definizione come insiemi con due operazioni binarie.
    Bibliografia:   [Ca] Capitolo II, paragrafo 1.3(B), paragrafo 5 - [G-P] file Aritmetica sugli interi, congruenze, Teorema Cinese del Resto; file Relazioni - 2; file Reticoli, paragrafi 1 e 2 - [L-L] Chapter 11, section 9; Chapter 14, sections 1, 2, 3, 5, 7 and 8 - [PC] Capitolo 2, paragrafi 7, 8 e 9
    Videolezioni:   Insiemi ordinati   (generalità, esempi, elementi speciali)   -   Reticoli 1   (generalità, esempi; complementi in un reticolo; distributività)

QUINDICESIMA LEZIONE - 22 Novembre 2012:
  Elementi invertibili in Z_n; criterio di invertibilità, calcolo dell'inverso mediante risoluzione di una equazione congruenziale.
  La funzione di Eulero: definizione, formula esplicita.
  Ripetitività delle potenze in Z_n: generalità, il Teorema di Eulero (senza dimostrazione).
  Esercizi espliciti su equazioni congruenziali, calcolo di inversi in Z_n, calcolo di potenze in Z_n.
    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

QUATTORDICESIMA LEZIONE - 21 Novembre 2012:
  Congruenze in Z (richiami). Ogni congruenza è una equivalenza; descrizione delle classi di congruenza e dell'insieme quoziente Z_n.
  Aritmetica modulare: compatibilità di somma e prodotto con ogni congruenza modulo n. Somma e prodotto in Z_n .
  Teorema: Z_n è un anello commutativo unitario (senza dimostrazione).   Esercizio:   Z_n è un dominio se e soltanto se n è irriducibile (=primo).
  Criteri di divisibilità in Z: strategia generale - calcolo di una classe in Z_n - esempi specifici.
  Equazioni congruenziali in Z: definizione, connessione con equazioni in Z_n, connessione con equazioni diofantee in Z; criterio di esistenza di soluzioni, algoritmo per il calcolo di una soluzione, insieme completo di soluzioni.
    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

TREDICESIMA LEZIONE - 15 Novembre 2012:
  Elementi coprimi (o "primi tra loro").
  Esistenza del MCD in Z, e identità di Bézout per esso: calcolo con l'algoritmo euclideo delle divisioni successive. Esercizi di calcolo esplicito.
  Tra numeri interi, ogni irriducibile è primo.
  Teorema Fondamentale dell'Aritmetica: esistenza e unicità di una fattorizzazione in irriducibili per interi (non nulli) non invertibili (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) .
  Equazioni diofantee: definizione, criterio di esistenza di soluzioni, algoritmo per il calcolo esplicito di una soluzione. Esempi espliciti.
    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

DODICESIMA LEZIONE - 14 Novembre 2012:
  Il problema generale della fattorizzazione in un monoide: esempi varî di esistenza, controesempi all'unicità.
  Elementi riducibili, elementi irriducibili. Fattorizzazioni banali, fattorizzazioni equivalenti.
  Teorema Fondamentale dell'Aritmetica: esistenza e unicità di una fattorizzazione in irriducibili per interi (non nulli) non invertibili (dimostrazione dell'esistenza).
  Teorema di Euclide: Esistono infiniti interi irriducibili a due a due non associati (senza dimostrazione).
  Elementi primi; ogni primo è irriducibile. Massimo comun divisore (=M.C.D.) e minimo comun multiplo (=m.c.m.).
  Divisione con resto tra numeri interi: esistenza e unicità di quoziente e resto (positivo).
    Bibliografia:   [AaVv] file Numeri interi (D'Andrea), paragrafo 4 - [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

UNDICESIMA LEZIONE - 8 Novembre 2012:
  1^o Teorema di Cantor: L'unione di una famiglia finita (non vuota) o numerabile di insiemi numerabili è numerabile   -   Applicazioni: Z, Q e NxN 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 "Aleph_n" (per ogni n in N). La cardinalità del continuo: |R| = |P(N)| (senza dimostrazione). L'ipotesi del continuo generalizzata (cenni).
  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.
    Bibliografia:   [AaVv] file Cardinalità (D'Andrea) e file Numeri interi (D'Andrea) - [Ca] Capitolo I, paragrafo 6; Capitolo II, paragrafo 2 - [G-P] file Funzioni e cardinalità, paragrafo 5 - [L-L] Chapter 3, section 7; Chapter 11, sections 1, 2 & 5 - [PC] Capitolo 1, paragrafo 5; Capitolo 2, paragrafo 1
    Videolezioni:   Cardinalità 1   (insiemi equipotenti, cardinalità; Primo Teorema di Cantor)   -   Cardinalità 2   (Secondo Teorema di Cantor)

DECIMA LEZIONE - 7 Novembre 2012:
  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; Teorema di Schroeder-Bernstein (senza dimostrazione).
  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
    Videolezioni:   Cardinalità 1   (insiemi equipotenti, cardinalità; Primo Teorema di Cantor)

NONA LEZIONE - 31 Ottobre 2012:
  Divisione con resto tra numeri naturali; 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à. La procedura operativa per il calcolo della scrittura posizionale di un numero naturale in una base data.
  Esempi di calcolo di scrittura posizionale (in base data) di un numero assegnato. I numeri descrivibili con al più N cifre nella scrittura posizionale in base b sono tutti quelli da 0 fino a   b^N - 1 .
    Bibliografia:   [AaVv] file Numeri naturali (D'Andrea) - [Ca] Capitolo I, paragrafo 5; Capitolo II, paragrafo 2 - [G-P] file Induzione; file Aritmetica sugli interi, etc. (complementi), paragrafo 1 - [L-L] Chapter 1, section 8; Chapter 11, section 3 - [PC] Capitolo 1, paragrafo 4; Capitolo 2, paragrafo 10
    Videolezioni:   Divisione (divisione con resto tra numeri naturali)   -   Numerazione (numerazione in base arbitraria / scrittura posizionale)

OTTAVA LEZIONE - 25 Ottobre 2012:
  Sistema dei numeri naturali (=S.N.N.): definizione tramite assiomi di Peano. Il Principio di Induzione Debole, o Semplice (=Pr.I.D./S.). Il problema della esistenza e unicità di un S.N.N. (cenni).
  Relazione d'ordine (totale), somma e prodotto tra numeri naturali. L'insieme dei numeri naturali è un semianello (per somma e prodotto) in cui l'ordine è compatibile con le due operazioni.
  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).
  Dimostrazioni per induzione: strategia - base, passo induttivo - esempi.
    Bibliografia:   [AaVv] file Numeri naturali (D'Andrea) - [Ca] Capitolo I, paragrafo 5 - [G-P] file Induzione - [L-L] Chapter 1, section 8; Chapter 11, section 3 - [PC] Capitolo 1, paragrafo 4
    Videolezioni:   Naturali (sistema dei numeri naturali: assiomi di Peano, ordine, operazioni)   -   Induzione (metodo di dimostrazione per induzione [semplice / forte / minimo])

SETTIMA LEZIONE - 24 Ottobre 2012:
  Operazioni (binarie) in un insieme; gruppoidi. Proprietà speciali di operazioni binarie. Unicità di elemento neutro (se esiste) e di elemento inverso (se esiste) di un elemento dato.
  Semigruppi, monoidi, gruppi. Il sottoinsieme degli elementi invertibili in un monoide è un gruppo (per la stessa operazione).
  Esempi e contro esempi di gruppoidi, semigruppi, monoidi, gruppi. Permutazioni di un insieme. L'insieme delle permutazioni di un insieme è un gruppo per la composizione.
  Il monoide libero A^* su un insieme A (=linguaggio sull'alfabeto A) con l'operazione di giustapposizione.
  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, paragrafi 1 e 2; Capitolo 4, paragrafo 1
    Videolezioni:   Operazioni 1 (operazioni in un insieme; insiemi con una operazione)   -   Operazioni 2 (insiemi con più operazioni)

SESTA LEZIONE - 18 Ottobre 2012:
  Rappresentante di una classe di equivalenza.
  L’insieme quoziente di un insieme modulo un’equivalenza; l’insieme quoziente è una partizione dell’insieme di partenza. La relazione associata ad una partizione è un’equivalenza. Le due costruzioni precedenti sono una l’inversa dell’altra.
  La proiezione canonica associata a un’equivalenza.
  Esempi di equivalenze, classi di equivalenza, insiemi quozienti, proiezioni canoniche, ecc. ecc.
    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)

QUINTA LEZIONE - 17 Ottobre 2012:
  Relazioni (binarie) in un insieme; composizione, inversa e potenze di relazioni. Proprietà notevoli per una relazione: riflessività, simmetricità, antisimmetricità, transitività.
  Relazioni di equivalenza: definizione, esempi. La congruenza modulo n tra numeri interi è una equivalenza. La relazione in X associata ad una funzione f da X a Y è una equivalenza. Generalizzazione: la relazione in X controimmagine, per una funzione f da X a Y, di una relazione in Y, è riflessiva, risp. simmetrica, risp. transitiva, se tale è la relazione iniziale in Y.
  Classi di equivalenza. La relazione in X associata ad una partizione di X.
    Bibliografia:   [Ca] Capitolo I, paragrafo 3 - [G-P] file Relazioni 1 - [L-L] Chapter 2 - [PC] Capitolo 1, paragrafo 2
    Videolezione:   Relazioni (relazioni in un insieme: generalità, esempi)

QUARTA LEZIONE - 11 Ottobre 2012:
  Composizione di funzioni: descrizione, associatività, non commutatività (in generale). Potenze di corrispondenze (da un insieme in sé stesso), potenze di funzioni (da un insieme in sé stesso).
  Funzioni invertibili: definizione; caratterizzazione in termini intrinseci (biiettività) e in termini della corrispondenza inversa (dev'essere a sua volta una funzione).
  Funzioni caratteristiche in un insieme. Biiezione naturale tra l'insieme delle parti di un insieme A e l'insieme delle funzioni caratteristiche in A.
    Bibliografia:   [Ca] Capitolo I, paragrafo 2 - [G-P] file Funzioni e cardinalità - [L-L] Chapter 3 - [PC] Capitolo 1, paragrafo 3
    Videolezioni:   Funzioni 2 (composizione di funzioni, funzioni invertibili)   -   Funzioni caratteristiche (funzioni caratteristiche in un insieme)

TERZA LEZIONE - 10 Ottobre 2012:
  Funzioni (o "applicazioni"): definizione, esempi, controesempi. Immagini e controimmagini di sottoinsiemi del dominio o del codominio.
  Restrizione di una funzione ad un sottoinsieme del dominio. Caratterizzazione delle famiglie come funzioni.
  Funzioni iniettive; funzioni suriettive; funzioni biiettive. Caratterizzazione della biiettività di una funzione tramite la corrispondenza inversa (deve essere a sua volta una funzione).
    Bibliografia:   [Ca] Capitolo I, paragrafo 2 - [G-P] file Funzioni e cardinalità - [L-L] Chapter 3 - [PC] Capitolo 1, paragrafo 3
    Videolezione:   Funzioni 1 (funzioni; iniettività, suriettività, biiettività)

SECONDA LEZIONE - 4 Ottobre 2012:
  Famiglie: definizione, comparazione con gli insiemi. Partizioni: definizione, esempi.
  Corrispondenze tra insiemi: definizione, esempi. Corrispondenza vuota, corrispondenza totale; corrispondenza identica. Immagine - tramite una corrispondenza data - di un sottoinsieme del dominio. Controimmagine - tramite una corrispondenza data - di un sottoinsieme del codominio.
  Corrispondenza inversa; composizione - o prodotto (operatorio) - di due corrispondenze: definizione, esempi. Proprietà notevoli di inversione e composizione: associatività, esistenza di "elementi neutri", ecc.
    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)

PRIMA LEZIONE - 3 Ottobre 2012:
  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. L'insieme vuoto. L'insieme delle parti di un insieme.
  Operazioni tra insiemi: intersezione, unione, differenza, complementare, differenza simmetrica, prodotto cartesiano. Proprietà notevoli: (1) associatività e commutatività di intersezione, unione e differenza simmetrica; (2) 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)