Geometria e Combinatoria - modulo 1

Geometria e Combinatoria

I^o MODULO

Dalle lezioni della professoressa Francesca Merola presso: il Dipartimento di Ingegneria dell'Università degli Studi Roma Tre

Relatore: Shoel Canulli                                           Anno: 2020

Geometria e Combinatoria

I^o Modulo

Dalle lezioni della professoressa Francesca Merola

presso:

il Dipartimento di Ingegneria dell'Università degli Studi Roma Tre

Relatore: Jhoel Canulli

Anno: 2020

Lezione 1 - 1/10/20

Teoria degli insiemi:

Insieme

Collezione non necessariamente ordinata, di oggetti (o elementi) distinti.

Esempio: A = { 2 , 4 , 6 , 8 } = { x ∈ N : n ∈ N, 2 ≤ x ≤ 8 }

Esempi di insiemi importanti: N, Z, Q, R, C

Sottoinsieme

A è sottoinsieme di B se B contiene A. Si denota A ⊆ B. Quindi: se x ∈ A e x ∈ B allora B contiene A

Sottoinsieme proprio (⊂)

Dati A ⊂ B, se y ∈ B allora y può ∉ A

Sottoinsieme improprio (⊆)

Dati A ⊆ B, se y ∈ B allora y ∈ A

Da ciò si evince che N ⊂ Z ⊂ Q ⊂ R ⊂ C

Operazioni fra insiemi

Unione ( ∪ )

Dati 2 insiemi A e B, (A ∪ B) è l'insieme degli elementi che appartengono o ad A o a B o ad entrambi.

(A ∪ B): { x | x ∈ A ∨ x ∈ B }

Intersezione ( ∩ )

Dati 2 insiemi A e B, (A ∩ B) è l'insieme degli elementi che appartengono sia ad A che a B.

(A ∩ B): { x | x ∈ A ∧ x ∈ B }

Insiemi Disgiunti

Se (A ∩ B) = ∅ allora A e B si dicono Disgiunti.

Cardinalità

Dato l'insieme A, la cardinalità di A, cioè |A|, è il numero degli elementi contenuti in A.

Insieme vuoto

Un insieme privo di elementi è un insieme vuoto, si denota con ∅ o {}.

La Cardinalità di un insieme vuoto è 0 , |∅| = 0   A = ∅:

La Cardinalità di un insieme che contiene solo un insieme vuoto è 1 , A₁ = {∅} :

Quando A = ∅ e A₁ = {∅} sono diverse, perchè |A| = 0 e |A₁| = 1.

Proprietà degli insiemi:

• Commutativa:

A ∪ B = B ∪ A

A ∩ B = B ∩ A

• Associativa

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

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

Non è vera,

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

Perché:

(A ∪ B) ∩ C

è invece

A ∪ (B ∩ C)

Da ciò, però, evinciamo che generalmente è sempre vera.

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

Dimostrazione formale del dato sull'insieme:

Prendiamo un esempio x ∈ (A ∪ B) ∩ C , ciò implica che

x ∈ C ∈ (x ∈ A ∪ B ), cioè (x ∈ A ∈ x ∈ B) ∈ x ∈ A , B) (x ∈ x ∈ C).

Analizziamo le casistiche

1°) x ∈ A avremo x ∈ (A ∩ C) ∈ quindi che x ∈ A ∩ (B ∩ C)

2°) x ∈ x ∈ B avremo x ∈ (B ∩ × ∩ C) da cui x ∈ A ∩ (B ∩ C)

A ∪ (B ∩ C) : (A ∩ B) ∪ (A ∩ C)

A ∩ (B ∪ C) : (A ∩ B) ∪ (A ∩ C)

I° Legge:

u (A ∩ B) = u (A) ∪ u (B)

Ossia:

¬ (A ∩ B) ≅ ¬ A ∪ ¬ B ≅ (A ∩ B)^c ≅ u (A ∩ B)

è uguale a:

¬ (A) ∪ ¬ (B) ≅ ¬ A ∪ B^{¬ A ∪ B} ≅ u (A) ∪ u (B)

U : Insieme Universo

U Insieme Universo

L'legge:

u(A ∪ B) ≅ u(A) ∩ u(B)

Ossia:

¬(A ∪ B) ≅ A ∪ B ≅ (A ∪ B)^c ≅ u(A ∪ B)

∪ insieme Universo

è uguale a:

¬(A) ∩ ¬(B) ≅ ¬A ∩ ¬B ≅ Â ∩ B̂ ≅ u(A) ∩ u(B)

Differenza fra insiemi.

B \ A (o B - A) ≜ {x ∈ B : x ∉ A}

Differenza Simmetrica.

A Δ B ha 2 definizioni... entrambe vere:

1. A Δ B ≜ (A \ B) ∪ (B \ A)
2. A Δ B ≜ (A ∪ B) \ (A ∩ B)

Dimostrazione dell'equivalenza delle 2 definizioni.

Definizione 1

A Δ B ≜ (A \ B) ∪ (B \ A)

(A \ B) ∪ (B \ A) ≜ A Δ B

Definizione 2

A Δ B ≜ (A ∪ B) \ (A ∩ B)

(A ∪ B) \ (A ∩ B) ≜ A Δ B

Quindi:

(A \ B) ∪ (B \ A) ≅ (A ∪ B) \ (A ∩ B) ≜ A Δ B

Lezione 2 - 2/10/20

Prodotto Cartesiano

Dati 2 insiemi, il prodotto Cartesiano (A x B) e' l'insieme delle coppie ordinate {a, b} ⨯ a ∈ A e b ∈ B &.

Essendo coppie ordinate, non sono commutative, quindi generalmente A x B ≠ B x A

Dimostrazione di non commutativita':

A = {1, 2}₁; B = {a b, c}₃

A x B = {a₁, a₁b, c₃} ≠ B x A = {a₁, a₂, b₁, b₂, c₁, c₂}

Complemento/Complementare:

Il complementare di A rispetto a U e' la differenza U - A, cioe', l'insieme degli elementi in U che non appartengono ad A.

Si denota con C_A (o C U A)

Insieme delle parti:

L'insieme delle parti di A = P (A) è { B: B ⊆ A^3 }

cioe', e' l'insieme di tutti i sottoinsieme di A.

Proposizione 1: |P(A)|= 2ⁿ n=|A|

Di