Corso di Laurea in Ingegneria Informatica
a.a 2014-2015 - 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) - 29 Gennaio 2015:
  Esercizi varî su:
      -   equazioni modulari, equazioni congruenziali, equazioni diofantee, identità di Bézout per M.C.D.(a,b);
      -   calcolo di potenze e calcolo di inversi in anelli Z_n di classi resto modulo n;
      -   dimostrazioni per induzione;
      -   relazioni; preordini, ordini.
  FINE del CORSO

TRENTUNESIMA LEZIONE (soltanto esercitazioni) - 28 Gennaio 2015:
  Esercizi varî su:
      -   equazioni modulari, equazioni congruenziali, equazioni diofantee: collegamento tra i tre problemi;
      -   sistemi di equazioni congruenziali (discussione, risoluzione tramite sostituzioni successive o tramite il Teorema Cinese del Resto;
      -   atomi, v-irriducibili, fattorizzazione in v-irriducibili in un reticolo; algebre di Boole;
      -   successioni ricorsive (di secondo grado, lineari omogenee a coefficienti costanti).

TRENTESIMA LEZIONE (soltanto esercitazioni) - 22 Gennaio 2015:
  Esercizi varî su:
      -   successioni ricorsive (di secondo grado, lineari omogenee a coefficienti costanti), con "condizioni iniziali" di vario tipo;
      -   iniettività, suriettività, biiettività di funzioni;
      -   equazioni modulari ed equazioni congruenziali corrispondenti;
      -   insiemi ordinati, elementi massiamli, elementi minimali, massimo, minimo; reticoli;
      -   svolgimento di operazioni tra numeri naturali utilizzando la notazione posizionale in base qualsiasi.

VENTINOVESIMA LEZIONE (soltanto esercitazioni) - 21 Gennaio 2015:
  Esercizi varî su:
      -   successioni ricorsive (di secondo grado, lineari omogenee a coefficienti costanti), con "condizioni iniziali" di vario tipo;
      -   equazioni diofantee, equazioni congruenziali, equazioni modulari; calcolo del M.C.D. e di un'identità di Bézout per esso;
      -   analisi dell'invertibilità, e calcolo dell'inverso (quando esista), per una classe in Z_n;
      -   relazioni di preordine, relazioni di equivalenza, classi di equivalenza.

VENTOTTESIMA LEZIONE - 15 Gennaio 2015:
  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 (seguiranno soltanto 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 - 14 Gennaio 2015:
  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 - 8 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 - 7 Gennaio 2014:
  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 da cui non si può cancellare alcun termine.
    Bibliografia:   [G-P] file Funzioni booleane; file Forme minimali di una funzione polinomiale - [L-L] Chapter 15, sections 8 and 9

VENTIQUATTRESIMA LEZIONE - 18 Dicembre 2014:
  Prodotti, prodotti fondamentali, prodotti completi in P_n. Somme di prodotti (fondamentali/completi); somme di prodotti ridondanti o non ridondanti.
  Passaggio da un oggetto - prodotto o somma - non "buono" ad uno "buono" (= fondamentale, completo, o non ridondante) 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.
  P_n(2) = F_n(2) , cioè ogni funzione booleana su 2 è polinomiale.
    Bibliografia:   [G-P] file Funzioni booleane - [L-L] Chapter 15, sections 8 and 9

VENTITREESIMA LEZIONE - 17 Dicembre 2014:
  Sottoalgebre di Boole di un'algebra di Boole.
  Teorema (Stone - caso generale): Ogni algebra di Boole è isomorfa a una sottoalgebra di Boole dell'insieme delle parti di un opportuno insieme.
  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).
  Il Principio di Dualità per algebre di Boole.
  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.
    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 - 11 Dicembre 2014:
  Isomorfismi tra reticoli, reticoli isomorfi. Sottoreticoli di un reticolo.
  Teorema: Un reticolo è distributivo se e soltanto se non ha sottoreticoli isomorfi a N₅ o a M₅ (senza dimostrazione).
  L'isomorfismo tra un reticolo D_r e un opportuno reticolo "iperparallelepipedo". Criterio di isomorfismo tra D_r e D_s .
  Algebre di Boole: definizione come reticoli, definizione come insiemi con due operazioni; equivalenza delle due definizioni (cenni di dimostrazione).
  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. Esempio: (1) la biiezione canonica da P(X) a {0,1}^X - per ogni insieme X - è 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 ha cardinalità 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 - 10 Dicembre 2014:
  Reticoli distributivi: definizione, 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).
  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 - 4 Dicembre 2014:
  Ordinamento indotto in un sottoinsieme di un insieme ordinato. Ordinamento prodotto sul prodotto cartesiano di insiemi ordinati. Ordinamento per funzioni da un insieme ad un insieme ordinato.
  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; equivalenza delle due definizioni (cenni di dimostrazione).
  Principio di Dualità per reticoli.
  Esempi (e controesempi) di reticoli: gli insiemi con ordinamento totale, N e N₊ con la divisibilità, ogni intervallo in un reticolo, il reticolo D_n dei divisori di n, l'insieme delle parti di un insieme.
  Reticoli limitati.   -   Proposizione: Ogni reticolo finito è limitato.
  Complementi in un reticolo limitato; reticoli complementati. Esempi e controesempi.
    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 - 3 Dicembre 2014:
  Relazioni d'ordine, insiemi ordinati; ordini totali, ordini buoni. 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.
  Insiemi (ordinati) limitati inferiormente / limitati superiormente / limitati.
    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 - 27 Novembre 2014:
  Sistemi di equazioni congruenziali: discussione, sistemi in forma risolta, sistemi cinesi (o "in forma cinese").
  Il Teorema Cinese del Resto per sistemi cinesi (senza dimostrazione).
  Metodo di risoluzione di un sistema tramite sostituzioni successive oppure - sotto le ipotesi del caso - tramite la procedura fornita dal Teorema Cinese dei Resti.
  Esempi espliciti di risoluzione di sistemi di equazioni congruenziali, tramite il Teorema Cinese del Resto o mediante il metodo delle sostituzioni successive.
    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 - 26 Novembre 2014:
  Equazioni congruenziali in Z, equazioni modulari in Z_n: 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, proprietà, formula esplicita.
  Ripetitività delle potenze in Z_n: generalità.
  Il Piccolo Teorema di Fermat (senza dimostrazione), il Teorema di Eulero (senza dimostrazione), applicazione alla semplificazione delle potenze in Z_n. Elaborazione dei casi in cui non si applichi il Teorema di Eulero (cenni).
    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 - 20 Novembre 2014:
  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 (cenni di dimostrazione).
  Esercizio:   Z_n non ha divisori di zero non banali se e soltanto se n è irriducibile (=primo) se e soltanto se Z_n è un campo.
  Criteri di divisibilità in Z: strategia generale - calcolo della classe in Z_n di un intero non negativo z tramite la scrittura posizionale di z in una data base - esempi specifici.
  Equazioni congruenziali (in Z): definizione, connessione con equazioni modulari (:= 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 - 19 Novembre 2014:
  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à).
  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.
    Bibliografia:   [AaVv] file Numeri interi (D'Andrea), paragrafo 4 - [Ca] Capitolo II, paragrafo 3 - [G-P] file Aritmetica sugli interi, congruenze, Teorema Cinese del Resto - [L-L] Chapter 11, section 7 - [PC] Capitolo 2, paragrafi 2, 3

QUATTORDICESIMA LEZIONE - 13 Novembre 2014:
  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.) tra numeri interi non nulli. 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 di MCD e identità di Bézout.
    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 - 12 Novembre 2014:
  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 - 6 Novembre 2014:
  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; cardinali infiniti superiori)

