1

1

Fundamentele algebrice ale informaticii

pentru anul I Informatic ( zi + ID) ncepnd cu anul universitar 2005/2006 CURSUL nr. 1

1. Mulimi. Operaii cu mulimi

n cadrul acestei lucrri vom privi mulimile n sensul n care ele au fost privite de ctre

GEORG CANTOR - primul matematician care a iniiat studiul lor sistematic (punct de vedere cunoscut n matematic sub numele de teoria naiv a mulimilor).

Definiia1.1.. Dac A i B sunt dou mulimi, vom spune c A este inclus n B (sau c A

este submulime a lui B) dac elementele lui A sunt i elemente ale lui B; n acest caz vom scrie AB iar n caz contrar AB.

Avem deci : AB pentru orice xA xB AB exist xA a.. xB.

Vom spune despre mulimile A i B c sunt egale dac oricare ar fi x, xA xB. Deci, A=BAB i BA.

Vom spune c A este inclus strict n B i vom scrie AB dac AB i AB. Se accept existena unei mulimi ce nu conine nici un element care se noteaz prin i

poart numele de mulimea vid. Se observ c pentru orice mulime A, A (deoarece n caz contrar ar trebui s existe x a.. xA absurd.!).

O mulime diferit de mulimea vid se zice nevid. Pentru o mulime T, vom nota prin P(T) mulimea submulimilor sale (evident , TP(T) ). Urmtorul rezultat este imediat : Dac T este o mulime oarecare iar A, B, CP(T), atunci : (i) AA (ii) Dac AB i BA, atunci A=B (iii) Dac AB i BC, atunci AC. n cadrul acestei lucrri vom utiliza deseori noiunea de familie de elemente a unei mulimi

indexat de o mulime nevid de indici I (prin aceasta nelegnd o funcie definit pe mulimea I cu valori n mulimea respectiv).

Astfel, vom scrie de exemplu (xi)iI pentru a desemna o familie de elemente ale unei mulimi sau (Ai) iI pentru a desemna o familie de mulimi indexat de mulimea I. Pentru o mulime T i A, BP(T) definim : AB={xT | xA i xB}

AB={xT | xA sau xB} A\B={xT | xA i xB} AB=(A\B)(B\A).

Dac AB=, mulimile A i B se zic disjuncte. Operaiile , , \ i poart numele de intersecie, reuniune, diferen i diferen

simetric. n particular, T\A se noteaz prin T (A) (sau (A) dac nu este pericol de confuzie) i poart

numele de complementara lui A n T.

2

2

n mod evident, pentru A, BP(T) avem: A\B=AT (B)

AB=(AB)\(AB)=(AT (B))(T (A)B) T ()=T, T(T)= AT (A)=T, AT (A)= iar T (T (A))=A.

De asemenea, pentru xT avem: xAB xA sau xB xAB xA i xB xA\B xA sau xB xAB (xA i xB) sau (xA i xB) xT (A) xA.

Din cele de mai nainte deducem imediat c dac A, BP(T), atunci: T (AB)=T(A)T (B) i T (AB)=T (A)T (B).

Aceste ultime dou egaliti sunt cunoscute sub numele de relaiile lui De Morgan. Pentru o familie nevid (Ai )iI de submulimi ale lui T definim:

IIi

iA

={xT | xAi pentru orice iI} i

UIi

iA

={xT | exist iI a.. xAi }.

Astfel, relaiile lui De Morgan sunt adevrate ntr-un context mai general: Dac (Ai) iI este o familie de submulimi ale mulimii T, atunci:

( )iIi

TIi

iT ACAC UI

=

i ( )i

IiT

IiiT ACAC IU

=

.

Urmtorul rezultat este imediat:

Propoziia 1.2. Dac T o mulime iar A, B, CP(T), atunci: (i) A(BC)=(AB)C i A(BC)=(AB)C (ii) AB=BA i AB=BA (iii) AT=A i A=A (iv) AA=A i AA=A. Observaia 1.3. 1. Din (i) deducem c operaiile i sunt asociative, din (ii) deducem c

ambele sunt comutative, din (iii) deducem c T i sunt elementele neutre pentru i respectiv pentru , iar din (iv) deducem c i sunt operaii idempotente pe P(T).

2. Prin dubl incluziune se probeaz imdiat c pentru oricare A, B, CP(T) avem: A(BC)=(AB)(AC) i A(BC)=(AB)(AC) ,

adic operaiile de intersecie i reuniune sunt distributive una fa de cealalt. Propoziia1.4. Dac A, B, CP(T), atunci:

(i) A(BC)=(AB)C (ii) AB=BA (iii) A=A iar A A= (iv) A(BC)=(AB)(AC).

3

3

Demonstraie. (i). Prin dubl incluziune se arat imediat c: A(BC)=(AB)C=[AT(B)T(C)][T(A)BT(C)] [T(A)T(B)C](ABC).

(ii), (iii) sunt evidente. (iv). Se probeaz fie prin dubl incluziune, fie innd cont de distributivitatea interseciei fa

de reuniune. Din cele de mai inainte deducem ca dac T este o mulime oarecare , atunci (P(T), ,)

este inel Boolean .

Definiia1.5. Fiind date dou obiecte x i y se numete pereche ordonat a obiectelor x i y mulimea notat (x, y) i definit astfel:

(x, y)={ {x}, {x, y} }. Se verific acum imediat c dac x i y sunt dou obiecte a.. xy, atunci (x, y)(y, x) iar

dac (x, y) i (u, v) sunt dou perechi ordonate, atunci (x, y)=(u, v) x=u i y=v ; n particular, (x, y)=(y, x) x=y.

