Matematica discreta - Insiemi

Matematica discreta - Corso C

(Primo corso di algebra) (Discreta = non continua) ⇩ insieme non continui

Teoria ingenua degli insiemi

Teoria ingenua (intuitiva) degli insiemi

Insieme: collezioni di oggetti (elementi)

X dichiara un insieme:

• Elenco i suoi elementi (piccolo)
• Attraverso gli insiemi numerici

N = {0, 1, 2, 3, …} (naturali)

Z = {…, 0, -1, -2, -3, …} (interi)

Q = {a/b | a, b ∈ Z, b ≠ 0} (razionali)

R = Q a cui aggiungo gli irraz. (es: √2 e π) (reali)

C = {a + bi | a, b ∈ R} (i² = -1) (complessi)

⇧ unità immaginaria

Espressione dei numeri

Per esprimere numeri voglio considerare:

• Numeri pari - ambiguo, non preciso ⇩ {x ∈ Z (N) | x = 2·ℓ con ℓ ∈ Z (N)}
• Numeri dispari ⇔ x ∈ Z | 2x + 1 ⇩
• Numeri divisi 3 ⇔ {x ∈ Z | x = 3ℓ con ℓ ∈ Z}
• N° che divisi x 11, R = 0 3 ⇔ {x ∈ Z | x = 11ℓ + 7 con ℓ ∈ Z} ⇐ resto

Matematica discreta - Corso C

(Primo corso di algebra) (Discreta = non continua) → insiemi non continui

Teoria ingenua degli insiemi

Teoria ingenua (intuitiva) degli insiemi

Insieme: collezioni di oggetti (elementi)

Per dichiarare un insieme:

• Elenco i suoi elementi (piccolo)
• Attraverso gli insiemi numerici

N = {0, 1, 2, 3, ...} (Numeri naturali)

Z = {..., -1, 0, 1, 2, 3, ...} (Interi)

Q = {a/b | a, b ∈ Z, b≠0} (Razionali)

R = Q a cui aggiungo gli irraz. (Es: √2 e π) (Reali)

C = {a+bi | a, b ∈ R} (i²= -1) (Complessi) → Unità immaginaria

Espressione dei numeri

Per esprimere numeri voglio considerare

• [Numeri pari] = ambiguo, non preciso {x ∈ Z\N | x = 2·k con k ∈ Z\N}
• [Numeri dispari] → {x ∈ Z\N | 2x + 1}
• [Numeri divisi.3 i 3] → {x ∈ Z | x = 3·e con e ∈ Z} (Multiplo di 3)
• {n.° che divisi x 11, R=0 3} = {x ∈ Z\N | x = 11e+7 con e ∈ Z\N} → Resto

Uguaglianza tra insiemi e simboli

Quando 2 insiemi sono uguali? (Principio di estensionalità)

A e B sono uguali se: x ∈ A ⇔ x ∈ B

Simboli:

• ∃: "Esiste" (+ di 1)
• ∃!: "Esiste ed è unico" (solo 1)
• ∄: "Non esiste"
• ∀: "Per ogni", "Qualsiasi" (Tutti)
• ⇒: "Implica" (ciò che è scritto a sinistra fa accadere allora la cosa di destra)
• ⇔: "Se e solo se" (entrambe le parti sono equivalenti)
• |A|: "Cardinalità" (quanti elementi contiene A)
• B ⊂ A: "Incluso" (⊚ A) (inclusione stretta)

Varianti:

• ⊆: "Incluso o uguale"
• ⊊: "Incluso stretto" (senza confusione)

Esempio di inclusione

Es:

A = {-2, 0, 6, 18.000}

B = {x ∈ ℤ | x = 2ℓ con ℓ ∈ ℤ}

C = ℕ

A ⊂ B; A ⊄ C; B ⊄ C

Doppia inclusione:

A = {x ∈ ℤ | x² - 3x + 2 = 0} = 3 ➔

B = {1, 2, 3}

Come manipolare 2 insiemi

Come manipolare 2 insiemi:

A ∩ B: "intersezione" = {c | c ∈ A ∧ c ∈ B}

A ∪ B: "unione" = {c | c ∈ A ∨ c ∈ B}

A ∪ ∅ = A A ∩ ∅ = ∅ ∅ ⊆ C A, ∀ A insieme

Dimostro che ∀ A ins., ∀ B ins.:

A ∪ B ⊇ B: Tesi B ⊆ A ∪ B

∀ x ∈ B => x ∈ A ∪ B bisogna riempire i punti

A ∪ B = {c | c ∈ A ∨ c ∈ B}

quindi se x ∈ B rientra in "c ∈ A ∨ c ∈ B"

⇒ x ∈ A ∪ B

Es.

A ∪ B ⊄ A se è vera la delo dimos se è falsa bisogna esibire 1 controesempio

A = {x ∈ ℕ | x = 2e ∈ ℕ}

B = {x ∈ ℕ | x = 2e+1 ∈ ℕ}

A ∪ B = ℕ ⊈ A

(infinito)

Unioni e intersezioni arbitrarie

Le ∪ e ∩ si possono fare su un numero arbitrario di insiemi:

Se A₁, A₂, A₃, ... insiemi

