Matematica Discreta - Algebra

Matematica discreta

Lezione 1: Divisibilità numeri interi

L'anello d'insieme numeri Z = { ... , -2, -1, 0, 1, 2 ...}, definisce due operazioni binarie interne (sommando/moltiplicando rimarremo sempre nell'insieme Z):

• Somma
• Prodotto

Valgono le proprietà: commutativa, associativa, distributiva ed esistenza dei neutri. Un'altra operazione binaria interna è la differenza, per cui non valgono le proprietà commutativa e associativa.

Divisibilità in Z

Definizione: Siano a appartenente a Z, b appartenente a Z escluso 0. Se esiste un intero q tale che a = bq, si dice che b | a (ossia b divide a).

In Z solo due elementi sono dotati di reciproco: -1 e 1. In Q e in R ogni divisore è dotato di reciproco.

Teorema del quoziente del resto

Siano a, b appartenenti a Z, b diverso da 0. Esistono e sono unici due interi q (quoziente) e r (resto) tali che:

a = bq + r

• 0 ≤ r < |b|

MCD: Se MCD(a, b) = d, allora -d è l'unico altro massimo comun divisore di a e b.

mcm: Un intero m è detto minimo comune multiplo di a e b se:

• a divide m, b divide m

Algoritmo di Euclide per trovare MCD

ax + by = d sia il MDC (a, b), con a e b > 0.

• Trovo il maggiore tra a e b, e pongo quanto segue: a = bq₁ + r₁ (q₁ = quoziente, r₁ = resto)
• Se il resto > 0, eseguo: b = r₁q₂ + r₂
• Eseguo ancora se resto > 0: r₁ = r₂q₃ + r₃
• Eseguo il procedimento fino a quando r_n = 0. Trovato quest'ultimo, il MCD sarà dato da r_n-1

Numeri primi

a e b sono detti numeri primi tra loro se MCD (a, b) = 1 e quindi ax + by = 1.

Definizione: Un numero p appartenente a Z, che non sia 0, 1, -1, si dice primo se ogni volta che divide il prodotto di due interi a, b divide almeno uno dei due:

• p | ab ma non divide a e contemporaneamente p divide b

Esempi:

• a = 2, b = 15 => ab = 30
• Con p = 6 => 6 divide 30, ma 6 non divide 2 né 15. Numero composto
• Con p = 3 => 3 divide 30, non divide 2 ma divide 15. Numero primo

Definizione: Un numero p appartenente a Z è irriducibile se è divisibile solo per ±p e ±1.

Teorema di fattorizzazione unica

Sia z appartenente a Z, diverso da 0, 1, -1. Esistono s numeri primi ≥ 1, non necessariamente distinti, tali che:

z = p₁ * p₂ * p₃ * ... * p_s

Si possono raccogliere i fattori uguali: esempio 18 = 3*3*2 = 3*2.

Calcolare numero di divisori di un numero => Guardo i numeri di fattorizzazione, prendo i loro esponenti, gli sommo uno e li moltiplico tra loro.

• Es: 18 = 3 * 2 => (2+1)*(1+1) = 3 * 2 = 6 divisori

Lezione 2: Equazioni diofantee

Rappresentazione degli interi in base n

Scelta la base n (esempio 10) e scelto il numero da scomporre (esempio 128), applichiamo l'algoritmo della divisione come segue:

• 128 : 10 = 12 (resto 8) => 8 posizione 10
• 12 : 10 = 1 (resto 2) => 2 posizione 10
• 1 : 10 = 0 (resto 1) => 1 posizione 10

Equazioni lineari diofantee

Con questo nome indichiamo equazioni del tipo ax + by = c con a, b, c appartenenti a Z, e le soluzioni sono cercate nelle coppie ordinate di numeri interi.

Condizione necessaria e sufficiente per risolubilità: ax + by = c => MCD(a, b) divide c.

Tutte le soluzioni hanno la forma:

(x₀ + b/d h, y₀ – a/d h)

Es: 9x + 15y = 27 MCD(9, 15) = 3 => 3 divide 27

x₀ = 3 e y₀ = 0

Soluzioni variano da (3 + 5h, 0 – 3h con h appartenente a Z)

Lezione 3: Polinomi reali

Polinomi del tipo => a(x) = a₀x⁰ + a₁x¹ + ... a_nxⁿ => ∑ a_ixⁱ

Grado del polinomio => massimo grado presente con coefficiente diverso da 0.

Sono polinomi se il grado di x ≥ 0 intero (quindi non razionale e negativo).

In R[x] sono definiti somma e prodotto e valgono proprietà del tutto analoghe viste in Z.

Divisibilità polinomi

Definizione: a(x) e b(x) appartenenti a R[x] con b che non sia zero. Se esiste una q(x) appartenente a R[x] tale che:

a(x) = b(x) * q(x) => b(x) | a(x)

Teorema quoziente del resto

a(x) = b(x) * q(x) + r(x) con r(x) = 0 oppure grado r(x) < grado di b(x)

Teorema di Ruffini

Siano a(x) e b(x) = x + b₀ appartenenti a R[x]. Il resto della divisione polinomiale di a(x) per b(x) è dato da: a(-b₀) => se fosse 0 a zero è divisibile, altrimenti no.

Definizione: Radice o soluzione di a(x) => a(k) = 0 con k appartenente a R.

Con il Teorema di Ruffini affermiamo che tutte le radici di un polinomio a(x) sono tutti e solo i k tali che a(x) è divisibile per (x-k).

Importante per quando si vuole scomporre un polinomio:

Definizione: Sia a(x) polinomio con grado maggiore o uguale a 1:

• a(x) è riducibile se esistono due polinomi di grado minore b(x) e c(x) tali che a(x) = b(x)c(x). (La riducibilità varia in base al campo in cui operiamo)
• In caso contrario è irriducibile. (Polinomio di grado 1 sempre irriducibile)

Lezione 4: Insiemi e relazioni binarie

Prodotto cartesiano

Siano A e B due insiemi. Il prodotto cartesiano è dato da:

A x B = {(a, b) | a appartenente A, b appartenente B} => coppie ordinate da elementi A e B.

A x B è diverso da B x A.

2^A x A con A avente n elementi. Elementi risultanti n.

Insieme delle parti

Sia S un insieme. La collezione formata da tutti e soli i suoi sottoinsiemi, compreso S completo e l'insieme vuoto, è l'insieme delle parti e si indica con P(S).

Se S ha n elementi, P(S) è costituito da 2ⁿ elementi.

Relazione tra due insiemi, introduzione e terminologie

Definizione: Siano X e Y due insiemi non vuoti. Si dice Relazione Binaria tra X e Y (o da X a Y) ogni sottoinsieme R di X x Y, cioè ogni insieme di coppie ordinate (x, y) con x appartenente a X e y appartenente a Y. Indicato con xRy oppure (x, y) appartenenti a R. (x è in relazione R con y)

Tipo di relazioni

• Banali: R = vuoto, quando nessun elemento di X è in relazione a Y
• R = X x Y, quando ciascun elemento di X è in relazione con tutti gli elementi di Y
• Universale: se Y = X la relazione X x X = X
• Identica: quando ho I = { (x, x) | x appartiene a X }
• Trasposta: relazione opposta => anziché tra X e Y, analizzo la relazione tra Y e X. Si indica con R^T = { (y, x) appartenente a Y x X | (x, y) appartiene a R}
• Complementare: Indicata con R^c è data dalla relazione X x Y, in cui vengono sottratte le relazioni di R.
• Composta: Sia R una relazione di X x Y, e sia S una relazione Y x Z. La relazione composta di X x Z cosi definita => (x, z) appartenenti a X x Z con y appartenente a (x, y) in R e (y, z) in S.

Trovare numero di relazioni (con X avente n elementi):

• Numero tutte le relazioni: 2^{n^2}
• Relazioni contenenti identiche: 2^{(n^2 + n)/2}
• Relazioni che coincidono con la trasposta: 2^{(n^2-n)/2}
• Relazioni che sono I e coincidono con trasposta: 2ⁿ

Lezione 5: Composizione e proprietà relazioni

Termini di relazioni

• R riflessiva: se I è contenuta in R, cioè per ogni x appartenente a X, (x, x) appartiene a R
• R^T è simmetrica: se R = R^T cioè (x, y) appartenenti a R => (y, x) appartiene a R
• R^T è antissimetrica: se R intersezione R^T è contenuta in I cioè (x, y) appartenenti a R e (y, x) appartenenti a R^T => x = y
• R è transitiva: se (x, y) appartenenti a R e (y, z) appartenenti a R => (x, z) appartenenti a R
• Relazione di equivalenza: R che sia riflessiva, simmetrica e transitiva
• Relazione d'ordine: R che sia riflessiva, antissimetrica e transitiva

Lezione 6: Matrici di incidenza

Matrice booleana

Matrice A in cui sono presenti solo elementi 0 e 1 e scrivo A appartenente a Mat(B) se ha m righe e n colonne.

Matrice complementare

Matrice risultante composta da tutti 1.

Verifica delle matrici

• Per verificare se una matrice A è minore rispetto a una matrice B, controllo ogni termine a_ij con il corrispettivo termine b_ij, il quale deve essere maggiore rispetto al termine A.

Matrice di incidenza

Matrice A appartenente a Mat(B) così definita: a_ij = 1 se e solo se (x_i, y_i) appartiene a R.

Matrice trasposta

Quando A appartiene a Mat di m x n se B appartiene a Mat di n x m.

Lezione 7: Applicazioni

Definizione di applicazioni

Siano X e Y insiemi non vuoti e sia p contenuto in X x Y una relazione tra X e Y. Dico che p è un'applicazione da X a Y se per ogni x appartenente a X esiste una e una sola y tale per cui:

(x, y) appartenenti a p => concetto di FUNZIONE

• x: Dominio => y è un'immagine di x mediante p
• y: Codominio

Due applicazioni coincidono se e solo se hanno uguale dominio, codominio e se hanno relazioni identiche tra X e Y.

Terminologia applicazioni

• p è suriettiva se: ogni elemento del codominio, Y, è immagine di almeno un elemento del dominio, X.
• p è iniettiva se: Ad ogni elemento del dominio, X, corrisponde un elemento distinto del codominio, Y.