UNDICESIMA LEZIONE - 5 Novembre 2014:
  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 della "transitività").
  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 - 30 Ottobre 2014:
  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.
  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.
    Bibliografia:   [Ca] Capitolo II, paragrafo 2 - [G-P] file Aritmetica sugli interi, etc. (complementi), paragrafo 1 - [PC] Capitolo 2, paragrafo 10
    Videolezione:   Numerazione (numerazione in base arbitraria / scrittura posizionale)

NONA LEZIONE - 29 Ottobre 2014:
  Operazioni di somma e prodotto tra numeri naturali (definizione ricorsiva, tramite il Pr.I.D.). Proprietà di somma e prodotto, compatibilità 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).
  Il metodo di dimostrazione per induzione (debole o forte o mediante principio del minimo): idea, strategia - base, passo induttivo (con ipotesi induttiva).
  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.
    Bibliografia:   [AaVv] file Numeri naturali (D'Andrea) - [Ca] Capitolo I, paragrafo 5; Capitolo II, paragrafo 1 - [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])   -   Divisione (divisione con resto tra numeri naturali)

OTTAVA LEZIONE - 23 Ottobre 2014:
  Operazioni (binarie) in un insieme. Proprietà speciali possibili per operazioni binarie; elementi neutri, inversi. Unicità di elemento neutro (se esiste) e di elemento inverso (se esiste) di un elemento dato.
  Gruppi. In un insieme con operazione associativa e elemento neutro, gli invertibili formano un gruppo; esempio del gruppo S(E) delle permutazioni nell'insieme E^E di tutte le endofunzioni di un insieme E (per l'operazione di composizione). Esempi e controesempi.
  Insiemi con due operazioni (binarie); casi speciali (anelli, campi). Esempi e controesempi.
  Sistema dei numeri naturali (=S.N.N.): definizione tramite assiomi di Peano. Il Principio di Induzione Debole, o Semplice (=Pr.I.D./S.).
  Esistenza e unicità di un S.N.N. (cenni).
  Relazione d'ordine (totale) tra numeri naturali: definisione (ricorsiva) tramite il Pr.I.D.
    Bibliografia:   [AaVv] file Numeri naturali (D'Andrea) - [Ca] Capitolo I, paragrafi 4 e 5 - [G-P] file Gruppi, anelli, campi - [L-L] Appendix B - [PC] Capitolo 1, paragrafo 2; Capitolo 5, paragrafo 1; Capitolo 4, paragrafo 1; Capitolo 1, paragrafo 4
    Videolezioni:   Operazioni 1 (operazioni in un insieme; insiemi con una operazione)   -   Operazioni 2 (insiemi con più operazioni)   -   Naturali (sistema dei numeri naturali: assiomi di Peano, ordine, operazioni)

SETTIMA LEZIONE - 22 Ottobre 2014:
  Classi di equivalenza in un insieme X; rappresentante di una classe di equivalenza; insieme quoziente di X modulo un’equivalenza, proiezione canonica associata. 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.
  L'equivalenza associata alla proiezione canonica è l'equivalenza iniziale.
  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 - 16 Ottobre 2014:
  Relazioni (binarie) in un insieme; operazioni insiemistiche, inversione e composizione di relazioni (in uno stesso insieme).
  Proprietà notevoli per una relazione: riflessività, simmetricità, antisimmetricità, transitività.
  Relazioni di preordine, relazioni d'ordine; relazioni d'ordine totali. Relazioni di equivalenza: definizione, esempi.
  La congruenza modulo n tra numeri interi è una equivalenza. La relazione in E associata ad una funzione f da E a V è 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)

