Corso di Laurea in Ingegneria Informatica
a.a 2013-2014 - 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 dettagliata    

                                       

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

TRENTADUESIMA LEZIONE (soltanto esercitazioni) - 30 Gennaio 2014:
  Esercizi varî su:
      -   equazioni modulari, equazioni congruenziali, equazioni diofantee, identità di Bézout;
      -   polinomi booleani: somme di prodotti, forma normale disgiuntiva, forme minimali;
      -   calcolo di inversi in anelli Z_n di classi resto modulo n;
      -   relazioni di equivalenza e funzioni, classi di equivalenza.
  FINE del CORSO

TRENTUNESIMA LEZIONE (soltanto esercitazioni) - 29 Gennaio 2014:
  Esercizi varî su:
      -   equazioni modulari, equazioni congruenziali, equazioni diofantee: collegamento tra i tre problemi;
      -   atomi, v-irriducibili, fattorizzazione in v-irriducibili in un reticolo; algebre di Boole;
      -   successioni ricorsive (di secondo grado, lineari omogenee a coefficienti costanti);
      -   relazioni; preordini, ordini, equivalenze.

TRENTESIMA LEZIONE (soltanto esercitazioni) - 23 Gennaio 2014:
  Esercizi varî su:
      -   sistemi di equazioni congruenziali (con il Teorema Cinese dei Resti);
      -   atomi, v-irriducibili, fattorizzazione in v-irriducibili in un reticolo;
      -   successioni ricorsive (di secondo grado, lineari omogenee a coefficienti costanti);
      -   polinomi booleani (forma normale disgiuntiva, forme minimali).

VENTINOVESIMA LEZIONE (soltanto esercitazioni) - 22 Gennaio 2014:
  Esercizi varî su:
      -   successioni ricorsive (di secondo grado, lineari omogenee a coefficienti costanti);
      -   equazioni diofantee;
      -   sistemi di equazioni congruenziali (per sostituzioni successive);
      -   polinomi booleani (forma normale disgiuntiva, forme minimali).

VENTOTTESIMA LEZIONE - 16 Gennaio 2013:
  Lemma: Per successioni ricorsive l.o.c.c, 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 l.o.c.c. di grado 1.
  Calcolo esplicito di una base per lo spazio delle successioni ricorsive l.o.c.c. di grado 2 complesse: caso di due radici (del polinomio caratteristico) distinte, e caso di una (unica) radice doppia.
  Calcolo esplicito di una base per lo spazio delle successioni ricorsive l.o.c.c. di grado 2 reali: caso di due radici (del polinomio caratteristico) distinte reali, caso di una (unica) radice doppia (reale), caso di due radici distinte complesse non reali (coniugate).
  FINE del PROGRAMMA (seguono sole esercitazioni)
    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 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)   -   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 videolezione 3.2 è lo sviluppo consecutivo (senza transizione) della 3.1 precedente.

VENTISETTESIMA LEZIONE - 15 Gennaio 2014:
  Funzioni (o "successioni") ricorsive. Dati iniziali, equazione ricorsiva e grado (di ricorsività) di una funzione ricorsiva. Casi particolari di funzioni ricorsive: lineari, lineari omogenee, lineari a coefficienti costanti, lineari omogenee a coefficienti costanti (=l.o.c.c.) - esempi e controesempi. Polinomio caratteristico, equazione caratteristica nel caso lineare a coefficienti costanti.
  Teorema di Ricorsione per l'esistenza e unicità di una funzione che abbia dati iniziali assegnati e soddisfi una data equazione ricorsiva.
  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)

VENTISEIESIMA LEZIONE - 9 Gennaio 2014:
  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).
  Algoritmo di selezione di una forma minimale di un polinomio booleano a partire dalla somma di tutti gli implicanti primi del polinomio stesso (senza dimostrazione).
  Esempi espliciti di calcolo della forma normale disgiuntiva e di una forma minimale per un polinomio booleano. Esempi espliciti di polinomi booleani che hanno diverse forme minimali.
    Bibliografia:   [G-P] file Forme minimali di una funzione polinomiale - [L-L] Chapter 15, section 9

