Curs 1

Partea I

Multimi. Functii. Relatii.Grafuri

I.1 Multimi

I.1.1 Notiuni introductive

Conceptul de multime este fundamental ın Matematica si indispensabil ınComputer Science. Acest concept abstractizeaza ideea de a grupa ımpreunaobiecte si de a le vedea ca o entitate de sine statatoare.

Intuitiv, vom spune ca o multime este o colectie de obiecte distincte,numite elementele multimii1.

Deci o multime este formata din obiecte, numite elementele multimii re-spective. Elementele unei multimi pot fi de orice natura: numere, persoane,litere ale alfabetului, sau chiar alte multimi, etc. Doua elemente ale aceleiasimultimi pot fi doar egale sau diferite (momentan nu ne intereseaza decat caelemente ale multimii, fara orice alta structura).

Prin conventie, vom nota multimile cu majuscule: A, B, C etc., iar ele-mentele acestora cu litere mici: x, y, etc.

Ca exemple, sa cosideram multimea studentilor admisi la sectia Calcula-toare ın 2010, multimea culorilor curcubeului, multimea literelor alfabetuluilatin, etc. Dintre multimile importante ın matematica, pe care le-am ıntalnitdeja ın liceu, mentionam urmatoarele:

• multimea numerelor naturale N = {0, 1, 2, . . .}.1Aceasta a fost definitia utilizata de matematicianul G. Cantor (1845-1918), fondatorul

Teoriei multimilor.

1

2

• multimea numerelor ıntregi2 Z = {0,±1,±2, . . .}.

• multimea numerelor rationale Q = {ab| a, b ∈ Z, b 6= 0}.

• multimea numerelor reale R.

Notiunile de multime si de element sunt legate prin relatia de apartenenta:daca A este o multime si x un obiect al multimii, spunem ca x apartine lui Asi scriem x ∈ A3. In cazul ın care obiectul x nu este un element al multimiiA vom nota x /∈ A. De exemplu, 1 apartine multimii {1, 2, alb, {3, 4}}, dar3 si 4 nu apartin; elementele multimii sunt numerele 1, 2, sirul de caracterealb si multimea {3, 4}.

O multime poate fi specificata prin listarea tuturor elementelor sale ıntreacolade, cum ar fi multimea cifrelor pare {0, 2, 4, 6, 8}. De remarcat caordinea ın care apar elementele multimii ıntr-o asemenea scriere nu con-teaza, ın sensul ca {8, 2, 4, 0, 6} este aceeasi multime ca mai sus. De aseme-nea, repetitia elementelor este irelevanta: {a, b, b} si {a, b} reprezinta aceeasimultime (vom vorbi ın Cursul 2 despre multiseturi, multimi ın care repetitiilesunt permise).

Convenim ca exista o unica4 multime fara elemente, numita multimea vidasi notata ∅ sau {}. Nu se disting diferite multimi vide dupanatura diferitaa elementelor a caror absenta o avem ın vedere. De exemplu, multimeasolutiilor naturale ale ecuatiei 2x + 1 = 0, multimea punctelor comune uneiperechi de drepte paralele sau multimea punctelor din plan ale caror coor-donate satisfac ecuatia x2 + y2 + 1 = 0 reprezinta una si aceeasi multimevida. O multime poate fi vida (nu contine nici un obiect) sau nu; daca nueste vida, putem gasi cel putin un obiect care sa-i apartina.

Insa descrierea multimilor prin listarea elementelor ıntre acolade nu esteıntotdeauna eficienta; exemple ar fi multimea numerelor rationale saumultimea numerelor reale; ın acest caz se prefera descrierea multimii prinprecizarea unei proprietati P , comune tuturor elementelor sale. Scriem ast-fel:

A = {x ∈ B | P (x)}

De exemplu, multimea {12 , 2} poate fi descrisa prin {x ∈ R | 2x2−5x+2 = 0};

multimea punctelor de pe cercul unitate prin {(x, y) ∈ R2 | x2 + y2 = 1}, iar

2Notatia provine din limba germana, de la cuvantul zahlen(numere).3Simbolul ∈, utilizat pentru a indica relatia de apartenenta, a fost introdus de

matematicianul italian G. Peano (1858-1932) ın 1888 si provine din litera ε (epsilon) aalfabetului grec.

4Doua multimi sunt egale daca au aceleasi elemente. Daca ar exista doua multimi videsi ar fi diferite, atunci ar exista cel putin un obiect care ar apartine uneia si nu si celeilalte,fals.

3

multimea numerelor ıntregi pare prin {x | x = 2k, k ∈ Z}.Dar atentie: nu orice proprietate poate conduce la o multime! Pentru a

vedea aceasta, este suficient sa consideram M multimea tuturor multimilorcare nu se contin pe ele ınsele ca elemente: M = {A | A multime si A /∈ A}.Dar cum poate o multime sa se contina pe sine ınsasi? De exemplu, multimeatuturor notiunilor abstracte este la randul sau o notiune abstracta. Multmai usor este sa gasim exemple de multimi care nu se contin, cum ar fimultimea numerelor naturale, multimea literelor alfabetului, multimea vida(cum multimea vida nu are nici un element, ın particular rezulta ca nu secontine nici pe sine). Deci am ımpartit astfel multimile ın doua: multimilecare se contin pe sine ınsasi si cele care nu. Apare ın mod natural ıntrebarea:dar multimea M se contine pe sine ca element? Daca raspunsul este afir-mativ, atunci M este un element al sau. Dar elementele lui M sunt exactmultimile care nu se contin pe sine ınsasi, deci M /∈ M , contradictie. DeciM nu se contine pe sine ınsasi. Insa atunci prin definitie, M este un elemental sau, fals. Am ajuns astfel la un paradox 5, generat de presupunerea ca Meste o multime6. In teoria naiva a multimilor, situatia de mai sus nu estepermisa si nu vom considera asemenea cazuri ın cadrul acestui curs.

Acest tip de paradox a condus la un studiu amanuntit al fundamentelor teoriei multimilor.A. N. Whitehead si B. Russell, ın lucrarea Principia Mathematica, au dezvoltat o teorie amultimilor bazata pe o ierarhie, ale caror nivele le-au numit tipuri7. Astfel, cel mai de jos nivel(tip) contine doar elemente individuale. Orice alt tip contine doar multimi ale caror elementeprovin doar din nivelul imediat inferior. Se obtine astfel o ierarhie a tipurilor T0, T1, . . . , Tk, . . .,unde T0 este nivelul minim ce contine doar elemente, iar Tk+1 este tipul ale carui multimi auelementele in Tk. Deci ın aceasta teorie, o multime se regaseste exact ıntr-un singur tip Tk,unde k ≥ 1. In consecinta, putem spune ca A /∈ A pentru orice multime construita astfel:daca A este o multime de tipul Tk+1, elementele lui A sunt de tipul Tk. Daca presupunemA ∈ A, am obtine ca si A este de tipul Tk, deci s-ar regasi simultan ın tipurile Tk si Tk+1,imposibil, caci fiecare multime apartine exact unui singur tip. Paradoxul lui Russel nu poateavea loc ın aceasta teorie a tipurilor: cum A /∈ A pentru orice multime A, definitia lui Mdevine {A | A este o multime }, adica M contine toate multimile. Dar M nu poate fi omultime ın teoria tipurilor, deoarece contine multimi de tipuri diferite. Pentru ca M sa fieo multime ın acceptiunea teoriei tipurilor, ar trebui sa contina doar multimi de acelasi tip.De exemplu, constructia M = {A | A este o multime de tipul TK} este perfect valabila sidefineste o multime de tipul Tk+1. In particular, rezulta M /∈M , dar aceasta nu mai reprezintao contradictie.

In Computer Science, se ıntalneste uneori si o a treia varianta de specifi-

5Paradox celebru din 1901, datorat matematicianului si filosofului britanic B. Russel(1872-1970), fondatorul teoriei tipurilor din Computer Science.

6Dar aceasta nu ınseamna ca nu exista multimi avand drept elemente alte multimi - deexemplu multimea partilor.

7In Computer Science, teoria tipurilor este fundamentala ın constructia algoritmilor deverificare formala a limbajelor de programare.

4

care a unei multimi, prin recursivitate. Vom da numai un exemplu ın acestsens: fie A multimea numerelor naturale pare mai mari decat 3; atunci Apoate fi descrisa astfel:

(i) 4 ∈ A.

(ii) Daca x ∈ A, atunci x+ 2 ∈ A.

(iii) Nici un alt element nu apartine lui A.

O multime este complet determinata de elementele sale. Aceasta ınseamnaca doua multimi sunt egale cand au exact aceleasi elemente:

A = B ⇐⇒ (x ∈ A⇐⇒ x ∈ B)

Putem merge mai departe ın compararea a doua multimi, si anume vomspune ca o multime A este inclusa ıntr-o multime B si scriem A ⊆ B dacaorice element al multimii A este si element al multimii B:

A ⊆ B ⇐⇒ (∀x ∈ A =⇒ x ∈ B)

Rezulta ca A * B ⇐⇒ (∃x ∈ A si x /∈ B). De exemplu, avem incluziunileN ⊆ Z sau Q ⊆ R, dar Q * Z. Multimea vida este inclusa ın orice altamultime (de ce?). Se verifica imediat urmatoarele proprietati ale relatiei deincluziune:

A ⊆ A pentru orice multime A (reflexivitate)

A ⊆ B si B ⊆ C =⇒ A ⊆ C pentru orice multimi A,B,C (tranzitivitate)

Submultimile unei multimi date A formeaza la randul lor o multime,numita multimea partilor lui A si notata P(A) sau 2A (vom justifica aceastanotatie exponentiala cand vom discuta despre functii). In particular, aceastacontine multimea vida si multimea A ınsasi (deci este nevida). De exemplu,P({a, b}) = {∅, {a}, {b}, {a, b}}. Observati ca P(∅) = {∅} (a nu se confundacu multimea vida!), iar P(P(∅)) = {∅, {∅}}.

Exercitiul I.1.1.1. Aratati ca doua multimi A si B sunt egale daca si numaidaca A ⊆ B si B ⊆ A.

I.1.2 Operatii elementare cu multimi

In continuare vom presupune fixata o multime universala M , ın sensul catoate multimile cu care vom lucra ın aceasta sectiune vor fi incluse ın M .

5

Reuniunea multimilor A si B este multimea acelor elemente (din M) ceapartin fie lui A, fie lui B (sau amandorura):

A ∪B = {x ∈M | x ∈ A sau x ∈ B}

Intersectia multimilor A si B este multimea acelor elemente (din M) ceapartin atat A cat si lui B:

A ∩B = {x ∈M | x ∈ A si x ∈ B}

Daca A ∩B = ∅, spunem ca A si B sunt disjuncte.Atat reuniunea cat si intersectia pot fi reprezentate sugestiv cu ajutoruldiagramelor Venn8, ca ın Figurile 1 si 2:

Figura 1: A ∪B Figura 2: A ∩B

Mai general, se poate defini reuniunea unei familii arbitrare nevide F demultimi (F ⊆ P)(M)), prin

x ∈ ∪A∈F

A⇐⇒ ∃A ∈ F , x ∈ A

respectiv intersectia prin

x ∈ ∩A∈F

A⇐⇒ ∀A ∈ F , x ∈ A

Daca F = ∅, prin conventie, vom considera multimea vida drept reuniune simultimea universala M drept intersectie.

Complementara unei multimi A ⊆ M este multimea acelor elemente dinM care nu sunt ın A:

Ac = {x | x /∈ A}Complementara unei multimi este reprezentata ın Figura 3 printr-o diagramaVenn.Proprietati algebrice ale operatiilor cu multimi:

8J. Venn(1834 1923), matematician britanic.

6

Figura 3: Ac

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

ComutativitateA ∪B = B ∪ AA ∩B = B ∩ A

IdempotentaA ∪ A = A

A ∩ A = A

AbsorbtieA ∩ (A ∪B) = A

A ∪ (A ∩B) = A

ModularitateDaca A ⊆ C, atunci A ∪ (B ∩ C) = (A ∪B) ∩ C

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

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

Multimea vida sau legea contradictieiA ∪ ∅ = A

A ∩ ∅ = ∅

Multimea universala sau legea tertului exclusA ∪M = M

A ∩M = A

7

ComplementaritateA ∪ Ac = M

A ∩ Ac = ∅

Involutie(Ac)c = A

Legile lui de Morgan(A ∪B)c = Ac ∩Bc

(A ∩B)c = Ac ∪Bc

De exemplu, sa demonstram una din cele doua proprietati de absorbtie: dacax ∈ A ∩ (A ∪ B), atunci ın particular x ∈ A. Reciproc, daca x ∈ A, atuncix ∈ A ∩B, deci si x ∈ A ∩ (A ∪B).

De remarcat ca ın afara proprietatii de modularitate, toate celelalte aparın perechi; de fapt, exista o dualitate ın sensul ca orice identitate ın careapar operatiile de intersectie si reuniune ramane adevarata daca ∪ si ∩ suntinterschimbate. Acest fapt este datorat legilor lui de Morgan si proprietatii deinvolutie. Pentru exemplificare, sa aratam a doua lege de absorbtie, plecandde la prima (pe care am demonstrat-o anterior):

A ∪ (A ∩B) = ((A ∪ (A ∩B))c)c

= (Ac ∩ (Ac ∪Bc))c

= (Ac)c

= A

Operatiile de reuniune si intersectie amintesc de adunarea si ınmultireanumerelor ıntregi, iar complementara unei multimi de opusul unui numar ınraport cu adunarea, cu toate ca nu satisfac chiar toate aceleasi proprietati(de exemplu, A ∪ A = A pentru orice multime A, ın timp ce a + a = adoar pentru a = 0). Totusi, asa cum adunarea si ınmultirea determina ostructura algebrica (de inel comutativ) pe Z, la fel se ıntampla si cu P(M),ımpreuna cu operatiile ∪,∩, ()c. O multime ınzestrata cu doua operatii binaresi o operatie unara satisfacand proprietatile de mai sus se numeste algebrabooleana9. Deci, multimea partilor (P(M),∪,∩, ()c) este o algebra booleana.Asupra algebrelor booleene, cu mai multe detalii si exemple, vom reveni ıncursurile urmatoare. Un caz particular important se obtine daca multimeaM contine doar un singur element:

9Studiul algebric al multimii partilor si legatura acesteia cu rationamentele logice aufost initiate de matematicianul britanic G. Boole (1815-1864)

8

Exemplul I.1.2.1. Fie M = {a}. Atunci P(M) = {∅, {a}}. Daca notam∅ cu 0 si {a} cu 1, atunci tablele operatiilor de reuniune, intersectie si com-plementara vor fi:

∪ 0 10 0 11 1 1

∩ 0 10 0 01 0 1

()c

0 11 0

Remarcam ca acestea coincid cu tabelele de adevar din calculul propozitional,unde ın loc de reuniune avem disjunctia ( sau ∨), intersectia este ınlocuitade conjunctie ( si ∧), iar complementara devine negatie (¬). Scrieti tablade adevar pentru implicatie si determinati operatia cu (sub)multimi core-spunzatoare. (Indicatie: Ac ∪ B). Scrieti si tabla operatiei diferenta simet-rica. Puteti identifica corespondentul din calculul propozitional?

Identitatile ıntre multimi, ın care apar operatii elementare de tipul reuni-une, intersectie, complement, pot fi verificate si cu ajutorul tablelor de adevarprivind apartenenta: de exemplu, sa aratam prima lege a lui de Morgan:

A B A ∪B (A ∪B)c Ac Bc Ac ∩Bc

0 0 0 1 1 1 10 1 1 0 1 0 01 0 1 0 0 1 01 1 1 0 0 0 0

I.1.3 Produs cartezian

Intuitiv, o pereche ordonata de obiecte este o colectie formata cu douaobiecte astfel ıncat unul dintre acestea este desemnat prima componenta iarcelalalt a doua (ultima) componenta. Proprietatea fundamentala ce sta labaza notiunii de pereche ordonata este aceea de egalitate: doua perechi or-donate sunt egale daca si numai daca primele componente, respectiv ultimelecomponente coincid.

Fiind date doua obiecte x si y, se numeste pereche ordonata a obiectelorx si y multimea notata (x, y)10 si definita prin

(x, y) = {{x}, {x, y}}

Daca x 6= y, atunci (x, y) este o multime cu doua elemente: o multimecu un element {x} si o multime cu doua elemente (o pereche neordonata){x, y}. Prima componenta a perechii (x, y) se obtine din din {x}, iar a douacomponenta din {x, y} \ {x}. In cazul x = y, atunci {x, y} = {x, x} = {x}

10Kuratowski, 1921.

9

si (x, y) = {{x}, {x, y}} = {{x}, {x}} = {{x}} si cele dou ua componentecoincid. Deci ambele componente pot fi unic determinate pornind de lamultimea (x, y). Mai precis, are loc urmatorul rezultat:

Propozitia I.1.3.1. (x, y) = (x′, y′) daca si numai daca x = x′ si y = y′.

Demonstratie. Daca x = x′ si y = y′, atunci clar (x, y) = {{x}, {x, y}} ={{x′}, {x′, y′}} = (x′, y′).

Implicatia inversa este ınsa un pic mai laborioasa. Sa presupunem decica {{x}, {x, y}} = {{x′}, {x′, y′}}. Daca x 6= y, atunci neaparat {x} = {x′}si {x, y} = {x′, y′} (multimea cu doua elemente {x, y} nu poate fi egala cu{x′}, o multime cu un singur element). Din {x} = {x′} rezulta x = x′; apoi,{x, y} = {x′, y′} si x = x′ implica y = y′.

Daca x = y, atunci (x, y) = {{x}, {x, x}} = {{x}} = (x′, y′), de unde{x} = {x′} = {x′, y′}. Din acest sir de egalitati rezulta x = x′ = y′, deci vomavea si x = x′ si y = y′.

Exercitiul I.1.3.2. Aratati ca (x, y) ∈ P(P({x, y})).

Daca A si B sunt doua multimi, multimea

A×B = {(a, b) | a ∈ A si b ∈ B}se va numi produsul cartezian al multimilor A si B.

Prin conventie, produsul cartezian al oricarei multimi cu multimea vidaeste multimea vida: A× ∅ = ∅ × A = ∅.

Daca A,B,C sunt trei multimi, vom defini produsul lor cartezian prinegalitatea: A×B×C = (A×B)×C. Elementul ((x, y), z) din A×B×C ılvom nota mai simplu prin (x, y, z). Mai general, daca A1, A2, . . . , An(n ≥ 3)sunt multimi, punem A1×A2×. . .×An = ((. . . ((A1×A2)×A3)×. . .)×An). Incazul ın care toate multimile din produs coincid, ca ın A×A, notam produsulprin A2, A × A × A prin A3, etc. Asemenea produse sunt familiare dingeometria analitica: un punct pe o dreapta poate fi identificat cu un numarreal; punctele planului sunt unic determinate de perechi de coordonate, adicade elemente din R2, etc. Prin conventie, produsul cartezian al unei familiivide de multimi este o multime cu un singur element, ın timp ce produsulcartezian al unei familii continand o singura multime este chiar multimearespectiva.

I.1.4 Multiseturi

In matematica, notiunea de multiset11 este o generalizare a notiunii demultime, ın sensul ca daca pentru multimi, repetitia elementelor nu este luata

11Sau bag, ın limba engleza. Termenul multiset a aparut ın anii ’70, desi multiseturileau fost utilizate ınca din secolul XIX.

10

ın considerare, ıntr-un multiset un element poate avea duplicate. Ideea deplecare este urmatoarea: fie M o multime (universala). Atunci am vazutca o multime A ⊆ M poate fi specificata prin enumerarea elementelor sale,printr-o proprietate satisfacuta de elementele sale A = {x ∈ M | P (x)}, sauprin functia sa caracteristica (vezi Curs 2)

χA : M −→ {0, 1}, χA(x) =

