Corso di Laurea in Ingegneria Informatica
Anno Accademico 2015-16
Primo semestre
Diario delle lezioni del corso di ALGEBRA E LOGICA

LINEE GUIDA PER GLI SCRITTI

Il compito scritto verte sul programma svolto in classe durante il corso: teoria ed esercizi, come specificato nel programma dettagliato qui sotto.
Il compito consiste in un certo numero di esercizi. Possono essere richieste anche definizioni e semplici dimostrazioni.
Lo svolgimento degli esercizi deve contenere spiegazioni CHIARE, SINTETICHE, e COMPLETE: non sara' dato punteggio a risposte non motivate, anche se corrette.



TUTORATO

Durante le ore di tutorato potete chiedere chiarimenti sugli argomenti svolti a lezione. Ogni fine settimana trovate sul sito un foglio di esercizi sugli argomenti della settimana. Questi esercizi saranno discussi durante il tutorato della settimana successiva.





Prima settimana:


• Insiemi e sottoinsiemi. L'insieme vuoto. Uguaglianza fra insiemi. Operazioni sugli insiemi: unione, intersezione, complementare, prodotto cartesiano, insieme delle parti. Esempi. Alcune proprieta' delle operazioni di unione e intersezione: associativita', distributivita', etc..
  
• Preliminari pdf    Wikipedia wiki    Tavola riassuntiva link
  
  
• Funzioni tra insiemi. Dominio, codominio, immagine. Funzioni iniettive, suriettive, biiettive. Composizione di funzioni. Associativita' della composizione. Funzione identita'. Inversa di una funzione biiettiva. Esempi.
  
• Funzioni-Cardinalita', Sez. 1,2,3,4. pdf
  
• Testo: L&L., Cap I, Sez.1,2,3,4,5,6,7; Cap III: Sez.1,2,3.
  Esercizi1 2015; Esercizi-svolti 1: n. 1-14.
  
  
  

  Seconda settimana:
  

• Esempi di funzioni fra insiemi finiti e infiniti. Cardinalita' di un insieme. Insiemi numerabili e non numerabili: gli interi Z e i razionali Q sono numerabili.
• I reali R non sono numerabili. La cardinalita' di un insieme dato X e' sempre minore della cardinalita' dell'insieme delle parti P(X). Cenni al principio di induzione.
  
  Appunti: Funzioni e cardinalita': pag. 5-12; Induzione: pag. 1-7.
  Testo: L&L., Cap I, Sez. 8,9,10. Cap III: Sez. 5,6,7, Eserc. 3.13, 3.16, 3.28.
  Esercizi2 2015; Esercizi-svolti 1: n. 15-28.
  
  

  Terza settimana:
  

• Relazioni fra gli elementi di due insiemi A e B come sottoinsiemi del prodotto cartesiano A x B. Funzioni. Relazioni binarie su un insieme: riflessive, simmetriche, antisimmetriche, transitive.
  
• Relazioni di equivalenza: esempi. Classi di equivalenza e insieme quoziente. Partizione indotta.
  
  Appunti: Relazioni1: pag. 1-8.
  Testo: L&L., Cap.II: Sez.1,2,3,4,6,8.
  Esercizi3 2015; Esercizi-svolti 2: n. 1-10.
  
  

  Quarta settimana:
  

• Esempi di relazioni di equivalenza e rispettivi quozienti: i numeri razionali. Le classi resto modulo n. Relazioni di ordine su un insieme. Esempi: i numeri reali con l'ordinamento usuale, i numeri naturali con la relazione di divisibilita', l'insieme delle parti di un insieme con la relazione di contenenza. L'ordinamento lessicografico sul prodotto cartesiano di insiemi ordinati. Insiemi totalmente ordinati. Diagramma di Hasse associato ad una relazione di ordine.
  
• Insiemi ordinati: elementi massimali, massimo, elementi minimali, minimo. Maggioranti, estremo superiore, minoranti ed estremo inferiore di un sottoinsieme in un insieme ordinato.
  
  Appunti: Relazioni2: pag. 1-5.
  Testo: L&L., Cap.XIV: Sez.3,5,7.
  Esercizi4 2015; Esercizi-svolti 2: n. 11-15.
  
  

  Quinta settimana:
  

• Divisione con resto. Massimo comune divisore fra interi. L'algoritmo di Euclide. Equazioni lineari a coefficienti interi in due incognite. Un'equazione di questo tipo ax+by=c ammette soluzioni intere se e solo se mcd(a,b)|c. Soluzione generale di un'equazione omogenea a coefficienti interi ax+by=0.
  