VENTICINQUESIMA LEZIONE - 8 Gennaio 2014:
  F_n(2) = P_n(2) , cioè ogni funzione booleana su 2 è polinomiale.
  Misura della "grandezza" di una somma di prodotti; la relazione di "maggior semplicità" tra somme di prodotti equivalenti.
  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 è somma di (alcuni) implicanti primi di f.
    Bibliografia:   [G-P] file Funzioni booleane; file Forme minimali di una funzione polinomiale - [L-L] Chapter 15, sections 8 and 9

VENTIQUATTRESIMA LEZIONE - 19 Dicembre 2013:
  Prodotti, prodotti fondamentali, prodotti completi in P_n. Somme di prodotti (fondamentali, complete, ridondanti/irridondanti).
  Passaggio da un oggetto - prodotto o somma - non "buono" ad uno "buono" (= fondamentale, completo, o irridondante) equivalente.
  La forma normale disgiuntiva di un polinomio booleano.
  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.
    Bibliografia:   [G-P] file Funzioni booleane - [L-L] Chapter 15, sections 8 and 9

VENTITREESIMA LEZIONE - 18 Dicembre 2013:
  Teorema: Un reticolo è distributivo se e soltanto se non ha sottoreticoli isomorfi a N₅ o a M₅ (senza dimostrazione).
  Esempi espliciti dell'isomorfismo fornito dal Teorema di Stone.
  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 (soltanto cenni di dimostrazione).
    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])

VENTIDUESIMA LEZIONE - 12 Dicembre 2013:
  Isomorfismi tra reticoli, reticoli isomorfi. Sottoreticoli di un reticolo. Criterio di isomorfismo tra un reticolo D_r e un reticolo D_s .
  Algebre di Boole: definizione come reticoli, definizione come insiemi con due operazioni; equivalenza delle due definizioni (senza 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; prodotti di algebre di Boole; i prodotti {0,1}ⁿ.
  Esempi di isomorfismi: (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.
    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])

VENTUNESIMA LEZIONE - 11 Dicembre 2013:
  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.
    Bibliografia:   [G-P] file Reticoli, paragrafo 4 - [L-L] Chapter 14, sections from 8 to 11
    Videolezioni:   Reticoli 2   (v-fattorizzazione: v-irriducibili, atomi, esistenza/unicità di v-fattorizzazioni)

VENTESIMA LEZIONE - 5 Dicembre 2013:
  Reticoli: definizione come insiemi ordinati e definizione come insiemi con due operazioni binarie; 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.
  Insiemi ordinati limitati. 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à)

DICIANNOVESIMA LEZIONE - 4 Dicembre 2013:
  Relazioni d'ordine, insiemi ordinati; ordini totali. Principio di Dualità per insiemi ordinati.
  Relazione di copertura e diagramma di Hasse per un insieme ordinato. 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.
  Intervalli (chiusi, aperti, semi-chiusi/aperti, limitati o illimitati) in un insieme ordinato.
    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)

DICIOTTESIMA LEZIONE - 28 Novembre 2013:
  Sistemi di equazioni congruenziali: discussione, sistemi in forma risolta, sistemi cinesi (o "in forma cinese"). Il Teorema Cinese dei Resti (senza dimostrazione) per sistemi cinesi.
  Metodo di risoluzione di un sistema tramite sostituzioni successive oppure - sotto le ipotesi del caso - tramite la procedura fornita dal Teorema Cinese dei Resti.
  Esercizi espliciti su equazioni diofantee, equazioni congruenziali, equazioni modulari, sistemi di equazioni congruenziali, calcolo di inversi in Z_n, calcolo di potenze in Z_n.
    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 e 8

DICIASSETTESIMA LEZIONE - 27 Novembre 2013:
  Equazioni congruenziali in Z: criterio di esistenza di soluzioni, algoritmo per il calcolo di una soluzione, insieme completo di soluzioni.
  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).
    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 - 21 Novembre 2013:
  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) se e soltanto se Z_n è un campo.
  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.
    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 - 20 Novembre 2013:
  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 - e la formula mcm(a,b) = a b / MCD(a,b) .
  Equazioni diofantee: definizione, criterio per l'esistenza di soluzioni, algoritmo per il calcolo esplicito di una soluzione. Esempi espliciti.
  Congruenze in Z (richiami). Ogni congruenza è una equivalenza; descrizione delle classi di congruenza e dell'insieme quoziente Z_n.
    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, sections 7 e 8 - [PC] Capitolo 2, paragrafi 2, 3, 6 e 7