{1, x ∈ A0, x /∈ A

ın sensul ca valoarea 1 indica apartenenta la multimea A. Daca multimea{0, 1} este ınlocuita cu multimea numerelor naturale N, se obtine notiuneade multiset. Formal, un multiset A este o pereche (M,χA), unde M esteo multime nevida si χA : M −→ N este o functie cu valori ın multimeanumerelor naturale. Multimea M este baza multisetului, multimea

supp(A) = {x ∈M | χA(x) > 0}

se numeste multimea suport a multisetului, iar pentru x ∈M , numarul χA(x)este numit multiplicitatea lui x ın multisetul A.

Altfel formulat, un multiset A ın M este o multime de perechi{(x, χA(x)) | x ∈ M si χA(x) ∈ N}, unde χA(x) indica numarul de aparitii(de repetari ale lui x ın A.

Un exemplu de multiset des ıntalnit ın teoria clasica a probabilitatilor esteurna cu bile de mai multe culori. Aici multimea M este multimea culorilorbilelor din urna, iar functia m indica cate bile de fiecare culoare se gasesc ınurna.

Un alt exemplu, poate cel mai simplu si natural din punct de vederematematic, este multisetul factorilor primi ai unui numar natural nenuln ≥ 2. Multimea suport M este multimea numerelor prime (sau multimeadivizorilor primi ai lui n, daca nu dorim si multiplicitatea zero), iar functiam indica puterea la care acesti factori primi apar ın descompunerea lui N .De exemplu, 120 se descompune ın 120 = 233151, care conduce la multisetul{2, 2, 2, 3, 5}.

In clasele de liceu, rezolvarea ecuatiilor polinomiale conduce la multise-turi de solutii, ın care fiecare radacina apare de un numar de ori egal cumultiplicitatea sa.

In continuare, vom presupune ca toate multiseturile vor avea aceeasimultime baza M .

Fie A un multiset. Spunem ca x ∈ M apartine multisetului A dacaχA(x) > 0 si scriem x ∈A. Doua multiseturi A si B cu aceeasi multime bazaM sunt egale daca χA(x) = χB(x) pentru orice x ∈M . In particular, rezultaca si multimile suport vor fi egale supp(A) = supp(B).

11

Exercitiul I.1.4.1. Este adevarat si reciproc? Dati un exemplu.

Observatia I.1.4.2. Sa consideram urmatoarele exemple, vazute ca

• Multimi:{a, b, c, c} = {c, a, b, c} = {a, b, c}

• Multiseturi:{a, b, c, c} = {c, a, b, c} 6= {a, b, c}

Deci ıntr-un multiset nu conteaza ordinea, dar sunt permise repetitiile.

Fie A si B doua multiseturi. Spunem ca A este un submultiset al lui B,A ⊆ B, daca χA(x) ≤ χB(x) pentru orice x ∈ M . Daca A ⊆ B, atunci sisupp(A) ⊆ supp(B), dar nu si invers.

Vom numi multiset vid ∅ (cu baza M) multisetul dat de functia de mul-tiplicitate χ∅(x) = 0, ∀x ∈M .

Notiunile de intersectie, reuniune, diferenta, produs cartezian si cardinal-itate a unui multiset se obtin prin generalizarea celor pentru multimi. Astfel,

(i) A∪B este multisetul definit prin χA∪B(x) = max(χA(x), χB(x)). Aceastaınseamna ca pentru un obiect x ∈ M , reuniunea multiseturilor vacontine pe x cu o multiplicitate egala cu cea mai mare dintre mul-tiplicitatile cu care x apare ın A sau ın B. De exemplu, daca A ={2, 3, 4, 4} si B = {1, 4, 3, 3}, atunci A ∪ B = {1, 2, 3, 3, 4, 4}. Sa re-marcam ca A,B ⊆ A ∪B.

(ii) Similar, A ∩ B va fi definit prin χA∩B(x) = min(χA(x), χB(x)). Inparticular, au loc relatiile A ∩B ⊆ A si A ∩B ⊆ B.

(iii) A \ B este multisetul cu functia de multiplicitate χA\B(x) = χA(x) −χA∩B(x). De remarcat de exempplu ca (A \ B) ∩ B = ∅ nu mairamane neaparat adevarata: pentru A = {1, 1, 1, 1, 2, 2, 2, 2, 2} si B ={1, 1, 2, 2, 2}, atunci A \B = {1, 1, 2, 2} ⊆ B.

I.1.5 Multimi fuzzy

Pe langa multiseturi, o alta generalizare a multimilor o constituie multimilefuzzy 12.

12Multimile fuzzy (vagi, ın terminologia utilizata ın unele lucrari romanesti) au fostintroduse de matematicianul de origine azerbaigiana L. A. Zadeh (n. 1921) ın anii ’60 ıncorelare cu teoria logicii nuantate a lui Lukasiewicz, ın care propozitiile nu sunt pe de-aıntregul adevarate sau pe de-a ıntregul false.

12

O multime fuzzy este o multime fara o limita definita clar. Poate contineelemente doar cu un grad partial de apartenenta.

O multime clasica este un recipient care include sau exclude total oriceelement dat. De exemplu, multimea zilelor saptamanii este {luni,marti,miercuri, joi, vineri, sambata, duminica}. Dar week-end-ul este un exemplude multime fuzzy: putem afirma fara nici o urma de ındoiala ca sambata esteo zi a week-endului, dar ca vineri este o zi de week-end ın proportie de 0.7(ın cea mai mare parte da, dar nu ın totalitate), iar duminica este o zi deweek-end cu ponderea de 0.95 (da, dar nu la fel de mult ca sambata).

O multime fuzzy A este o pereche (M,χA), unde M este o multime nevidasi χA : M −→ [0, 1] este o functie cu valori ın intervalul ınchis [0, 1]. MultimeaM este baza multimii fuzzy, iar multimea

supp(A) = {x ∈M | χA(x) > 0}

se numeste multimea suport a multimii fuzzy, pentru x ∈ M , numarul realχA(x) este numit ponderea lui x ın multimea fuzzy A.

Fiecare element din multimea (universala) M are un anumit grad deapartenenta, cuprins ıntre 0 si 1, ıntr-o multime fuzzy data A. O multimefuzzy A este specificata prin listarea elementelor din baza, ımpreuna cu pon-derea acestora (elementele de pondere 0 de obicei nu se mai scriu).

Ca pentru multimi si multiseturi, putem considera operatii cu multimifuzzy; de exemplu, complementara unei multimi fuzzy A este multimea fuzzyAc, ın care gradul de apartenenta al unui element x este 1 − χA(x). Reuni-unea a doua multimi fuzzy χA∪B(x) = max (χA(x), χB(x), iar intersectiaχA∪B(x) = min (χA(x), χB(x)).

Curs 2

I.2 Functii

I.2.1 Notiuni introductive

Asemeni multimilor, functiile sunt o notiune indispensabila atat ın Mate-matica cat si ın Computer Science. In acest Curs vom reaminti si apro-funda principalele concepte referitoare la functii1, cu exemple ce apar ınsolutionarea unor probleme de Informatica teoretica si practica2.

Fie A, B doua multimi nevide. Reamintim ca o functie f cu domeniul Asi codomeniul B este o corespondenta prin care se asociaza oricarui elementx din A un singur element din B, numit valoarea sau imaginea functiei ınx si notat f(x). In scrierea f(x), x se numeste argumentul functiei. Se maispune ca f este definita pe A cu valori ın B si scriem f : A −→ B sau

Af−→ B. Reamintim ca imaginea functiei f , notata Imf , este submultimea

lui B formata cu toate elementele de forma f(x), unde x ∈ A. Scrierea uzualaf(x) (sau f x, cand nu este pericol de confuzie) se spune ca este ın notatieprefix, ca ın sin x; exista totusi situatii cand argumentul functiei apare primulx f (notatie infix ), cum ar fi functia factorial n!.

O functie poate fi privita echivalent ca un triplet (A,B, f), unde A siB sunt multimi (nevide) iar f este o submultime (nevida!) a produsuluicartezian A×B ce satisface urmatoarele:

• Pentru orice x ∈ A, exista y ∈ B astfel ıncat (x, y) ∈ f ;

• Daca (x, y) ∈ f si (x, y′) ∈ f , atunci y = y′.

1Matematicianul si filosoful german G. Leibniz (1646 - 1716) este cel care a introdustermenul de ”functie” ın 1692. Tot lui i se datoreaza, printre multe altele, si sistemulnumeric binar, logica simbolica si analiza matematica.

2Acestea vor fi utile la materiile din anii urmatori: de exemplu, la cursul de Paradigmede Programare din anul II, unde vor fi puse bazele calcului Lambda - calculul Lambda estevazut drept contextul teoretic ın Computer Science al descrierii si evaluarii functiilor. Desieste mai mult o abstractie matematica decat un limbaj de programare, calculul lambdaformeaza baza aproape tuturor limbajelor de programare functionale din prezent.

1

CC-Matematica 2 2

In particular, de aici rezulta ca functiile cu domeniu A si codomeniu Bformeaza o multime, notata BA, inclusa ın P(A×B).

De exemplu, orice program cu intrari si iesiri poate fi privit ca o functieI −→ O, unde I este multimea intrarilor valide pentru acel program, iar Oeste multimea iesirilor posibile.Domeniul si codomeniul unei functii sunt adeseori specificate explicit ın limbajele de progra-

mare. De exemplu, ın Java avem asertiunea int floor (float real){. . .}, iar ın Pascal

function floor (x: real): integer. Amandoua fac referire la functia floor (parte

ıntreaga) si precizeaza ca domeniul acesteia este multimea numerelor reale, iar codomeniul

multimea ıntregilor.

Doua functii sunt egale daca si numai daca au acelasi domeniu, acelasicodomeniu si aceeasi regula de corespondenta. De exemplu, functiilef : R −→ R, f(x) = x2 si g : R −→ [0,∞), g(x) = x2 nu coincid, chiar dacasunt date prin aceeasi formula si au aceeasi imagine, ıntrucat codomeniilesunt diferite.

Pentru orice multime nevida A, exista o functie speciala, numita functiaidentitate si notata 1A : A −→ A, care duce fiecare element din A ın el ınsusi,adica 1A(x) = x, ∀x ∈ A.

Pana acum am considerat functii pentru care atat domeniul cat si codome-niul erau nevide. Convenim ca pentru orice multime A exista o singurafunctie de la multimea vida la A, notata !A : ∅ −→ A. Intuitiv, aceastafunctie nu face nimic, ıntrucat multimea vida nu are elemente si deci nuavem ce corespondenta sa stabilim De asemenea, vom conveni ca nu existanici o functie cu codomeniul vid, exceptie facand functia identica a multimiivide.

Exercitiul I.2.1.1. Fie A si B doua multimi, cu B nevida. Aratati ca existacel putin o functie A −→ B; altfel spus, ca multimea BA este nevida.

Este util de retinut ca doua functii cu acelasi domeniu ce iau valorinumerice (de exemplu ın R), pot fi adunate sau ınmultite punctual, prin(f + g)(x) = f(x) + g(x), respectiv (fg)(x) = f(x)g(x).

Daca domeniul de definitie al unei functii este un produs cartezian demultimi, spunem ca functia are argument multiplu: de exemplu, adunareanumerelor naturale este o functie binara (primeste doua argumente):add : N× N −→ N, add(m,n) = m+ n.

Incluziunea si restrictia. Fie A o multime si X o submultime a sa. Atuncifunctia ιX : X −→ A, ιX(x) = x se numeste functia de incluziune a lui Xın A. A nu se confunda cu functia identica a multimii X, 1X : X −→ X,deoarece nu au acelasi codomeniu! Uneori se mai noteaza si prin X ↪→ A, faraa mai specifica numele functiei. Vom ıntalni ulterior ın functia de incluziune,

CC-Matematica 2 3

unde vom vedea ca joaca un rol important ın construc tia substructuriloralgebrice. Daca f : A −→ B este o functie si X ⊆ A, numim restrictia lui fla X functia notata f |X : X −→ B si data de f |X(x) = f(x), pentru oricex ∈ X.

Exemplul I.2.1.2. (i) Functia factorial. Atat domeniul cat si codome-niul functiei factorial sunt multimea numerelor naturale, iar legea decorespondenta este n 7→ n! = 1 · 2 · . . . n pentru n ≥ 1 si 0 7→ 0! = 1.Functia factorial poate fi definita si recursiv, prin

n! =

{1, daca n = 0

(n− 1)! · n, daca n ≥ 1

In combinatorica, n! este numarul de permutari distincte ale uneimultimi cu n elemente. In analiza matematica, functia factorial poatefi extinsa la toate numerele reale pozitive, obtinandu-se astfel functiaGamma a lui Euler,

Γ(x) =

∫ ∞0

tx−1e−tdt

(ii) Functia binomiala N× N −→ N, data de(n

k

)=

{n(n−1)...(n−k+1)

k!pentru k ≤ n

0 ın caz contrar

Se mai ıntalneste si sub notatia Ckn, dar doar pentru k ≤ n. In combi-

natorica,(nk

)reprezinta numarul de submultimi cu k elemente dintr-o

multime cu n elemente.

(iii) Functia parte ıntreaga. Partea ıntreaga [x] a unui numar real x esteıntregul cel mai mare ce nu depaseste pe x. Din definitie, avem [x] ∈ Zsi [x] ≤ x < [x] + 1. Diferenta {x} = x − [x] se numeste parteafractionara a numarului x; {x} ∈ [0, 1) si {−} : R −→ [0, 1), x 7→ {x}este o functie periodica cu perioada 1.

(iv) Permutari ciclice. Fie n = {0, 1, 2, . . . , n − 1} si σ : n −→ n functiadata de

0 7→ 1, 1 7→ 2, 2 7→ 3, . . . , n− 2 7→ n− 1, n− 1 7→ 0

Aceasta duce fiecare k ∈ n ın succesorul sau k+ 1, mai putin pe n− 1,caruia i se asociaza imaginea 0.

CC-Matematica 2 4

(v) Cel mai mare divizor comun. Fiind date doua numere ıntregi nenulem si n, cel mai mare divizor comun al acestora, notat (m,n), este celmai mare numar (natural) care le divide pe amandoua. De exemplu, celmai mare divizor comun al numerelor 12 si 18 este 6, iar cel mai maredivizor comun al numerelor −36 si −56 este 4. Reamintim urmatoareleproprietati:

(a) (m,n) = (n,m) = (m,−n).

(b) (m,n) = (n,m− nq) pentru orice q ∈ Z.

(c) (m,n) = d⇐⇒ (∃)k, l ∈ Z astfel ıncat km+ ln = d.

(d) d|mn si (d,m) = 1 implica d|n.

Cel mai mare divizor comun apare astfel ca o functie cu doua argu-mente, cmmdc : Z∗ × Z∗ −→ Z∗.

(vi) Functia caracteristica. Consideram o multime universala M , care vacontine toate multimile cu care vom lucra. Pentru A ⊆ M , functiacaracteristica asociata multimii A este χA : M −→ {0, 1},

χA(x) =

{1, daca x ∈ A0, daca x /∈ A

Reamintim ca am introdus notatia exponentiala pentru multimeafunctiilor cu domeniu si codomeniu dat; astfel, putem scrie χA ∈ 2M

(I.2.1.6.(v)), pentru orice A ⊆M . Mai mult chiar, corespondenta A 7→χA defineste o functie P(M) −→ 2M , ce asociaza fiecarei submultimiA functia sa caracteristica χA. Vom reveni ulterior asupra acesteia.

Currying3. Sa presupunem ca lucram cu o functie al carui domeniu esteun produs cartezian, f : A × B −→ C, adica cu o functie de mai multevariabile sau cu argument multiplu. Daca fixam primul argument x ∈ A,putem construi o functie fx : B −→ C prin fx(y) = f(x, y). Deci obtinem ofunctie A −→ CB, x 7→ fx, adica un element din (CB)A. Am stabilit astfel ocorespondenta numita curry ıntre multimea functiilor CA×B de la produsulcartezian A×B ın C, si multimea functiilor (CB)A, definita prin

curry : CA×B −→ (CB)A

3Aceasta tehnica a fost introdusa de M. Schonfinkel dupa numele matematicianului silogicianului Haskell B. Curry; ea a aparut datorita faptului ca λ-calculul are numai functiide un singur argument. O functie avand mai multe argumente se exprima, cu ajutorulacestei tehnici, ca o functie avand un singur argument si care ia valori tot functii.

CC-Matematica 2 5

curry(f)(x) = fx sau echivalent f 7→ (x 7→ fx)

Aceasta corespondenta transforma deci functiile de mai multe argumente ınfunctii ce primesc argumentele pe rand (succesiv).

I.2.2 Compunerea functiilor.

Fie f : A −→ B si g : B −→ C doua functii. Definim compunerea lui gcu f ca fiind functia g ◦ f : A −→ C, data de regula de corespondenta

(g ◦ f)(x) = g(f(x))

Prin utilizarea diagramelor Venn, putem vizualiza un exemplu de compunerea functiilor:

Figura 1: g ◦ f

Trebuie sa subliniem ca nu oricare doua functii f si g pot fi compuse;pentru aceasta, codomeniul lui f trebuie sa coincida cu domeniul lui g. Inacest caz, relatia dintre cele trei functii, f , g, si g ◦ f , poate fi vizualizata cuajutorul diagramei de mai jos:

Af //

g◦f ��@@@

@@@@

B

g

��C

Intuitiv, putem ajunge de la A la C ın doua moduri, cu acelasi rezultat: fieın doi pasi, mai ıntai aplicand f apoi g, fie ıntr-un singur pas cu functia g◦f .

Exemplul I.2.2.1. De exemplu, daca f : A −→ B este o functie si X ⊆ A,atunci restrictia lui f la X este o functie compusa: f |X = f ◦ ιX . Un alt

CC-Matematica 2 6

exemplu de functie compusa se obtine astfel: pentru o functie f : A −→ B,notam prin f : A −→ Imf functia avand acelasi domeniu A si aceeasi regulade corespondenta, f(x) = f(x). Atunci functia de la care am plecat se poatescrie ca o compunere astfel: f = ιImf ◦ f .

Propozitia I.2.2.2. Operatia de compunere a functiilor are urmatoarele pro-prietati:

(i) Este asociativa:(h ◦ g) ◦ f = h ◦ (g ◦ f)

pentru orice trei functii Af−→ B

g−→ Ch−→ D.

(ii) Este invarianta la compunerea cu functia identitate:

f ◦ 1A = f si 1B ◦ f = f

pentru orice functie Af−→ B.

De retinut ınsa ca ordinea ın care se efectueaza compunerea g ◦ f este im-portanta: mai ıntai f , apoi g. Nu ıntotdeauna putem efectua compunereaın orice ordine: pentru aceasta, ar trebui ca domeniul lui f sa coincida cucodomeniul lui g si invers, ca domeniul lui g sa coincida cu codomeniul luif . Totusi, nici ın acesta situatie nu putem avea neaparat g ◦ f = f ◦ g: fiede exemplu functiile f, g : N −→ N, f(x) = 3x + 1, g(x) = 3x + 2. Atunci(g ◦ f)(x) = g(f(x)) = 3f(x) + 2 = 9x+ 5, ın timp ce (f ◦ g)(x) = f(g(x)) =3g(x) + 1 = 9x+ 7.

Exemplul I.2.2.3. Fie A, B doua multimi si A × B produsul cartezianal acestora. Consideram functiile outA : A × B −→ A, outA(x, y) = x sioutB : A × B −→ B, outB(x, y) = y. Acestea se numesc proiectii: fiecareiperechi ordonate ıi asociem prima, respectiv a doua componenta. Fie acumC o multime, ımpreuna cu doua functii f : C −→ A si g : C −→ B. Aratatica exista o unica functie h : C −→ A × B astfel ıncat outA ◦ h = f sioutB ◦ h = g, ca ın diagrama de mai jos:

Cf

{{wwwwwwwwwg

##GGGGGGGGG

h��

A A×BoutAoo outB // B

CC-Matematica 2 7

I.2.3 Functii injective, surjective, bijective

O functie f : A −→ B se numeste injectiva, daca pentru orice x 6= x′,unde x, x′ ∈ A, rezulta f(x) 6= f(x′) ın B. Altfel spus, o functie injectivaeste o functie care duce obiecte diferite din domeniu ın imagini diferite dincodomeniu. Echivalent, daca functia duce doua obiecte ın aceeasi imagine,atunci obiectele coincid:

f(x) = f(x′) =⇒ x = x′

De exemplu, functia de incluziune este ıntotdeauna injectiva.O functie f : A −→ B se numeste surjectiva, cand imaginea sa coincide

cu codomeniul, Imf = B, adica pentru orice y ∈ B, exista x ∈ A astfel ıncatf(x) = y. De exemplu, fiecarei functii f : A −→ B ıi putem asocia o functiesurjectiva, si anume f (Exemplul I.2.2.1), prin restrictia codomeniului laimaginea functiei.

Exercitiul I.2.3.1. Aratati ca orice functie f : A −→ B se poate descom-pune sub forma f = g ◦ h, unde g este o functie injectiva si h este o functiesurjectiva.

In sfarsit, spunem ca o functie este bijectiva daca este simultan injectiva sisurjectiva. Cel mai simplu exemplu de functie bijectiva este functia identitatea unei multimi, 1A : A −→ A,1A(x) = x (demonstrati!). De retinut ınsa cao functie injectiva nu este neaparat surjectiva sau invers.

Exercitiul I.2.3.2. Fie f : A −→ B si g : B −→ C doua functii. Aratatica:

(i) Daca f si g sunt injective, atunci si g ◦ f este injectiva.

(ii) Daca g ◦ f este injectiva, atunci f este injectiva. Dati un exemplu ıncare g ◦ f este injectiva, dar g nu este.

(iii) Daca f si g sunt surjective, atunci si g ◦ f este surjectiva.

(iv) Daca g ◦ f este surjectiva, atunci g este surjectiva. Dati un exemplu ıncare g ◦ f este surjectiva, dar f nu este.

(v) Daca f si g sunt bijective, atunci si g ◦ f este bijectiva.

(vi) Daca g ◦ f este bijectiva, atunci f este injectiva si g este surjectiva.Dati un exemplu ın care g ◦ f este bijectiva, dar f si g nu sunt.

Exercitiul I.2.3.3. Fie f : A −→ B o functie. Aratati ca urmatoareleafirmatii sunt echivalente:

CC-Matematica 2 8

(i) f este injectiva.

(ii) Pentru orice functii g, h : C −→ A astfel ıncat f ◦ g = f ◦ h, rezultag = h.

Exercitiul I.2.3.4. Fie f : A −→ B o functie. Aratati ca urmatoareleafirmatii sunt echivalente:

(i) f este surjectiva.

(ii) Pentru orice functii g, h : B −→ C astfel ıncat g ◦ f = h ◦ f , rezultag = h.

Exemplul I.2.3.5. Nu exista nici o functie surjectiva f : A −→ P(A),pentru orice multime A. Intr-adevar, daca o asemenea functie exista, fieW = {x ∈ A | x /∈ f(x)} ⊆ A}. Cum f este surjectiva, putem gasi x ∈ A cuf(x) = W . Daca x ∈ W , rezulta x /∈ f(x) = W , fals. Deci x /∈ W = f(x),adica x ∈ W , contradictie. De remarcat ınsa ca o surjectie g : P(A) −→ Apoate fi construita ıntotdeauna, daca A este nevida; de exemplu, fie x0 ∈ Afixat si functia g definita astfel: g({x}) = x si g(X) = x0 pentru submultimiX ⊆ A care contin mai mult de un element sau sunt vide.

I.2.4 Functii inversabile. Functia inversa

Fie A,B doua multimi nevide si functiile f : A −→ B, g : B −→ A.Spunem ca g este inversa la stanga pentru f (sau ca f este inversa la dreaptapentru g) daca g ◦ f = 1A. Daca g ◦ f = 1A si f ◦ g = 1B, vom spune ca feste inversabila si ca g este inversa lui f . Prin simetrie, rezulta ca ın acestcaz si g este inversabila, cu inversa f .

Teorema I.2.4.1. Fie f : A −→ B o functie. Atunci:

(i) f este inversabila la stanga ⇐⇒ f este injectiva.

(ii) f este inversabila la dreapta ⇐⇒ f este surjectiva.

(iii) f este inversabila la stanga si la dreapta ⇐⇒ f este bijectiva.

Demonstratie. (i) Fie f inversabila la stanga, cu inversa g, si x, x′ ∈ Aastfel ıncat f(x) = f(x′). Atunci

x = 1A(x) = g(f(x)) = g(f(x′)) = 1A(x′) = x′

Deci pentru f(x) = f(x′) avem x = x′, de unde rezulta ca f este injectiva.Reciproc, sa presupunem ca f este o injectie. Vom construi o functie g :

CC-Matematica 2 9

B −→ A inversa la stanga pentru f . Alegem x0 ∈ A si ıl consideram fixat sidefinim g prin

g(y) =

{x daca exista x ∈ A astfel ıncat y = f(x)

x0 ın caz contrar

Injectivitatea lui f ne asigura ca g este bine definita: daca pentru y ∈ B arexista x, x′ ∈ A cu y = f(x) = f(x′), atunci x = x′. Rezulta (g ◦ f)(x) =g(f(x)) = x pentru orice x ∈ A. Deci g ◦ f = 1A, adica f este inversabila lastanga.

(ii) Daca f este inversabila la dreapta cu inversa h : B −→ A, atuncipentru orice y ∈ B avem y = 1B = f(h(y)), deci y este imaginea prin fa elementului x = h(y) din A. Rezulta f surjectie. Invers, daca f estesurjectiva, orice y ∈ B este imaginea a cel putin un element x ∈ A. Alegemcate un asemenea element xy cu f(xy) = y pentru y ∈ B si construim functiah : B −→ A prin h(y) = xy. Atunci f(h(y)) = f(xy) = y, deci f◦h = 1B.

De remarcat ca inversa la stanga (respectiv dreapta), daca exista, nu esteneaparat unica! De exemplu, fie f : {1, 2, 3} −→ {1, 2, 3, 4, 5}, data prin

1 7→ 2, 2 7→ 3, 3 7→ 4

Rezulta imediat ca f e o injectie. Fie functiile g1, g2 : {1, 2, 3, 4, 5} −→{1, 2, 3}, definite prin g1(1) = 1, g1(2) = 1, g1(3) = 2, g1(4) = 3, g1(5) = 3,respectiv g1(1) = 2, g1(2) = 1, g1(3) = 2, g1(4) = 3, g1(5) = 2. Atunci g1si g2 sunt inverse la stanga pentru f , dupa cum se poate observa efectuandcompunerea, dar g1 6= g2.

Existenta unei inverse la stanga sau la dreapta pentru o functie nu garan-teaza si unicitatea acesteia. Dar, daca exista simultan ambele, atunci:

Propozitia I.2.4.2. O functie f este bijectiva daca si numai daca este in-versabila la stanga (cu inversa la stanga g) si inversabila la dreapta (cu in-versa la dreapta h). In aceasta situatie, cele doua inverse coincid, g = h.

Demonstratie. Prima afirmatie este consecinta imediata a Teoremei prece-dente, daca tinem cont ca o functie bijectiva este o functie injectiva si sur-jectiva ın acelasi timp. Apoi avem

g = g ◦ 1B = g ◦ (f ◦ h) = (g ◦ f) ◦ h = 1A ◦ h = h

de unde rezulta ca cele doua inverse coincid.

CC-Matematica 2 10

Inversa comuna la stanga si la dreapta a unei functii bijective se noteazacu f−1; ın particular f−1 este de asemenea bijectiva, cu inversa (f−1)−1 = f .

A nu se confunda functia f−1 cu functia 1f, care asociaza fiecarui element

din domeniul de definitie valoarea 1f(x)

(aceasta din urma avand sens doar

pentru functiile pentru care f(x) este un numar real nenul).

I.2.5 Functii partiale.

In Computer Science, exista cazuri cand un program intra ıntr-o bucla saureturneaza mesaj de eroare, la introducerea unui input incorect. Similar, ınmatematica ne-am ıntalnit adesea cu functii definite numai pe o submultimea multimii numerelor reale, cum ar fi frac1x,

√x, sau arcsinx. Pentru a

putea studia aceste situatii, introducem notiunea de functie partiala.Fiind date doua multimi A si B, o functie partiala de la A la B este o

functie f : X ⊆ A −→ B, avand domeniul o submultime a lui A si codome-niul B. Vom spune ca pentru elementele din A care nu apartin domeniuluide definitie X, functia f nu este definita. Cand X = A, se mai spune ca feste o functie totala.Compunerea functiilor partiale. Fie f : X ⊆ A −→ B si g : Y ⊆B −→ C doua functii partiale. Definim compunerea g ◦ f ca fiind o functiepartiala A −→ C, astfel: pentru x ∈ A, daca f(x) e definit si f(x) ∈ Y ,prin (g ◦ f)(x) = g(f(x)); ın caz contrar. spunem ca g ◦ f(x) nu este definit.Compunerea functiilor partiale este asociativa, cu element neutru functiaidentitate.

Exercitiul I.2.5.1. Aratati ca o functie partiala f : X ⊆ A −→ B poate fivazuta ca o functie totala f : A −→ B ∪ {∗}, unde ∗ este un element ce nuapartine lui B, iar

f(x) =

{f(x) daca x ∈ X∗ x /∈ X

Curs 3

I.3 Relatii binare

I.3.1 Definitii; matricea asociata unei relatii

Definitia I.3.1.1. Fie X si Y doua multimi. O relatie binara R ıntre Xsi Y este o submultime a produsului cartezian R ⊆ X × Y (X se numestedomeniul relatiei si Y codomeniul).

Pentru (x, y) ∈ R mai scriem si xRy. Daca X = Y spunem ca R este orelatie pe multimea X.Multimea relatiilor ıntre X si Y este Rel(X, Y ) = P(X × Y ) (ın particular,daca |X| = m si |Y | = n, atunci |Rel(X, Y )| = 2mn).

Exemplul I.3.1.2. (i) Fie X multimea studentilor din seria CC , Y multimealiterelor din alfabetul latin si relatia R data prin xRy ⇐⇒ litera y ∈ Yse gaseste ın numele de familie al studentului x ∈ X.

(ii) Fie X o multime nevida. Pe X putem defini ıntotdeauna trei relatii,numite canonice, dupa cum urmeaza:

• ∅ - relatia vida.

• X ×X - relatia universala.

• EX = {(x, x)|x ∈ X} - relatia de egalitate.

(iii) Fie f : X −→ Y o functie, atunci Gf = {(x, f(x)) | x ∈ X} ⊆X × Y este o relatie (graficul functiei f). La fel, daca f : A ⊆ X −→Y este o functie partiala, putem construi relatia asociata prin Gf =

{(x, f(x)) | x ∈ A} ⊆ A × Y ⊆ X × Y . In acest sens, putem spuneca functiile partiale generalizeaza functiile, iar relatiile generalizeazafunctiile partiale.

(iv) Pe multimea numerelor reale R consideram relatia xRy ⇐⇒ x2 + y2 =4. Atunci perechea (x, y) este ın relatia R daca si numai daca punctulde coordonate (x, y) apartine cercului cu centrul ın origine si raza 2.

1

CC-Matematica 2 2

Fie X, Y doua multimi finite, cu X = {x1, x2, ..., xm} si Y = {y1, y2, ..., yn}.Fiecarei relatii R ⊆ X × Y ıi putem asocia o matrice MR = (aij)i=1,m,j=1,n,unde

aij =

{1 , daca xiRyj

0 , ın caz contrar

De exemplu, pentru cele trei relatii canonice pe o multime X finita cu nelemente, se verifica usor ca matricile asociate sunt M∅ = 0n, MX×X =1 . . . 1

......

1 . . . 1

si MEX= In. De asemenea, daca f : X −→ Y este o functie,

atunci matricea asociata relatiei Rf va contine pe fiecare linie o singuravaloare 1 (corespunzatoare elementului y = f(x)) si restul 0.

Exemplul I.3.1.3. Fie X = {1, 2, 3, 4}, Y = {1, 2, 3} si xRy ⇐⇒ 3 | 2x−y.

Atunci matricea asociata va fi MR =

0 1 01 0 00 0 10 1 0

.

I.3.2 Operatii cu relatii

Fie R,R′ ⊆ X × Y . Cum relatiile sunt submultimi ale produsului cartezian,au sens notiunile de reuniune, intersectie si complementara, si anume:

(i) Reuniunea x(R ∪R′)y ⇐⇒ xRy sau xR′y.

(ii) Intersectia x(R ∩R′)y ⇐⇒ xRy si xR′y.

(iii) Complementara xRcy ⇐⇒ x 6 R y

Corespunzator vom avea si operatii cu matricile asociate (pentru multimiX, Y finite!), cu observatia ca toate calculele se fac ın B = ({0, 1},∧,∨,¬)

In plus fata de operatiile mentionate mai sus, putem asocia fiecarei relatiiR relatia opusa Rop ⊆ Y × X, definita prin yRopx ⇐⇒ xRy. (Ce se poatespune daca R si Rop sunt functii?)

Compunerea relatiilor. Fie R ⊆ X × Y , R′ ⊆ Y × Z. Definim com-punerea relatiilorR siR′ prin x(R′◦R)z ⇐⇒ ∃y ∈ Y, astfel ıncat xRy si yR′z.Pentru multimi finite, compunerea relatiilor revine la ınmultirea matricilorasociate (tot ın B).Proprietati ale compunerii relatiilor

CC-Matematica 2 3

(i) Compunerea relatiilor este asociativa: daca R ⊆ X × Y , R′ ⊆ Y × Z,R′′ ⊆ Z × U , atunci (R′′ ◦R′) ◦R = R′′ ◦ (R′ ◦R).

(ii) Compunerea cu relatia de egalitate: daca R ⊆ X × Y si EX , respectivEY sunt relatiile de egalitate pe multimile X si Y , atunci R ◦ EX =EY ◦R = R.

(iii) (R′ ◦R)op = (R′)op ◦Rop.

Propozitia I.3.2.1. Multimea relatiilor pe X formeaza un monoid (cu involutie)(Rel(X), ◦, EX , (−)op).

Proprietati ale relatiilor. Fie R o relatie pe o multime X. Spunem caR este:

(i) Reflexiva, daca xRx, ∀x ∈ X.

(ii) Simetrica, daca xRy ⇐⇒ yRx, ∀x, y ∈ X.

(iii) Antisimetrica, daca xRy, yRx =⇒ x = y.

(iv) Tranzitiva, daca xRy, yRz =⇒ xRz.

Exemplul I.3.2.2. (i) Pe X = P(M), relatia de incluziune R =⊆ estereflexiva, antisimetrica si tranzitiva.

(ii) Pentru orice multime X, relatia R = {(x, y) | x 6= y} este simetrica,dar nu reflexiva sau tranzitiva.

Observatia I.3.2.3. (i) R reflexiva⇐⇒ EX ⊆ R⇐⇒ EX∩R = EX ⇐⇒EX ∪R = R.

(ii) R simetrica ⇐⇒ R = Rop.

(iii) R antisimetrica ⇐⇒ R ∩Rop ⊆ EX .

(iv) R tranzitiva ⇐⇒ R2 ⊆ R.

Exercitiul I.3.2.4. (i) R simetrica =⇒ Rc simetrica.

(ii) Fie X o multime cu n elemente. Cate relatii reflexive / simetrice /antisimetrice / de echivalenta exista pe multimea X?

CC-Matematica 2 4

I.3.3 Relatii de ordine

Definitia I.3.3.1. Fie X o multime. O relatie R se numeste relatie deordine pe X daca este reflexiva, antisimetrica si tranzitiva. Perechea (X,R)se numeste multime partial ordonata (poset).

In continuare, vom nota relatia de ordine cu ≤ ın loc de R.

Exemplul I.3.3.2. (i) Relatia de egalitate EX este o relatie de ordine peorice multime X.

(ii) Multimea numerelor reale cu relatia de ordine uzuala (R,≤), multimeanumerelor naturale nenule cu relatia de divizibilitate (N∗, |), multimeapartilor unei multimi cu relatia de incluziune (P(M),⊆) sunt exemplede poseturi pe care le-am ıntalnit ınca din liceu.

Fie (X,≤) si (Y,≤) doua poseturi. O functie f : X −→ Y se numestemorfism de poseturi daca pentru orice x, x′ ∈ X cu x ≤ x′, avem f(x) ≤ f(x′)(deci un morfism de poseturi este o functie care pastreaza relatia de ordine;este o functie monotona). Spunem ca doua poseturi (X,≤) si (Y,≤) suntizomorfe daca exista doua morfisme f : X −→ Y , g : Y −→ X astfel ıncatf ◦ g = 1Y , g ◦ f = 1X . In particular, rezulta f, g bijective si g = f−1.

Exercitiul I.3.3.3. Daca f : X −→ Y este un morfism de poseturi bijectiv,rezulta ca si inversa sa f−1 este un morfism de poseturi?

Fie (X,≤) un poset. Atunci exista mai multe relatii asociate relatiei deordine pe X: x ≥ y (opusa relatiei initiale), x = y, x < y (definita prinx ≤ y si x 6= y), x > y (opusa relatiei precedente), sau chiar relatia ”x,yincomparabile” (formal, aceasta este complementara reuniunii relatiilor ≤,≥, =, <, >). Pe langa acestea vom introduce acum o noua relatie, relatia deacoperire:

Definitia I.3.3.4. Fie (X,≤) un poset si x, y ∈ X, x 6= y. Spunem ca x esteacoperit de y daca nu exista nici un element z ∈ X astfel ıncat x < z < y.Vom nota ın acest caz x ≺ y si vom spune ca x este predecesorul lui y,respectiv ca y este succesorul lui x.

De exemplu, pentru posetul numerelor naturale cu relatia uzuala de or-dine, avem x ≺ y ⇐⇒ x+ 1 = y.

Relatia de acoperire astfel definita nu este reflexiva, simetrica, antisimet-rica sau tranzitiva, dar are o proprietate mult mai importanta: determina ınmod unic relatia de ordine pe multimi finite, dupa cum urmeaza:

CC-Matematica 2 5

Propozitia I.3.3.5. Fie (X,≤) un poset finit si x, y ∈ X astfel ıncat x < y.Atunci exista cel putin un lant (finit) x = x0 < x1.... < xn = y astfel ıncatxi−1 ≺ xi,∀i = 1, n.

Demonstratie. Prin inductie dupa numarul de elemente al multimii{z ∈ X | x < z < y} (cum X este o multime finita, rezulta ca si multimea{z ∈ X | x < z < y} ⊆ X va fi finita). Daca n = 0, nu exista z ast-fel ıncat x < z < y, deci x ≺ y si luam x = x0 < x1 = y. Sa pre-supunem afirmatia adevarata pentru orice doua elemente x, y pentru careexista cel mult n elemente z cu x < z < y. Fie acum x, y ∈ X cu|{z ∈ X | x < z < y}| = n + 1 si fixam a ∈ X un astfel de element(deci x < a < y). Atunci {w ∈ X | x < w < a} are cel mult n elemente(este inclusa strict ın {a | x < a < y}, pentru ca a < y); analog si multimea{t ∈ X | a < t < y}. Rezulta din ipoteza de inductie ca exista doua lanturix = x0 < . . . < xn = a si a = y0 < . . . < yn = y ın care xi−1 ≺ xi,∀i = 1, nsi yj−1 ≺ yj,∀j = 1, n. Deci x = x0 < . . . < xn = a = y0 < . . . < yn = yverifica cerinta problemei. Conform inductiei matematice, rezulta afirmatiaadevarata pentru orice n ≥ 0.

Observatia I.3.3.6. Din Propozitia precedenta rezulta ca relatia de acoperiredetermina ın mod unic relatie de ordine pe un poset finit: x ≤ y daca si numaidaca x = y sau exista un lant finit x = x0 ≺ ... ≺ xn = y.

Cu ajutorul relatiei de acoperire, putem reprezenta un poset finit printr-un graf orientat ın care nodurile sunt elementele posetului; ıntre doua nodurix si y exista un arc x −→ y daca si numai daca x ≺ y. Atunci x ≤ y dacaexista un drum ce ıncepe ın x si se termina ın y. Aceasta reprezentare aposetului se numeste diagrama Hasse. De exemplu, diagrama Hasse asociataposetului (P(0, 1, 2),⊆) este:

{0, 1, 2}

{0, 1}

99ttttttttt{0, 2}

OO

{1, 2}

eeJJJJJJJJJ

{0}

OO 99tttttttttt{1}

eeJJJJJJJJJJ

99tttttttttt{2}

eeJJJJJJJJJJ

OO

∅

eeKKKKKKKKKKKK

OO 99ssssssssssss

(I.3.1)

Definitia I.3.3.7. Fie (X,≤) un poset. Un element x ∈ X se numeste

CC-Matematica 2 6

(i) Minim (sau cel mai mic element) daca pentru orice y ∈ X, x ≤ y.

(ii) Maxim (sau cel mai mare element) daca pentru orice y ∈ X, x ≥ y.

(iii) Element minimal daca nu exista y ∈ X astfel ıncat y ≤ x.

(iv) Element maximal daca nu exista y ∈ X astfel ıncat y ≥ x.

Minimul sau maximul nu exista neaparat, dar daca exista, sunt unice: sapresupunem ca exista doua minime x1 si x2 ıntr-un poset (X,≤). Cum x1este minim, rezulta x1 ≤ y,∀y ∈ X. In particular, x1 ≤ x2. Analog avemx2 ≤ x1, deci x1 = x2. La fel rezulta si unicitatea maximului. De exemplu,orice interval deschis (a, b), vazut ca poset ımpreuna cu relatia de ordineuzuala, nu are minim si nici maxim.

De asemenea, ıntr-un poset (X,≤) elementele minimale sau maximalepot sa existe sau nu: daca relatia de oridne este egalitatea EX , atunci toateelementele sunt minimale si maximale. In posetul (P(M) \ {∅,M},⊆), ele-mente minimale sunt toate submultimile cu un singur element, iar elementemaximale sunt complementarele acestora. Rezulta ca elementele minimale(maximale) nu sunt neaparat unice. Pe de alta parte, (Z,≤) nu are nicielemente minimale nici maximale. Daca ıntr-un poset exista minim (respec-tiv maxim), atunci acesta este si element minimal (respectiv maximal), darreciproc este fals (de ce?).

Propozitia I.3.3.8. Fie (X,≤) un poset finit nevid. Atunci exista cel putinun element minimal ın X (respectiv maximal).

Demonstratie. Presupunem prin absurd ca nu exista nici un elementminimal. Fie atunci x0 ∈ X (care exista pentru ca X este nevida). Cumx0 nu este minimal, exista x1 < x0. Conform presupunerii facute, nici x1 nueste minimal, deci exista x2 < x1 < x0, etc. Obtinem astfel un lant infinit... < x2 < x1 < x0 de elemente distincte din X. Dar X este o multimefinita, contradictie. Deci presupunerea facuta este falsa si exista elementeminimale. Pentru cele maximale, rationamentul decurge analog.

Definitia I.3.3.9. Spunem ca un poset (X,≤) este o multime total ordonatadaca pentru orice x, y ∈ X, x ≤ y sau y ≤ x.

Exercitiul I.3.3.10. Cum arata diagrama Hasse asociata unei multimi totalordonate finite?

Exemplul I.3.3.11. (i) (X,EX) nu este total ordonata, pentru orice Xnevida.

CC-Matematica 2 7

(ii) (R,≤) este total ordonata.

(iii) (P(M),⊆) nu este total ordonata.

Reamintim ca pentru R1, R2 relatii pe multimea X, R1 ⊆ R2 daca sinumai daca xR1y implica xR2y, ∀x, y ∈ X.

Propozitia I.3.3.12 (Sortare topologica). Fie (X,≤) un poset finit nevid.Atunci exista R o relatie de ordine totala pe X care extinde relatia initiala,adica ≤⊆ R.

Demonstratie. Fie x0 ∈ X un element minimal (care exista conformPropozitiei precedente. Atunci (X \ {x0},≤) ramane un poset finit. Dacaeste vid, am terminat. Posetul contine doar un singur element, compa-rabil cu el ınsusi (orice relatie de ordine este reflexiva). In caz contrar,exista x1 ∈ X \ {x0} un element minimal. Continuam procedeul. FieX \ {x0, x1} = ∅, caz ın care ne oprim, fie gasim un element minimal x2ın X \ {x0}, etc. Cum X este finita, dupa un numar finit de pasi am epuizattoate elementele multimii X si ne oprim. Am obtinut astfel o enumerare atuturor elementelor; fie ≺ relatia corespunzatoare, x0 ≺ x1, x1 ≺ x2, etc. siluam relatia de ordine R a carei relatie de acoperire este exact ≺. Atunci Reste relatie de ordine totala prin constructie.

Dacax ≤ y, atunci y e ales ca element minimal dupa ce l-am ales deja pex (altfel y nu ar mai fi minimal). Rezulta deci xRy, deci relatia R extinderelatia initiala de ordine.

Exemplul I.3.3.13. Fie posetul (P({0, 1, 2}),⊆), cu diagrama Hasse din(I.3.1). Aplicand algoritmul de mai sus, obtinem ordinea totala astfel:

(i) Multimea vida este minim, deci si element mimimal.

(ii) Dupa ındepartarea multimii vide, raman trei elemente minimale: {0},{1}, {2}. Alegem de exemplu pe {0}.

(iii) In multimea ramasa, alegem dintre elementele minimale {1}si {2} pe{1}, de exemplu, urmand ca la pasul urmator sa luam pe {2}.

(iv) Am ramas doar cu multimile cu doua sau trei elemente. Elementeminimale sunt acum {0, 1}, {0, 2}, {1, 2}. Reluam operatia de extragerea elementelor minimale ca mai sus.

(v) Ultimul element ramas este {0, 1, 2}.

Am obtinut astfel ordinea totala ∅ ≺ {0} ≺ {1} ≺ {2} ≺ {0, 1} ≺ {0, 2} ≺{1, 2} ≺ {0, 1, 2}, care contine si relatia de incluziune initiala.

CC-Matematica 2 8

I.3.4 Relatii de echivalenta si partitii

Definitia I.3.4.1. Fie X multime nevida. O relatie R pe multimea X senumeste relatie de echivalenta daca este reflexiva, simetrica si tranzitiva.

Exemplul I.3.4.2. (i) Relatia de egalitate pe orice multime X este o relatiede echivalenta (de fapt, este cea mai mica relatie de echivalenta: oricarealta relatie de echivalenta R este ın particular reflexiva, deci EX ≤ R).

(ii) Fie X multimea punctelor din plan si O un punct fixat. Spunem cadoua puncte P si P ′ sunt ın relatia R1, respectiv R2, daca dreptele OPsi OP ′ coincid, respectiv daca segmentele OP si OP ′ au lungimi egale.Atunci R1 si R2 sunt relatii de echivalenta.

Definitia I.3.4.3. O partitie a multimii X este o familie de submultimi(Xi)i∈I (unde I este o multime de indici) astfel ıncat:

(i) Xi ∩Xj = ∅ ⇐⇒ i 6= j;

(ii) ∪i∈IXi = X

Fiecarei partitii (Xi)i∈I a multimii X ıi putem asocia o relatie R, prinxRy ⇐⇒ ∃i ∈ I, x, y ∈ Xi. Atunci R este clar reflexiva si simetrica. Studiemtranzitivitatea: fie x, y, z ∈ X astfel ıncat xRy si yRz. Rezulta ca exista i ∈ Ipentru care x, y ∈ Xi si j ∈ I cu y, z ∈ Xj. Dar daca i 6= j, Xi ∩ Xj = ∅,de unde obligatoriu i = j si x, y, z ∈ Xi. Deci relatia astfel construita este orelatie de echivalenta.

Invers, sa plecam cu R relatie de echivalenta pe X. Pentru x ∈ X, notam[x]R = {y ∈ X|xRy} ⊆ X. [x]R se numeste clasa de echivalenta a elementuluix.

Propozitia I.3.4.4. Cu notatiile de mai sus, au loc urmatoarele:

(i) ∪x∈X [x]R = X

(ii) xRy ⇐⇒ [x]R = [y]R ⇐⇒ [x]R ∩ [y]R 6= ∅.

In particular, rezulta ca familia ([x]R)x∈X formeaza o partitie a multimii X.

Demonstratie. Avem ∪x∈X [x]R = X pentru ca x ∈ [x]R,∀x ∈ X.Fie acum x, y ∈ X cu xRy si z ∈ [x]R. Atunci zRx; dar xRy, de unde zRy,adica z ∈ [y]R. Rezulta [x]R ⊆ [y]R; analog [y]R ⊆ [x]R, de unde [x]R = [y]R.Invers, daca [x]R = [y]R, atunci din x ∈ [x]R = [y]R rezulta yRx si prinsimetrie xRy. Sa aratam acum echivalenta xRy ⇐⇒ [x]R ∩ [y]R 6= ∅. DacaxRy, atunci x ∈ [y]R; dar x ∈ [x]R, de unde x ∈ [x]R ∩ [y]R. Reciproc, fiez ∈ [x]R ∩ [y]R. Rezulta xRz si yRz, de unde prin tranzitivitate xRy.

CC-Matematica 2 9

Consecinta I.3.4.5. Multimea relatiilor de echivalenta pe o multime X esteın bijectie cu multimea partitiilor multimii X.

Demonstratie. Am vazut ca fiecarei partitii ıi corespunde o relatie deechivalenta si invers, fiecarei relatii de echivalenta ıi corespunde o partitie.Vom arata acum ca aceste corespondente sunt inverse una celeilalte.

Fie (Xi)i∈I o partitie si R relatia de echivalenta asociata. Aceasta de-termina partitia ([x]R)x∈X . Vrem sa aratam ca cele doua partitii coincid.Fie deci Xi o multime din partitie si x ∈ Xi fixat. Atunci [x]R ⊆ Xi dinconstructia relatiei de echivalenta si reciproc, daca y ∈ Xi, cum x ∈ Xi,rezulta yRx, deci y ∈ [x]R. Am obtinut astfel Xi = [x]R.

Invers, fie acum R o relatie de echivalenta si partitia ([x]R)x∈X asociata.Notam cu R relatia de echivalenta determinata de acesta partitie: xRy ⇐⇒∃z ∈ X, x, y ∈ [z]R. Dar din tranzitivitate rezulta xRy. Invers, daca xRy,atunci x, y ∈ [x]R, deci xRy si cele doua relatii de echivalenta coincid.

Vom nota X/R = {[x]R | x ∈ X} multimea claselor de echivalenta; X/Rse numeste multimea factor asociata relatiei R. Multimea factor X/R este osubmultime a multimii partilor P(X). Functia πR : X −→ P(X), πR(x) =[x]R are imaginea Imf = X/R; functia surjectiva asociataX −→ X/R, x 7→ [x]R se numeste surjectia canonica si o vom nota totcu πR.

Exercitiul I.3.4.6. Cand πR : X −→ X/R e bijectiva?

Exercitiul I.3.4.7. Determinati multimile factor pentru fiecare dintre relatiilede echivalenta din Exemplul I.3.4.2.

Exemplul I.3.4.8. Fie f : X −→ Y o functie. Definim relatia nucleuasociata functiei f prin xRfx

′ ⇐⇒ f(x) = f(x′). Rezulta imediat ca Rf esteo relatie de echivalenta (daca f este injectiva, atunci Rf = EX). Obtinemurmatoarea diagrama:

Xf //

πR��

Y

X/Rf // Imf

i

OO

ın care i este functia de incluziune.Construim o functie f : X/R −→ Imf prin f([x]R) = f(x); atunci f e

bine definita si injectiva, caci din [x]R = [x′]R rezulta xRfx′, adica f(x) =

f(x′). Mai mult, f este si surjectiva: fie y ∈ Imf . Atunci y = f(x), x ∈ Xsi luam y = f(x) = f([x]R).

Se verifica imediat ca f = i ◦ f ◦ πR. Am scris astfel functia f ca ocompunere dintre o functie injectiva, una bijectiva si una surjectiva.

Curs 4

I.4 Grafuri

I.4.1 Grafuri orientate

Definitia I.4.1.1. Un graf orientat este un tuplu−→G = (N,A, ϕ : A −→

N × N), unde N si A sunt multimi, numite multimea nodurilor, respectivmultimea arcelor, iar ϕ este o functie care asociaza fiecarui arc a ∈ A opereche ordonata de noduri ϕ(a) = (p, q), numite extremitatile arcului a. In

acest caz, vom nota p a // q si spunem ca a este un arc de la nodul p lanodul q.

Un arc pentru care extremitatile coincid se va numi bucla sau ciclu. Ungraf simplu este un graf fara bucle pentru care exista cel mult un arc ıntreoricare doua noduri (ın particular, ϕ este injectiva).

Exemplul I.4.1.2. Dintre grafurile orientate cu patru noduri reprezentatemai jos, doar primele trei sunt simple:

◦ // ◦

��◦

OO

◦oo

◦ // ◦ // ◦ // ◦ ◦ // ◦ // ◦

��◦

__@@@@@@@

◦ // ◦ ((66 ◦

��◦

Definitia I.4.1.3. Spunem ca doua grafuri orientate−→G = (N,A, ϕ) si

−→G′ =

(N ′, A′, ϕ′) sunt izomorfe daca exista doua functii bijective f : N −→ N ′,

g : A −→ A′ astfel ıncat ıntre nodurile p, q ∈ N din graful−→G exista un arc

p a // q daca si numai daca exista arcul f(p)g(a) // f(q) ın

−→G′.

Cu alte cuvinte, diagrama de mai jos

A

ϕ

��

g // N ×Nf×f

��A′

ϕ′ // N ′ ×N ′

1

CC-Matematica 2 2

comuta, adica ϕ′g(a) = (f × f)ϕ(a) pentru orice a ∈ A.In particular, doua grafuri orientate finite (cu numar finit de noduri

si arce) izomorfe au acelasi numar de noduri (respectiv arce). Insa recip-roca este falsa. Pentru a putea da un contraexemplu, introducem mai ıntainotiunea de grad (intern/extern) pentru un graf orientat finit:

(i) Gradul intern al unui nod p ∈ N este numarul arcelor care intra ın p,grd+(p) = |{a ∈ A | ϕ(a) = (q, p), unde q ∈ N}|;

(ii) Gradul extern al unui nod p ∈ N este numarul arcelor care ies din p,grd−(p) = |{a ∈ A | ϕ(a) = (p, q), unde q ∈ N}|

Este usor de vazut ca daca doua grafuri sunt izomorfe, atunci nodurilecorespunzatoare vor avea acelasi grad intern, respectiv extern.Sa consideram acum urmatoarele grafuri:

−→G : ◦1 // ◦2 //

��@@@@@@@ ◦3 // ◦4 // ◦5

◦6 // ◦7 // ◦8

−→G′ : ◦1 // ◦2 // ◦4 // ◦5 // ◦6 // ◦7 // ◦8

◦3

??~~~~~~~

Se vede imediat ca cele doua grafuri au acelasi numar de noduri si de arce.In tabelele de mai jos avem situatia gradelor interne si externe ale nodurilordin fiecare graf:

−→G :

nod grd+ grd−1 0 12 1 23,4,6,7 1 15,8 1 0

−→G′:

nod grd+ grd−1,3 0 12 2 14,5,6,7 1 18 1 0

Cum ın primul graf apare un nod cu gradul extern 2 iar ın al doilea graf nuexista un asemenea nod, rezulta ca cele doua grafuri sunt neizomorfe, desiau acelasi numar de noduri si de arce.

Exercitiul I.4.1.4. Aratati ca ın orice graf orientat finit are loc relatia∑p∈N

grad+(p) =∑p∈N

grad−(p) = |A|

CC-Matematica 2 3

I.4.2 Grafuri orientate si relatii

Fie−→G = (N,A, ϕ) un graf orientat. Acestuia ıi putem asocia o relatie

binara pe multimea nodurilor N , prin

pR−→Gq ⇐⇒ ∃a ∈ A,ϕ(a) = (p, q)

Reciproc, fiecarei relatii binare R pe N ıi corespunde un graf orientat simplu−→GR = (N,AR, ϕR), unde AR = {(p, q) ∈ N ×N | pRq} si ϕR : A −→ N ×Neste functia de incluziune ϕR(p, q) = (p, q).

Observatia I.4.2.1. Fie−→G un graf orientat simplu si R−→

Grelatia asociata.

Atunci graful orientat asociat relatiei R−→G

,−→G (R−→

G) este izomorf cu graful de

la care s-a plecat. Invers, fiind data o relatie R pe o multime N , acesteia

ıi corespunde un graf orientat simplu−→GR ca mai sus, iar relatia asociata

grafului R(−→GR)

este tocmai relatia de la care s-a plecat. Rezulta ca pentru

orice multime N , exista o corespondenta bijectiva ıntre multimea relatiilorbinare pe N si multimea claselor de echivalenta a grafurilor orientate avandmultimea nodurilor N , ın raport cu relatia de izomorfism.

I.4.3 Grafuri neorientate

Definitia I.4.3.1. Un graf orientat este un tuplu−→G = (N,A, ϕ), unde N si

A sunt multimi, numite multimea nodurilor, respectiv multimea arcelor, iarϕ este o functie care asociaza fiecarui arc a ∈ A o pereche neordonata denoduri, numite extremitatile arcului a.

Un graf n-complet este un graf neorientat cu n noduri pentru care existaun arc ıntre oricare doua noduri distincte sale (deci un graf complet va avean(n−1)

2arce).

Exemplul I.4.3.2. (i) Un graf complet cu 4 noduri:

◦

@@@@@@@ ◦

~~~~~~~

◦

◦

��������������

//////////////

(ii) Cubul unitar n-dimensional poate fi vizualizat ca un graf neorientat(este complet?) cu 2n noduri, ın care multimea nodurilor (reprezen-tate ın coordonate carteziene) coincide cu multimea secventelor binare

4

de lungime n. Atunci ıntre doua noduri exista o muchie doar dacasecventele binare corespunzatoare difera exact pe o pozitie. Mai jos amreprezentat cazul n = 3:

◦001 ◦011

◦101���

◦111���

◦000 ◦010

◦100���

◦110���

Exercitiul I.4.3.3. Aratati ca graful de mai sus este izomorf cu graful

��������???? ��������

������������ ����������������

������������

????

�������� ��������Fiecarui graf neorientat G = (N,A, ϕ) ıi putem asocia urmatoarele relatii:

(i) Relatia de incidenta ıntre A si N : aRGp ⇐⇒ p este o extermitate aarcului a;

(ii) Relatia de adiacenta (doar pentru grafuri simple) pe N : pRGq ⇐⇒∃ arc a ∈ A cu extremitatile p, q; RG este o relatie simetrica.

Partea II

Structuri algebrice

II.1 Operatii

II.1.1 Notiuni introductive

Definitia II.1.1.1. Fie A o multime. O operatie pe A este o functieo : Am −→ A, unde m ∈ N.

Am notat Am = A× . . .× A︸ ︷︷ ︸m

, pentru m ≥ 1. Pentru m = 0, vom conveni

ca A0 sa fie o multime cu un singur element. m se numeste aritatea operatiei;pentru m = 2 spunem ca operatia este binara. Exemple de operatii binare

5

sunt adunarea sau ınmultirea numerelor naturale. O operatie de aritate m =1 se numeste operatie unara: ridicarea la patrat a numrelor reale, opusulunui numar reale , negatia sunt exemple de operatii unare. O operatie dearitate m = 0 se mai spune si operatie nulara sau o constanta (o funtie de lao multime cu un singur element ıntr-o multime nevida A este acelasi lucruca un element din A).

DacaA este o multime finita, A = {x1...xn}, pentru reprezentarea operatiilorse folosesc tablele operatiilor. De exemplu, pentru operatii unare scriem

x1 o(x1)...

...xn o(xn)

, iar pentru operatii binare

x1 . . . xj . . . xnx1...

...xi . . . o(xi, xj) . . ....

...xn

Definitia II.1.1.2. Vom numi algebra1 o multime A, ımpreuna cu o familiede operatii pe A (posibil de aritati diferite), (A, (oi)i∈I).

Pentru o multime A pe care exista o operatie o : Am −→ A, o submultimeX ⊆ A se numeste ınchisa la operatia o daca pentru orice x1, ...xm ∈ X,o(x1, ..., xm) ∈ X (ın liceu: parte stabila).

Observatia II.1.1.3. Daca X1, X2 ⊆ A sunt ınchise la operatia o, atuncii X1 ∩ X2 este ınchisa la o. Intr-adevar, fie x1, . . . , xm ∈ X1 ∩ X2. Atuncix1, . . . , xm ∈ Xi ınchisa ∀i = 1, 2, deci =⇒ o(x1, . . . , xm) ∈ Xi,∀i = 1, 2.Rezulta o(x1, . . . , xm) ∈ X1 ∩X2.

O subalgebra B a unei algebre (A, (oi)i∈I) este o submultime B ⊆ Aınchisa la toate operatiile oi, i ∈ I.

II.1.2 Proprietatile operatiilor binare

Fie A o algebra, cu o : A × A −→ A operatie binara pe A. Vom notao(x, y) = x · y, pentru x, y ∈ A.

Spunem ca operatia o este:

(i) Asociativa, daca (x · y) · z = x · (y · z), pentru orice x, y, z ∈ A.

Daca operatia este asociativa, atunci

In particular, putem defini recursiv puteri, prin: x1 = x, xn+1 = xn · x,pentru n ∈ N, unde x ∈ A.

1Termen originar din limba araba, secolul IX.

6

Exercitiul II.1.2.1. Aratati ca pentru orice x ∈ A, avem xm+n =xm · xn, xmn = (xm)n, ∀m,n ∈ N.

(ii) Comutativa, daca x · y = y · x, pentru orice x, y ∈ A.

(iii) Idempotenta, daca x · x = x, pentru orice x ∈ A.

Exemplul II.1.2.2. Reuniunea si intersectia pe P(M) sunt operatii asocia-tive, comutative si idempotente.

Elemente speciale. Reamintim ca o operatie nulara pe o multime nevidaA este complet specificata printr-o constanta (un element) din A. Daca ınplus A este o algebra cu o operatie binara o : A × A −→ A, o(x, y) = x · y,atunci constanta se numeste:

(i) Element neutru (notat e ∈ A), daca e · x = x · e = x, ∀x ∈ A.

Elementul neutru, daca exista, este unic: daca e1, e2 ∈ A sunt elementeneutre, atunci e1 = e1 · e2 = e2, deci e1 = e2. Multimea numerelor nat-urale cu operatia de adunare admite elementul neutru numarul natural0. Dar sunt si algebre cu operatie binara pentru care nu exista elementneutru, cum ar fi (N,−).

(ii) Element zero (element absorbant) si notat 0 ∈ A, daca 0 · x = x · 0 =0,∀x ∈ A.

Elementul zero, daca exista, este unic: daca 01 si 02 sunt elemente zero,atunci 01 = 02 · 01 = 02. De exemplu, multimea vida este element zeropentru operatia de intersectie pe multimea A = P(M). Un alt exempluse obtine pentru A = {0, 1, . . . , n} si operatia x ·y = max(x, y). Atuncin este element zero pentru ca max(x, n) = n,∀x ∈ A.

Fie acum A o algebra cu o operatie binara notata ca mai sus, asociativasi pentru care exista elementul neutru e ∈ A. Fie x ∈ A. Spunem ca x esteinversabil la stanga (dreapta) daca exista un element xs ∈ A (xd ∈ A) astfelıncat xs · x = e (x · xd = e). xs (respectiv xd) se numeste inversul la stanga(la dreapta) al lui x Elementul x se numeste inversabil daca este inversabil lastanga si la dreapta si xs = xd; vom nota atunci cu x−1 inversul elementuluix.

Observatia II.1.2.3. Inversul unui element x, daca exista, este unic (falspentru invers doar la stanga sau doar la dreapta). Sa presupunem ca existax−11 , x−12 inverse pentru x. Atunci

x−11 = x−11 · e = x−11 · (x · x−12 ) = (x−11 · x) · x−12 = e · x−12 = x−12

deci x−11 = x−12 .

7

II.2 Monoizi

II.2.1 Definitie. Proprietati

Fie (A, o : A × A −→ A) o algebra cu o operatie binara. Spunem ca Aeste:

(i) Semigrup, daca operatia este asociativa.

(ii) Monoid, daca operatia este asociativa si admite element neutru.

(iii) Grup, daca operatia este asociativa, admite element neutru si oriceelement din A este inversabil ın raport cu operatia data.

Exemplul II.2.1.1. Exemple de monoizi:

(i) Multimea numerelor naturale ımpreuna cu operatia de adunare (N,+, 0).

(ii) Multimea partilor cu operatia de reuniune (P(X),∪, ∅) sau cu cea deintersectie (P(X),∩, X).

(iii) Multimea functiilor X −→ X, cu compunerea functiilor (XX , ◦,1X).

(iv) Multimea relatiilor binare pe o multime X, ımpreuna cu compunerearelatiilor si cu relatia de egalitate ca element neutru formeaza un monoid(Rel(X), ◦, E).

Definitia II.2.1.2. Fie (M, ·, eM) si (N, ·, eN) doi monoizi. Un morfism demonoizi este o functie f : M −→ N astfel ıncat

f(x · y) = f(x) · f(y),∀x, y ∈M si f(eM) = eN

Un izomorfism de monoizi este un morfism bijectiv.

Fie (M, ·, e) un monoid. Am definit anterior puterile unui element x ∈Mprin recursivitate x1 = x, xn+1 = xn ·x; prin conventie vom considera x0 = e.Un monoid este ciclic daca exista un element x ∈ M astfel ıncat M = {xn |n ∈ N} (spunem ca M este generat de x). Orice monoid ciclic este comutativ(caci xn ·xm = xm ·xn = xn+m). De exemplu, (N,+, 0) este un monoid ciclic,generat de 1.

8

Propozitia II.2.1.3. Orice monoid ciclic infinit e izomorf cu N. Oricemonoid ciclic finit de ordin n (numarul de elemente din monoid) e de forma

e // x // . . . // xm

##FFFFFFFF

xm+k−1

::uuuuuuuuuxm+1

��. . .

OO

. ..

· · ·

unde m+ k = n, m > 0 si xn = xm.

Demonstratie. Fie (M, ·, e) monoid ciclic cu generatorul x. Atunci M ={e, x, x2, . . .}. Daca elementele lui A sunt distincte doua cate doua, functiaf : M −→ N, xn 7→ n este un izomorfism de monoizi. In caz contrar,fie n ∈ N minim astfel ıncat exista m ∈ N, m < n cu xm = xn. AtunciM = {e, x, x2, . . . , xn−1} si pentru i, j ∈ N avem xi · xj = xi+j−n−mk undek ∈ N este cel mai mic numar natural astfel ıncat k > i + j − n, altfel k =0.

Universalitate. Din teorema precedenta rezulta ca (N,+, 0) este un monoidcu proprietati speciale: pentru orice monoid (M, ·, e) si pentru orice x ∈M(sau echivalent pentru orice functie 1 −→M), functia N −→M , n 7→ xn esteun morfism de monoizi. Spunem ca N este monoidul liber cu un generator.

Vom generaliza aceasta situatie ın sectiunea urmatoare

II.2.2 Monoid liber. Alfabet. Limbaj

Definitia II.2.2.1. Fie A o multime. Numim monoidul liber generat de Aun monoid (M, ·, e) pentru care exista o functie ϕ : A −→M cu urmatoareaproprietate: pentru orice monoid (N, ·, e) si pentru orice functie f : A −→ N ,exista un unic morfism de monoizi f : M −→ N astfel ıncat f ◦ ϕ = f , caın diagrama de mai jos:

Aϕ //

f

��

M

f~~||||||||

N

9

Constructia monoidului liber. Fie A o multime, deocamdata nevida(adesea finita in Computer Science). Elementele lui A le vom numi simboluri(sau litere, sau caractere). Multimea A se va numi alfabet. Un string (saucuvant sau lista) din A este un element din An, n ≥ 1, care va fi scrisα = a1a2 . . . an (fara paranteze sau virgula), si vom nota prin | α | = nlungimea string-ului. Convenim ca exista un unic string vid, notat ε, delungime | ε |= 0. Daca un string contine pe toate pozitiile sale acelasicaracter a . . . a︸ ︷︷ ︸

n ori

, vom nota an = a . . . a︸ ︷︷ ︸n ori

.

Multimea tuturor string-urilor peste alfabetul A se va nota A∗. Deci A∗

= {ε}︸︷︷︸A0

∪A ∪ A2 ∪ . . . = ∪n≥0An. De exemplu, daua A = {a}, atunci A∗ =

{ε, a, aa, aaa, . . .}, iar daca A = {a, b}, atunci A∗ = {ε, a, b, aa, ab, ba, bb, . . .}.Convenim ca pentru A = ∅ sa luam A∗ = {ε}.

Propozitia II.2.2.2. Daca A este un alfabet finit, atunci A∗ este o multimenumarabila.

Demonstratie. Fie A = {x1, . . . , xn} si definim functia f : A∗ −→ N prin

f(α) =

{i1 + (n+ 1)i2 + (n+ 1)2i3 + . . . daca α = xi1 . . . xik ∈ A∗

0 daca α = ε

Cum i1 . . . ik ∈ {1, . . . , n}, fiecarui string ıi va corespunde un unic numarnatural a carui scriere ın baza (n+1) este i1 . . . ik. Rezulta f injectiva. CumA∗ este o multime infinita (contine de exemplu toate stringurile formate doarcu simbolul x1), obtinem ca A∗ este numarabila.

Fie acum α, β ∈ A∗, α = a1 . . . am si β = b1 . . . bn. Definim operatia deconcatenare a string-urilor α si β prin:

α · β = a1 . . . amb1 . . . bn

Convenim ca pentru concatenarea cu stringul vid sa punem

α · ε = ε · α = α

In particular, rezulta | α · β |=| α | + | β |,∀α, β ∈ A∗.Se observa usor ca operatia de concatenare este asociativa (αβ)γ = α(βγ)

si necomutativa (pentru | A |> 1), cu string-ul vid drept element neutru.Deci (A∗, ·, ε) este un monoid. Mai mult, pe A∗ putem defini operatia

unara de involutie αR = an . . . a1, daca α = a1 . . . an. Atunci (αR)R = α,(α · β)R = βR · αR si εR = ε.

10

Teorema II.2.2.3. (A∗, ·, ε) este monoidul liber generat de multimea A.

Demonstratie. Fara demonstratie.

Exercitiul II.2.2.4. Functia care asociaza fiecarui string lungimea sa, A∗ −→N, α −→ |α| e morfism de monoizi. Indicati cum poate fi construit acestmorfism de monoizi folosind Definitia II.2.2.1 si Teorema II.2.2.3.

Limbaje si operatii cu limbaje. O submultime L ⊆ A∗ se numestelimbaj. Deci multimea limbajelor peste alfabetul A este P(A). Daca A esteun alfabet finit, am vazut ca A∗ este o multime numarabila, deci P(A∗) vafi nenumarabila.

Cum limbajele sunt submultimi ale monoidului stringurilor A∗, putemefectua cu acestea toate operatiile specifice multimilor, si anume reuniunea,intersectia, complementara. Pe langa acestea, introducem urmatoarele operatii:

(i) Concatenarea limbajelor: daca L1, L2 ⊆ A∗, atunci

L1 · L2 = {α · β | α ∈ L1, β ∈ L2}

De exemplu, daca A = {a, b} si luam limbajele L1 = {ε, a, a2, . . .} siL2 = {b}, atunci L1 · L2 = {b, ab, a2b, . . .}.Concatenarea limbajelor este o operatie asociativa, necomutativa, pen-tru care

L · {ε} = {ε} · L = L

L · ∅ = ∅ · L = ∅Exercitiul II.2.2.5. Aratati ca operatia de concatenare a limbajeloreste distributiva peste reuniune, dar nu si peste intersectie (Indicatie:considerati A = {a, b, c}, L1 = {a, ab}, L2 = {b}, L3 = {ε}).

(ii) Inchiderea (ınchiderea Kleene): daca L ⊆ A∗, atunci

L∗ = {ε} ∪ L ∪ L · L ∪ L · L · L ∪ . . .

In particular, ∅∗ = {ε}. Inchiderea Kleene verifica urmatoareleproprietati:

(a) L ⊆ L∗

(b) L1 ⊆ L2 ⇒ L∗1 ⊆ L∗2(c) A ⊆ L∗ ⇒ L∗ = A∗

(d) L∗ · L∗ = L∗

(e) (L∗)∗ = L∗

(f) L∗ = {ε} ∪ L · L∗ = {ε} ∪ L∗ · L

Curs 5

II.2.3 Actiuni ale monoizilor

Observatia II.2.3.1. Fie (M, ·, e) un monoid. Atunci M , ımpreuna cuoperatia binara m ·op n = n ·m,∀m,n ∈ M , formeaza un monoid cu acelasielement neutru e, numit monoidul opus lui M si notat M op. Daca M estecomutativ, atunci clar M op coincide cu M . Daca M este grup, atunci functiaM −→M op, m 7→ m−1 este un izomorfism de monoizi. Daca M nu este grupsi nici comutativ, atunci monoizii M si M op nu mai sunt neaparat izomorfi.

Exemplul II.2.3.2. Fie M = {e, a, b} cu operatia binara a · a = a · b = a,b · a = b · b = b si elementul neutru e. Se verifica usor ca M este un monoidnecomutativ. Daca ar exista un izomorfism f : M −→M op, atunci f trebuiesa fie bijectiva si f(e) = e. Exista numai doua cazuri posibile: f = 1M sau

f(a) = b, f(b) = a

Dar 1M : M −→ M op nu e morfism de monoizi. Ramane deci al doilea caz.Din conditia f(a ·b) = f(a) ·op f(b) = f(b) ·f(a), rezulta b = f(a) = f(a ·b) =f(b) · f(a) = a · b = a, fals.

Definitia II.2.3.3. Fie (M, ·, e) un monoid si X o multime. Spunem caM actioneaza pe X la dreapta (sau ca X este o M-multime) daca exista ofunctie δ : X ×M −→ X astfel ıncat:

(A1 ) δ(x, e) = x,∀x ∈ X.

(A2 ) δ(x,m · n) = δ(δ(x,m), n),∀x ∈ X, m, n ∈M .

Vom nota δ(x,m) = x C m; spunem ca elementul m ∈ M actioneaza pex ∈ X prin xCm ∈ X. Relatiile (A1) - (A2) se scriu atunci:

xC e = x si xC (m · n) = (xCm) C n

1

CC-Matematica 2 2

Exemplul II.2.3.4. (i) Fie (M, ·, e) un monoid si X o multime. Atuncifunctia δ : X×M −→ X, δ(x,m) = x (deci scriem xCm = x), definesteo actiune a lui M pe X, numita actiune triviala: prin constructie, avemx C e = x si (x C m) C n = x C n = x = x C (m · n), pentru oricex ∈ X,m, n ∈M .

(ii) Fie (M, ·, e) un monoid. Atunci operatia binara ” · ” pe M determinao actiune a monoidului pe el ınsusi δ : M × M −→ M, δ(x,m) =x ·m,∀x,m ∈M , numita actiune regulata (deci scriem xCm = x ·m).Axiomele (A1)-(A2) sunt verificate: xCe = x ·e = x si (xCm)Cn =(x ·m) · n = x · (m · n) = xC (m · n).

(iii) Fie (M, ·, e) monoid si X o multime pe care M actioneaza la dreaptaprin X ×M −→ X, (x,m) 7→ x Cm. Atunci functia P(X) ×M −→P(X), (A,m) 7→ ACm = {xCm | x ∈ A}, ∀A ⊆ X,m ∈M , definesteo actiune a lui M pe multimea partilor lui X. Verificam:

AC e = {xC e | x ∈ A}= {x | x ∈ A}= A

(ACm) C n = {xCm | x ∈ A}C n

= {(xCm) C n | x ∈ A}= {xC (m · n) | x ∈ A}= AC (m · n)

Exercitiul II.2.3.5. Daca (M, ·, e) este un monoid si X o multime pe careM actioneaza la drepta, atunci M actioneaza si pe produsul cartezian Xn =X × . . .×X︸ ︷︷ ︸

n ori

,∀n ∈ N∗.

II.2.4 Submonoizi. Morfisme de monoizi. Monoid fac-tor

Definitia II.2.4.1. Fie (M, ·, e) un monoid si N ⊆ M . Spunem ca N esteun submonoid daca:

(S1) e ∈ N .

(S2) ∀m,n ∈ N =⇒ m · n ∈ N .

Orice submonoid este ın particular un monoid cu operatia binara indusa, darnu orice submultime a unui monoid care este la randul sau monoid cu operatia

CC-Matematica 2 3

indusa este submonoid. De exemplu, fie M = ({a, b}, ◦,1{a,b}) monoidultuturor functiilor {a, b} −→ {a, b} cu operatia de compunere. Luam N ={fa}, unde fa este functia constanta ın a. Atunci fa ◦ fa = fa, deci N estemonoid ın raport cu compunerea, dar N nu e submonoid deoarece 1{a,b} /∈ N .

Observatia II.2.4.2. Fie N ⊆ M submonoid si X o multime pe care Mactioneaza la dreapta prin δ : X ×M −→ X. Atunci restrictia lui δ la N ,δ|X×N : X ×N −→ X defineste o actiune a lui N pe X.

Fie (M, ·, e) un monoid si X, Y ⊆ M . Produsul submultimilor X, Y estesubmultimea

X · Y = {x · y | x ∈ X, y ∈ Y }

Se obtine astfel o operatie binara pe multimea submultimilor lui M P(M);P(M), ımpreuna cu aceasta operatie formeaza un monoid cu elementul neu-tru {e} si element zero ∅. De remarcat ca daca N ⊆ M este submonoid,atunci N este element idempotent (adica N ·N = N) ın P(M) (exercitiu!).

Reamintim: fie A o multime, pe care o vom numi alfabet. Un stringα (de lungime n) este un element din An = A× · · · × A︸ ︷︷ ︸

n ori

,∀n ∈ N∗, scris

α = a1 . . . a2, fara paranteze sau virgula. Convenim existenta unui stringvid (de lungime 0), notat ε. Multimea tuturor stringurilor se va nota A∗

(formal, A∗ = ∪An, n ≥ 0, unde A0 = {ε}). Pe A∗, definim o operatienumita concatenare prin:

α · β = a1 . . . anb1 . . . bm

daca α = a1 . . . an ∈ A∗, β = b1 . . . bm ∈ A∗. De asemenea, convenim ca

α · ε = ε · α, ∀α ∈ A∗

Atunci (A∗, ·, ε) devine un monoid, numit monoidul liber peste A.

Definitia II.2.4.3. Fie (M, ·, eM), (N, ·, eN) monoizi. O functie f : M −→N se numeste morfism de monoizi daca:

(M1) f(eM) = f(eN)

(M2) f(mm′) = f(m)f(m′),∀m,m′ ∈M

Un izomorfism de monoizi este un morfism bijectiv.

Exemplul II.2.4.4. Functia l : A∗ −→ N, l(α) = |α| este un morfism demonoizi, caci |ε| = 0 si |αβ| = |α| + |β|, ∀α, β ∈ A∗. Daca A = {a}, atuncil este chiar un izomorfism.

CC-Matematica 2 4

Observatia II.2.4.5. Fie f : M −→ N un morfism de monoizi. Atuncipentru orice M ′ ⊆ M submonoid, f(M ′) ⊆ N este submonoid. Reciproc,daca N ′ ⊆ N e submonoid, atunci f−1(N ′) ⊆M e submonoid. In particular,daca luam M ′ = M , obtinem ca Imf e submonoid ın N .

Demonstratie. Reamintim ca f(M ′) = {f(m) | m ∈ M ′} si f−1(N ′) ={m ∈ M | f(m) ∈ N ′}. Aratam acum ca f(M ′) e submonoid: cum eN =f(eM) si eM ∈ M ′ (M’ este submonoid), rezulta eN ∈ f(M ′). Acum ,fiem,m′ ∈M ′. Atunci f(m)f(m′) = f(m ·m′) ∈ f(M ′) deoarece m ·m′ ∈M ′.Trecem la a doua afirmatie, privind f−1(N ′): f(eM) = eN ∈ N ′, deci eM ∈f ′(N ′). Daca m,m′ ∈ f ′(N ′), atunci f(m)·f(m′) ∈ N ′. Dar N ′ e submonoid,deci f(m ·m′) = f(m) · f(m′) ∈ N ′, adica m ·m′ ∈ N ′.Definitia II.2.4.6 (Congruenta). O relatie de echivalenta R pe monoidulM se numeste congruenta daca

(C) mRm′ =⇒ (m · n)R(m′ · n) si (n ·m)R(n ·m′),∀m,m′, n ∈M .

Reamintim ca fiecarei relatii de echivalenta R ıi corespunde o partitie amonoidului M ın clase de echivalenta ([m]R)m∈M , unde [m]R = {n ∈ M |mRn}. Multimea claselor de echivalenta s-a notat cu M/R si se numestemultimea factor.

Exemplul II.2.4.7. Pe A∗ luam relatia

αRβ ⇐⇒| α |=| β |

Este ın mod evident o relatie de echivalenta; ın plus, pentru orice γ ∈ A∗,| αγ |=| α | + | γ |=| β | + | γ |=| βγ | si analog | γα |=| γβ |, deci R este ocongruenta.Daca | α |= n, atunci [α]R = {β ∈ A∗ | αRβ} = An este multimea tuturorstringurilor de lungime n.

Daca (M, ·, e) este un monoid si R o congruenta pe M , atunci putem definio operatie binara pe multimea factor M/R prin:

[m]R · [m′]R = [m ·m′]R,∀m,m′ ∈M

Aceasta definitie nu depinde de reprezentantii claselor de echivalenta: daca[m]R = [n]R si [m′]R = [n′]R, atunci mRn si m′Rn′. Rezulta m ·m′Rn ·m′si n · m′Rn · n′, de unde m · m′Rn · n′, adica [m · m′]R = [n · n′]R. Maimult, operatia astfel definita este asociativa si admite elementul neutru [e]R(exercitiu!), deci (M/R, ·, [e]R) este un monoid. Fie πR : M −→ M/Rfunctia care asociaza fiecarui element clasa sa de echivalenta: πR(m) = [m]R(πR se numeste surjectie canonica). Atunci πR este surjectiva (de ce?) simorfism de monoizi: πR(e) = [e]R prin constructie si πR(m·m′) = [m·m′]R =[m]R[m′]R = πR(m)πR(m′), ∀m,m′ ∈M .

CC-Matematica 2 5

Congruenta nucleara. Fie f : M −→ N o functie. Consideram relatiamRfm

′ ⇐⇒ f(m) = f(m′), ∀m,m′ ∈ M . Atunci Rf este o relatie deechivalenta, ale carei clase vor fi (f−1(n))n∈Imf . Daca M,N sunt monoizi si feste morfism, atunci Rf este chiar o congruenta: fie m,m′ ∈ M astfel ıncatmRfm

′. Atunci f(m) = f(m′). Daca n ∈M , avem f(m ·n) = f(m) ·f(n) =f(m′) · f(n) = f(m′ · n), deci (m · n)R(m′ · n) si analog la stanga.Sa remarcam ca dacaR este o congruenta atunci congruenta asociata surjectieicanonice πR este chiar R: daca mRπRm

′, atunci πR(m) = πR(m′), deci

[m]R = [m′]R, echivalent cu mRm′. In consecinta, a da o congruenta R peun monoid M este acelasi lucru cu a da un morfism de monoizi cu domeniulM (pornind de la congruenta R, obtinem morfismul de monoizi πR; invers,daca f : M −→ N este un morfism de monoizi, atunci obtinem congruentaRf ).

Teorema II.2.4.8. Fie f : M −→ N un morfism de monoizi. Atunci functiaf : M/Rf −→ N , f([m]Rf

) = f(m) este un morfism injectiv de monoizi cu

imaginea Imf . In particular, rezulta ca exista un izomorfism de monoizi

M/Rf∼= Imf

Demonstratie. Aratam mai ıntai ca f e bine definita si injectiva: daca[m]Rf

= [m′]Rf, atunci mRfm

′, de unde f(m) = f(m′). f e morfism demonoizi:

f([m]MRf) = f(e) = e

si

f([m]Rf· [m′]Rf

) = f([m ·m′]Rf)

= f(m ·m′)= f(m) · f(m′)

= f([m]Rf) · f([m′]Rf

)

Din constructie, Imf = Imf , deci avem izomorfismul M/Rf∼= Imf .

Exemplul II.2.4.9. Fie A={a, b} si M = A∗. Am vazut mai devreme cafunctia l : A∗ −→ N, l(α) =| α | este un morfism de monoizi (surjectiv). FieRl congruenta asociata:

αRlβ ⇐⇒| α |=| β |,∀α, β ∈ A∗

Atunci A∗/Rl∼= (N) este un izomorfism de monoizi, dat de de A∗ 7→ n

(reamintim partitia ın clase de echivalenta: daca α ∈ A∗, | α |= n, atunci[α]Rl

= An), unde operatia binara pe An/Rleste (An, Am) 7→ An+m.

CC-Matematica 2 6

Reamintim ca pentru orice alfabet A, monoidul A∗ are urmatoarea pro-prietate : pentru orice monoid M si pentru orice functie f : A −→ M ,exista un unic morfism de monoizi f ∗ : A∗ −→ M care extinde pe f (adicaf ∗(a) = f(a), ∀a ∈ A), si anume:

f ∗(ε) = eM

f ∗(α) = f(a1) · . . . · f(an), daca α = a1...an ∈ A∗

Fie acumX o multime si δ : X×A∗ −→ X o actiune a monoidului stringurilorpe X. Cum A ⊆ A∗, prin restrictie se obtine o functie δA : X × A −→ X.Reciproc, orice functie δA : X × A −→ X determina o actiune a monoiduluiA∗ pe X, prin functia δ : X × A −→ X, definita recursiv astfel:

δ(x, ε) = x

δ(x, αa) = δA(δ(x, α), a), ∀α ∈ A∗, a ∈ A

Atunci functia δ astfel definita verifica ın mod clar (A1). Verificam si (A2)δ(x, αβ) = δ(δ(x, α), β), prin inductie dupa | β |: daca | β |= 0, adica β = ε,atunci

δ(δ(x, α), β) = δ(δ(x, α), ε)

= δ(x, α)

= δ(x, αε)

= δ(x, αβ)

Presupunem acum afirmatia adevarata pentru stringuri de lungime mai micasau egala cu n si fie β ∈ A∗ , | β |= n + 1. Atunci putem scrie β = γa, cuγ ∈ A∗, | γ |≤ n, a ∈ A si avem

δ(x, αβ) = δ(x, αγa)

= δA(δ(x, αγ), a)

= δA(δ(δ(x, α), γ), a)

= δ(δ(x, α), γa)

= δ(δ(x, α), β)

II.2.5 Automate

Definitia II.2.5.1. Un automat determinist finit (DFA) este un tuplu A =(X,A, I, F, δ), unde

(i) X este o multime finita, numita multimea starilor;

CC-Matematica 2 7

(ii) A este un alfabet finit;

(iii) I ⊆ X este o submultime numita multimea starilor initiale, iar F ⊆ Xmultimea starilor finale;

(iv) δ : X × A −→ X este o functie numita functia de tranzitie.

Din observatia precedenta rezulta ca un DFA peste un alfabet A este defapt o multime peste care actioneaza monoidul stringurilor A∗ , ımpreunacu doua submultimi bine determinate (submultimile starilor de intrare si deiesire).

Definitia II.2.5.2. Un automat nedeterminist finit (NDFA) este un tupluA = (X,A, I, F, E) ca mai sus, cu diferenta ca ın loc de o functie de tranzitieδ : X × A −→ X, avem o relatie E ⊆ X × A×X.

Daca (x, a, y) ∈ E sau δ(x, a) = y, vom nota xa−→ y si vom spune ca

automatul a trecut din starea x ın starea y la primirea input-ului a.Sa remarcam ca o relatie E ⊆ X × A × X este echivalenta cu o functie

τ : X × A −→ P(X), unde τ(x, a) = {y ∈ X | (x, a, y) ∈ E} (si reciproc,pentru orice functie τ : X×A −→ P(X), obtinem o relatie E prin (x, a, y) ∈E ⇔ y ∈ τ(x, a)). Putem extinde o asemenea functie la multimea partilorprin P(X) × A −→ P(X), (X ′, a) 7→ {y ∈ X | ∃x ∈ X ′, y ∈ τ(x, a)}, undeX ′ ⊆ X. In particular, fiecarui NDFA A = (X,A, I, F, E) ıi corespunde unDFA prin Det(A) = (P(X), A, I,F , δ), unde I = {I} ⊆ P(X), F = {X ′ ⊆X | X ′ ∩ F 6= ∅} si τ ca mai sus. De asemenea, sa remarcam ca si un NDFAcorespunde unei actiuni a monoidului stringurilor A∗, numai ca de aceastadata multimea pe care se actioneaza este P(X) si nu X.

In continuare, vom reprezenta automatele (NDFA sau DFA) prin grafuriorientate, astfel: nodurile grafului vor fi starile din X, iar ıntre doua nodurix si y exista un arc cu eticheta a ∈ A ⇐⇒ (x, a, y) ∈ E (sau δ(x, a) = y).Starile finale, respectiv initiale vor fi marcate prin sageti care ies, respectivintra din noduri.

Exemplul II.2.5.3. Fie A = (X = {1, 2, 3}, A = {a, b}, I = {1}, F ={2}, δ), unde δ : X × A −→ X e data in tabelul urmator:

Aa b

X1 1 22 3 33 2 3

CC-Matematica 2 8

Atunci automatul va avea reprezentarea

// ?>=<89:;1

a

b // ?>=<89:;2

a,b** ?>=<89:;3ajj

b

//

Un drum ın automatul A este o secventa finita de stari consecutive ıntrecare exista tranzitii, x0

a1 // x1a2 // . . . an // xn . Spunem ca stringul α =

a1...an este asociat drumului. Prin conventie, pentru orice stare x ∈ Xconsideram un drum vid cu stringul asociat ε. Spunem ca un string α =a1 . . . an este acceptat de automatul A daca exista un drum cu x0 ∈ I stareinitiala si xn ∈ F stare finala. In particular, stringul vid este acceptat dacaexista o stare initiala care este si finala. Multimea stringurilor acceptate deun automat A se numeste limbajul acceptat de automatul A si se va nota cuL(A).

Exemplul II.2.5.4. (i) Un automat care accepta limbajul {anb | n ∈ N}

///.-,()*+a

�� b ///.-,()*+ //

(ii) Un automat care accepta limbajul vid.

///.-,()*+

(iii) Un automat care accepta limbajul format din stringul vid

///.-,()*+ //

(iv) Un automat care accepta toate stringurile peste alfabetul {a, b}

///.-,()*+a,b

��//

(v) Un automat care accepta doar stringul α = a1....an

///.-,()*+ a1 ///.-,()*+ a1 // . . . an ///.-,()*+ //

Spunem ca doua automate sunt echivalente daca accepta acelasi limbaj.

Propozitia II.2.5.5. Orice NDFA este echivalent cu un DFA.

Curs 6

II.2.6 Automate-continuare

Teorema II.2.6.1. Orice automat finit nedeterminist este echivalent cu unautomat finit determinist.

Demonstratie. Fie A = (X,A, I, F, E) un automat nedeterminist, unde:

• X este multimea starilor;

• A este alfabetul input-urilor;

• I ⊆ X este multimea starilor initiale;

• F ⊆ X este multimea starilor finale (acceptoare);

• E ⊆ X × A×X este relatia de tranzitie.

Construim un automat determinist astfel: Det(A) = (P(X), A, I,F , δ),unde:

• I = {I} ⊆ P(X);

• F = {X ′ ⊆ X | X ′ ∩ F 6= ∅};

• δ : P(X)× A −→ P(X), δ(X ′, a) = {y ∈ X | ∃ x ∈ X ′, (x, a, y) ∈ E}.

Trebuie sa aratam ca cele doua automate accepta acelasi limbaj. Fie α ∈ A∗un string acceptat de A. Daca α = ε, atunci ∃x ∈ X stare initiala si finala.Deci I ∩ F 6= Ø , adica I ∈ I ∩ F este stare initiala si finala ın automatulDet(A). Rezulta ca ε este acceptat de Det(A). Reciproc, daca ε este acceptatde Det(A), starea initiala I ın Det(A) este si finala, adica I∩F 6= ∅. Rezultaca exista x ∈ I ∩F stare initiala si finala ın A, de unde ε este string acceptatde A.

Fie acum α = a1 . . . an. Atunci: α este acceptat de A ⇔ ∃x1, . . . , xn ∈ Xastfel ıncat (x0, a1, x1), (x1, a2, x2), . . ., (xn−1, an, xn) ∈ E si x0 ∈ I, xn ∈ F(altfel scris: x0

a1→ x1a2→ . . .

an→ xn).

1

CC-Matematica 2 2

Fie atunci ın Det(A) urmatoarea secventa de stari, definita recursiv:{X0 = IXk+1 = δ(Xk, ak+1), pentru k = 0, n− 1

Prin constructie, aceasta secventa de stariX0, . . . , Xn ⊆ X admite tranzitiile:

X0a1→ X1

a2→ . . .an→ Xn

si X0 = I e stare initiala. Ramane de vazut ca Xn e stare finala. Pentruaceasta, vom arata prin inductie dupa k = 0, n− 1 ca xk ∈ Xk. Pentruk = 0, avem x0 ∈ I = X0. Presupunem x0 ∈ X0, . . . , xk ∈ Xk si aratamxk+1 ∈ Xk+1 : cum (xk, ak+1, xk+1) ∈ E si xk ∈ Xk din ipoteza inductiva,rezulta xk+1 ∈ δ(Xk, ak+1) = Xk+1.

Deci pentru orice k = 0, n− 1, xk ∈ Xk; ın particular xn ∈ Xn; darxn ∈ F , de unde Xn ∩ F 6= Ø si Xn e stare finala ın Det(A).

Rezulta ca stringul α = a1 . . . an e acceptat de Det(A). Reciproc, dacaα = a1 . . . an e acceptat de Det(A), atunci exista o secventa de stari ınDet(A),

X0a1→ X1

a2→ . . .an→ Xn

unde X0 = I,Xn ∈ F si Xk+1 = δ(Xk, ak),∀k = 0, n− 1.De remarcat ca prin constructia functiei de tranzitie δ, toate starile

X0, . . . , Xn sunt nevide. Fie atunci xn ∈ Xn ∩ F (Xn e stare finala); cumXn = δ(Xn−1, an), rezulta ca exista xn−1 ∈ Xn−1 cu

(xn−1, an, xn) ∈ E(xn−1an→ xn).

Analog construim xn−2 ∈ Xn−2, . . . , x0 ∈ X0 = I cu (xn−2, an−1, xn−1) ∈E, . . . , (x0, a1, x1) ∈ E.

Am obtinut deci x0a1→ x1

a2→ . . .an→ xn ın A si x0 ∈ I, xn ∈ F .

Rezulta ca α = a1 . . . an e acceptat de A.

Observatia II.2.6.2. In practica, se poate eficientiza determinizarea unuiautomat nedeterminist cu n stari astfel: ın loc de P(X) pentru multimeastarilor ın Det(A) se considera doar multimea acelor submultimi pentru careexista o secventa de tranzitii pornind de la I (vezi exemplul urmator).

Observatia II.2.6.3. Din teorema rezulta ca orice automat finit este echiva-lent cu un automat cu o singura stare de intrare; ın continuare toate auto-matele vor avea doar o singura stare de intrare.

Exemplul II.2.6.4. Determinizati urmatorul NDFA:

// ?>=<89:;p0

0,1 // ?>=<89:;q

��

0,1 // ?>=<89:;r1

��

CC-Matematica 2 3

Avem X = {p, q, r}, A = {0, 1}, I = {p}, F = {q}, de unde rezultaınparticular ca P(X) are 8 elemente. Functia de tranzitie δ : P(X) × A →P(X) este descrisa ın tabelul urmator:

0 1Ø Ø Ø

→ {p} {p,q} {q}← {q} {r} {r}

{r} Ø {r}← {p,q} {p,q,r} {q,r}

{p,r} {p,q} {q,r}← {q,r} {r} {r}← {p,q,r} {p,q,r} {q,r}

In coloana din stanga a tabelului, am indicat cu o sageata ”→” starea deintrare si cu o sageata orientata invers ”←” starile finale. Automatul deter-minist asociat va fi:

// GFED@ABC{p} 0 //

1��

ONMLHIJK{p,q}

OO

0 //

1��

ONMLHIJK{p,q,r}

0

//

1{{xxxxxxxxxx

GFED@ABC{q}

0,1

��

ONMLHIJK{q,r} //

0,1}}zzzzzzzzz

GFED@ABC{r} 0 //

1

TT?>=<89:;∅0,1

UU

Nu am mai reprezentat starea {p, r} pentru ca nu este accesibila (nu existanicio secventa de tranzitie de la starea de intrare {p} care sa conduca la{p, r}).

II.2.7 Limbaje rationale

Definitia II.2.7.1. Fie A un alfabet. Atunci

(i) ∅, ε si orice a ∈ A sunt expresii regulate, numite expresii regulateprimitive.

(ii) Daca r1 si r2 sunt expresii regulate, la fel sunt r1 + r2, r1 · r2, r∗1 si (r1).

CC-Matematica 2 4

(iii) Un string este o expresie regulata daca poate fi obtinut din expresii reg-ulate primitive ın urma unui numar finit de aplicari ale regulii prece-dente.

Exemplul II.2.7.2. Fie A = {0, 1}. Atunci ∅, ε, 0, 1, 0+1, 0 ·1, 0+0 ·1, (0+(0 · 1))∗ sunt expresii regulate. Dar (0 + 1 · 1+) nu este o expresie regulata.

Definitia II.2.7.3. Limbajul rational este limbajul asociat unei expresii reg-ulate r, notat L(r), dupa regulile urmatoare:

(i) L(∅) = ∅ , L(ε) = {ε}, L(a) = {a}, ∀a ∈ A.

(ii) L(r1 + r2) = L(r1) ∪ L(r2), L(r1 · r2) = L(r1) · L(r2), L((r1)) = L(r1),L(r∗1) = L(r1)

∗, ∀r1, r2 expresii regulate.

Exemplul II.2.7.4. L(0∗ ·(0+1)) = L(0∗)·L(0+1) = L(0)∗ ·(L(0)∪L(1)) ={0}∗ · ({0} ∪ {1}) = {0}∗ · {0, 1} = {ε, 0, 00, . . .}.Teorema II.2.7.5. Fie L ⊆ A∗ un limbaj rational. Atunci exista un automatfinit determinist care accepta L.

Nu vom da demonstratia acestei teoreme, ci un algoritm pentru constructiaunui automat determinist (nu este unic!) pentru o expresie regulata data.

(i) Pentru fiecare dintre limbajele asociate expresiilor regulate ∅, ε, a, undea ∈ A, am construit ın cursul trecut cate un automat nedeterminist careaccepta acest limbaj. Prin determinizare, rezulta:

(a) Automat care accepta L(∅) = ∅:

///.-,()*+ determinizare=⇒ ///.-,()*+

a,∀a∈A

YY

(b) Automat care accepta L(ε) = {ε} :

///.-,()*+ // determinizare=⇒ ///.-,()*+

��

a,∀a∈A///.-,()*+a,∀a∈A

YY

(c) Automat care accepta L(a) = {a} :

///.-,()*+ a ///.-,()*+ // determinizare=⇒ ///.-,()*+ a //

b,∀b6=a��

/.-,()*+ //

b,∀b∈A����������

/.-,()*+b∀b∈A

YY

CC-Matematica 2 5

(ii) Presupunem ca am construit deja automate deterministe pentru L(r1)si L(r2) cu r1 si r2 expresii regulate; fie acestea A1 = (X1, A, x1, F1, δ1)si A2 = (X2, A, x2, F2, δ2).

(a) Automat care accepta L(r1+r2) = L(r1)∪L(r2): A = (X,A, x, F, δ),unde: X = X1 × X2, starea initiala este x = (x1, x2), F ={(y1, y2) ∈ X1 × X2 | y1 ∈ F1 sau y2 ∈ F2}. Functia de tranzitieeste:

δ : X1 ×X2 × A −→ X1 ×X2, δ((y1, y2), a) = (δ(y1, a), δ(y2, a))

Atunci un string α = a1 . . . an ∈ A∗ este acceptat de A ⇐⇒ existao secventa finita de tranzitii

(y(0)1 , y

(0)2 )

a1→ (y(1)1 , y

(1)2 )

a2→ · · · an→ (y(n)1 , y

(n)2 )

unde(y

(0)1 , y

(0)2 ) = (x1, x2)

este starea initiala,(y

(n)1 , y

(n)2 ) ∈ F

si(y

(k+1)1 , y

(k+1)2 ) = δ((y

(k)1 , y

(k)2 ), ak), k = 0, n− 1

adicay(k+1)1 = δ1(y

(k)1 , ak)

siy(k+1)2 = δ2(y

(k)2 , ak),∀k = 0, n− 1

Dar(y

(n)1 , y

(n)2 ) ∈ F ⇔ y

(n)1 ∈ F sau y

(n)2 ∈ F

de unde rezulta α ∈ L(r1) sau α ∈ L(r2).

Reciproc, se arata analog ca orice α ∈ L(r1)∩L(r2) e acceptat deautomatul A.

(b) Automat care accepta L(r1·r2) = L(r1)·L(r2) : A = (X,A, x, F,E),mai ıntai nedeterminist si apoi determinizat, unde: X = X1 ∪X2

(presupunem X1, X2 distincte; daca nu, le redenumim), x = x1,

F =

{F2, daca x2 /∈ F2

F1 ∪ F2, daca x2 ∈ F2

CC-Matematica 2 6

si relatia de tranzitie E ⊆ (X1∪X2)×A×(X1∪X2) descrisa prin:

(y, a, δ1(y, a)) ∈ E, y ∈ X1 \ F1

(y, a, δ1(y, a)), (y, a, δ2(x2, a)) ∈ E, y ∈ F1

(y, a, δ2(y, a)) ∈ E, y ∈ X2

Atunci α = a1...an ∈ L(r1) si β = b1...bm ∈ L(r2) (β 6= ε) ⇐⇒αβ = a1...anb1...bm este acceptat de automatul A:

A1 : x1 = y(0)1

a1→ y(1)1

a2→ ...an→ y

(n)1 ∈ F1

A2 : x2 = y(0)2

b1→ y(1)2

b2→ ...bm→ y

(m)2 ∈ F2

A : x1 = y(0)1

a1→ y(1)1

a2→ ...an→ y

(n)1

b1→ y(1)2

b2→ ...bm→ y

(m)2 ∈ F2 ⊆ F

Daca β = ε, atunci α ∈ L(r1)⇐⇒ α e acceptat de automatul A.

In final, prin determinizare se obtine un automat determinist careaccepta L(r1 · r2).

(c) Automat care accepta L(r∗1) = L(r1)∗: din nou ın doi pasi: mai

ıntai un automat nedeterminist: A = (X,A, x, F,E), unde X =X1 ∪ {x} (adaugam o noua stare x care va deveni stare initiala),F = F1 ∪ {x} si tranzitiile:

• Din starea x:

(x, a, δ1(x1, a)), (x, a, x1) ∈ E, daca δ1(x1, a) ∈ F1

(x, a, δ1(x, a)) ∈ E, ın caz contrar

• Dintr-o stare arbitrara y ∈ X1:

(y, a, δ1(y, a)), (y, a, x) ∈ E, daca δ1(y, a) ∈ F1

(y, a, δ1(y, a)), ın caz contrar

Atunci ε este acceptat deA (x e stare initiala si finala) si un produsde stringuri α1...αn este acceptat de A ⇐⇒ α1, ..., αn ∈ L(r1∗).Pentru a vedea aceasta, fie α1 = a

(1)1 ...a

(1)k1

, α2 = a(2)1 ...a

(2)k2

, . . .,

αn = a(n)1 ...a

(n)kn

. Atunci fiecarui string ıi corespunde o secventa de

CC-Matematica 2 7

stari, astfel:

A1 : x1a(1)1→ x

(1)1

a(1)2→ ...

a(1)k1→ x

(1)k1︸ ︷︷ ︸

α1

∈ F1

. . . . . . . . .

x1a(n)1→ x

(n)1

a(n)2→ ...

a(1)kn→ x

(n)kn︸ ︷︷ ︸

αn

∈ F1

A : xa(1)1

!!BBBBBBBB

x1

a(n)1

��

a(2)1

$$

a(1)1 // x

(1)1

a(1)2 // . . .

a(1)k1−1// x

(1)k1−1

a(1)k1

jja(1)k1 // x

(1)k1

x(2)1

a(2)2 // . . .

a(2)k2−1// x

(2)k2−1

a(2)k2

UU

a(2)k2 // x

(2)k2

. . . . . .

x(n)1

a(n)2 // . . .

a(n)kn−1// x

(n)kn−1

a(n)kn // x

(n)kn

∈ F1 ⊆ F

Exemplul II.2.7.6. Fie L1 = L(1∗0(0 + 1)∗) si L2 = L(01∗). Un exemplude automat A1 care accepta L1 este

// ?>=<89:;1

1

0 // ?>=<89:;2 //

0,1

Pentru L2, consideram mai ıntai un automat nedeterminist A2, cum ar fi

// ?>=<89:;p 0 // ?>=<89:;q //

1

care prin determinizare conduce la automatul A2 dat de

// ?>=<89:;p 0 //

1��

?>=<89:;q //

1

0�����������

?>=<89:;r0,1

VV

CC-Matematica 2 8

unde r corespunde multimii vide si am omis scrierea acoladelor.Construim acum automatul care accepta L1 ∪ L2 = L(1∗0(0 + 1)∗ + 01∗):

// GFED@ABC1p

0

@@@@@@@@@

1

��GFED@ABC1q

0

��@@@@@@@@@

1

�� GFED@ABC1r

1

0

��

//

GFED@ABC2p

1

EEoo 0 // GFED@ABC2q 0 //

1

��

��

GFED@ABC2r

0,1

TT//

De remarcat ca starile 1q si 2p nu sunt accesibile, deci se poate renunta laele.

Automatul (nedeterminist) care accepta L1 ·L2 = L(1∗0(0 + 1)∗01∗) va fi:

// ?>=<89:;1

1

0 // ?>=<89:;2

0

$$

1��?????????

0,1

?>=<89:;p 0 //

1

��

?>=<89:;q //

1

0�����������

?>=<89:;r0,1

VV

In acest automat, starea p devine inutila.In final, sa construim si automatul care accepta (L1)

∗:

// ?>=<89:;x

��

0,1**

0

��?>=<89:;10

jj

1

0 // ?>=<89:;2

��

0,1

Teorema II.2.7.7. Fie L un limbaj acceptat de un automat finit. Atunci Leste rational (exista o expresie regulata r astfel ıncat L = L(r)).

Algoritm de determinare a limbajului acceptat de un automatfinit.

Fie A = (X, a, x0, F, δ) automat finit cu n stari, determinist, care acceptaL. Redenumind starile, putem presupune X = {1, 2, ..., n}.

CC-Matematica 2 9

FieR(k)ij numele unei expresii regulate al carei limbaj asociat este multimea

stringurilor α astfel ıncat exista un drum de la starea i la starea j cu inputulα astfel ıncat starile intermediare nu sunt mai mari strict decat k.

Vom construi R(k)ij inductiv pentru k = 0, n (din constructie va rezulta

R(k)ij expresie regulata).

Daca k = 0, atunci nu vor fi stari intermediare.Cazul I: i 6= j ⇒ putem avea doar tranzitie i→ j- daca nu exista a ∈ A astfel ıncat δ(i, a) = j, atunci R

(0)ij = ∅ (expresie

regulata)

- daca exista a1, ..., al ∈ A cu δ(i, a1) = ... = δ(i, al) = j, atunci R(0)ij =

a1 + ...+ al (expresie regulata)Cazul II: i = j ⇒- daca nu exista a ∈ A astfel ıncat δ(i, a) = i, atunci R

(0)ij = ε (expresie

regulata)

- daca exista a1, ..., al ∈ A cu δ(i, a1) = ... = δ(i, al) = i, atunci R(0)ij =

ε+ a1 + ...+ al (expresie regulata)Presupunem acum ca exista un drum i → j pentru care toate starile

intermediare sunt mai mici sau egale cu k.Cazul I: Drumul nu trece deloc prin starea k. Atunci toate starile inter-

mediare sunt strict mai mici decat k si obtinem expresia R(k−1)ij

Cazul II: Drumul trece prin starea k cel putin o data. Atunci putemımparti drumul atfel:

?>=<89:;i // . . . // ?>=<89:;k // . . . // ?>=<89:;k // . . . // ?>=<89:;k // . . . // ?>=<89:;j

si obtinem expresia regulata R(k−1)ik (R

(k−1)kk )∗R

(k−1)kj . Rezulta R

(k)ij = R

(k−1)ij +

R(k−1)ik (R

(k−1)kk )∗R

(k−1)kj expresie regulata.

In final, limbajul acceptat de automat va fi limbajul asociat expresiei∑j∈F

R(n)ij (suma finita), deci un limbaj rational.

Exemplul II.2.7.8. Consideram automatul determinist A dat prin

// ?>=<89:;1

1

0 // ?>=<89:;2

0,1

//

CC-Matematica 2 10

Atunci L = L(R(2)12 ). Calculam:

R(2)12 = R

(1)12 +R

(1)12 (R

(1)22 )∗R

(1)22

R(1)12 = R

(0)12 +R

(0)11 (R

(0)11 )∗R

(0)12

R(2)22 = R

(0)22 +R

(0)21 (R

(0)11 )∗R

(0)12

Avem

R(0)11 = ε+ 1

R(0)12 = 0

R(0)21 = ∅

R(0)22 = ε+ 0 + 1

De aici rezulta

R(1)12 = 0 + (ε+ 1) · (ε+ 1)∗ · 0 =

= 0 + (ε+ 1)∗ · (ε+ 1) · 0= 0 + (ε+ 1)∗ · (0 + 10)

= 0 + 1∗ · (0 + 10)

= 0 + 1∗ · 0 + 1∗10

= 0 + (1∗ + 1∗1)0

= 0 + 1∗ · 0= 1∗ · 0

si

R(1)22 = ε+ 0 + 1 + ∅ · (ε+ 1)∗ · 0 =

= ε+ 0 + 1 + ∅= ε+ 0 + 1

dar si

R(2)12 = 1∗ · 0 + 1∗ · 0 · (ε+ 0 + 1)∗ · (ε+ 0 + 1) =

= 1∗ · 0 + 1∗ · 0 · (ε+ 0 + 1)∗

= 1∗ · 0 + 1∗ · 0 · (0 + 1)∗

= 1∗ · 0 · (0 + 1)∗

In final, rezulta L = L(1∗ · 0 · (0 + 1)∗)

Curs 7

II.3 Grupuri

II.3.1 Definitie. Exemple

Definitia II.3.1.1. Un grup G este o multime, ımpreuna cu o operatie binarape G, notata · : G×G −→ G, (x, y) −→ x · y, astfel ıncat:

(G1) (Asociativitate) (x · y) · z = x · (y · z), (∀)x, y, z ∈ G;

(G2) (Element neutru) (∃)e ∈ G astfel ıncat x · e = e · x = x (∀)x ∈ G;

(G3) (Inversabilitate) (∀)x ∈ G(∃)x−1 ∈ G astfel ıncat x ·x−1 = x−1 ·x = e.

Daca ın plus are loc:

(G4) (Comutativitate) x · y = y · x, (∀)x, y ∈ G,

spunem ca G este abelian sau comutativ.

Exemplul II.3.1.2. (i) (Z,+) si (Zn,+) sunt grupuri abeliene.

(ii) (Z, ·) si (Zn, ·) sunt doar monoizi. Dar pentru orice monoid M , multimeaelementelor inversabile formeaza un grup, notat U(M). In particular,avem: U(Z) = {−1, 1}, grup multiplicativ cu 2 elemente, U(Zn) ={k ∈ Zn | (k, n) = 1} grup cu φ(n) elemente.

Merita reamintita aici metoda de determinare al inversului unui ele-ment k ∈ U(Zn). Acesta se bazeaza pe urmatoarele observatii: fiinddate doua numere ıntregi a, b ∈ Z∗, cel mai mare divizor comun alacestora este (a, b) = d ⇔ (∃)k, l ∈ Z, ak + bl = d. De asemenea,(a, b) = (a, b−a). De exemplu, sa determinam inversul lui 3 ın U(Z47).Avem (3, 47) = 1, obtinut prin algoritmul lui Euclid astfel:

47 = 3 · 15 + 2

3 = 2 · 1 + 2

1

CC-Matematica 2 2

de unde rezulta ca

1 = 3− 2 · 1= 3− (47− 3 · 15) · 1= 3− 47 · 1 + 3 · 15 · 1= 3 · 16− 47 · 1

Trecand la clase de resturi modulo 47, obtinem

1 = 3 · 16− 0 · 1= 3 · 16

Deci (3)−1 = 16.

(iii) (Mn(R),+) este grup abelian, dar (Mn, (R), ·) este doar monoid. Defapt, U(Mn(R)) = {A ∈ Mn(R) | detA 6= 0} (si se noteaza de obiceicu GLn, grupul general liniar de ordin n).

(iv) Fie X o multime si (XX , ◦) monoidul functiilor definite pe X cu valoritot ın multimea X. Atunci U(XX) = {f : X → X | f bijectie }. Acestgrup se mai noteaza si cu SX . Reamintim ca o functie bijectiva semai numeste si permutare. Avem deci (SX , ◦,1X) grupul permutarilormultimii X (grup necomutativ daca |X| > 2). Daca X este finita,|X| = n, atunci SX se mai noteaza si Sn si |Sn| = n!.Cazul n = 3: putem considera X = {1, 2, 3}; vom reprezenta o functie

bijectiva f : X → X printr-un tabel

(1 2 3

f(1) f(2) f(3)

). Se obtine

astfel

S3 =

{(1 2 31 2 3

),

(1 2 32 1 3

),

(1 2 33 2 1

),

(1 2 31 3 2

),

(1 2 32 3 1

),

(1 2 33 1 2

)}

Notand 1 =

(1 2 31 2 3

), f =

(1 2 32 1 3

)si g =

(1 2 32 3 1

), atunci

avem: f 2 = g3 = 1, g2 =

(1 2 33 1 2

), fg = g2f =

(1 2 31 3 2

), gf =

fg2 =

(1 2 33 2 1

).

(v) Grupul diedral Dn (grupul simetriilor poligonului regulat cu n laturi).Vom prezenta doar cazul n = 4: consideram un patrat ımpartit ın 4

parti egale:2 13 4

. Asupra acestui patrat vom efectua urmatoarele

transformari:

CC-Matematica 2 3

• Rotatii ın sens trigonometric ın jurul centrului patratului:

R0 :2 13 4

, R90 :1 42 3

, R180 :4 31 2

, R270 :3 24 1

.

• Reflexii fata de axele de simetrie:

S| :1 24 3

, S− :3 42 1

, S/ :4 13 2

, S\ :2 31 4

Fie D4 = {R0, R90, R180, R270, S|, S−, S/, S\}. Atunci multimeaD4 este ınchisa la operatia de compunere a functiilor (exercitiu: scrietitabla!). De exemplu, R90 ◦ S| = S\, S| ◦ R90 = S/. Cum operatiade compunere a transformarilor (functiilor) este asociativa si fiecaretransformare este inversabila (de exemplu, fiecare simetrie este propriasa inversa), rezulta ca D4 este un grup necomutativ cu elementul neutruR0.

Definitia II.3.1.3. O submultime H a unui grup G se numeste subgrupdaca:

(SG1) (∀)x, y ∈ H ⇒ x · y ∈ H

(SG2) e ∈ H

(SG3) (∀)x ∈ H ⇒ x−1 ∈ H

(conditia (SG2) nu e necesara; rezulta din (SG1) si (SG3)).

In particular, orice subgrup H este grup cu operatia indusa, cu acelasielement neutru.

Exemplul II.3.1.4. (i) {0} este subgrup ın (Z,+). La randul sau, Z estesubgrup de exemplu ın (Q,+).

(ii) Subgrupurile lui S3:

S3

vvvvvvvvv

jjjjjjjjjjjjjjjjjjjj

HHHHHHHHH

UUUUUUUUUUUUUUUUUUUU

{1, f} {1, fg} {1, gf} {1, g, g2}

{1}

HHHHHHHHH

TTTTTTTTTTTTTTTTTTTT

vvvvvvvvv

iiiiiiiiiiiiiiiiiiii

CC-Matematica 2 4

(iii) Subgrupurile grupurilor (Z12, +) si (U(Z12), +) (unde U(Z12 = {1, 5, 7, 11}):

Z12

JJJJJJJJJJ

ppppppppppp

{0, 2, 4, 6, 8, 10} {0, 3, 6, 9}

{0, 4, 8} {0, 6}

UUUUUUUUUUUUUUUUUUUU

{0}

MMMMMMMMMMMM

uuuuuuuuuu

U(Z12)

uuuuuuuuu

JJJJJJJJJ

{1, 5} {1, 7} {1, 11}

{1}

HHHHHHHHH

uuuuuuuuuu

Ordinul unui grup G este numarul de elemente al multimii G (posibil∞ ). Ordinul unui element x ∈ G este cel mai mic numar natural n astfelıncat xn = e (sau ∞ daca nu exista asemenea n ). Daca x ∈ G, atunci< x >= {e, x, x2, x3, . . .} este subgrup (numit subgrupul ciclic generat dex) de ordin n egal cu ordinul lui x.

Teorema II.3.1.5. (Lagrange) Fie G un grup finit si H ⊆ G un subgrup.Atunci |H| | |G|.Corolarul II.3.1.6. Fie G un grup finit de ordin |G| = n si x ∈ G. Atuncixn = e.

Exemplul II.3.1.7. Fie p un numar prim. Atunci U(Zp) = {1, 2, ..., ˆp− 1}si din Corolar rezulta kp−1 = 1,∀k ∈ U(Zp). In particular, pentru oricex ∈ Z prim cu p, avem xp−1 ≡ 1(mod p) (teorema lui Fermat).

Aplicatie: test partial pentru detectarea numerelor prime:

• Alegem x numar natural nedivizibil cu p;

• Daca xp−1 6≡ (mod p), atunci p nu e prim.

Testam p = 35. Alegem x = 2. Avem 234 ≡ 9(mod 35), deci p nu e prim.Testam acum p = 341 = 11 · 31. Alegem x = 2. Atunci 2340 ≡ 1(mod 341),deci rezultatul nu este suficient. Alegem si x = 3. Atunci 3340 ≡ 56(mod 341),deci 341 nu e prim.

II.3.2 Grupuri ciclice ın criptografie. Protocolul Diffie-Hellman (1976)

Este o metoda prin care doua parti pot comunica prin mesaje secrete peun canal public de comunicatie, fara sa fie nevoie de o terta parte sau schimboff-line; se bazeaza pe conceptul de cheie publica privata:

CC-Matematica 2 5

(i) Se fac publice urmatoarele elemente: un numar prim mare p si unnumar g primitiv modulo p (adica multimea resturilor modulo p alenumerelor g, g2, . . . , gp−1 coincide cu {1, 2, 3, ..., p− 1}).

(ii) Utilizatorii Alice si Bob doresc sa stabileasca o cheie secreta.

(iii) Alice alege o valoare aleatoare x ∈ Zp, calculeaza a ≡ gx(mod p) sitrimite rezultatul lui Bob pe canalul public.

(iv) Analog Bob alege y ∈ Zp, calculeaza b ≡ gy(mod p) si trimite rezultatullui Alice.

(v) Alice calculeaza bx ≡ (gy)x ≡ (gx)y ≡ ay(mod p).

(vi) Bob obtine acelasi rezultat.

(vii) K = bx = ay este cheia privata care o vor utiliza ın viitor.

Daca un al treilea utilizator Eve urmareste comunicarea, atunci afla p, g, a,b, deci are de rezolvat sistemul

gx ≡ a(mod p)

gy ≡ b(mod p)

pentru a descoperi cheia privata k = ay = bx. In practica, aceast lucru estefoarte dificil.

Exemplul II.3.2.1. Fie p = 7, g = 3.

• Alice alege cheia x = 1, iar Bob alege y = 2.

• Alice calculeaza cheia sa publica a ≡ gx(mod p), a = 3 si o trimite luiBob.

• Bob calculeaza cheia sa publica b ≡ gy(mod p), b = 2 si o trimite luiAlice.

• Alice calculeaza K ≡ bx(mod p), K = 2

• Bob calculeaza k ≡ ay(mod p), K = 2

Deci K = 2 este cheia secretape care o vor folosi ın viitor pentru a comunicamesaje private.

CC-Matematica 2 6

II.4 Inele. Corpuri

II.4.1 Definitie. Exemple

Definitia II.4.1.1. Un inel R este o multime, ımpreuna cu doua operatiibinare, notate + : R×R −→ R, · : R×R −→ R, astfel ıncat:

(R1) (R,+) este grup abelian.

(R2) (R,·) este monoid.

(R3) (Distributivitate) x · (y + z) = x · y + x · z, (∀)x, y, z ∈ R, (x+ y) · z =x · z + y · z, (∀)x, y, z ∈ R

Proprietati suplimentare

(i) Inel comutativ: x · y = y · x, (∀)x, y ∈ R.

(ii) Inel boolean: x · x = x, (∀)x ∈ R.

(iii) Inel integru: (∀)x, y ∈ R \ {0}, x · y 6= 0 (avem voie sa simplificam ladreapta sau la stanga).

(iv) Corp: (∀)x ∈ R \ {0}, x este inversabil ın raport cu operatia ·.Exemplul II.4.1.2. (i) (Z,+, ·) este un inel comutativ integru.

(ii) (Mn(R),+, ·) este un inel necomutativ si cu divizori ai lui zero.

(iii) (Q,+, ·), (R,+, ·), (C,+, ·), (Zp,+, ·) (p prim) sunt corpuri comutative.

(iv) Exista si corpuri necomutative: corpul cuaternionilor H ( dupa nu-mele matematicianului W.R. Hamilton), avand drept elemente tupluride forma q = (a, b, c, d) cu a, b, c, d ∈ R, cu operatia aditiva - adunareape componente. Pentru operatia multiplicativa, notam 1 = (1, 0, 0, 0),i = (0, 1, 0, 0), j = (0, 0, 1, 0), k = (0, 0, 0, 1). Atunci orice q ∈ H,q = (a, b, c, d) se mai scrie q = a ·1 + b · i+ c · j+d ·k. Definim operatiamultiplicativa prin:

1 · 1 = 1

1 · i = i · 1 = i

1 · j = j · 1 = j

1 · k = k · 1 = k

i2 = j2 = k2 = −1

i · j = −j · i = k

j · k = −k · j = i

k · i = −i · k = j

CC-Matematica 2 7

si extindem prin liniaritate la toate elementele lui H. Se obtine astfelpe H o structura de inel necomutativ, ın care orice element q ∈ H\{0}este inversabil, cu inversul: q−1 = 1

a2+b2+c2+d2(a · 1− b · i− c · j − d · k),

deci un corp necomutativ.

Teorema II.4.1.3. Orice corp finit k este comutativ si exista p, n ∈ Ncu p prim astfel ıncat |k| = pn. Mai mult, oricare doua corpuri finite cuacelasi numar de elemente sunt izomorfe (izomorfism de corpuri: bijectiecare pastreaza cele doua operatii, elementele simetrizabile si inversabilitateaın raport cu operatiile).

Un corp finit cu pn elemente se mai numeste si corp Galois si se noteazaGF (pn) sau Fpn .

Constructia unui corp Galois cu pn elemente: fie P ∈ Zp[X] un polinomireductibil de grad n; atunci multimea resturilor la ımpartirea cu P formeazacorpul dorit ın raport cu adunarea si ınmultirea polinoamelor modulo P .

Pentru p = 2, asociind fiecarui polinom a0+a1X+. . .+an−1Xn−1 ∈ Z2[X]

secventa coeficientilor sai (a0, a1, . . . , an−1) ∈ (Z2)n, obtinem o structura de

corp pe multimea stringurilor binare de lungime n.

Exemplul II.4.1.4. Corpul GF (23) (realizat pe multimea (Z2)3).

Cautam un polinom de grad 3 ireductibil din Z2[X]; din cele 8 polinoameexistente, se verifica usor ca doar X3+X+1 si X3+X2+1 sunt ireductibile.Alegem de exemplu P = X3 + X + 1. Atunci resturile la ımpartirea cu Psunt:

0←→ 0001←→ 001X ←→ 010X + 1←→ 011X2 ←→ 100X2 + 1←→ 101X2 +X ←→ 110X2 +X + 1←→ 111Pentru adunarea si multiplicarea modulo P , avem de exemplu

(X2 + 1) + (X2 +X + 1) = 2X2 +X + 2

= X(mod P )

si

(X2 + 1)(X2 +X + 1) = X4 +X3 +X2 +X2 +X + 1

= X4 + 2X2

= X4

= X2 +X(mod P )

CC-Matematica 2 8

Exercitiul II.4.1.5. Scrieti tabla ınmultirii ın (Z2)3 folosind corespondenta

de mai sus si verificati ca orice string diferit de 000 este inversabil.

Fie acum Bbbk un corp si k[X] = {a0 + a1X + . . . + anXn | a0, a1, an ∈

k, n ∈ N} inelul polinoamelor cu coeficienti ın k.Proprietati:

(i) k[X] inel integru.

(ii) (Teorema ımpartirii cu rest) (∀)P,Q ∈ k[X], Q 6= 0, exista ın modunic doua polinoame C,R ∈ k[X], astfel ıncat gradR < gradQ siP = Q · C +R.

(iii) (Teorema lui Bezout) Fie P ∈ k[X], a ∈ k. Atunci P (a) = 0 ⇔X − a | P .

(iv) P ∈ k[X], gradP = n =⇒ P are cel mult n radacini.

Consecinta II.4.1.6. Orice functie f : k −→ k, unde k este un corp finit,este polinomiala (solutie: polinomul de interpolare Lagrange).

II.4.2 Aplicatie ın criptografie. Secret Sharing

Este metoda de a distribui un secret la un grup de participanti, fiecaruiparticipant fiindu-i atribuita cate o parte a secretului1. Secretul poate fireconstituit doar prin combinarea a cel putin un numar fixat de participanti.Ideea: asa cum doua puncte din plan determina ın mod unic o dreapta( decio functie de gradul I), 3 puncte determina o parabola(o functie de gradul II),etc., k puncte ın plan vor determina ın mod unic un polinom de grad k − 1.Fie n numarul participantilor, k < n si S mesajul secret(un element dintr-uncorp finit k). Alegem la ıntamplare k − 1 elemente a1, a2, a3, ..., ak−1 ∈ k siluam a0 = S. Construim polinomul

P (X) = a0 + a1X + . . .+ ak−1Xk−1

si calculam (i, P (i)) pentru i = 1, n (deci corpul k va avea mai mult de nelemente). Fiecarui participant i se atribuie o pereche (i, P (i)) de elementedin corpul k (cunoscut de toti). Fiind dat orice grup de k participanti sepoate reconstitui polinomul si afla mesajul secret S = a0.

Exemplul II.4.2.1. Fie n = 5, k = 3, P = 2X2 + 7X + 10 ∈ k = Z11.Secretul este S = 10. Mesajele participantilor sunt: P (1) = 8, P (2) = 10,

1A. Shamir, 1979.

CC-Matematica 2 9

P (3) = 5, f(4) = 4, P (7) = 7. Alegem grupul de participanti (1, 2, 4). Atuncipolinomul reconstruit este:

P (X) = 8 · (X − 2)(X − 4)

(1− 2)(1− 4)+ 10 · (X − 1)(X − 4)

(2− 1)(2− 4)+ 4 · (X − 1)(X − 2)

(4− 1)(4− 1)

si

S = P (0)

= 8 · 2 · 4 · 10−1 · 8−1 + 10 · 1 · 4 · 1−1 · 9−1 + 4 · 1 · 2 · 3−1 · 2−1

= 8 · 2 · 4 · 10 · 7 + 10 · 1 · 4 · 1 · 5 + 4 · 1 · 2 · 4 · 6= 3 + 2 + 5

= 10

II.5 Latici si algebre Booleene

II.5.1 Latici

Laticile pot fi definite ın doua moduri: fie ca multimi cu anumite structuride ordine, fie ca algebre (multimi cu operatii), ınsa cele doua definitii suntechivalente:

Definitia II.5.1.1. O latice este un poset (L,≤) cu proprietatea ca pentruorice x, y ∈ L, exista sup{x, y} si inf{x, y}.

Reamintim ca pentru o submultime X ⊆ L se defineste marginea sasuperioara - sau supremum - prin:

a = supX ⇐⇒

{(∀)x ∈ X, x ≤ a

(∀)b ∈ L astfel ıncat x ≤ b, (∀)x ∈ X =⇒ a ≤ b

Analog definim marginea inferioara sau infimum:

a = infX ⇐⇒

{(∀)x ∈ X, a ≤ x

(∀)b ∈ L astfel ıncat b ≤ x, (∀)x ∈ X =⇒ b ≤ a

Definitia II.5.1.2. O latice este o multime L ımpreuna cu doua operatiibinare ∧ : L× L −→ L, ∨ : L× L −→ L astfel ıncat

(L1) (Asociativitate) x∨(y∨z) = (x∨y)∨z, x∧(y∧z) = (x∧y)∧z (∀)x, y, z ∈L

CC-Matematica 2 10

(L2) (Comutativitate) x ∧ y = y ∧ x, x ∨ y = y ∨ x (∀)x, y ∈ L

(L3) (Idempotenta) x ∧ x = x, x ∨ x = x (∀)x ∈ L

(L4) (Absorbtie) x ∨ (x ∧ z) = x, x ∧ (x ∨ z) = x (∀)x, z ∈ L

Propozitia II.5.1.3. Cele doua definitii sunt echivalente.

Demonstratie. Def.II.5.1.1⇒ Def.II.5.1.2: notam x ∨ y = sup{x, y} si x ∧y = inf{x, y}, (∀)x, y ∈ L.

Def.II.5.1.2⇒ Def.II.5.1.1: relatia de ordine este x ≤ y ⇐⇒ x ∧ y =x (∀)x, y ∈ L

Exemplul II.5.1.4. (i) (P(X),∪,∩) este o latice.

(ii) Fie X o multime. Atunci multimile fuzzy peste X formeaza o latice(reamintim ca o multime fuzzy peste X este data printr-o functie f :X −→ [0, 1]). Pe multimea FuzzyX = {f : X −→ [0, 1]} punem relatiade ordine f ≤ g ⇐⇒ (∀)x ∈ X, f(x) ≤ g(x). Atunci sup{f, g}(x) =max(f(x), g(x)) si inf{f, g}(x) = min(f(x), g(x)), (∀)x ∈ X.

(iii) Fie G un grup abelian cu operatia notata aditiv. Atunci multimea sub-grupurilor sale formeaza o latice ın raport cu incluziunea, cuinf{H1, H2} = H1 ∩ H2 si sup{H1, H2} = H1 + H2 = {h1 + h2 | h1 ∈H1, h2 ∈ H2}

(iv) Nu orice poset este o latice: fie de exemplu, multimea {1, 2, 3, 12, 18, 36}ordonata prin divizibilitate. Atunci perechea (2, 3) nu are margine su-perioara, iar perechea (12, 18) nu are margine inferioara.

(v) Multimea numerelor ıntregi (Z) cu x ∧ y = cmmdc(x, y) si x ∨ y =cmmmc(x, y) este o latice.

(vi) Exemple de latici finite: ·

·

������� · ·

=======

·

=======

�������

si ·

·

������� ·

=======

·

·

=======

��������������

sunt (sin-

gurele!) latici cu 5 elemente.

CC-Matematica 2 11

II.5.2 Algebre Boole

Definitia II.5.2.1. O algebra Boole este o multime B ımpreuna cu: douaoperatii binare ∧ : B × B −→ B, ∨ : B × B −→ B, o operatia unara(−)′ : B × B −→ B si doua constante ( operatii nulare ) notate 0, 1 ∈ B,astfel ıncat:

(B1) (Asociativitate) x ∨ (y ∨ z) = (x ∨ y) ∨ z, x ∧ (y ∧ z) = (x ∧ y) ∧z (∀)x, y, z ∈ B

(B2) (Comutativitate) x ∧ y = y ∧ x, x ∨ y = y ∨ x (∀)x, y ∈ B

(B3) (Idempotenta) x ∧ x = x, x ∨ x = x (∀)x ∈ B

(B4) (Absorbtie) x ∨ (x ∧ z) = x, x ∧ (x ∨ z) = x (∀)x, z ∈ B

(B5) (Distributivitate) x∨ (y ∧ z) = (x∨ y)∧ (x∨ z), x∧ (y ∨ z) = (x∧ y)∨(x ∧ z) (∀)x, y, z ∈ B

(B6) (Top si bottom)(primul si ultimul element) x∨1 = 1, x∧1 = x, x∨0 =x, x ∧ 0 = 0(∀)x ∈ B

(B7) (Complementaritate) x ∧ x′ = 0, x ∨ x′ = 1(∀)x ∈ B

Deci o algebra Boole este o latice cu proprietati suplimentare. Dar atentie:nu orice latice este si algebra Boole. Fie de exemplu FuzzyX multimeamultimilor fuzzy peste X, ca mai devreme, cu 0 functia constanta X −→[0, 1], x −→ 0 si 1 functia constanta X −→ [0, 1], x −→ 1 si complementareadata de f ′(x) = 1− f(x) (atentie: nu este vorba despre derivata functiei f !).Atunci FuzzyX nu este o algebra Boole, caci de exemplu relatia f ∨ f ′ = 1este falsa ( max(f(x), 1− f(x)) nu este ıntotdeauna egal cu 1 pentru oricarex).

Corolarul II.5.2.2. In orice algebra Boole au loc relatiiile:

(i) (x′)′ = x

(ii) (x ∨ y)′ = x′ ∧ y′

(iii) (x ∧ y)′ = x′ ∨ y′

CC-Matematica 2 12

Demonstratie. (i) Sa remarcam mai ıntai ca x′ e unicul element cu propri-etatea (B7): daca exista x1 si x2, atunci

x′1 = x′1 ∧ 1

= x′1 ∧ (x ∨ x′2)= (x′1 ∧ x) ∨ (x′1 ∧ x′2)= 0 ∨ (x′1 ∧ x′2)= x′1 ∧ x′2

si analog x′2 = x′1 ∧ x′2, deci x′1 = x′2. Acum afirmatia (i) rezulta imediat.(ii) Este suficient sa aratam ca (x′∧y′)∨(x∨y) = 1 si (x′∧y′)∧(x∨y) = 0.

Dar

(x′ ∧ y′) ∨ (x ∨ y) = [(x′ ∧ y′) ∨ x] ∨ y= [(x′ ∧ x) ∨ (y′ ∨ x)] ∨ y= [0 ∨ (y′ ∨ x)] ∨ y= (y′ ∨ x) ∨ y= (y′ ∨ y) ∨ x= 1 ∨ x= 1

si analog (x′ ∧ y′) ∧ (x ∨ y) = 0.(iii) La fel.

Exemplul II.5.2.3. (i) (P(X),∪,∩, (−)c, ∅, X) este o algebra booleana.

(ii) ({true, false}, or, and, not, false, true) este o algebra booleana (se obtinedin exemplul precedent pentru X o multime cu un singur element).

Observatia II.5.2.4. Orice algebra booleana este si inel boolean si reciproc:daca (B,∨,∧, (−)′, 0, 1) e algebra booleana, atunci x+ y = (x∧ y′)∨ (x′ ∧ y)si x ·y = x∧y determina (B,+, ·) inel boolean (+ este echivalentul diferenteisimetrice sau XOR); reciproc, daca (B,+, ·) este inel boolean, atunci x∨y =x+ y + x · y si x ∧ y = x · y conduc la o algebra booleana cu x′ = 1− x.

Teorema II.5.2.5. (M. Stone) Fie B o algebra booleana finita. Atunci existao multime X astfel ıncat B ∼= P(X) (izomorfism de algebre Boole: bijectiecare pastreaza ∨, ∧, 0, 1 (rezulta ca pastreaza si (−)′ )).

~

_ 11_ U ,/J., e.,.,"-'\J2 C) '-<J lAJ tQ.1 {(2

- --------

-~flJ-z;;;; --- ,,->- ~u

o a-tiQ r-o::pk ~ r o..:iJ ~ J:.u~~ ta,'"" ~ /;) c.o..fu kLa. _'da c.aU

q > 0 lie ~ e C1. CUe! Q~ QfdV ~~ c:£iJ~ ~ Q ~ ~ C<.<.) ).."

v? ) d...o..< ~ rFUJ U;L t.u..o eu//J ca..I...a.:J C ~UA..u ~ e.u Q ) t?e

!'Uut..U~0 rcl..u4u.1l ~ C2 ~ ~ JaCf2V a ~ ~v-)

...k t?~ ~~ 'ClfJ a..t ~ ~ . ~7v-. €.U..L d.tJ.., a CVrf ~ ~ C<aV

1.u.~ < ~ a dB..I ~ cn-u' '?:-~tey..I (..(.liJ -&.vJ./!;'UL lie d-f)..u' Cu ....,Cae::vv',--'--~ JeJ..ie...r0.-6I~a~ ) ~ ~ft'IA..I. a.t~lA.P.a. c;(, ~~ II(!C/.vvaR

~~ if r~ u..u e..r,~ (£.0 CA...tJJ ~Jv- (k) +).:;O/< ') 11<) ;

~ 1<.u '7~ WCl-&-u'a..2. ~ Cn.r k ~.ft.<f::'-u "zc.v.J Iv~ '6 ~

• () tU...t.u e:t:.u UJ e ~ &..av V)

("k.u u...u t u.e c..I-in.L ( ~u.t e..u ~

~ /)oua..v ~ a..tfl? ~.

~ Go~ ~ , eRg u.; eu:tlt ~ V"o UJ..

c::tiu ~ Ie ~ ifC/L btt..iu..LI' ~~)

8): Vx V -~> V

Mu..h::iJ~'ca"'U-O Cu r.>~ G " k)( V - ,> Vo ~ t:t>%~e. :

(s V1) AI"dOCJ~7CA~ ad..u..u r '1O/Lu tM c..A9.u' ~

(=fE; cr).f£J ~ = '>< (j)((j <£J ~ ) (fh X'd) '6 (; V( S II~.) c..o t..uu J.a:::c<.7w 4-0. /.e Q. (') •.1).. ~_'1

~ vee...trTu ~

x (f)d ~eY fj) ')( (-16 rx)d -E ((

@( S l/3) E x i?J"l-eu.~ '€.&<.U e.uZv '&.u ' tIf e..u teu ~ ~ a.du..u c:u €.a- voeUt!-u' ~

l~) 0v -E:- V ~ ~c2X ?C. ~ 0.; =- 0v f£) x =- ~ <..'1i> ~ <? (/

(S V It) £xi ~ ~ """/}-v €Lv' -<.u ~ Cu a.t::b..uJ cv,,-<>- I;e~

(bL) 't: ~ v (:JJ _ ~ ~ l; ~ --Zu~;t -x -f (-x) =(-X) -f x -z 0v

( S VF) I1I.l &J-h' c.a t'\.L£2 e.u t'7) Ct:J.la ~ ~ Uf-<.j J-.a.:L

1/<0 ~ =- x. <...12)?C E V

(8) l/ ~ ) 4J-o CJ'~ ..;'Vi ~ I...t-t.U e:.t;,?:f-0'Ca/tVl e..u r::,Ga €c"'U '

0( (9 (t 0 ",,-)= (0<'1') (9 'X (11) o()f> E k > '" <2 lJ

( 2) (/ ':f) ~~ 1-£ u..:L "JLA-fo..li..a.. r.>CD l2a (1A' ~

(0( -t ?-') G;x - 0{ Q?<. -ft (9'><- Ct!> 0( '!?> k) "-

( 8 l/ J>) ~ ~ 1~ u...1IJ v-I~ w C~9..<./ 4

D( 0 ( 'X.+(J ) = c{0><. + ex GJ (;;I, 0( e k ) >r.,J E V

J!e ~<!eA.v'; c...aV (SV1) _ (SV/r) w ~ e-au (iJ?@j Ov) "-Z

Lt..u ry ~~I/:> /QA (SVI) -(SVb') u,v UJoun~

fk),? Ik) Cl.cf'ti» "'" r V ~ ~,?rD~fv e.- 7(e V u.u Ie< - Sf~ I/e c.I-\tv 'cJJ, A-ci..t..u 0 '

1) CVE) 0u ::::.0(/ (-M D< E K

:2) (()X0?t:. -:::. 0V C.t6 ~ € V3) 0< 0 X- ~ 0 v ) u..vd?..t. 0( € k) ~ E- V (. ;)0( ~ Ok t?a..u...

(Sl/3) (SVR)I) ex GOv = 0(0(01/ + OV) = 0<'001/ + o(()0V j+{-C(0D,;J

0v :::-0(8 Ov

~

; I'=-> ~tu ~ EK ~ ;/ C<;; Ok JCU{

0( <.u ve... .ta..P.:,)'(! u.v

~ ~ 1/~ <fv....e O(--t,

C('(Jz = °v I~-I ->

'7 --Io(G(C(G~) '= o(QOV 2;>

(D( '"f to() G °vx. -=.J

1k 0 ':X... - Ov -=-)

x... - Ov~_rle_C_-t·~ Pounrd-u-R ~/'~) a~'4l/ (k)-I) 4~~fQ +0<" r V ~~,.E)(~ Jj '2{ 1-A.UJ~7LUe.Q f/e~'~ ~'8ev' ~ ~~ ,

;

I)OU-' t.Lok C-u S /J-h o::L "1 e... ?b-f. L ~ ~'UJ E.U.I:J VVta.-e . £&t.ueu~t! ') !J ~

;-uo d2u tPu eu.., .La 1 ~ ').( a-u Sx S t=- { ( q) -e:) I a:) t; <= S;(;0 UJ. lIU..t u...u I ~0J ~ ~ .' (a) ~) e.Z ~u.Je..u..£J

t>-Je-u.:t:4:T <:I~ ~;r-uea ~ ~I -e: / -e1e. S> x S ~ tJ ~e ~ LUz-'-U£ 1-0 ~ a.-- 14 ea:v ~ ~

'eclv 'I./Q../l €A , 7lof;J .'

~

.h.u ~ '<..U e..Q "y'a c.A-L- S x Sh ;:::{L (4') 6 )] / 4 ) b C S'!J (9 vrJQL

nJ- R,.1'>-7 R. /J'~" •~ k Cu f./ .:!::> t?-.J I">e. I/a UU U.J... J w.u 'CAJ7~ ~ Ve~ ~ ~

dU.t rr~ , ?e- ~ ~ KocfJ..P CfLu.t vkLucf,,/o~ 19-/4~~

t..& w ~ v ) 7A.u. U.u'~ v a.d..u ~A.t..a ~ ch;;.u' ~ ,.

--yV-3

----\.u...u ~ c::i.Q c..a L/ ..A..I '> -::::£/a;t:~) J &-..J ~ '::)-= [ (q2. 'e2.}"7 ) a:li..u../ (.I 7

/ I / J<. .., -.l ) VI<..~ ---? •

~ I c:f!),u 2. -eN a.f.ar.!rOL ~ e dv va...!eu:p: b tQeefUJ ~~ . 6UI e..uJ!iiT-

~!!1A.uJt Q~d. ' ~OeLu e... E 5 ~ ~~7 {a,,e.) l2(q~,b2)-ftJ,

-t,/

"::=.-). a~ €-

._---~Q 2- -&1.-

~ ~~1.u.. I~~e Cv c.&IZtr/€, ('Ol) -e/} -:N, ('0,,<:)

~ ' ~ ~o fA @ 1J- :::: [@:ll) d)J ) L<..u ~ cf ~ ~ ;!...aJW ~Q.

RvtEf ,z.R. {rutoed{/' rc;u V" eu.., :~7~~ Ve~~~

'::fnu...t ~ l..4..l N ~'a..u Gu

L-(~J C~ a E: S ~ w Gu~d-u..R- Lu-u-tL vt<'c.A12 Zi --[(0) ~ )]1<..)

dcvt- ~ -;;- -=-[{ 6J Q)J J< 'Z. a; Li.u~ocLuQUJ ~ 0 ~~e. ~ <.u.» eet~·C<UJ e.u.

0t.u LU IU't! Iu..a..k ; Q ! & x t?J; y 0'3 ) / / n..- '

eX ~ 1i2) U-e V-3 = ~ 0(' 0 u) ~ v:e~ ~ C0Le.

C4 .R.u-urr LU e ~ j-I UJ e..a ..eu...,' -zl w..u &:,~'Ca..fuu ec., /0(1)

q CR..tl o~ <C(0 ~ c{'/7e. ~ Q. Ct ~ tfJ-UUJ {d-a Cfov 0( .> 0 ? r-u L

0( <: 0 rH: ('7)e.iv't..u ~ 'Or ~ ) ~.~ 0(' ~ 0 C-t9-U d...u ~ ~ V'f~

~ 0).~0 ' ( ~ ) (i;> )0) ~"'-' u.u ~ !H' ~'a..e ~

4r2r e.. I1A-u <..u. e re ~ It I 0 ~ .e.v U-U..J Io:!ZJr ?)

tfl..) f( e (~? -f ) .) -U..JJ GqlrV-~ .Iv( e ;)v-J<, ~Ct' I< -= ~~ 16--n ~.

tV err1'\..0- Ltu k - ~~ V'e ch-U tzR ) e.u f9r ra:p)~ '(~f ) } 2( n) & ((;J/' . ~) ~(~ -f d" i - ) ~n -I ;r )

o0( 0 (X( _ - x.~) == (01, XI ) _ - ) or~~ 'f )

l \7) 0( E f><) (r;y) } ?( ~ ) J ( :; I) - ) ~ ) E- /<. .l-uJdJ ~~?.UJ; ("VteLL t..u L t'I.~iflf ~ W ~ (o)_.~o))

/r:M. (rJ UJ e... -tu7euJ o...-t.uJ' (?J1.; ) - . ) ~) "4G (- X() _ ) -~)

~ ~ to.Ab7CJJ .~., k -:::172 ) h C 2, /l-&.u0 1i ~ )c:!eu 1v1'CA..-

1;:/ Cu- rL /~/h (~)<1)f ~ '7X- -t ~ ~ C ~V1.£

IR - ~a ,:>p( J , IH c..J-r9..<J ' CLl Cu..

<::>(0 ('"X. -f L;:; ) :::-o(':x -f c-'00'-3) f.< C-rLrJ ~ U-Ut ~ l/ -::::-;) w..u e:zpLU e.a ~''-LO eu..u ~ /([x]~ <2MI' ~ ...;;..,k. ~ /.Iv dLM u..u' bt ~ X ~ ~ u.u.

!<- rr~ 1M cHJ.U'ctP 0.J ~~ ~ .'

@ ; k[x] x k[x] - '> Jerx7

?) Q t k [ x] ? ::.a 0 --I- C4)( -I- qz.X~ __. -I CZu X li.=> Q ~ -go ., ~X f

+ ...LJ, " \/ '-<..t -"..... L:>.4) I":) / ()10 ~ A --.. r ~ ~ =: \..a0 + '(g-o) -t a.r -f -&,. )( +__ _

0; kx k{x] -- ~ k'[x]

0< e k ') ?E k rx] __'> O('Gl = o('ao -I o(tZt)(-f. -fo(c:&tXI1.

k tQ~ €-u€-<:L J k'r)[x] - -{ PE k[x] / r?~"?} ~'-U.-U k __~~ tH Cfi)..(j'a..{J •

r A.--. -T., ~ J1 I ( L-) et..t- I -/ t.A.12. UJ..l k _<i>J:, ••• :. • '- .Ex '€..I. ~ ~ 'Ll - ~ ,.,~ C-c::l -----e..t11{.( ) J," .,I / ;-c--u~

I.JecJ-s-u'a..1 J-u ~ eu O-d.u..u Q...l..eA:t {.( CJ..u. ~ a

Lua::cvLt~:; ~L<...uJep7~ 1.A.P-a.h..i70'~ e.u ~~ '(l<.uc:le.

cloc.av o(~ R?oJ A- t ht,v 1'l (k) A-;:. (a..,j). _ )~07) ,) / [=-/,l..u

01. If ,,( 0( ay) t '_ <!~. ). v·~ ,.,..- v' .....I)..,

"Jv, ~ t.cu au.., ,f'4-' tu, 7'0e" e,Yet.<A1 C2. r.:>c.u... c''') (/0 ~ '" o/a.

~ -f~. i~ee {;~-er--c~'-f)?:Q.

v U-t...t k--~~ Jte cA9-uQ..O ~ U c V ~ 01d0w..u ~7l.Ue

U ~ hu tV t..Z ~ '?4>ah.U V't' c..hJ-u 'c<...R. o...P ~' tI) ---tJ-) ----

( 55 IJ I) (i7S;Jc) d ~ u =::> ~ -I d -t: U

(S5 I/~) Ih o<'~ k)::>: U ~"o(. xU. ~~dJ/~J~(SSIl.(} ~ (<;'SII2.) ?tJI? ~GU?e ~det.lJa..r o(x-;jOd' cU) {ry~jS€ex ~]Cufu.., ~ ~'cp ~?~ ~0 r~ ve~'a...I! 1<.

C!.u ~a..!?U' ~ Curd.u k

O~.J-etv41e I) 2JQ~u U ~ u..u k~ ~~ 1I'e~'CJ ~

U U 0t..u.J ou...e '?Pa...:.t.u ~ aL u,CI ) U? () U 2..... -e. ~ !?J;:h~,) 2.. (/ -.> tt :>

w cI-t;).u .a-flie.. ~) J e UI} () U2.- ; 0( ~ k, A:t;;u..,CJ 1 ?()d (;;UL' ~ t. 'c I-;i;

'Z:> ~ -f l..f )0(. X .£ Ul' L' - /) <.. ~ u..ud.t., Z-f Lf J 0(. ~ E r;, (){/

(7 .») (/ <-Ex et c..,V V *-€-- U U-U. k.~ a.Ii.u ve ~a..f) '?-J U, U c. V

") ):> :> 2-----~cqn A-l:iLu C1 ~ t% U U2- ~ ~~ C.--~ ~ S U2-

Au..u U-t C LIt ,

c:2 ) +;.e (J t..U.1 k ~ ~UZiu treCI-t)..u'aJ ~ y S V 0 ou..Pa UJJJ eN~'/. F ') "") ::>

~v:kl~ No /.Q UJ ? X == {~€ V 1(7.;.u. E N J,c) q',,) O)o{v, E k..//lot.

1· . ) Xu ~ X CV:J/fJ --wcOf z- ~' ~'. ?~. Y ~ 7x I'd-e-~ ~~

'VJJ Uj ~ _~ ~ e d e.u e.ro..:l ~ X .

P,.."'/><r.)?X e. ~7~ IJeChu'aJ2.

<-f/;} ~ Q cav x;; u c V ~ U ~ ~O...UU tie c.hf;..u'~) ~ :>

~Gl7 ~ X ~ (j (~)'~ cU- e.-uau' ..u.u'c ~r~ Q

~;;~ re- X)~. ~ *~

~J ~ 'JY -f ~2.. -I, ~ -f- ;{ , ~2. IK k

21(1 f: ~ / ~.>/, --=?'X.t)')(2..€~UV

~~Ev~ 2

:> ~ ~ Ik'?ct T ~' ')(2 t ~(~ U(/2..) flu

I2e C-J'r L) d.-a c.£ ~ ~ ~/::>(Uf U U2-)) o..1".UJJ Ct 1 ~:Z~':U')~I

u..ucLt o(i~ 04.uE k ~ X,,. ';KwE?~U~, ~tueror/kd

1.€..(je.u1U.oJ fM ~ ) F ku..t. ~ tl-rUru-u e 0~" _.1~« ~~-I-I - . 2f.-<-u E: u'<' A-e:u.uv 7 d f =- C-\:':; 'de I + ~. +~ ~.eE ~ J d-< =-

o!..t+IZtf1 -.+ of.w 2( w £ {J-0 '?: z -}'I TJ 2- ~ L0 -f (; f0 ~V-<..

~ «+ {j~ = ~ (U~ u UZ-) ,.4a c.oU UI () U2- ~{OvY (/?-' kuJ. 0cVe.a U, () U2- = <;f :?))r ~cO duJ..ua ~ofU ~ tJ'e UtJ..u~ U; I'd'j U2- ~

~~ chlCJ 04 r.JW €..UJ. U @ (j___ ..., I 2.....

r!J~ ~~'u ~~ (;-eCh).uCLl IJ Cu.t oJ ~ ~cJ ~aXu' .'~ "0/" e WJ1 r0 V ~ ';" ~ ~ 7~ e II (/" h.p d.a.. l.U..<

ej,., ~~ au -rcif',lj £1.t'~h-..tJ ~ /LLU ~ a1.L~:J ~ ? )

(Bt.u.J d..t. ~ ' ~ . e 1./ t;}..) ~ I \ ~ ' ~ X IJ&Lu c/

7)/1 ,,~ )dJ'X--fJ =0 ~"'-,-+,- . -f%><" -t /'_:;1-1. -+ ftw,jw~ 1'X ~

0( , x ~ 0(, 0(A?C; -+. - -f 0(, % ~ VI c:. ~p /\ ( t1) 0( E k'------" -" /Ek E I<

~) 7X e.;[, u.u ~~ V't' UfJ-u'oJ ~ 1/,

--e) -ke z 7' X ---> "< ~ OCt' ~' 1 o(,'E k ''l':".-e X~ X £ CJ =) ~'€ U ~/ U <LXI ~'Po.p) c&(!J'

~ '= ~ 2tt.-{ . -I- %:x 1'] <2 U =:> ?ox c U,

~cf.e~ i-Qv *e. U1

(j ~ pca.u") ~ V /)y Ll1 -f U2. = i~ (/I?- ?'.< /) :>

( ?]) ~ £. U/ ~ Xz.-£' Uz..) ~ ="::4 1- ')(2.)- ~U1 U/-I U.( -

Sf (VI U U~), (td-e- //uJ UJ ~ ~/o..!fue I'duU-LOW

)

~. #e ~ E.. Uf -{- U2-

.t'Oa:z, 15 '? Cu~ ~ t:<--t:v "Lbt.1 fYu..4, ~ I...u CL A x. ~ 1:» t...uJ ~

"L ~ !I~)e .--u-" J" ( I<.) <c 1<" (IN! CN-L cdo C2.<.u>~ !)l ~..,

/ lrvo f. ' 1)~kU-u...l fJ (1) au ,p~;e ~ Ua~ ~ 2A..uLUOJ' ~ Ca~J

~ /0 a..J!j /J ~eu~ CO c C!.o'-U tg) h a.fUe c...e.u.u' Q..l c:J.J a... ~0J ~

w. Q tv16.-,1 A,~ . tsk- Jv.;;:'C<'~ J.{ "..gk<I/~ cor J.JJ.~f/ocde.

~ ~Cu~ ~ r<..u.Q A

~t .(~~ )+_~_ T xn.~?~ :(;1!A. 0 t,;:::<.u. C (4) -..3 !;'~ / ~.•...

f C,.,., (-4)Je ~' lu..u~) Lue..o... 1Ie~'o _ / AD11 ~ 1'_

~l ~ /?~ <:!.<:U,e ~'()~ e -e. CoIQI.t~/

% Sf f C,(4)r .> C,.,(4) ~ J !.<u ~'7'~" ~ Ie ":h 10 lez u..L

17 /' cL cA?o CUJ~ W-a fc, c.U ..,~"-<) e l A ) ~o. '!;,'u 1J J eLL e rQ.!/

j' cr w..u N~" e.t..{ et:J ~ e '

.!!-. IfI1.L- ~ ~ '0.51 @.o~) (d;.e,' ~ ~aTle.u..A»e-u' (I) j ~

~ /..uu ~ f>-.J Iw. ~~ a ~ ~ 't<... &.u IJctu-6 UI t.liA.I..,

~ ~ ' ~ ~ 0 ? ~ (J' ~ f lA.Q U-l u..u ?J~ (X.ub/ e..u A x.. -- 0

?r"'t l"lu.Ll.jI.<.H.A_ ~7~ .!-J.tle<.u.u &U' A~ 2- 0

y,nu.J-~ U-u ~ ~~ ~ k-~ .11_ ~ ?2.._~__ ~ rre.. ~) if e k Cu.. A- ~ ==- 0 ) A(j - o. A-::tuuCt

A( '>( -Ie!!) '=' <0 ) d..c.' ?c TJ " "'~7e ) ':;' 4{C<''X..) c-

O( A ~ =- 0(. 0 :::0 (-II:> 0( E- k .)

~/o:p." e !">:. Eo k ~/ A z 'Z. 0 j @e.. t.uoka ~J ~ At?-v G-e IA..u UJ ~ ()u.A d <fLU e. ~'A ..., "") ----

~ -t x~ - 0?L., -r ~3 =0

J?C( -f 't'?(-z.. -1 g~ '3 ~ 0 <'=-::> 3 'X.., -r 3A"~ = 0

2~ + !t'?(z -f 6~3 2- 02?c.t -f It 'J( 2.. -f 6::(3 .= 0

(~ f x.3 = - "4-~ ~2.:::- - 2 ~ - G ~~ - z/

't £~~) ~f£;/~~fij;&e., ,~~ A ~(I <0 /

~A ::J~ L; 9 )

2- 4- G

c--

{:..)(~~kkt eu.J 1-1.£ Lu u..R..e It ~~-, ~ CJ'~ Ui.o..tv )e.-U '

A- 2 (~ j) ~ itc< ( ~) :

&e (4) CO l' !(6)) (;j)?; :=!'>< (ef) -f /3(~) Io('f E/12 ?; ""

- !(<><;f3) /o(0rt R )

tlu.J...U 9-U'CL (1A..u u_uJ'/l Iu a..P If-,() o...:L ? I;) u../~ c.a <0 cL~~e.-

ce. chu£ !k<JLUe.re ~ J ~ ~v G4~ A "-( ~1FE £!J?~c h. (4) ) QGu'eJ.JJ ~e ~0'o..:f_~

!1· 'X:.t + (-I),?J(2... ~ to c:---:) I "4 - :l( 2.. 0 ( ? X-t ~ )(~

O 0 CJ z::.0. ~ -I ' 'dt 2... =- ()kc-./

Row (A) ~ ~ (Al) =c 11r-~))IgJ !; ~{,,?U -ft(~)!oI}

?E 02? :; £ (0(-<) / 0( E !K }SJ~~ € cvrDcJo51 wo.h7w';f~ e.-;r.; ,"

f 4, "<t -; 0, 0( L. "'" 0 (=.-,! ?4 = 0

-I ,sy -I- 0, ?( 2- z 0 -?4 :c 0

v u.u I cqw f/ed&<J a.Jl ~ A..u..I ~ Ie, ';' ~) -.):(n ~ l/

<lo~ (giu.-a.Jl:..,7e. ~11.AJ'OJ- Qt..J Ck v-e cJ-s-ul~ ?<.1 ) " . ) ~---- .,-----f)u'CR.. v-ec..hn c:h r ~CL ~ ''"X..I -+ ~. -r ~ I ~ '1 ) LuJ d...t D{1?_ . .;% e k,

(X ~7e.u ecu ) 0v ::-O,::Y -f _ . -f 0, ~~ e () WUI ~~,~

~ -'CU; ) r (() e.tu.u (lW cqve. ~ 'aLO e,(C kQ.1.A..u ~ ~ ca'-J

Q.R ~ u..u r.>~ ~ t4 0(" ? _ J ~ 4G lItJ. WJ e .. ) ,

Sr e..u..J ci: 1M cJ-t:ruJ.' ~,,_ _ ~ ~ ~_~ _7_0-I__ UJ_~ e.ud~_cf..a C<2v ~'CL ClJ-u.., ~ ~7e ~~ 1A..Jll..<...U~ 'V Q en ~ IA..t ~ ~ v,"

~

(jD 0(-1 ?", ) ct& € Ie. J ~·k1-f,,· T %'?(I? ~ 0v =- >0:/ ~ -' -=-~ :: 0k.'-

rt; ~ ~~ / ~~ cQ 1J.e~7 ~/_· '"Xu ~

~7~ ~ eu4~-:,

r:x~ V 1;' 0'; ) <4-' I/'f'CAu' '71.J..UY ...eu..u<... ~d~

~cQ.~ ~u.LOJ' d..acQ:" ~ ~/Uv'a...u'..J Ji.l...t7 WcAru/~

<-e'I/IJ'~ ~cf~ (-=--.::> ~ ~r/')

$) ~Q ~ ~e awN ve c.Aru I (' ~ ~ ~~) e.;;r;, 0v.J

~7 ~r. ~ 0W.JSI -0.2ulC4. ~d~ __

V ~ ~7cU1 ;A 2:/13 3 Zj ~~~(2. 6::; J~

-( -3 '3 0

~~ > olH.DO-AICt Co? (4) = 3 e,(4-j ) ~ <u.

3, C/{A) + (-I)" C' (4) av-(f. If. 2.. 1-0, c3 (A.) + 0, C1e ('4) ~ 0000

It) ~.-a-u e.& ~ 7c..U7 A =- (3 4' 2..) ~ -0.-u~( ~ ,( J~

o 0 2-~ct~~d<4.tk ~~ ~ ~!lC4L.J ~ ~rNd.Lr-cfl.J.J VJ

3o(rf !ter'2- -f 20(3 - 0 L~:> OCt ~(-Irrx2- - ~){=O~ T Fo(3 Z (0 ~;,-.Jc{3Z.0

oe o(?; ;;:. 0 c13 ~ 0

X ~7C-u ea.-.) d. OJ'G' n.L1Jul2hJ~ ~ A ;zl(f) Jc- /~.~, .;, ~d..,b.L7 t~illcu 0~~ld~ 4!.L''Vt.iJ~c X-e.t C-L ~ - v) ~------ J

~7~1 A ~ <.U..-a..t! ~ •

.2) -7;"<.- V l..u..J 7~ w U&u'a..R ~ ~ ~ ~ v-e CI+c../ ~ b.A..-

~ol.LJ~de.u..V. .Aa.. era.v ~ I ~ /;:) Co.J ~7 0(, ~ /34, ~ .. fA E' 1<: ~-7 ') tI - '/:::> .// > .A'~

"'1,?<.r i -~.7' ~/>(., '" 11~'Y-f .. ~ -+ ~'?(h

~CJ7 o(L 1 =- fL' UP t..' =:... I) YL

3) ke Vck[x] ~ ~j_.)?hEk[")(] ~oO-UJe ~

~~ d..L7~'1e. A-tQ~7 06. ~_. Ph ~ ~7Q..L

~~" £~ ~~"'?: /-cqCUr~ ?I,) [;e. cItJU.,-, "4. _. "l::v -E (j /du..u¢ J!.WJ7O-L LV ~ e.ud ~

do Ca.'-J ~ I/Lu ILl Q.I' cU:l <!..a~ ~ c.,' Lt..u ~ l.' L1.u ~ r o:z<

/dUJI-e, Co..- (() C-£) U-I'"f}.( h-a.ZUe, ~ 7Q..Lo V Q ~ eafr:/y ,.~ :::>

~ IJQ<..o'-' ~'= <y,. 'Y -f ~ -. + q". '~- -f o(~ . '«'1- c1 - + ,<-,?(.,-- 6_1 -/ C-rf/ / ~

~6° q-;.')(, + .. ~'f 0''t,-~+_~-I ~'~ = 0 1/ ~ 1aLo.If.

~K

6] iJ~~ X-=--{ r)(_() __ • -' ~} c. V e.lG(}eU8-u' ~~ !J..I~~4~ ~ !f.£: X

Cr- ) '?

lJec.I-rJ?.Ul d.£u Y t?ru-uJI -e.u..u1::vL. LU~ d~ 0#

~ NAfl ~Uov y ~ 0 Lu...u~e Q..L WL.Hu' ~~~ ) ,

~d~ "f !I s- X C V J ~6 7 X ~ 0 tv.u-e::-uU/~

o l..u..uet:.iJUJ '€. ~:>

~d....a u Q rJZiu.. <Lt 7;>

~d~-f .k - r~ 1/e~lcU2. 0 be.;~~-- ~ c l! 46-

rqJ~~ ~LUSJ.oOVJt?R!o ~ ~7 LV e c4 u-ec/-f)..U , C...c <'? a:J!..J 'otC7t c.

(81) ~ -e'vv'ev CJJ7-Gud~)

(132-) G,,-,-, e r<' 0. ..,6 y~ E' ve c~a.. Q V, '7 f>::, = l!

?r-"'/'- :fla. '-0v (j ~ LuJ nr ~ VP<JtffJa..R 'iN I) ~ 0

~0 7 (9...u1~ ue dn.. U-e (J "de ~ Gu' ~ ~ u...t0 d e...u..u' c c...a (0

~<HJ-0z:"r ~ -c><~<- 2) 0!..LLL/t.J~ (I'd' /2.),.

Ex ofU....u-~ Uh.~ ~ k a. k.U& nu..u l' ~ UJ-,t 'cie '-& Ga...J...t(C) <-U <J !,1) V =~ ) 3 z: !~:l:>kJ ~tJ-u. u- 7lt ~ rv; !'de- Qu.j (? LZ;--P C> -'/QY = :L.7. -f d r~~.k- a.u.

~ ) {/ -::::- /0('h Lx J.J

~ ~~ V'(! c.AJ..u' ~

~~v J::U l:iq~eL

/j 0 \..LL

3 ::::-{I J XJ)( ~ ~ - . J >< ~J

OJJd.lJ-ufQ~ rr~7 f~dlOLV~ .!

() 't5a ~ u ~ (}.<.J' Co..J. e. ~~ ~ 0. ~ ~

it'e dJ a.. Q C~.c.-,arh:t- 0 ~ LU -e..b... tIJ2 LU.. £ 1-0 ~ .'

@/h,. d..t '€. ~ I~ /-c...... e::t ~ Q ~ ~_____ J _

£.1> II kn~ u.u.. - ~ ve C.H~<./oJl. 4ZiLu e." ,

oJ c£a.6tJu \/i: {Oil? ~0' -e>o/~u 8 0 ~Q~~~..tLu-' V)

-Ii) ~ cetJ X. S (/ 4Q () WJJ et;7UJ e d..t lI'echru I ...w...J CVt w~_

~ "") ) a1Zu..t. <2.(7 X ~ /0 ~ '<*,u..udJ ..eo to '-4 Q.4ou ~ ~' [/

CJ , ~ c.<JV II:::, Y X ) h ~u 6' e..,.,i->Z<>" 13 c. X ~ QAa ••.• a..

....f.t..u V ( tXt'CL U-uJ ~t..U e dL cfeli. e.ro..liU 7r ;tJ /-ud.u ~ (;.j

~ 0 --(6Q~U )

A. C-aA.. dJ' £...La (J" QUA' ~ Q 4-U '

H e.- U L<...u k ~ ~o ~ '0 lie ~'a...I2. ~ CJ 7 ;-w 1\.v (9.U 'Q

~'-' ~~ 8,,? 32- all ~. (/) /8,1 z. /62/ '

IJ-.o. etaU I 731

I <. 00 ) ~ ~ e..cu C4Jt../ cLt Iu..L fU..J d-JJ IALta. ~ a...t.iu e..u'

(Iechu a..fl. V e.;r; clU.-u 1/ lJ = /!3{! I tJa. CDv 5, ~ 0

T\ bo COU

I..U-U eu 7L.U e.. ~..,P. u./ Iv;: ./ W €...<....u d t t J I V ~ OJ ,., r) kdJ'<..u. (J z 0

I<

Ex e..u.L~ A-:G. /U..U.J L.La..p ~ k 0 ~.-Q4£ ~ dJ..UJ eu .A.U ~

FtLu f.re c...eu..L d..J....u UkUJ 6k;aAL ~ r.J!~ 1 ve cHJ.-u'a..£t :

~ 2- 'if {(f, f ,0)) (2) 0, -t)!J s: 12::'

V,t - !(jl~&'3 / '>: - :J - ~ '" 0 !JII-QLa!';;.J CLr-u.J raU fI.-u.J r::u ~ () (/2- 1iN ~ -f- V2.- .

? ~ r - ~~ 1I:.u 'tC., ~ _' ~o2.,re.uJ ..~..J.jQJ ..-t.u~eud~

1J€~ 'lJ-, ~ (I, I,0),,;, 11-2- '" (2,0, -J eQJ..L d om.x.&1t<:fr ~:f -€- o() ~ -E 1/2. ~ o{r 11;, +t.1/2,. ~ to (-=-::>

01((,1)0) + r(2)o,-I)-(()JO,oj (-;:::-) fC>!+2.j3ZO ~> cYz.j?>=-rO.0( ~ 0

-f3~O

'11:t ~ 'lJ-2

(') €..t.J ~ re..ta <1-0<.Jr 1/( J /u ~

/31 z. {'))-1 ')'lr2

0 ~ dJ 'UJ Ii2 v" c 2.. .

11ufd ( eu'leu-u j-4 cZj~ d.od ~ t.uCU t.u..u~ veCfJ,Ju'

t?o.Lt d....o. c..aU Ii-(! ~l ca.u LU a...t I iU..LI eL. co ~ ()v eu.Z.J )-'

- t7>L<.J'e-u..., IX! c...I-Uzi.., 7 ~ U-Lu ~I..U ~ d..t d €.J..I-€ r<:i:Irn..L· ~

~ LU 0 ~ 1tAi.J..en.- Uu €..l' (...UQ iu u .

4 z (~ ; _~) ~

r ;erayu7~u..la ~'rL

(~~ -~):~

~Q -e' ~,~ / CU::Lu CI2LU LU tJJ.E./ ~ Q -ea....J;V7uJJ~~0 nQ..u ~.gSJ~u.:

=-> /~l -1(~ -2

O)~-I ~-2cr:2. /f

W! dr:ru.:.t I t..€.., I \.,U\e.. IAA. tA..u. 6.-' dJ...U Lu.a.L<...t ~ ~ ~t.tVu..J....ho v ~ tv ~ fro v

o --ga QU

8 =- [rv:, ') '11-2- - 2 t!A !J (' d./f- r/Id dJ '-€q "90 H:,f t.vJ J.ooJ

au.Li~j rIL !)~ Vl.f' c.: ~ ~A &'\. UJ...( e u..u..J Gt2 ~ ) cUJ a...t tAu- u..I.. <f t'LU.-R ve c.I-tn./4

~h- __E::> ~aJI<)"" '€ ~~ !?e.u r:c.., V2.- ~ "X ~ d - ~ z 0 (~ ~ ==(f -t.z: .

&Cl \ t/2 = ~ (J+~-yJ')i:) ~ 1K3 /:1-/2. E Ie.} -

~ {d (" , t, 0) -f ~ (I)0) ,,) !,1)~e Ii?;

~ SI {( I? -I, 0) J (t, 0') I)}4.u ~ !:~ V'@cNuJI (/) I} 0) ~ (~') 0) -I} Ca.-J Q...U er~7

~t:u (/2.- ~ u..e.-v'/J~ ~7~ t<J~eud~ Q~q,

y; -e- 0(, j3 e !R Cu ~- (I) I')0) +r (f) 0) I) =- (0) OJ 0) ;=->

r:"f :~ -) o(~j3~O/ <he./ $-t-r!(;,f,O)JI,O,f)!2 /3 ~ 0 ~ 0 ~q¥ rztv Vz.. ,?v ~Ae v2. --0

~tLu {J1+V2-:

~ -f- V2, ;:: ~t(V1 U V2..) - '1(f 81U S; 132) -= r (131 U 132-) .

A~'~ UJ'~ e r r:::;L7c ~ '" e.ub u..u:::u 1 kf1..l..U.l e "

1 1

2 0

11 -11 0

o-I

o 0 0 iN"" - t.I1

() - I 1 w;. - rv-"

it! -{ 0 flj-"

IZu'-z-Vf => 07 -1 1 ~-1lf

'1/2.. -2'Vf 0 -0 I ~ (12 '1/-2 - 21J1 - 2 ~ -11-;- )~ - 1./(

o 0 0 0J;, _ ru-"

~~~ Z z {(I,fJO)} (O?-IJI)J(OJO?-3)'!t

....fa~ 4J ~ ~ ~ + l/ r;r., dU..u ~ -r f/.z =- 3f 2- J If?- '

?~~ ~ () V2.-: '/;~ rv- E 1)1 () (/2- ' ~U7 /V-lE ~ =-'l l!JI ) ~ (2.) , V- -=- 0( ( ,I? t! J 0) --tr (2) 0) -I) ~ 11"' <2 (j2- =

~ 1.32) ~ e.t' rv- =- 7(1 J -1? 0) -+ J (1) 0) -I) ,

~~v CV(f) I) 0) + I (2) 0) -I) :;;:.0(1) 1) 0) + cf'(t!) 0) I) ==->

(J/ -f -t(> - c:- 0~0 0( z:. r( j;c( :::7.:z::-> th - - d -=->.r

-'7J':::.0 j- a =0

- p - 0- = 0 1-2 d-7- cf ::::0 ~= 0

;<.. w Uc,'-' tJ" () 1/2.- ,;;; i 0( (I? ,(J o)!c( E R!J == '1{(f, I, 0);

-I

o1

-1 -1 0

o -1 1() - 2.. -I

t) He X 0 ~ ~7<-u" ) r /,i2X ~ {i -'x - ~ti2 ~ ~"" dVcf '-'-'

r~-'~ .'(i +d ) (>cJ ~ I'(~)+ J (><-)

(0<I) (-.:)7 0( -I' (,><) (~ c( € R ) 1'\J E &!J .,.. EX~c 7 R X ~~ !i2 - ~~ l/ec.A9-u'a...fl .

.f<) 7;e ~= {(">();;')~)(2I/2?/2?(+3(J-26Z0} ~

V.;> = U", 'd' iJ;) ~ #2' / ;:'0< - J/; N = 0 :;, .,4M~7 c£ du.WI'

~1 ~ fi23, (1 ~e~.J lecU-le.t:v.7c ? /)rQ/v ou.e~Cff'2J

U, n U-t ?

1)~ 7~' t¥ c.AJ--U'~ ? ~/

v, ~ 1('"eLl). )~)EI2I ~f -1-_. -f ')(.q ~ 0 l'U.J< = f ( "41) ~ •. } ?4J) ~ fR. '1 I 'dt., + __ -f ~ Vi = I!J

U'6 = ~(~ ~- ")'X<.., ) E !J2?t / '"X-I( ') _. ) ?U.., E @., ~

F) ~ ~7 UJ ~ r U6 ~ ~ j-t b otvz.~t..o"" oe..U., ~ e-Z

n<.u ~~ -L R 2. C- ') !J-UIf IA..i <2 a.;--a-+'1A4 ~);

~ F't..v L<-U ~ ...rz .,,~,C) he. /2[><] ~~e lI'€~a...R a..Q ~'hOOUAJ~ ~

vCovu. c::OJJ ~ CA./L t.v &1[j; CVtt Cb ~ ~ ~ fAo 1

)a&.e 'f' cJ &L f-' luo...14 ' ~

~~~~'?

@VI ~ J 'PE IE!XJ / ?('x) ~ J>(~X) ?

U L "Z ~ ?E £r><,] I PiX} - _ ?(><) ~

U3 r- -{ f>{;' !J2fx] / 7>(0) ~ /j

Ut; ;:; !P£!Rt><] / p(o}:<" o?1) k~ X~ Y ~'€~0LUJ' -lv --:J~e urOtJucdi. (/~

~c.,1 :

J'X ~~y~)< - S;(xuJov?)1(~X)~7Y'l (V) '=- VS;f> (!0v ~) = 10 II ?

~j!ert'f e:f., ~~~d') lYe- v z: ~ 2- ~ ( ~ )d-) ~ If?'2 Uti ~ c..rV[ o.£.u 0 7

~ ~(~)::;)~ ~ ~ ~ ~CI ~ (r;r;:;) -; r ~;rtt.e..Do.CoV V ~ ,123 rr ()() Y:; i) ) (x I) '1');;;) d&.uo' ~cZ.

c(j~c.£. d-t'/er//e c::I..L r0) 0 J 0) ":; lA.Q cre1//v~ Cu (°1OJ 0) ,-

-A-tiiuc.> 7 ~(x':;J;i}.),rx"/J:t/Js ~ ~e c< T.;<J

ru:., (XJ):;)~)? ()<') j'}:t,!)) (o,o) 0) <>

~) :fte- \I z: /2Y) ~. '~r?J]Da::llt.U e U ~ I {'X..( - ~} c le"'/'2Y-I- -'"') /"

-f cx..v 0 ~ . ~ 0" Utu e:lfW €..a.. X=f (I) I) 0) - ) 0) ) (~ 1) -I) O. 0))

(oJ --) 0) I) --1')? J ruu~J ~ u) a.c&'c",v f'X =u."fJ) 7Ye V 7 ~ (It:.) , A--ci..u CJ 7 1/ <=" r X) I..uLde X-=

~[ (: ~)} (gt) (1°0° ), (g?)!; .II} f(e- V- fRrX]. ~CJ' V-= ~y) u.uctz 'J-1K'n/~E~j

"% ~7tALl.t::>....J....q) V'<oCU ~cra. Cu ~ "Wu..le.re-~ ft.e..~ k = 172.

Ar I.A..L' /-.; e< 2

'k e.- V u..u S 1/, .Ie- &J-.) U-t ~)f; ~~ ('()~ r- v 0 f u.u ~7 e

<. ) :> " v x V ;;> Ii2 6..l ~r'eJ.47-e, .-

(?s I) <: ~):;> ~ <:; ) '><-> ) (ft, "'d E v( 'PS 2-) ~ 'X..( -f )(2. ) d > "2 .('>4)d '> + <'")(2)d '» (~ >'Cf .:>(:? )d ( v(PS~) «O<"-'d> =. 0«'><1:;'> ,,(If,o<'EcIR,?(Jd*=V

(?Sft) !('?(,)?L) ~ 0 ) lb) x. Vc:( 'd.:) X> -= 0 .:::.=.> 'Z- =" Q

do eoU <: l':i') d' > -z 0 r- "tJJ 6J..U~ -r -::/J (~? J..,) v d..oCo'-.;

<,e.,')~t'> : I 0) ~'4(/ )1J --l- 4::d

e", ~ . "f:, 1/ = ()2 ~ e..u 10 d..u ~ 0co..R..o...c c&.. e.,., ~I'"Yt

~e CLd~ ((')(, _. Xu)? (:I (_.~),> ~.=r%")l') --.g a.:J6O ~OUJ'GoV

1(1?- _) 0) (0:> I ...._. 0) ( 0 J 0 _ _ -I) l ~ 6-tIe h<fl GV a..I-av.) ,/).) ~ - . ;> ) '} •

O£~le f} he- (0:;> <') » --uJJ 7~ ~ ~'ch'Qu ~

X :: ~?( ( ? ) ~ ~ c lJ. /) 0.. CQ'- V E: ~) ?<., ') _. ) ~ ~

t:J-th? ~ o...fb' oI..IJ...,' ~ ol.di) ~ 0' (~ ..eu. ~ ~~d~).,......

~} 0-u Ir __UJJ ~n!,DI ~ c...G'rcLt·~ "Yo irilou cd2. ~ 0 ~ a..gQ~

tJ-LIo vtU1 U-t a.JfaU, ~ {)lJ .h.u...u e d.t 1>-01-0cf.cJ.-U. o...!J' 3-a re G'~ tv -

S~'df .

X- "2- (J():;>,Acu ~~') rL "<'de II 4o~} kOAs:UJ t) <:1>:;>:;'

C f't?( ck LA.uUJe~~ f~ ~74- ~' ~ r ;;)II'e ~ ~~h U/?UJa~

2t1.AL ), he Geu LU ;:<) ~ {-e.,) .. , ""'; 0 .gOL:l'Q.u ~ II, UO<L<.

v~ kt::i..u 1 0 --(5Q'l5 0"" h.-~(9....tL~ 3 /:::.f '-<"';1') •. :;> .h h ~ :> ~' 0- ..gq 80.

r:n..Jo ~ (flW o.QoV 3 II ~ {'l':(? _. > 'V n ~ r" VI ~r u.u..J6.h- :

:=:- e2... - « e 2.) Lt I). A..J.--- - .,</..(,,)L(,,>

3::: ~~f ') ~ - ) ~ ~

~E:Va..v€.U.L

-ft-/}< I "','...re.- -t1~ 4ehv,{/R.)

4 ~ w~ .fa..1o~U

c1J w a::Lu l:e A k £,u..uU ~ ~~ o.eoV d,Q caU

(N A-I=:-A-t..,?r'i~~e_ ~ !..UQ/N''cJ. A ~ ~~cU,av~;?

Lv- a. to)c.i.J1 fn- UJ U) ~ U tJ 'iQ i OV tn. 10 l-I d1 w o.Zov ~

A- =( ~-t-( ~f

~ J'urr.J2 !)JJ~~»

~~~

(w~~ lLUf!J' tc()J~7 dJ; ~Cvr -t

~) A 2 (~ 7~) ~1 0 D

( Lu-a.::t:v la-a ~ ~ l.-U.JJ. Ir::t a. k e..& d..L e.IH57-d.uvL o.::r& Ox') 0d) 0-.0 ;:

(ji ) rO:J ) Ox - eHWf?-07ez {~U c4 &e~ x =- ~)d =-0 )

O~~vo::L7e?

-Y\

~ Lu..JJ ~ lI'e Ur>-u' ~ ~ ;123CLI <0 ULQ~ ct CfL 7/~ u

~~-Q~ cfJ7.ffau~e< ~ UJJcf~r/&z .

~!: ~ ( d...t' 21 b-U- a..fh. .; a..<. e..«. u..u ~ o...t 0-t 70 ' JJ e..u. e. izt )~

-flL A ~ --U", (tR) 1)..1 <-U<e.. -tv 7eou ) A -: A -to A-Iu..u Gl I !

a) +a~ cr~ I (~W) L:U.t. -Lu..t' A- hud ~ -I'

--to) A- Ie. d.t'~~ldLcL~ ~ 4)~V 0 --eCl.~4v O1~VL~/z..U--(a..iav rc..u.a..Iav

~ if.e ~. ~ ;-W..., ,) d..e CJ' A ~ 7, D· 7 -t U..t•.u:::f..l. 7 ~ I..t.L.4tu 7~

~ VVLa..la"V ~ e.£/1.Lt' ~ CU--(e ~ l!'e ~..., ;--or} CD...t.Q fn e..u eq f1('-'

~4. t,a. ~frL Lu0...1 aVr

~~ ~~ ct,ret~~

I/, ~ ~7 d../cf-..reu{t7 ~ ell en 01./ 1A...U e I[~cU!.U1'6 dJ ~ ~ ,/Q /1 ~) 7 e.t~Ja.fb... M <J..U ~ e...c.. -..<..v /J..L 0 c£,eo~ l-U aX, U/o;(;~

a. cRJ'~1e4 rate ~ '/J~ca:, LfAW?) du·u.u~ ~au e~u.ue;

o e(VJ.~e dJ'te~JaJbu dJ ndJ'lA..Ue I ~:

(64)1) F( -t) 0<- ) ,,)j = 0/ -

CA..-u d..L F ~ 0 Iuu clfJe. c'&-<_u.:i/l-1.U OV ) L~ 0(:.. =- ~ I i.) ~

~ <:...u.uF;) ~ ~ ~ Cu- va.u~~ -t:..

JQ u:;V ~ (Ef)I) f-U kuJ- ~'e.uo- -x-I

GQ fu.,u~7e..-

~ t- of: ~) rl '''VI..-

(ED 2.-) x.1:: ttt:) ~ )

MJ-t dJ :f -'/)c ,R2-_-~ IK %[/ 0 yUJJ. ~e ~YU.Lo'-JreilJ c:: eeu~J'" dJ/fe~a.k~ ~~~~ (ElJ2) d [;',pULa Yf01~~,

() ~)e ea- ~~' clt~~ (l D7-) ~ 0 yuuq.tJe--::<:. _' I c.. fi2. ~ 112. ~ -w c.; t :

,

(1:) -x (-f)) E-.D) (16 -eEL

~ I (-t) :: :; (-I:-~~ (1:))) (-!h t-E iE)(~~ .~ ~Wo..f" dJye~a.h ~N.f!.uJ'k ~ ;I?t~CQv

",) ~ ~ ~ cu../ -I: e.& c..1r'-c V!.,...U1 0..::#" ~ 4-- ([) N ~,~ <...J R...:J tJ-/' ~ C>

--4tH1,/?1q.J d!.t ~~~u L r<N 0 ~ d-t ~~~ E(+)L/ ,)

JJ£)nJ; ~ ~le . ~:rnUJ. ~7 4' ("(.l~()tf .> l-f-U1ut1J1oJ.eCL--cT-· - V r-l~L I &..tt1.e.u.1:U 0..u' ~ e-I-rl 'c f/CU.J Q 8 Q ~

~ 't ~ ~' ~e.o.. ('<'eu'4lQ. chr",-,~--- !-<b.h1 u)

IL~1(f:) -I 1<. II-t) z £16).

~ ~ d.<M:;, ~c, ~ ~ 'j"""'" en.

f ~' it}~ ~ft:)~ Ii) = - d-

v<.<..ua0 ?t: ({) e.£~) Vo~"" ~ ~o/e r:£ kJ.)rlJ-! t:-) ~ f1H H 4 a ) vl:uL d IC.t(P ~ ~ ~loac... ~~J vn a..R.Ao,u.

E)(~ c:::6 ~i-&-&-QJe- (:( e W~7-en..- d..t~~~ ~

'-fJ) €. eu o:R...t7e ~ CQ.I e 'f u.u ~7a tcrC-U.LI K> Cu_nr/" x. It) Z I <::-- 'I (1:: ~ J :.c: ru.u ~ ->. ~ c:l.uJ'va./-o- It.

~ ..w~/LQ/u. ~'''''ck>u" ><-It) --I:/(b)~r~·'2~WJ~ +0~ 0 ~ ,?k~v /4.;t c.. 0 ~ ~ aJ'flLhAJU/v(C: :<.fto))

.v4eua. ~ u e...eu~ 7e. r e ~ w 0 ~ a w.J. fTL r Cfl,J.e ch cbu.a..u..u,~

a /D~~7e.n... dJ'I/'U.fe~ ~eit7) uuclJ /) ~~ )laiC ~

Iu~.t"()d..ut...Lf'e, (/0 c.LI d.L.L At-uJ' U.Q. ~a.. q ~) 'l? eu ~ 7 .

Pt2.Jl ~~,) £UJ..V~ ra...LU ~/L' UUulrg b' Cu e -At-:

Ix.. :. /) . x.

?LI . e-) r-f ~c.. (e - A t) I == 0.J

(z. e-A-t) I ~ 0)

';)<..,e-At- ::= ~ {} ~

~ W- .t!2av eou ~ e (!.u ~)e., \ 1~ I=- ~ :;r) ~ <:h r <.LL<L

f~ (of ) ~ ee/\ :1) ~ ~ e- R. ( cfL tuLfl~!)4vUJ..! 1~ = ~(o)1 ~ ~A.L~lou /7~..re.a:~:iJ6( ~ e.uoe..u~

-1::::0

--3-~} 0 ~e ~eu-f!a..L4:2u Q eeu~'( E!JY 4e ~J.yN ~

~ d~et~V r'cu' 10:A..:tr7Ct1rLa.v'<kufu;L ~~

J) 0 ~7~ rkU~~"'" fZ£; 0 ~ Q ehJ¥Je,'(EtJ2)~ Itlu <Fe- /"0.:£ ~f'~ d..U.; ~7eL ?tU.lera.LarLU

~euec..u'~ ~~J~

X' ~1a 'U:,u~en ~~~ frO&! ~hSe..u· JItY~e

tutet!u'~ ~ : /

'eb/er/eL'fa ~ ...u..t.u'~~ ~7~

")

__ ~~'~ ~7~.

-- ~It..U-IJ'LLQ A..~ AJ.~. _.." ';v) _ 1/_ '-,~ ~~ Cu. Q..u.uUJ-joH!- ~'~7.) dJ ~~.)

(9 Cl.$.u~ .;..,e. -.iuJ7k a..&.~ ,.., .:> •

j ~I .= fit:) ':ILJ'::t:.-(~o}=Zo

Te..I-cLu.tO- (<:& "k/~ ~ <.uu'cNoX ~ ~"" rt0 ~Q •.J]"'>-He. if -'2) c. Ill- -.:'!R. 0 'IUJJ q,dfl- ~f,...;u.uaUF tzu ~

U ~/;:lQU IC)..J ~ f!.B.<.rQ1A..u-CV. A-Gu c-(" J.R..u. 1;U ~ 'Ct... (co ~:f0)E /)9~? f ..-J~a- ~ ~ (~ / =- fl-t.) ':t: ) a..Le ~ e u...u...c:ea.~ Ql cb'ud:

?c: 1-1:0) =- ~ 0 • vw.JJCO •

~.;tX .<w kk..l/~ ~€I s Ii? '?' 0'1u..u c{i 'e dPn/ va./I>I'4° ""- ~I ---'>-ea.:<re.e ...0ed.t '"'-(-to ) =. ~" ?:; ?d"'):=l'(t ,'x.JO) (-If> .f:: E- I ..

(FtS'r-a ~~ .Q~u>.J?e)!Je- '? uJ'!: e 0 e-e.u ~ d./~cdav 4?LuJ-r:u. OU dU (Y)dJltuJ e 'I

% 0<-/ =- 111:')0<. -f 8ft) , u.udJ 1\7 fuJ.J ~~ ~","",eu - r 0 e..uO ~eLLO ~ ~

J)ac.a (j it)z 0 ) e eu~7Q... k ~UJ -.;rv -(7--'

C!.o.u~) r et:Ll.- e..,Y u.u ~'l. 'lIG fl<Douu:;j=""' ..

I2t ~ e.-~ t::LlU7t?n rdJ~re..uLJQ/l, ~'UJ'QJ e.I _- -) ------

-1-ePQ

U M6rieM.J~ co""' d..a0af!.; ~ I(h d(2 .4uu.:J- .J~~ a..0 'etPH.nff.Je.,'(EtJ 3)" ~ .:. -~ :J

Q..IiUU:j7 ~ ~-f2(,,\ ~ O('~I ~ ~7 ('fb 0(E-f2 ~to'--'...., " ~ ") J )

tu..u ~7 LU e..a ~ Lv, ~ -L,.., <..u e..o ~u ~ ~ a...t..iu II'euv-u I~ •

') ? lV' / :>

A(/~

~! - ¥f-f)·?C '= "> 2/ = e.t!(&)?C,. T I )

1-1:~/(6) -t:'to "'(7,) 4{; '".[ /("6)dr;)

~ l>«~/jT; z j -t:-Y('6)dr,-Cu -to

t~ I"" (-t) / - 4 I~)I = -£ {(?;}<:/'b

'1-to ~ c...

7:-> ..1u jr." (r)I <= '-tu lei + .{ ~/(1 )<1'0

~ -t: ~ / -- J/lt!tt-?C-/-1) '" e _e 'to /(b}d~ .c£...'va &uP) rk<» Jw'e l)dtJ~ Ce J

Rt~u U;V ~7~ ~eua{t7e.t 1"":(.1;;:;flr}- ~,-{ ~ d.t ~LU~

l-~-/-t)~ c...-e-_ ito !('b}dbJJ

w. e.. E If( c:Lo7A ~ (Co =' -,::lio)) -

i!...:;~ !i E ~)e "-' e.o u.J';J~: ",-''"t(iJ ~ of () (l) (ED '1) )

u.u rd..t d({) -1 0, _ ~ t:jfoJd '"G

7£./::;. 'lIt) '=t. +d I-t) I e

of ~ (t tI - J-to f{"{,)d _ J-to 1('0 )db -1r('b}db

x /0 e ~ z 'I (t) "dO e -/; -f (J (-l)e. 'to

If J - to !('6}dZ (I) -ftoN'b)d'b -J/,I-fbJdb'X .( e + ::((-,-).-!(t:)j e =:/t)e

, ---.l-----d.Rkt' ~ fULl c.ftJ(..('

t - it-t 'f("6Jd0

(_ fto~(b)d6) I e 0 -1tt/6)d"b

?( 1-1.) , ~ := d ft). e to

~ d...a UJV ~ I ) de 2- a(~.e~Jfija..e, e eA.J ~ 7€J ,( E by) ) ~ CI '

z; ,- ';(2- ~}e Q <£ I2u ~J0' (~!)3)ta ou e:&.u --0 ~'h.u Q ffl ~Q (ElJft) ~ ~ c.ku..f/

/hf e<ut({)~ '" -;}Julur& cf~)"~'" c()y))

~ Gt uP e-t.I e-r~ ~ ~ ft l1-Qu d...u:-k r a..dLt.u fLc.Q ~ ~

~ ~o~ '7 CL ~e/ d"-U~ a &J.l<:>:pv

t! C1.J (!'~ "'- Q/;() C/'a..ff:, ) Qc£, 'C&v S'n- ~ So + lz:x;p J ..•,i ~ I'f{)-">:7 Jl1() /- e. -J~!t:)clj

,/. e - J!(-t}¢T _J-/!t-}eU -f/loeU~ t(i:),x-· e -fJ(t)~e

I; - Jflt)d..I- f/-') I'} -J/f-l)<U _f(t-t)O&

~ f)e - jlT: ~rx. L ,e ::::::J1I:}e

'"XI(~} - JlffJotf /-JlltJeU)/ _f.(ftJdJIe -I- ?L(-tJ~ce / ; rJl-t:)e

(/ I) - Jf{f) d:J- ) I - j -P(f:-Jo&-

Z-(t . e / ~(j(-t-Je T'

- J.g(i::) c# r -J/fl;JcU_ Z(-fJre T' _ .=JJ(~),e eY +~/

",-U) = e f11-t-)eU(e..-f!Jf!:-Je-J1ft:)#) ;:~:--_------------~---L q ~~a.Z~'

)

I ""/=ftt:} ">1'JlU) I

~/f~ fZ

/

7 /Ii I: /-=-

y 'X/ -r z ~ -I:- '" 4uJi. ~t: ) tE{-{)f)

~I 00 ~ fJ tf 'Z -f 4W t .e.r., -t------v-- '--------y--

ftt) d (i)

e. JfUJdJ _ j- Ij I' elf l/Lle..oi:j-e -=e =/fLotl=~T

hftJe -JI(~dr ~J~{.yi. e/-t oY 0= - &;1:

/!.hJu ~ u "<. (-Ie ) -=- I!.-;-t (e - e.,-t) ) C'- e ;,:e .

:f, ~Jkt.u~ ~ e.~~r:£,l!~ o...R.t.

4 J.I (. Iet.u <:£R eeu a'fU 7 ~'1u'~7a.k ~ nd./ lA.U e 'j a;Gc- . --( )c: ~ 1~(-t~~I J ~ ) ~)

~ (r:!J r)(~~: 'f.,,~-l)><I'_'~)

~d.i. 1"" _~ , D c 112)( Ie ~--,p 112 ~~ ju-uCf-U7 ~J.lLu/~

Ll'~ ~ z ?t.t It)) ~ ) ~ <;:- 'Xu (-t) Av-u-t- 1Afl ~ c/.:)~ €, ~ ~

€.u t/Q...u, a..IJ, ~ t.o ~-e Q /..i~~. ~ 0 'ftV-u-l'€!./e dJ ru»i-U~cR.!N'~t,;.;G.

:t.. ,- /) _~!) Ifl 04 -/J> I ...w W ~ ~ d-U' Gi -t e I ;>" ') . ~' ) ~ -' .L C I'/'< 'e:::. ~~ I

(-t, ?l,to, _ ) "'-'-'(tyeJJ "::! ></ (l) 0 :/,,(t) ",,(t), _-> x.~ (i))) -- -'

~ ( -L J-=- /n (-Ie ) "4 ( f:) J __ ) 9<JJ (-t)) -

Sv{;,Ieu..t e ~ eJu..I a.:.u7 d.tfe r~"b1L ~1a:.t e <!.U ~ I!u'~f~~)

..A...u..I. ~ Q1/ J ) Q l? Vi E IK..... ~ -e I ) ~

i u..u. c{U 1 ~ t.::Ct 7kJJ (! ,

(

~/ (i)

A •. (a.:j)<,j = '-;-h 13 it) "'.. X 0'

) tn/~)) ~'"

~ ~ ., {E D6) M UJ Of.•/ I":l CA../' e. .tu. o..tv 1Ct' a...R ~ ,

X I :::.A .X-f 8 It )'61-t) ~ 0

5({) 7- 0

-::(1I

~/a...t oUJVeu

-euu7Q...(. lAP 0 UJ d e.u ,

·~-<.U~V~ ICU::tu..u 'k ~ fI-e U-U.../' ecr- r ~

( 7'eFtuaV d.Q. LU <!U.L~o.:R.i7e )

~ ~ fJ-U' 4u rd-t ~ ~u..t.iu a..u CL ~ ~eJ '/: ~ €J' @-au ~

( dsQL ~~ wa-tu.'0' A d..,'dt9-Ua-e;~~1'6 ~ I,i2 ~~

~Zt rC ) .ea ~ / D.f. ku..J t:h e eu ~.., ~~ /"(..A..;!£~ ...fu.u0..., e 0 UJd e.u e.. ..'

3(i-}~o ~ ~ X/~ A ,X. (Af

0

1. LJ Q C;; e.u. Q -6u 7aa ~ t;;/jcrBV o.f!..a:U') A=-;~ U-eu-u...t e ~ r.)Cu· e.

~/:= .-:1f:>c( ) -=t..f(~'O)::=..::t1

) ~'? (-lu) c ';t: ~

~rk.u..t t<q #&a 'P- ~ '€ eu. ~7'E'

~l~ ,I

;> -1. r7 ( (-I:) -=- C1 e ~

?L/~ 1'Zr -f!P~z.- '<:X3:,-1

I~ ;;:< Z; -f 7~:<- ~3

I';;{3 =: - O<'>y - ~ 2 .f 0/ ~3

- .,6, \

z {£-k)(1~X) ~ 1-; + f - f (f~~)- it ( It ---X) - ( I- - X ) =-

~(j- - X) ( /6 --Rx -f K / -I J? - 3:2 -f RX- f--f)( =-

= I I~ - 16 X - J6)( + <f X ~ ;t X 2-_ X 3-f J'~ 3 2 -f J> x - t- -f 'j. =-

~ - X3 -f IJ~X2- -b''bX + J>I

he,' ,11 = 3 ')"'If '7- .z, ~ ,,-\-< - 9">~2::- I

~ Q CA.V-U r-e~7 r/~ -,..~f 2 {(~}~r,e~/4(~~J~~{~)}

=--? ':f 'X.t -f ~ ?( 2 - ~ ~ 3 -= 2> Xf :2.->

o(l'Xj -f 't?t 2 - ?~ ::z 3'::\' L

-2.'"X.f - ':r 2. -f It?:}) - ~~~

:;;;;?-) ~'X.t 1- '"{~ - ?!:- 3 Q <O? t;;t? = ':<0<.; rf ~-0

V?,,=- J(~ J 1~)~~eff<J =-Sf!(f)J(JJ 1; ~\~'I:;-f?(l- - 'if:

'1.1'-1 z...

3 -I ,f~

3 -I :JJ -1 0

:;14 +t(?(z - ,2';(3 ~ fj~

:{ 'Xi T 't?(", ~ ~ ~ :;:? g~ 1-

-2.'X.t -?(1. -J O/?(3 ~ 9'X3>

~)Q rleJJ~v v'C< j:;

z r!.t e Af ~ V- -L /) e A, t: n /\ l.. t1-' ".< ' 1r2.- -+ '- 6 e . 1/""3 -

v

IJu:., ~ch'9' ee ?<t (oj z- _ / ~ ><~r oj z 0, ""3(O) ~ 4- /lU-U €!a

0; - ~C2 =- I

Q~ - C 3> z 0

:<Q -lei- -I c3z it?(/ (.f J e 3f-- ~

?(2 (-I:.) 'e ~f- _ e fj r-'X? {-l} 3e '3 t- -I e ~ t-

tt .9ku., e tS:I!.t €.- eu aL) r;;L'..c? re.u.Ll~-------) --~- ., ~Q...cq C4 ~0'~) ~f/o...u..L.7

f'X/ ~ c?'1/ ~ ""I - -f a:..;"'t.. ~>'! -f '"'-tIt) ----::>-

?(fn ~ q I? I ~ -I _ . -r a.I/J '" ?C?1... + ~'" It)aLj' E- R Yfl/ ~ / L ~1!21/ }, ~} 17 ~ /,

~ 40hJ A = (~/)" _ "';/ 1.:J=1/"z

4e /dCu'L :

I)( = A-,)( of 13ft:)

-l<u<R.t X -=~:I~ wcH1.u.R e,w,-<Ulo ~ a.P r qu e.., "'" C<.<.<.uo euX

..4a..t.u.W 4-t w. 6tJ.-"') ~ C rJ; U..( -'-<..U GQ4-u e 4 u..Ln tv 70. d.,'~6UJ O-h' cj ~H!.o CJ

~ 3ffJ =- 0 (/')J~ o~0c! ~ ), HU-J. ~ OJ/7:) ~ ~n.Iu..R rCtc:l~

~7q rf<tlU er~. a 1!.J.J>ku..t.u~' ~ etJ£~Q ..[V ~ ./1Ja:z

f/~ ~r1 aflt tu~~' A Ju.u..jf ~ ,

h~ (Uu a &leu ui' A- QAJl ~ V'~. rr7 co~)o e, Cu <-u...

tY-rU. CL /.I'a.h) ~ ~t € €..J(; d cLli u:u Qut:(I 0-&' J--I 0 <-t...uJ ~' CQ...(..QC'.ku i't..Je-

fA- (X) ~ f< [)< ] ) Iu ~v CQ'--' eta C<l~ ~ ~ t7( -t ~ 00 ~ O--VL

r1':/e Q ~7Oj7 A eu. tJ-rd.,'k.u e ch U-UJ €:c,u~ 'c'f.o...x; Gq } ~ 6.'

~ X- ~ e>( - L,? I/'Q j!; ua...UJQ.J.Q;-va ~ I e Gu a ~ V1~ ~

W.u ~ '0' 1-c<Z, JJOJ' GLu.-t~ ~ CJIfn.LiJtr1 ~~ ct-04-u'

0.v' ~ ~ ~.~~") N~ r;u' ~U-V~hru'~'.

~ ) cU.e-~ ~ dq~V ?J-e- V c CENt.. ~Ct7 A '?J-'=-~ 1r ~~) )

A 11-' ~ A- 'l/'-' :::'- )., U- .

&~ -r;:'4 = (-32 -l) E h.< CIR.-/ ~C<' ~(x) -

/- 2 -3 X - 3 / = X ~ It X -f It -;-:J :::: X ~ ~)( f 13 eu ~ ci:.uJ1€z

-2->( )

/)1 = - 2 + 3,') t'h.,:- I) /G = - ..< - '3L' ) .::1-2 -: -I, ~/'l.u..u' Vt~

t¥u-~ /-'~r' :

';/'1· = -~2 ('?(- ~ 2.-t:

q6?~)~ ,,) ?e.uCLu /) -=- 0(7 y? E Cl) CI;.u.t.t~ tUUCf7Q ~u.ye&1oQU

icx'+'1It e oif (e.,Jt-TC'~/'-t-), JAW d'o"iV""'" ) ~H~

(,/o(-/LI'J"V I '=' (eo<I ~{/-I <,&0</ .rurt/ =

OCt- 0( t- . ) .,. c::ij-, L~ 0( e ~ t -I e (- ~ .hU /b -t. -f L , 0( e. Aut or -f

+ eoif, f~rr) ~

~ 'e. 0& Cr.>t f' ( 0( -fLr) -f / eo«/.M l' f (0(-/ c;r) =

fK -/0) e '€r + 'f) -t( .--/i) I ".{t

~ ~ C<f ~ 7;j.., ~' <:..t. ,.\ C cr.) <:::Lv e..J.-A..J (e -~ e •

~ 7;e A = 0( '"f ~ tJ f/a.Lo Q...L€.. r;-u' e Q U-lO tv7cij A-QJ r>'-'2C 4 A-uJ ve~ ~ ~~';;:i;;L ~) r;t.W) ;}r

A--~ ..HJ ' 1u...u. elf' ~ ~;\'- ~ (-e- ?i -C, '1r ) )y==?, t-u (e ), ~ 1J-) ~~ C-

~~e OUJve.u ~/?ArXrX~ - a dZ.u.xrf'/l ) eu U-l '1GUJ ~c:L (ve cA9-u'cU2..Cl u ) ~u.y~ JoQv

2..= eA t-,'Ir ?a1:t'rfc<c. 2.' = 1" A t~1/- = ~;I~Ar =: A z: ,)/u?;-<.t-0-qv (Ii-i.'Y)1 =- A-(X-tt'Y) X~L'Y I-=: A-X'iL'A;

) ~

4~tJ..U '!-v.L ~ c:t..i:kA:LuJu OJ e 0 d~~, cJ e.u e ra..f2.t. a I.tpKULIJ 6.-U '

(9UlO/'eu Xl=- AX' (~ CQ~ 4 COJe... A (U~ ~ 1/a.f4fu·/~~'

4) UJ..;~k>e -<) __~I;i; dJ'~~~lko~u~ ([.,1

,{ ~ (n::J.t>-U'f!o rr' A,. ;) VI f e.£k () ~Q~av r~ frCOJe-

P-u-4,~?~ j!-' or ~")..)~'vt (e.u ~ cA!A vcq»Q Cor oto Co'-.J

/) ~ X ~rf ~'r;u.j,j j'(;pa-L) ~CJJ c<.)0 ¥c/~40 ~ tU-<.u' ~ d<J"'-<. ue eJ.-rLUl r;0-'" r ~/\> au l-'~~ -1

N~o(!/a~d jUJ 7'd~);'(, ?e..v r:u '/H ocv e A E Ii2 va-en c>--u rr 'e ~ V-e ~ C(f)JJ ~-~./ t

CUJ feu, O?- ) J' Qt'~ ~ 4- J!.-J l !eJ-U.u e.u' e r1~ / J) ,~ (/'

?e..u G r co..te ~ E:cL /12 C<..L % ~> 0 ~ 1J--e ~") ~tl/))

~ ~I t ~ leu 'C/f... ) /dCJ../et...u.. ~ ~a. ~ ~ }:(j' !<rL(e ~C/1J-'

~ 'k (eM/I)). I

~ ~~, ~t~ W~eude.e"k J'r.u'~

j!t~? 4e ~~~ ~ ~c..hJu' ~a...uoCX(?h __/

X1't(-t}.:3 ~7a- J&Je..r~u Q J.J~~e..v' ~

J It / c::- C I X I I I::) -t __ . -t ~ l ~(-t).

c~~, I) / x; z - ~I'" "''"

~z = - ~ - ';;(?-.

A- =( - 1 1) =;7 fA (X) ~ / - (- x " !::o I--f 2)( -f I..,. 1 =:: X ~ 2x of 2.- I -I - I - 1-)(

=:> ~ 1 = - (T l...') 0-z., -::. I) j1 2. -:a.. - I - L'} "l7 z. = I

~, = {(:;je tL'-j A-(::/- A,(::) y{- 'X.( -I ?( 2.. :::- ( - f -f L! 'XI

-xt -?f'L 2.- {-I-I-L)?(L

Vill - 1( ~~) / '4 ~ tL} ~ l'{IJ)} = > ~ Lz ~ Y_4J 3

X '2. = <':?<"'1

I"X./ z:. ?<.; - ')( 2. - ?( ~

I?C2

= '?4 -t ?( 2..

?(~' = ??4 + ?C. 3

4 :;::'~;f -I -I) -='-> f:.t(X)=:-/I-X-I -I 1::0-

1 1 0 1 t1-)( 0

3 0 f / 3 0 I-X

~({-Xf -f 3(I-X) -f (I-x) JI-X)f(j_,x/-t It) ) '-u ~w""""e-.

?tt :: ~(?( 2.-

3?(; Z :(L l?( J ,

~Lt/A1l.u...(-,r:y/f:)

?(2. /t)

?(3{f)

~~ _1/ (~IA.liQ...(J2 ~.: - ) () ~~ CU/l JuJ2 1< e &d e.uJ ~ .r fleLue dt e euapclt 'Ie r~ ~ ~ tU e D UI- ~ tUJ e Xl=- A-X' + 13 (-f ) /"

~~ v I~€..UJ c.a Qu..t k.t ttJ.€vcd' ~ ~k U-u.Je 0 u..I~ e<..L ~ oo'a.:f X =A,K

1: ~ ~lefilAJJ'l/LoSf (J- --&q~av...[U 7~ e d"~)~ ~({~- )~(-I:)

f1aZu'Qa. /VI it:) j X, 1-0/ ¥'dt) I-_ / )(.,It)) 1!e Uu U1 ~ Ut QAi'c2\.. e.uUJ x/ff) ==- -4 -Xt/t} {fbc'= (J17) /'U<J.ueLo

V

';:/ LLU. d.a...uJ e.L L W 1.aV' dt ~ (,1'7 IL) / 'A- 11.'I-t . M ~ '1 f+) tL,.Ci WII'fA .lC(W~/ __ --------?- l~ =. I) / .J u!>-t .::..

?~Nlk {XI-I:} ~ !1Ii:I C- 1- I1H}j/1ftF 131-t)e&l.yc, ~'CL

J €L..(erakU Q .In k...u.u fu,' ••.e<J<ll ~ Ie:: 11-)\ i- 8(f) ( WJd.L ,(! ~~:j '; w ~ ra.Q.a Of' ~ ~ €V ea.u d A.U te,t /a.P.o ;j!te =nL.

~eu1: )

~&.u~7e ~v ~~v,aU-l l.UaJ' J;U~, e.av 11!i:JjMli)-t./34-)d!fI

e..;;c; 0 ~~ Q .f.iS ~'0.-u' rwl 0 UJ d e.u X' =- A.x -18ft) :

( M (i JfM ({ if 13HI d7 ) /=- lit!)1/"1 It /"/3 H) <:U -I:!!!!!!!!/eN)A. t1!-t) .In-

=' 4 (M/-OJ ~(-lcJ 7, N-l)cY)-r !3f-t). n'11.e- a w LU XII} tJ r?~7e- f)Q.J e c.a .re ct u.& /!eu..-u..J C..t...4l- bt e-a u..L(/ e..u ,

AGue- XH) - /'11-0} /1It) ~ 13/1) d:r IfW'/-IC4w

~

- 0~

( x - f1 (-I:)Jf1(t) ~fj If) #) ,=- A X f Y;~(4/1/-l If 1i)~/OH-I-

--(prO) =- A· (x _ !'1(-O!l1fti!f3/-IJd:I ) ) d.~ ...,z, 0 ~'e

a. /-J J /-eu w 6.u' <J-<-Lt.;;!' e..u. ovyo e..iaSl _ ~ ••..•• --<» a Ct4:f "-Q 3 11<.uL&~ J~

~)& :/>VJ.d dt. rWQ (2, X, (-t)-I-. -f c., J(({)::: 11('J.~~')f<p w -&au )(( -f) - M ( Ifii-O -:r ~ (0 eU ~ /"J (tJ ft;}. ~ ) t?O..J....L J

C""-ed./va..J~ ~.r; 1 '-) l.f-f) = I1ff} ,~ -f 11 (+}) 11ft 1131tJdF,

f?x ~/~ 1)!'<I; % 'If" ""2 " ~ e.-ot: . ~) 'l3It)~/ ~""",-t )')(2 =-? ~ - )( 2. - 5"k-<.u -t l- 0".{<JJ t-

4 =-( 4 1) ~7 ~(X)~II- X 1 !-=:. X?.-I-?J '"Z-X~y -=-->3 - I 3 - (~X

..11

:::.(.) h1

~ I') /12. ;;.-2, 1'7'2.=-1.

~, = i(::)4 A r::} % ;,/::) ;

!"-I-f?(2. = h-l ~> ~ = 'Y2~' ~, z ~(;)/"'UJ2!r=~!~J}3 'X( -?( z- ""- ~?( z- -v-"

t z {r::j ~III A (::) = /J2(~JJJ ?4 +?(-z. z- - .<.~1 3'>4 - ?('2.. -z. - .< ~ 'L

I1I·t:}~ 131-1:) z-( - 1t AU.<:r -:y ~ -&- \

1l: c-,.:u- -.z+,0,.!if)

jl1(tP. Bit) e& = (~-}) @vo.:y - !-te71)~.2./ J~-I-() ~!lj- i (U_j)<J»e&-

I1lt}-J fvJN) ': 13k )& =0 i -I I)!(j-- -1..

V04c.7/UtUll ~)o. J(ijJ eroJ2..aU

? )

(:!u~)J~~/·(-:~V)7~~(~~) + (~~;)

q~.I-eA.././a::pe j QJut /<:.<. '1A 01 ~ UJ Q ~ <M €.LV ~ -e.' le>er I') ;vJeeuu.

~ 42.0 l./ij CfJ...n< ~ rT r>Q ~ d../ ~ ¥!.-Ja~ \....U..U~'~, ~ C<:U(?J' ---- ))

Q.li.I~6 ~~~~ ~ ~cru~ ~1::tAe .

?V (t) z o.s# -f ~ ) ~2./t)~ d ~d,~ .Pt;7.t:£u"--Lcf ~ eIJ .t teuJ J ~ ~ ~ Q

f Q -= - -< et - -&:I -I- 't-t ~ > a"Z. - 2 d) - 2 c i 0/ == cD -=->-1c- = :&:v; -f ~-e -!ij- c- ~ 210 '24 - 2 ~ 0

J

-z -> etlt)?: i i I ?({(tJ=,v - /J -z

~~~.\

~rtJ-u<f!:tot:J ~ -UJJ~' e;c UJ:V' Q»~~ t?Q~ ~~ e> ~

/eu..:t»o, ~~t2 ~ a N Cf!e..1 ", J &.u t2<.o ~ <..tJ Cl ~ .J ~Q cl Q.L/ er~(;J

s-eJ4~du~.f:e /'~ ~J3cQr-e«L QCJl~l ~ f~~ceo. ~QJeJ.I~G ~ J-r.cku..u-l~' oUJ~~.