Fundamentele algebrice ale informaticii

pentru anul I Informatica ( zi + ID) incepind cu anul universitar 2005/2006

CURSUL nr. 1

- 1. Multimi. Operatii cu multimi

In cadrul acestei lucrari vom privi multimile in sensul in care ele au fost privite de catre

GEORG CANTOR - primul matematician care a initiat studiul lor sistematic (punct de vedere

cunoscut in matematica sub numele de teoria naiva a multimilor).

Definitia1.1 Daca A si B sunt doua multimi, vom spune ca A este inclusa in B (sau ca A

este submultime a lui B) daca elementele lui A sunt si elemente ale lui B; in acest caz vom scrie

A- B iar in caz contrar A- B.

Avem deci : A- B- pentru orice xa - x- B

A- B- exista xa a.i. x- B.

Vom spune despre multimile A si B ca sunt egale daca oricare ar fi x, xa- x- B. Deci,

A=Ba- B si Ba.

Vom spune ca A este inclusa strict in B si vom scrie A- B daca A- B si A- B.

Se accepta existenta unei multimi ce nu contine nici un element care se noteaza prin - si

poarta numele de multimea vida. Se observa ca pentru orice multime A, - a (deoarece in caz

contrar ar trebui sa existe x- - a.i. xa - absurd.!).

O multime diferita de multimea vida se zice nevida.

Pentru o multime T, vom nota prin P(T) multimea submultimilor sale (evident - , T- P(T) ).

Urmatorul rezultat este imediat :

Daca T este o multime oarecare iar A, B, C- P(T), atunci :

(i) Aa

(ii) Daca A- B si Ba, atunci A=B

(iii) Daca A- B si B- C, atunci A- C.

In cadrul acestei lucrari vom utiliza deseori notiunea de familie de elemente a unei multimi

indexata de o multime nevida de indici I (prin aceasta intelegand o functie definita pe multimea I cu

valori in multimea respectiva).

Astfel, vom scrie de exemplu (xi)i- I pentru a desemna o familie de elemente ale unei multimi

sau (Ai) i- I pentru a desemna o familie de multimi indexata de multimea I. Pentru o multime T si A,

B- P(T) definim :

A- B={x- T - xa si x- B}

A- B={x- T - xa sau x- B}

A- B={x- T - xa si x- B}

A- B=(A- B)- (Ba).

Daca A- B=- , multimile A si B se zic disjuncte.

Operatiile - , - , - si - poarta numele de intersectie, reuniune, diferenta si diferenta

simetrica.

In particular, Ta se noteaza prin - T (A) (sau - (A) daca nu este pericol de confuzie) si poarta

numele de complementara lui A in T.

2

2

In mod evident, pentru A, B- P(T) avem:

A- B=A- - T (B)

A- B=(A- B)- (A- B)=(A- - T (B))- (- T (A)- B)

- T (- )=T, - T(T)=-

A- - T (A)=T, A- - T (A)=- iar - T (- T (A))=A.

De asemenea, pentru x- T avem:

xa- B - xa sau x- B

xa- B - xa si x- B

xa- B - xa sau x- B

xa- B - (xa si x- B) sau (xa si x- B)

x- - T (A)- xa.

Din cele de mai inainte deducem imediat ca daca A, B- P(T), atunci:

- T (A- B)=- T(A)- - T (B) si - T (A- B)=- T (A)- - T (B).

Aceste ultime doua egalitati sunt cunoscute sub numele de relatiile lui De Morgan.

Pentru o familie nevida (Ai )i- I de submultimi ale lui T definim:

II

i

i A

I

={x- T - xai pentru orice i- I} si

UI

i

i A

I

={x- T - exista i- I a.i. xai }.

Astfel, relatiile lui De Morgan sunt adevarate intr-un context mai general:

Daca (Ai) i- I este o familie de submultimi ale multimii T, atunci:

( )i

i I

T

i I

T i C I A UC A

I I

= ??

o

ce

ae si ( )i

i I

T

i I

T i C U A IC A

I I

= ??

o

ce

ae

Urmatorul rezultat este imediat:

Propozitia 1.2. Daca T o multime iar A, B, C- P(T), atunci:

(i) A- (B- C)=(A- B)- C si A- (B- C)=(A- B)- C

(ii) A- B=Ba si A- B=Ba

(iii) A- T=A si A- - =A

(iv) Aa=A si Aa=A.

Observatia 1.3. 1. Din (i) deducem ca operatiile - si - sunt asociative, din (ii) deducem ca

ambele sunt comutative, din (iii) deducem ca T si - sunt elementele neutre pentru - si respectiv

pentru - , iar din (iv) deducem ca - si - sunt operatii idempotente pe P(T).

2. Prin dubla incluziune se probeaza imdiat ca pentru oricare A, B, C- P(T) avem:

A- (B- C)=(A- B)- (A- C) si

A- (B- C)=(A- B)- (A- C) ,

adica operatiile de intersectie si reuniune sunt distributive una fata de cealalta.

Propozitia1.4. Daca A, B, C- P(T), atunci:

(i) A- (B- C)=(A- B)- C

(ii) A- B=Ba

(iii) A- - =A iar A a=-

(iv) A- (B- C)=(A- B)- (A- C).