Definiia1.6. Dac A i B sunt dou mulimi, mulimea notat AB={ (a, b) | aA i bB } se va numi produsul cartezian al mulimilor A i B.

n mod evident: AB A i B AB= A= sau B= AB=BA A=B AA i BB ABAB.

Dac A, B, C sunt trei mulimi vom defini produsul lor cartezian prin egalitatea : ABC=(AB)C. Elementul ((a, b), c) din ABC l vom nota mai simplu prin (a, b, c).

Mai general, dac A1, A2, ..., An (n3) sunt mulimi punem A1 A2 ...An =(( ...((A1A2)A3) ...)An) .

Dac A este o mulime finit, vom nota prin |A| numrul de elemente ale lui A. n mod evident, dac A i B sunt submulimi finite ale unei mulimi M atunci i AB este submulime finit a lui M iar

|AB|=|A|+|B|-|AB|.

Vom prezenta n continuare un rezultat mai general cunoscut sub numele de principiul includerii i excluderii:

Propoziia1.7. Fie M o mulime finit iar M1, M2, ..., Mn submulimi ale lui M. Atunci :

( ) nnnkji

kjinji

jini

i

n

ii

MM

MMMMMMM

+

+=

4

4

2.Relaii binare pe o mulime. Relaii de echivalen

Definiia 2.1. Dac A este o mulime, numim relaie binar pe A orice submulime a

produsului cartezian AA. Dac a, bA i (a, b) vom spune c elementul a este n relaia cu b.

De asemenea, vom scrie ab pentru a desemna faptul c (a, b). Pentru mulimea A vom nota prin Rel (A) mulimea relaiilor binare de pe A (evident, Rel

(A)=P(AA) ). Relaia A={ (a, a) | aA} poart numele de diagonala produsului cartezian AA. Pentru Rel (A) definim -1={(a, b)AA | (b, a)}. n mod evident, (-1)-1= iar dac mai avem Rel (A) a.. -11-.

Definiia2.2. Pentru , Rel (A) definim compunerea lor prin ={(a, b)AA

| exist cA a.. (a, c) i (c, b)}.

Rezultatul urmtor este imediat: Propoziia 2.3. Fie , , Rel (A). Atunci: (i) A=A= (ii) ()=() (iii) i (iv) (1-(=1--1 (v) (1-(=-11- ; mai general, dac (i) iI este o familie de relaii binare pe A,

atunci

UUIi

iIi

i

=

11

.

Pentru n i Rel (A) definim :

>

== 1....

0

npentrunpentru

orin

An

4434421ooo .

Se probeaz imediat c dac m, n atunci mn=m+n. Definii 2.3. Vom spune despre o relaie Rel (A) c este:

i) reflexiv dac A ii) simetric dac -1 iii) antisimetric dac -1A iv) tranzitiv dac 2. Rezultatul urmtor este imediat: Propoziia2.4. O relaie Rel(A) este reflexiv ( simetric, antisimetric, tranzitiv )

dac i numai dac -1 este reflexiv ( simetric, antisimetric, tranzitiv ) . Definiia 2.5. Vom spune despre o relaie Rel(A) c este o echivalen pe A dac este

reflexiv, simetric i tranzitiv.

5

5

Vom nota prin Echiv (A) mulimea relaiilor de echivalen de pe A. Evident, A, AAEchiv (A).

Propoziia 2.6. Dac Echiv (A) , atunci -1= i 2=. Demonstraie. Cum este simetric -1. Dac (a, b)-1, atunci (b, a)-1 (b, a)-

1 (a, b), adic -1, deci -1=. Cum este tranzitiv avem 2. Fie acum (x, y). Din (x, x) i (x, y) (x, y)=2, adic 2, deci 2=.

Lema 2.7. Fie Rel(A) i =A-1. Atunci relaia are urmtoarele proprieti:

(i) (ii) este reflexiv i simetric (iii) dac este o alt relaie binar de pe A reflexiv i simetric a.. , atunci .

Demonstraie. (i ). este evident .

(ii). Cum A deducem c este reflexiv iar cum 1

= (A-1) 1=A-1-1 (-1)-1=A-1= deducem c este i simetric. (iii). Dac este reflexiv i simetric a.. , atunci -11-= i cum A deducem

c =A-1.

Lema 2.8. Fie Rel(A) reflexiv i simetric iar U1

=n

n . Atunci are urmtoarele

proprieti : (i) ; (ii) este o echivalen pe A; (iii) Dac Echiv(A) a.. , atunci . Demonstraie. (i). este evident. (ii). Cum A deducem c A , adic este reflexiv. Deoarece este simetric

i pentru orice n* avem (n)-1=(-1)n=n , deducem c

( ) ===

=

UUU11

11

1

1

n

n

n

n

n

n ,

adic este i simetric. Fie acum (x, y) o ; atunci exist zA a.. (x, z), (z, y) , adic exist m, n* a.. (x, z)m i (z, y)n. Deducem imediat c (x, y)nm=n+m , adic 2 , deci este tranzitiv, adic Echiv (A).

(iii). Fie acum Echiv (A) a.. . Cum n n = pentru orice n* deducem c U

1=

n

n .

Din Lemele de mai sus deducem imediat: Teorema 2.9. Dac Rel(A), atunci

( )U U U1

1

=n

n

A .

6

6

Definiia 2.10. Dac Echiv (A) i aA, prin clasa de echivalen a lui a relativ la nelegem mulimea

[a]={xA (x, a)} (cum este n particular reflexiv deducem c a[a], adic [a] pentru orice aA).

Mulimea A / ={ [a] aA } poart numele de mulimea factor ( sau ct ) a lui A p