Matematica Discreta (Elementi) 2001-2002

Crediti: 6

Conoscenze: conoscenze di matematica di base (Scuola Superiore)

Abilità: uso delle tecniche di logica in un ragionamento matematico; tecniche di dimostrazione; linguaggio degli insiemi; nozioni introduttive su relazioni, grafi e reticoli; insieme delle classi di resto modulo n; matrici e sistemi lineari:

Docenti: Docenti: Proff. M. Cazzola, F. Dalla Volta, M. Rigoli

Programma:

  1. Elementi di logica delle proposizioni:
    Cenni di logica formale. Operazioni tra proposizioni: congiunzione, disgiunzione, o esclusivo, implicazione materiale, doppia implicazione, implicazione contronominale, proposizioni composte. Equivalenza di proposizioni: tautologie e contraddizioni, dimostrazioni dell'equivalenza di proposizioni. Quantificatori: quantificatore universale e quantificatore esistenziale; verità e falsità di proposizioni contenenti quantificatori, quantificatori multipli, negazione di un quantificatore.
    Tecniche di dimostrazione: deduzioni logiche fondamentali, dimostrazioni dirette e indirette, dimostrazioni per assurdo, dimostrazioni per induzione (prima e seconda forma). Esempi di deduzioni errate.
  2. Insiemi:
    Come si denota un insieme, operazioni tra gli insiemi. Corrispondenze e applicazioni. Prodotto cartesiano, corrispondenze e relazioni. Applicazioni: iniettività, suriettività, biiettività. Applicazioni composte. Cardinalità di insiemi .
  3. Numeri naturali e numeri interi:
    Divisione tra numeri interi, divisori e multipli, numeri primi (teorema fondamentale dell'aritmetica), esistenza di infiniti primi. Massimo comun divisore e minimo comune multiplo, algoritmo euclideo per il calcolo del MCD, identità di Bezout. Principio di induzione: prima e seconda forma.
  4. Insiemi e relazioni:
    Grafo di una relazione. Equivalenze e partizioni, insieme quoziente. Insieme delle classi di resto modulo n. Ordinamenti: massimo, minimo, elemento massimale, elemento minimale, maggiorante, minorante, estremo inferiore, estremo superiore..
  5. Grafi e strutture algebriche
    Reticoli, reticoli booleani. Cammini e circuiti euleriani, alberi e grafi piani. Insiemi dotati di una operazione: gruppi. Insiemi dotati di più operazioni: anelli, campi. Esempi.
  6. Matrici e sistemi lineari:
    Matrici a coefficienti in un campo, somma e prodotto di matrici
    Sistemi lineari a coefficienti in un campo. Sistemi equivalenti, discussione sull'esistenza delle soluzioni di un sistema lineare: metodo di triangolazione di Gauss.

Testi consigliati:

Modalità di esame: scritto e orale

Link al corso: www.matapp.unimib.it/~marina/did/mdis01/