1 Fundamentele algebrice ale informaticii - math.ucv. chirtes/auxiliare/books/doc/Fundamentele...

download 1 Fundamentele algebrice ale informaticii - math.ucv. chirtes/auxiliare/books/doc/Fundamentele algebrice

of 90

  • date post

    29-Aug-2019
  • Category

    Documents

  • view

    8
  • download

    1

Embed Size (px)

Transcript of 1 Fundamentele algebrice ale informaticii - math.ucv. chirtes/auxiliare/books/doc/Fundamentele...

  • 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