QUATTORDICESIMA LEZIONE - 14 Novembre 2013:
  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.
  Teorema Fondamentale dell'Aritmetica: esistenza e unicità di una fattorizzazione in irriducibili per interi (non nulli) non invertibili (cenni di dimostrazione dell'unicità).
    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 - 13 Novembre 2013:
  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 - 7 Novembre 2013:
  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).
    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 - 6 Novembre 2013:
  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).
  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
    Videolezioni:   Cardinalità 1   (insiemi equipotenti, cardinalità; Primo Teorema di Cantor)

DECIMA LEZIONE - 31 Ottobre 2013:
  Scrittura posizionale (in base data): i numeri descrivibili con al più N cifre nella scrittura posizionale in base b sono tutti quelli da 0 fino a   b^N - 1 .
  Esercizi varî sulla scrittura posizionale (in base data) di un numero assegnato: conversione da una base ad un'altra, calcolo di somme e prodotti in una base arbitraria, ecc.
  Esercizi varî sulle dimostrazioni per induzione.
    Bibliografia:   [Ca] Capitolo I, paragrafo 5; Capitolo II, paragrafo 2 - [G-P] file Induzione - [L-L] Chapter 1, section 8; Chapter 11, section 3 - [PC] Capitolo 1, paragrafo 4; Capitolo 2, paragrafo 10
    Videolezioni:   Numerazione (numerazione in base arbitraria / scrittura posizionale)   -   Induzione (metodo di dimostrazione per induzione [semplice / forte / minimo])

NONA LEZIONE - 30 Ottobre 2013:
  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.
    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 - 24 Ottobre 2013:
  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 - 23 Ottobre 2013:
  Operazioni (binarie) in un insieme; gruppoidi. Proprietà speciali possibili per operazioni binarie. Unicità di elemento neutro (se esiste) e di elemento inverso (se esiste) di un elemento dato.
  Semigruppi, monoidi, gruppi. Esempi e controesempi. Il monoide E^E delle endofunzioni di un insieme E; il gruppo E^E delle permutazioni di un insieme E (per l'operazione di composizione). Il monoide libero A^* su un insieme A (=linguaggio libero 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 1, paragrafo 2; 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)

SESTA LEZIONE - 17 Ottobre 2013:
  Classi di equivalenza; rappresentante di una classe di equivalenza. Quoziente di un insieme X modulo un’equivalenza; relazione in X associata ad una partizione di X.
  Il quoziente di un insieme X modulo un’equivalenza è una partizione dell’insieme X. La relazione in X associata ad una partizione di X è un’equivalenza. Le due costruzioni precedenti sono una l’inversa dell’altra.
  Esempi di equivalenze, classi di equivalenza, insiemi quozienti.
  La proiezione canonica associata a un’equivalenza; l'equivalenza associata alla proiezione canonica è l'equivalenza iniziale.
    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 - 16 Ottobre 2013:
  Relazioni (binarie) in un insieme; composizione, inversa e potenze di relazioni.
  Proprietà notevoli per una relazione: riflessività, simmetricità, antisimmetricità, transitività. Relazioni di preordine, relazioni d'ordine.
  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.
    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)

QUARTA LEZIONE - 10 Ottobre 2013:
  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 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.
  Biiezione naturale tra l'insieme delle parti di un insieme X e l'insieme delle funzioni caratteristiche in X.
    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 - 9 Ottobre 2013:
  Funzioni (o "applicazioni"): definizione, esempi, controesempi. Immagine - tramite una funzione - di un elemento del dominio; immagine, risp. controimmagine, di un sottoinsieme del dominio, risp. del codominio.
  Restrizione di una funzione ad un sottoinsieme del dominio. Caratterizzazione delle famiglie (di oggetti scelti in un insieme E indicizzati da 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).
    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 - 3 Ottobre 2013:
  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 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", 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 - 2 Ottobre 2013:
  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. Famiglie di insiemi. Partizioni 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) 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)