Appunti Matematica discreta

1° CAP - INSIEMI

Def (Intuitiva) Collezione di oggetti detti elementi appartenenti ad un'insieme.

P = "proprietà di un insieme"

defA = { x : x ha P }

Significa che A è l'insieme che hanno da proprietà P.

A ⊆ B - "A sottoinsieme di B" ≡ Ogni elemento di A è dell'insieme B.

A ⊈ B - → A è sottoinsieme di B ma gli elementi di A non appartengono all'insieme B.

A = B quando A ⊆ B e B ⊆ A

A ∪ B def = { x : x ∈ A ∨ x ∈ B }

A ∩ B def = { x ∈ A : x ∈ B }

Proprietà

Distributiva

A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)

Associativa

(A ∪ B) ∪ C = A ∪ (B ∪ C)

(A ∩ B) ∩ C = A ∩ (B ∩ C)

P_o^def = { A : A ≠ A + A }

Questo: R ∈ P_o

se R ≠ R → P ≠ P ∈ A assurdo

se R = R → P ∈ R assurdo

U = INSIEME UNIVERSO

Tutti gli insiemi sono sottoinsiemi.

A'^def = { x ∈ U : x ∉ A }

Insieme complementare di A

LEGGI DI DE MORGAN

(A ∪ B)' = (A') ∩ (B')

(A ∩ B)' = (A') ∪ (B')

A \ B^def = { x ∈ A : x ∉ B }

DIFFERENZA di A e B

A Δ B^def = (A \ B) ∪ (B \ A)

DIFF. SIMMETRICA

PRODOTTO CARTESIANO

A × B^def = { (a, b) : a ∈ A, b ∈ B }

tutte le possibili combinazioni

esempio

[1] × [3] = { (1,1), (1,2), (1,3), (2,1), (2,2), (2,3) }

A² = A × A    A³ = A × A × A

Gruppo Simmetrico

Sn := {f : [n] -> [n] : f biettiva}

Ge: elementi sn dati permutazione

Esempio

S3 := {f : [3] -> [3] : f biettiva}

S3 = {123, 132, 213, 231, 312, 321}

se f, g ∈ Sn, f: a1 ... an e g: b1 ... bn allora

f∘g = (a1 aσ1, aσ2 ... aσn)

Esempio

n = 7, f = 7152436, g = 2734565

f∘g = 1652739

g∘f = 5217436

sia f ∈ Sn, f = a1 ... an, allora:

f^-1 = b1 ... bn dove b_i è la posizione di i in f

Esempio

n = 7, f = 7152436

f^-1 = 2653471

LEGGE DISTRIBUTIVA E DI DE MORGAN

(due leggi insiemistiche, valgono anche x le proposizioni)

DE MORGAN

¬(P∧Q) = (¬P)∨(¬Q)

¬(P∨Q) = (¬P)∧(¬Q)

DISTRIBUTIVA

P∧(Q∨R) = (P∧Q) ∨ (P∧R)

P∨(Q∧R) = (P∨Q) ∧ (P∨R)

LOGICA E PROGRAMMAZIONE

do … per rendere un programma più semplice e più veloce

esempio: IF (x>0 || (x100))

Il codice si scompone in

A∨(¬B∧B)

Si può semplificare in

A∨B

Infatti, applicando le proprietà:

A∨(¬B∧B) = (A∨¬B) ∧ (A∨B) = A∨B

Quindi il codice si può scrivere

IF (x>0 || y>100)

a e b sono coprimi se c|a e c|b -> c=1n si dice perfetto se è uguale alla somma deisuoi divisori <n6 è perfetto (1+2+3)Teorema: ci sono infiniti numeri primiFunzione π(n): = |{m ∈ P: m ≤ n, m° primo}|

Teorema dei numeri primi

limn -> ∞

^π(n) = 1_(n/ln⁡(n))N.B. π(n) è molto vicino a n°quindi l'andamento π(n)verso l'∞ è molto caotico

Algoritmo euclideo (procedura x calcolare MCD)

Massimo comune divisore tra a e bdefMCD(a, b) := max { c ∈ P : c|a e c|b }MCD è il numero più grande che puòdividere sia a che b

Come calcolarlo

Proprietà: a,b ∈ P , a > b : ∃ q, r ∈ Zcosì chea = b·q + r e 0 ≤ r < b

Teorema fondamentale dell'aritmetica (detto anche unico)

Sia n ∈ ℕ, n≥2.

Teorema: n è prodotto di numeri primi in uno ed un solo modo, a parte l'ordine dei fattori.

Equazione Diofantee lineari

Teorema 1: Siano a, b, n ∈ ℙ. Esistono x, y ∈ ℤ tali che ax + by = n se e solo se (a,b)n

Teorema 2: Siano a, b, n ∈ ℙ tale che (a,b)n. Allora tutte le soluzioni x, y ∈ ℤ di ax + by = n sono nella forma:

Classi di Resto

Def: Numeri che hanno lo stesso colore.

Relazione di congruenza mod n:

a ≡ b (mod n) ⟺ n|(b-a)

Significa che a e b divisi per n danno lo stesso resto r

Sia n ∈ ℕ

Piccolo Teorema di Fermat

Siano k, p ∈ N, p primo, tali che

p ∤ k

Allora

k^p-1 ≡ 1_p

Codice RSA

da: spedire un messaggio da A a B in modo che solo B possa decifrarlo

Tre Fasi:

• Preparazione:
• B sceglie p, q tali che
• p > 0, q > 0
• p ≠ q
• p e q primi
• B calcola n = p⋅q
• Trova e ∈ P tale che
• MCD (φ_n, (p-1)(q-1)) = 1
• Calcola l'inverso moltiplicativo
• [d]_(p-1)(q-1) di
• [e]_(p-1)(q-1)
• Vengono Pubblicati
• n, e
• Soggetti
• p, q, d

Proprietà (Coefficiente binomiale)

Sia n ∈ ℕ, allųra

(1+x)ⁿ = ⁿ∑_k=0 (ⁿC_k) x^k

Proprietà

Siano n, k ∈ ℕ, 0 ≤ k ≤ n

allųra

(^n-1 C_k) = (ⁿC_k)

Principio di inclusione - esclusione

Se A e B sono due insiemi finiti, allora

|A ∪ B| = |A| + |B| - |A ∩ B|

Nel caso in cui abbiamo A, B, C:

|A ∪ B ∪ C| = |A ∪ B| + |C| - |(A ∪ B) ∩ C|

= |A| + |B| - |A ∩ B| + |C| - |(A ∩ B) ∩ C|

= |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C|

+ |A ∩ B ∩ C|

RISCORSIONI LINEARI A COEFFICIENTI COSTANTI

TEO FONDAMENTALE DELL'ALGEBRA

Siano a_n,...,a₀ ∈ ℝ

Esisto x₁,...,x_n ∈ ℂ e d₁,...,d_k ∈ ℕ

Tale che

a_nxⁿ + a_n-1x^n-1 + ... + a₀ = a_n(x-x₁)^d₁(x-x_k)^d_k

d₁,...,d_k = RADICI DEL POLINOMIO

d₁,...,d_k = MOLTEPLICITA` DI d_i

PROPRIETA`

Se P(x)∈ℝ[x] e a∈ℂ, P(x):

P(a)=0 ⟺ (x-a) | P(x)

Risoluzione di un polinomio con Ruffini (2^a parte)

Esempio

x²-3x-4

P(-1) = -1 + 3 -4 = 0

(x+1) | P(-1)

d=0

-a-b

g=

g=

9a+8b-3(3a-3b)=14

d=0

g=3-a-b

b=

12a+6(

d=0

a=

12a+=11 => a=

Quindi

=^nʌ2|

| =

|

n ⦁

=

o Quanto è grande

n!

analogo procedimento - prop dei logaritmi

ln(n!) = ∑_i=1ⁿ ln(i)

Quindi

n! = exp(∫₁ⁿ ln(x) dx)

{ esponenziale

stimiamo ∑_i=1ⁿ ln(i) in quanto la funzione è monotona

e crescente

Sappiamo che

ln(x) + ∫_xⁿ ln(x) dx ≤ ∑_i=1ⁿ ln(i) ≤ ln(n) + ∫₁ⁿ ln(x) dx

VFC IP Ma

∫₁ⁿ ln(x) dx = [ x ln(x) - x ]₁ⁿ = n ln(n) - n + 1

Quindi

n ln(n) - n + 1 ≤ ∑_i=1ⁿ ln(i) ≤ ln(n) + n ln(n) - n + 1

n ln(n) - n + 1 ≤ ln(n!) ≤ ln(n) + n ln(n) - n + 1