• L'algoritmo di Euclide esteso. L'identita' di Bezout. Soluzione generale di un'equazione lineare a coefficienti interi ax+by=c compatibile.
  
  Appunti: nota1, pag.1-7.
  Esercizi5 2015; Esercizi-svolti 3: n.1-11.
  
  

  Sesta settimana:
  

• Equazioni diofantee ax+by=c: esempi. Congruenze modulo n.
  
• Congruenze modulo n.
  
  Appunti: nota1, pag.8-11.
  Esercizi6 2015; Esercizi-svolti 3: n.12, 15-18, 23.
  
  

  Settima settimana:
  

• Sistemi di congruenze. Il Teorema Cinese del Resto.
• Calcolo modulo n: somma e prodotto su Z_n. Introduzione ai gruppi.
  
  Appunti: nota1, pag.8-11; nota2, pag. 1-5.
  Esercizi7 2015; Esercizi-svolti 3: n. 20,21,22.
  
  

  Ottava settimana :
  

• Calcolo di un inverso modulo n. Gruppi abeliani finiti: (Z_n,+) e (Z_n^*,*). La funzione φ di Eulero.
  
• Il teorema di Lagrange e il Piccolo Teorema di Fermat. Applicazioni al calcolo di grosse potenze modulo un intero ed ai test di primalita' (cenni).
  
  Appunti: nota2, pag. 5-10.
  R. Schoof, Fattorizzazione e criptosistemi a chiave pubblica.
  Esercizi8 2015; Esercizi-svolti 4: n. 1-24 (no es.15, 16).
  
  

  Nona settimana:
  

• Il criptosistema a chiave pubblica R.S.A.: esempi con PARI/GP.
• Introduzione ai reticoli. Operazioni di reticolo e loro proprieta'. La relazione di ordine associata alle operazioni di reticolo (continua).
  Esempi: (P(X), ⊆, ∪, ∩), (N, | , mcd, mcm), (D_m, | , mcd, mcm).
  
  Appunti: Reticoli, pag. 1-2.
  L&L., Cap.XIV: Sez. 8 (tranne dualita' e Teorema 14.2).
  Esercizi11 2015; Esercizi-svolti 6: n. 2,4.
  
  

  Decima settimana:
  

• Reticoli: la relazione di ordine associata alle operazioni di reticolo. Esempi: (P(X), ⊆, ∪, ∩), (N, | , mcd, mcm), (D_m, | , mcd, mcm).
  
• Reticoli limitati. Complemento di un elemento in un reticolo limitato. Reticoli complementati. Reticoli distributivi.
  
  Appunti: Reticoli, pag. 1-6 (no sezione 4).
  L&L., Cap.XIV: Sez. 8 (tranne dualita' e Teorema 14.2), 9, 10,11.
  Esercizi12 2015; Esercizi-svolti 6: n. 1,3, 5, 6, 7, 17-23.
  
  

  Undicesima settimana:
  

• Algebre di Boole: assiomi di definizione; ulteriori proprieta' delle operazioni su un'algebra di Boole. Reticoli booleani e algebre di Boole.
  
• Isomorfisismi di reticoli e di algebre di Boole. Classificazione delle algebre di Boole finite (solo enunciato). Cenni al teorema di Stone.
  
  Appunti: Reticoli: pag. 9-11; Algebre di Boole, pag. 1-4.
  L&L., Cap. 15, Sez.1-6.
  Esercizi13 2015; Esercizi-svolti 7: 1-5.
  
  

  DODICESIMA SETTIMANA:
  

• Espressioni booleane: forma disgiuntiva (somma di prodotti).
  
  Appunti: Funzioni Booleane: pag. 1-4;
  L&L., Cap. 15, Sez.7-8.
  Esercizi14 2015; Esercizi-svolti 7: n. 9, 10.1.
  
  

  TREDICESIMA SETTIMANA:
  

• Esistenza e unicita' della forma normale disgiuntiva (somma di prodotti completa).
  
  
  Appunti: Funzioni Booleane: pag. 5-7;
  L&L., Cap. 15, Sez.7-8.
  Esercizi14 2015; Esercizi-svolti 7: n. 9, 10.1.
  
  

  QUATTORDICESIMA SETTIMANA:
  

• Implicanti primi e forme minimali. Metodo del consenso per la determinazione degli implicanti primi in una espressione booleana.
• L'algebra di Boole del calcolo proposizionale.
  
  Appunti: Forme minimali di una funzione polinomiale.
  L&L., Cap. 15, Sez.9.
  Esercizi15 2015; Esercizi-svolti 7: n. 10.2, 10.3, 12, 13.
  
  

  QUINDICESIMA SETTIMANA:
  

• L'algebra di Boole del calcolo proposizionale.
• Predicati e quantificatori (cenni).
  
  L&L., Cap. 4.
  Esercizi16 2015; Esercizi-svolti 8.
  
  

  Fine