Matematica Discreta MDL

Insiemi

Insieme: collezione di oggetti (= elementi) distinti (= le ripetizioni di oggetti uguali non contano).

Ben definito: non ci sono dubbi sul fatto che un elemento appartenga o meno ad un insieme.

a ∈ A → appartiene. a ∉ A → non appartiene.

Insiemi numerici

IN _{Numeri naturali} = {0, 1, 2, 3, ...}

Z _Interi = {..., -2, -1, 0, 1, 2, ...}

Q _Razionali = {a/b | a ∈ Z, b ∈ Z, b ≠ 0}

IR _Reali = p² ≤ 2, √2 ∈ N

C _Complessi = {a + bi, a, b ∈ R, i² = -1}

Simboli

∃ esiste. ⊥ esiste ed È unico. ⊤ per ogni.

¬ negazione. ⇒ implica. ⇔ se e solo se.

|A| cardinalità: numero di elementi dell'insieme A.

B ⊂ A: B È incluso in A, B È sottoinsieme di A strettamente.

A = B ⊆ B ⊇ A.

A ∩ B = {c : c ∈ A ∧ c ∈ B} _Intersezione "e", simultaneamente.

A ∪ B = {c : c ∈ A ∨ c ∈ B} _Unione "oppure", in A, in B o in entrambi.

Ø _{Insieme vuoto} privo di elementi.

A ∩ B = Ø _{Insiemi disgiunti}.

C(A) = {b ∈ B : b ∉ A} _{Complementare di A in B}.

B ∖ A = {b ∈ B : b ∉ A} = C(A).

Esercizi

A = {2m | m ∈ IN}, B = {5m | m ∈ IN}.

A ∪ B = {c : c = 2m con m ∈ IN ∨ c = 5m con m ∈ IN} = {c : 10m | m ∈ IN}.

A ∩ B = {c : c = 2m con m ∈ IN ∧ c = 5m con m ∈ IN} = {c : c = 5m con m ∈ IN}.

C = {c : 5m con m ∈ IN ∧ c = 5m con m ∈ IN} = {c : c = 10m | m ∈ IN}.

B ∖ A = {c : c = 5m con m ∉ IN ∧ c = 2m con m ∉ IN} = {c : c = 5m < 10m ∈ IN}.

A ∖ B = {c : c = 2m con m ∉ IN ∧ c ≠ 5m con m ∈ IN}.

Insiemi

Insieme = collezione di oggetti (=elementi) distinti (= le ripetizioni di oggetti uguali non contano).

Ben definito = non ci sono dubbi sul fatto che un elemento appartenga o meno ad un insieme.

∈ appartiene.

∉ non appartiene.

Insiemi numerici

ℕ numeri naturali = {0,1,2,3,...}

ℤ interi = {0,±1,±2,...}

ℚ razionali = {a/b | a∈ℤ, b∈ℤ, b≠0}

ℝ reali = {...√2√n...}

Iℝ sono il completamento della retta dei numeri razionali.

ℂ complessi = {a+bi | a,b∈ℝ, i²=-1}

Simboli

∃ esiste.

∃! esiste ed È unico.

∀ per ogni.

¬ negazione.

→ implica.

⟺ se e solo se.

|A| cardinalità : numero di elementi dell'insieme A.

B⊂A: B È incluso in A, B È sottoinsieme di A strettamente.

A=B ⟺ A⊂B ∧ B⊂A.

A∩B = {c ∈ A ∧ c ∈ B} intersezione "e" simultaneamente.

A∪B = {c ∈ A ∨ c ∈ B} unione "opp" in A, in B o in entrambi.

∅ insieme vuoto privo di elementi.

A∩B= ∅ insiemi disgiunti.

C(A) = {b∈B : b ∉ A} complementare di A in B.

B\A = {b∈B : b ∉ A} = C_B(A).

Esercizi

A = {2m | m ∈ ℕ}, B = {5m | m ∈ ℕ}.

A∪B = {c : c=2m con m ∈ ℕ ∨ c=5m con m ∈ ℕ } = { 0 } ∪ {m | m ∈ ℕ}.

A∩B = {c : c=2m con m ∈ ℕ ∧ c=5m con m ∈ ℕ } = { c : c=10m | m ∈ ℕ}.

B\A = {c : c=5m con m ∈ ℕ ∧ c≠2m con m ∈ ℕ} = { c : c=5m con m ∈ ℕ}.

A\B = {c : c=2m con m ∈ ℕ ∧ c≠5m con m ∈ ℕ} = { c : c=2m con m ∈ ℕ}.

Insieme delle parti

Insieme cui elementi sono tutti i sottoinsiemi di X.

P(X)={∅,...,X} NB: sempre presenti quindi P(X)≠∅.

|X|=m⇒|P(X)|=2^m.

Proprietà di ∩ e ∪

A=A∪B.

B=A∪B.

A∩B=A.

B∩A=B.

A∪B=A ⟺ B⊆A.

Pr. commutativa: A∩B=B∩A e A∪B=B∪A.

Pr. associativa: ∩ e ∪ sono definite solo per 2 insiemi.

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

Distributività di ∩ rispetto ad ∪.

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

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

Leggi di De Morgan

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

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

Intervalli

R²={(x,y)∈ℝ: x<y<y}₂} → intervallo aperto.

R={[x,y]=x∈ℝ: x<x<y}^x,y} → chiuso.

(x,y) o [x,y) né aperti né chiusi.

[a,+∞)={[x∈ℝ:x>a]} → intervallo illimitati.

(-∞,a)={[x∈ℝ:x<a]} → intervallo illimitati.

Ricoprimento di X

Famiglia di sottoinsiemi A₁,...,A_m di X per cui ∪A_i=X.

Partizione di X

Famiglia di sottoinsiemi A₁,...,A_m di X tali che:

• A₁,...,A_m sono un ricoprimento di X.
• A≠∅ ∀i∈{1,...,m} → non vuoti.
• A_i∩A_j = ∅ ∀i≠j{1,...,m} ⤳⤳ → sottoinsiemi a due a due disgiunti.

(Simile ad un puzzle)

Quoziente di X secondo la partizione A₁