QUINTA LEZIONE - 15 Ottobre 2014:
  Funzioni invertibili (definizione). Caratterizzazione delle funzioni invertibili in termini intrinseci (biiettività) e in termini della corrispondenza inversa (dev'essere a sua volta una funzione). Conseguenza: se una funzione è invertibile, allora la sua funzione inversa non è altri che la sua corrispondenza inversa.
  L'ínsieme S(E) delle permutazioni di un insieme E. L'ínsieme 2^E delle funzioni caratteristiche in un insieme E.
  La corrispondenza naturale tra l'insieme delle parti di un insieme E e l'insieme 2^E delle funzioni caratteristiche in E è una funzione invertibile.
    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)

QUARTA LEZIONE - 9 Ottobre 2014:
  Funzioni (o "applicazioni"): definizione, esempi, controesempi. Restrizione di una funzione ad un sottoinsieme del dominio. La composizione di due funzioni è a sua volta una funzione.
  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 - e in tal caso sarà a sua volta biiettiva).
    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à)

TERZA LEZIONE - 8 Ottobre 2014:
  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.
  Operazioni insiemistiche tra corrispondenze (unione, intersezione, ecc.). Corrispondenza complementare; corrispondenza inversa.
  Composizione - o prodotto (operatorio) - di due corrispondenze. Proprietà notevoli di inversione e composizione: associatività, esistenza di "elementi neutri", ecc.
  Potenze di una corrispondenza con dominio e codominio coincidenti.
    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 - 2 Ottobre 2014:
  Famiglie (di oggetti). Partizioni di un insieme: definizione, esempi, controesempi.
  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:   [G-P] file Insiemi - [L-L] Chapter 1 - [PC] Capitolo 1, paragrafo 2
    Videolezione:   Insiemi (insiemi, sottoinsiemi, insieme delle parti, operazioni tra insiemi)

PRIMA LEZIONE - 1 Ottobre 2014 (soltanto un'ora):
  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.
    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)