• ∞i=1: ∩ A_i = A₁ ∩ A₂ ∩ A₃ ∩ ...
• ∞i=1: ∪ A_i = A₁ ∪ A₂ ∪ A₃ ∪ ...

[sommatona con ∪ ∩]

A ∩ B = ∅ "Disgiunti"

C_B(A) = {b ∈ B | b ∉ A} "Complementare"

Esempio:

A = {1,2,3}, B = ℕ

C_B(A) = {x ∈ ℕ | x = 0,5,...}

C_A(B) = ∅

B \ A: "Insieme differenza" (È uguale al C)

Si legge "B meno A"

{b ∈ B | b ∉ A} = C_B(A)

Proprietà di intersezione e unione

Proprietà di ∩ e ∪

• A ⊆ A ∪ B; B ⊆ A ∪ B
• A ∩ B ⊆ A; A ∪ B ⊆ B
• A ∪ B = A ⇔ B ⊆ A

Dimostrazione: "⇒" Ipotesi: A ∪ B = A

Tesi: B ⊆ A

A ∪ B = A ⇒ {x | x ∈ A ∪ x ∈ B}:

{x | x ∈ A} ∀x ∈ B, x ∈ A ⇒ B ⊆ A

"⇐" Ipotesi: B ⊆ A

Tesi: A ∪ B = A

A ∪ B = A : A ∪ B ⊆ A (se sono vere, sono:)

A ⊆ A ∪ B ⇒ Sempre vera

{x | x ∈ A ∪ x ∈ B} = {x | x ∈ A ∧ B ⊆ A}

4) A∩B = B∩A → "Commutativa"

A∪B = B∪A

5) (A∩B)∩C = A∩(B∩C) → "Associatività"

(A∪B)∪C = A∪(B∪C) (Si possono unire/intersecare in qualunque ordine)

6) A∩(B∪C) = (A∩B)∪(A∩C) → "Distribuitività"

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

Leggi di De Morgan

Leggi di De Morgan

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

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

Prodotto cartesiano di insiemi

Prodotto cartesiano di insiemi

A x B := {(a,b) | a∈A, b∈B} ↳ coppia ordinata (da non scambiare)

Es:

A₁, A₂,..., Aₙ

A₁ x A₂ x ... x Aₙ = {(a₁,...,aₙ) | aᵢ ∈ Aᵢ} ₙ-uple

Per sapere |A¹ x B| si fa (|A| · |B|)

Se: A = A x A x ... x Aₙ sono =, allora si scrive Aⁿ

Relazione n-aria

Relazione n-aria

R ⊂ A₁ x ... x Aₙ

n = 2 relazione binaria

n = 3 "ternaria"

Nelle relazioni binarie:

R ⊆ A×B, se (a, b) ∈ R si può scrivere “aRb”

Partizione

Partizione

X insieme =

Una partizione di X è una famiglia di sottoinsiemi con 3 proprietà:

• A_i ≠ ∅ non vuoti
• A_i ∩ A_j = ∅ nulla in comune tra di loro (disgiunti)
• A₁ ∪ ... ∪ A_n = X tutti uniti fanno X (⋃_i=1ⁿ A_i = X)

Ricomprimento

Ricomprimento

Un ricoprimento di X è una famiglia di sottoinsiemi A₁, ..., A_n x cui vale la 3 della partizione

P(x): insieme degli elementi di X

Es: x = {1, 2, 3}

P(x) = {∅, {3}, {2, 3} {3}, {2, 3}, {1, 3}, {1, 2, 3}, X}

{1, 3} ∈ P(x) perché è un elemento di P(x)

{3} ∈ x perché è un sottoinsieme di x

{{1, 3}} ⊆ P(x)

• P(A) × P(B) = prima calcolo P(A) e P(B) e poi faccio il prod. cart.
• # da P(A×B) ha molti meno elem.
• * P(x) = 2ⁿ dove |x| = n → come si dimostra?

Assiomi di Peano

Assiomi di Peano

(Regole)

L'ins. di ℕ è caratterizzato dai seguenti assiomi:

• 0 ∈ ℕ
• ∀n ∈ ℕ, ∃m successore di n : s(n) ∈ ℕ
• ∀n, m ∈ ℕ, m ≠ n, s(m) ≠ s(n)
• ∀n ∈ ℕ, 0 ≠ s(n)
• Se U (ins.) ⊆ ℕ | 0 ∈ U ∧ ∀n ∈ U, s(n) ∈ U allora U = ℕ

Dimostrazione per induzione

Dimostrazione x induzione*

• P(0) vera Passo Base → (come se salissi una scala)
• ∀n ∈ ℕ, se P(n) è vera, allora P(n+1) è vera
• → P(n) vale ∀n ∈ ℕ Passo induttivo

Ricorsione

Ricorsione (collegato alla dim. induzione)

Algoritmo che durante la sua esecuzione richiama una sua nuova esecuzione su dati + semplici

Fattoriale

Fattoriale

n! : il prodotto di tutti i no. n da 1 a n

Es: n! = 1·2·...·(n-1)·n

3! = 3 (1·2·3)

5! = 120 (24·5)

4! = 24 (1·2·3·4)