1 Fundamentele algebrice ale busneag/auxiliare/books/Fundamentele algebrice ale...آ  Fundamentele...

download 1 Fundamentele algebrice ale busneag/auxiliare/books/Fundamentele algebrice ale...آ  Fundamentele algebrice

of 90

  • date post

    02-Nov-2019
  • Category

    Documents

  • view

    8
  • download

    2

Embed Size (px)

Transcript of 1 Fundamentele algebrice ale busneag/auxiliare/books/Fundamentele algebrice ale...آ  Fundamentele...

  • 1

    1

    Fundamentele algebrice ale informaticii

    pentru anul I Informatică ( zi + ID) începînd cu anul universitar 2005/2006 CURSUL nr. 1

    §1. Mulţimi. Operaţii cu mulţimi

    În cadrul acestei lucrări vom privi mulţimile în sensul în care ele au fost privite de către

    GEORG CANTOR - primul matematician care a iniţiat studiul lor sistematic (punct de vedere cunoscut în matematică sub numele de teoria naivă a mulţimilor).

    Definiţia1.1.. Dacă A şi B sunt două mulţimi, vom spune că A este inclusă în B (sau că A

    este submulţime a lui B) dacă elementele lui A sunt şi elemente ale lui B; în acest caz vom scrie A⊆B iar în caz contrar A⊈B.

    Avem deci : A⊆B⇔ pentru orice x∈A ⇒x∈B A⊈B⇔ există x∈A a.î. x∉B.

    Vom spune despre mulţimile A şi B că sunt egale dacă oricare ar fi x, x∈A⇔ x∈B. Deci, A=B⇔A⊆B şi B⊆A.

    Vom spune că A este inclusă strict în B şi vom scrie A⊂B dacă A⊆B şi A≠B. Se acceptă existenţa unei mulţimi ce nu conţine nici un element care se notează prin ∅ şi

    poartă numele de mulţimea vidă. Se observă că pentru orice mulţime A, ∅⊆A (deoarece în caz contrar ar trebui să existe x∈∅ a.î. x∉A – absurd.!).

    O mulţime diferită de mulţimea vidă se zice nevidă. Pentru o mulţime T, vom nota prin P(T) mulţimea submulţimilor sale (evident ∅, T∈P(T) ). Următorul rezultat este imediat : Dacă T este o mulţime oarecare iar A, B, C∈P(T), atunci : (i) A⊆A (ii) Dacă A⊆B şi B⊆A, atunci A=B (iii) Dacă A⊆B şi B⊆C, atunci A⊆C. În cadrul acestei lucrări vom utiliza deseori noţiunea de familie de elemente a unei mulţimi

    indexată de o mulţime nevidă de indici I (prin aceasta înţelegând o funcţie definită pe mulţimea I cu valori în mulţimea respectivă).

    Astfel, vom scrie de exemplu (xi)i∈I pentru a desemna o familie de elemente ale unei mulţimi sau (Ai) i∈I pentru a desemna o familie de mulţimi indexată de mulţimea I. Pentru o mulţime T şi A, B∈P(T) definim : A∩B={x∈T | x∈A şi x∈B}

    A∪B={x∈T | x∈A sau x∈B} A\B={x∈T | x∈A şi x∉B} A△B=(A\B)∪(B\A).

    Dacă A∩B=∅, mulţimile A şi B se zic disjuncte. Operaţiile ∩, ∪, \ şi △ poartă numele de intersecţie, 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, 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: x∉A∩B ⇔ x∉A sau x∉B x∉A∪B ⇔ x∉A şi x∉B x∉A\B ⇔ x∉A sau x∈B x∉A△B ⇔ (x∉A şi x∉B) sau (x∈A şi x∈B) x∉∁T (A)⇔ x∈A.

    Din cele de mai înainte deducem imediat că dacă A, B∈P(T), atunci: ∁T (A∩B)=∁T(A)∪∁T (B) şi ∁T (A∪B)=∁T (A)∩∁T (B).

    Aceste ultime două egalităţi sunt cunoscute sub numele de relaţiile lui De Morgan. Pentru o familie nevidă (Ai )i∈I de submulţimi ale lui T definim:

    I Ii

    iA ∈

    ={x∈T | x∈Ai pentru orice i∈I} şi

    U Ii

    iA ∈

    ={x∈T | există i∈I a.î. x∈Ai }.

    Astfel, relaţiile lui De Morgan sunt adevărate într-un context mai general: Dacă (Ai) i∈I este o familie de submulţimi ale mulţimii T, atunci:

    ( )i Ii

    T Ii

    iT ACAC UI ∈∈

    =  

       şi ( )i

    Ii T

    Ii iT ACAC IU

    ∈∈ =

     

       .

    Următorul rezultat este imediat:

    Propoziţia 1.2. Dacă T o mulţime iar A, B, C∈P(T), atunci: (i) A∩(B∩C)=(A∩B)∩C şi A∪(B∪C)=(A∪B)∪C (ii) A∩B=B∩A şi A∪B=B∪A (iii) A∩T=A şi A∪∅=A (iv) A∩A=A şi A∪A=A. Observaţia 1.3. 1. Din (i) deducem că operaţiile ∪ ş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 operaţii idempotente pe P(T).

    2. Prin dublă incluziune se probează imdiat că pentru oricare A, B, C∈P(T) avem: A∩(B∪C)=(A∩B)∪(A∩C) şi A∪(B∩C)=(A∪B)∩(A∪C) ,

    adică operaţiile de intersecţie şi reuniune sunt distributive una faţă de cealaltă. Propoziţia1.4. Dacă A, B, C∈P(T), atunci:

    (i) A△(B△C)=(A△B)△C (ii) A△B=B△A (iii) A△∅=A iar A △A=∅ (iv) A∩(B△C)=(A∩B)△(A∩C).

  • 3

    3

    Demonstraţie. (i). Prin dublă incluziune se arată imediat că: A△(B△C)=(A△B)△C=[A∩∁T(B)∩∁T(C)]∪[∁T(A)∩B∩∁T(C)]∪ ∪[∁T(A)∩∁T(B)∩C]∪(A∩B∩C).

    (ii), (iii) sunt evidente. (iv). Se probează fie prin dublă incluziune, fie ţinând cont de distributivitatea intersecţiei faţă

    de reuniune. ∎ Din cele de mai inainte deducem ca dacă T este o mulţime oarecare , atunci (P(T), △,∩)

    este inel Boolean .

    Definiţia1.5. Fiind date două obiecte x şi y se numeşte pereche ordonată a obiectelor x şi y mulţimea notată (x, y) şi definită astfel:

    (x, y)={ {x}, {x, y} }. Se verifică acum imediat că dacă x şi y sunt două obiecte a.î. x≠y, 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.

    Definiţia1.6. Dacă A şi B sunt două mulţimi, mulţimea notată A×B={ (a, b) | a∈A şi b∈B } se va numi produsul cartezian al mulţimilor A şi B.

    În mod evident: A×B≠∅ ⇔ A≠∅ şi B≠∅ A×B=∅ ⇔ A=∅ sau B=∅ A×B=B×A ⇔ A=B A׳⊆A şi B׳⊆B ⇒ A׳×B׳⊆A×B.

    Dacă A, B, C sunt trei mulţimi vom defini produsul lor cartezian prin egalitatea : A×B×C=(A×B)×C. Elementul ((a, b), c) din A×B×C îl vom nota mai simplu prin (a, b, c).

    Mai general, dacă A1, A2, ..., An (n≥3) sunt mulţimi punem A1× A2× ...×An =(( ...((A1×A2)×A3)× ...)×An) .

    Dacă A este o mulţime finită, vom nota prin |A| numărul de elemente ale lui A. În mod evident, dacă A şi B sunt submulţimi finite ale unei mulţimi M atunci şi A∪B este submulţime finită a lui M iar

    |A∪B|=|A|+|B|-|A∩B|.

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

    Propoziţia1.7. Fie M o mulţime finită iar M1, M2, ..., Mn submulţimi ale lui M. Atunci :

    ( ) nn nkji

    kji nji

    ji ni

    i

    n

    i i

    MM

    MMMMMMM

    ∩∩−+−

    −∩∩+∩−=

  • 4

    4

    §2.Relaţii binare pe o mulţime. Relaţii de echivalenţă

    Definiţia 2.1. Dacă A este o mulţime, numim relaţie binară pe A orice submulţime ρ a

    produsului cartezian A×A. Dacă a, b∈A şi (a, b)∈ρ vom spune că elementul a este în relaţia ρ cu b.

    De asemenea, vom scrie aρb pentru a desemna faptul că (a, b)∈ρ. Pentru mulţimea A vom nota prin Rel (A) mulţimea relaţiilor binare de pe A (evident, Rel

    (A)=P(A×A) ). Relaţia △A={ (a, a) | a∈A} poartă numele de diagonala produsului cartezian A×A. Pentru ρ∈Rel (A) definim ρ-1={(a, b)∈A×A | (b, a)∈ρ}. În mod evident, (ρ-1)-1=ρ iar dacă mai avem ρ׳∈Rel (A) a.î. ρ⊆ρ׳⇒ ρ-1⊆ρ1-׳.

    Definiţia2.2. Pentru ρ, ρ׳∈Rel (A) definim compunerea lor ρ∘ρ׳ prin ρ∘ρ׳={(a, b)∈A×A

    | există c∈A a.î. (a, c)∈ρ׳ şi (c, b)∈ρ}.

    Rezultatul următor este imediat: Propoziţia 2.3. Fie ρ, ρ׳, ρ׳׳∈Rel (A). Atunci: (i) ρ∘△A=△A∘ρ=ρ (ii) (ρ∘ρ׳)∘ρ׳׳=ρ∘(ρ׳∘ρ׳׳) (iii) ρ⊆ρ׳⇒ ρ∘ρ׳׳⊆ρ׳∘ρ׳׳ şi ρ׳׳∘ρ⊆ρ׳׳∘ρ׳ (iv) (ρ∘ρ1-(׳=ρ1-׳∘ρ-1 (v) (ρ∪ρ1-(׳=ρ-1∪ρ1-׳ ; mai general, dacă (ρi) i∈I este o familie de relaţii binare pe A,

    atunci

    UU Ii

    i Ii

    i ∈

    − −

    ∈ =

     

       

     1 1

    ρρ .

    Pentru n∈ℕ şi ρ∈Rel (A) definim :

     

     

    >

    =∆ = 1....

    0

    npentru npentru

    orin

    A n

    4434421 ooo ρρρρ .

    Se probează imediat că dacă m, n ∈ℕ atunci ρm∘ρn=ρm+n. Definiţi 2.3. Vom spune despre o relaţie ρ∈Rel (A) că este:

    i) reflexivă dacă △A ⊆ρ ii) simetrică dacă ρ⊆ρ-1 iii) antisimetrică dacă ρ∩ρ-1⊆△A iv) tranzitivă dacă ρ2⊆ρ. Rezultatul următor este imediat: Propoziţia2.4. O relaţie ρ∈Rel(A) este reflexivă ( simetrică, antisimetrică, tranzitivă )

    dacă şi numai dacă ρ-1 este reflexivă ( sim