Cazanescu Curs Programare Declarativa Si Logica (1)

PROGRAMARE LOGICA ECUATIONALA

editia a III-a

Virgil Emil Cazanescu

October 4, 2008

1 SIGNATURI SI ALGEBRE MULTISORTATE


March 6, 2008

1 Signaturi multisortate

In programare, mai mult decat n orice alta activitate, datele utilizate sunt de mai multe feluri, sau sorturi asacum vom spune n continuare. Mai mult, de cele mai multe ori, n diferitele constructii sintactice, ntr-un anumitloc al acestora nu poate fi plasata decat o data de un anumit fel(sort). Aceasta ar fi explicatia faptului ca algebrelemultisortate constituie una dintre cele mai utile unelte pentru informatica teoretica.

Algebrele la randul lor nu sunt toate la fel. Felul algebrelor este dat de signatura lor. O signatura are douacomponenete una pentru date si una pentru operatii.

Componenta pentru date este pur si simplu o multime S ale carei elemente s S se numesc sorturi.Fiecare operatie este caracterizata de modul acesteia de actiune. Operatia actioneaza pe un anumit numar fix de

date de sorturi precizate si are rezultatul de un sort dat. Ca exemplu pentru operatia cu numele o notam cu

o : s1s2 . . . sn s

faptul ca ea are n argumente de sorturi s1, s2, . . ., sn iar rezultatul acesteia este de sort s.Toate aceste informatii privind felul algebrei sunt adunate n conceptul de signatura. Cu S notam multimea

sirurilor finite formate cu elemente din S.

Definitia 1.1 O signatura(S, {s1s2...sn,s}s1s2...snS,sS)

este formata dintr-o mutime S si o familie de multimi

{s1s2...sn,s}s1s2...snS,sS .

Pentru fiecare s1s2 . . . sn S si s S multimea s1s2...sn,s contine numele operatiilor cu n argumente de sorturi

s1s2 . . . sn si rezultat de sort s.

Mentionam ca multimile s1s2...sn,s pot avea elemente comune, ceea ce permite modelarea suprancarcarii operato-rilor, adica permisiunea ca mai multe operatii sa aiba acelas nume.

Cand nu exista pericol de confusie vom scrie pur si simplu (S,) sau n loc de (S, {s1s2...sn,s}s1s2...snS,sS).

2 Algebre multisortate

Algebrele sunt formate n mare din date si operatii. Datele sunt de mai multe sorturi, adica pentru fiecare sorts algebra contine o multime a datelor de sort s. Familia acestor multimi, numita si suportul algebrei, constitue omultime sortata.

2.1 Multimi si functii multisortate

Fixam multimea S a sorturilor.

Definitia 2.1 O familie de multimi M = {Ms}sS indexata de S se numeste multime S-sortata.

Observam ca aceeasi litera este folosita atat pentru ntreaga multime cat si pentru toate componentele acesteia.Conceptele uzuale cu multimi se extind pe componente de la multimile uzuale la multimile S-sortate asa cum se

vede din exemplele de mai jos

{Ms}sS {Ns}sS daca si numai daca Ms Ns s S,

1

{Ms}sS {Ns}sS = {Ms Ns}sS ,

{Ms}sS {Ns}sS = {Ms Ns}sS ,

{Ms}sS {Ns}sS = {Ms Ns}sS.

O functie ntre doua multimi sortate duce un element din prima multime ntr-un element de acelasi sort din adoua multime.

Definitia 2.2 O functie S-sortataf :M N

este o familie de functii f = {fs}sS unde componenta de sort s este o functie uzuala fs :Ms Ns.

Ca si n cazul multimilor S-sortate, operatiile cu functiile S-sortate se fac pe componente. Daca f : M N sig : N P sunt functii S-sortate atunci compunerea lor f ; g :M P este definita prin

(f ; g)s = fs; gs.

Compunerea functiilor S-sortate este asociativa.Pentru orice multime S-sortata M functia ei identitate 1M : M M este definita prin (1M )s = 1Ms pentru

orice s S. Functia identitate are efect neutru la compunere.

2.2 Algebre multisortate

Definitia 2.3 O -algebra A = ({As}sS , {A}) este formata dintr-o multime S-sortata A = {As}sS si ofamilie de operatii {A}. Pentru claritate, daca s1s2...sn,s, adica : s1s2 . . . sn s, atunci

A : As1 As2 . . . Asn As.

Daca nu exista pericol de confuzie n loc de ({As}sS , {A}) vom scrie mai simplu (As, A).Din definitia de mai sus rezulta ca daca ,s unde este sirul vid din S

, atunci A As. Deci operatiilefara argumente, numite si constante, sunt elemente ale algebrei de sort corespunzator sortului rezultat.

Vom continua prin a defini pentru algebrele multisortate cele mai uzuale concepte specifice algebrei: morfisme,subalgebre, algebre libere, congruente.

3 Morfisme de algebre multisortate

Un morfism ntre doua algebre multisortate, asemanator oricarui morfisrm de structuri algebrice, este o functiemultisortata ntre suporturile celor doua algebre care verifica o conditie suplimentara. Pentru a scrie aceasta conditiepentru cazul algebrelor multisortate sa plecam de la conceptul uzual de morfism pentru o structura algebrica bazatape o operatie binara. h : (A, ) (B,&) este morfism daca

(a A)(b A)h(a b) = h(a)&h(b).

Sa analizam egalitatea de mai sus. Pentru un numar de elemente arbitrare din prima algebra egal cu numarul deargumente ale operatiei evaluam cei doi membri

- membrul stang:1) se aplica operatia din prima algebra elementelor din prima algebra2) se aplica morfismul h rezultatului obtinut

- membrul drept:1) se aplica morfismul h elementelor din prima algebra obtinandu-se niste elemente din a doua algebra2) se aplica operatia din a doua algebra acestor elemente

- se cere ca rezultatul evalarii celor doi membri sa fie egali.

Sa facem acelasi lucru pentru doua algebre multisortate A = (As, A), B = (Bs, B) si o functie S-sortatah : A B. Conditia de mai sus trebuie pusa pentru fiecare operatie cu numele : s1s2 . . . sn s si oricare ar fielementele a1 As1 , a2 As2 . . . an Asn

- membrul stang:1) se aplica operatia din prima algebra elementelor din prima algebra: A(a1, a2, . . . , an)2) se aplica morfismul h rezultatului obtinut hs(A(a1, a2, . . . , an))

2

- membrul drept:1) se aplica morfismul h elementelor din prima algebra obtinandu-se niste elemente din a doua algebra:hs1(a1), hs2(a2), . . . , hsn(an)2) se aplica operatia din a doua algebra acestor elemente: B(hs1(a1), hs2(a2), . . . , hsn(an))

- se cere ca rezultatul evalarii celor doi membri sa fie egali.

hs(A(a1, a2, . . . , an)) = B(hs1 (a1), hs2(a2), . . . , hsn(an)).

Definitia 3.1 Functia S-sortata h : A B este un morfism de -algebre multisortate h : A B daca pentruorice s1s2 . . . sn S

, pentru orice s S, pentru orice s1s2...sn,s, pentru orice a1 As1 , a2 As2 ,. . .,an Asn

hs(A(a1, a2, . . . , an)) = B(hs1 (a1), hs2(a2), . . . , hsn(an)).

Este util sa remarcam ca exista cate o conditie pentru fiecare nume de operatie. In cazul operatiilor fara argumente,asa zisele constante, conditia de morfism este pentru orice ,s egalitatea hs(A) = B. Cu alte cuvintemorfismele trebuie sa pastreze constantele. Pe cazuri particulare observam ca orice morfism de monoizi duce elementulneutru n elementul neutru si ca orice morfism de semiinele duce elementul neutru la adunare, respectiv la nmultiretot n elementul neutru la adunare respectiv la nmultire.

Observam ca functia identitate 1A este morfism de -algebre de la A la A.

Propozitie 3.2 Compunerea ca functii S-sortate a doua morfisme de -algebre este un morfism de -algebre.

Demonstratie: Fie h : A B si g : B C doua morfisme de -algebre. Probam ca h; g : A C este morfismde -algebre.

Fie s1s2 . . . sn S, s S, s1s2...sn,s si a1 As1 , a2 As2 , . . ., an Asn . Observam ca

(h; g)s(A(a1, a2, . . . , an)) = gs(hs(A(a1, a2, . . . , an))) = gs(B(hs1(a1), hs2(a2), . . . , hsn(an))) =

= C(gs1(hs1(a1)), gs2(hs2(a2)), . . . , gsn(hsn(an))) = C((h; g)s1(a1), (h; g)s2(a2), . . . , (h; g)sn(an)). 2

Compunerea morfismelor de -algebre este asociativa.Morfismul identitate are efect neutru la compunere.

3.1 Izomorfisme de algebre multisortate

Definitia 3.3 Morfismul de -algebre h : A B se numeste izomorfism daca exista morfismul g : B A cuproprietatile h; g = 1A si g;h = 1B.

Daca exista, morfismul g din definitia de mai sus este unic. Intradevar daca f : B A este un alt morfism cuproprietatile h; f = 1A si f ;h = 1B. Observam ca

g = g; 1A = g; (h; f) = (g;h); f = 1B; f = f.

Datorita unicitatii sale, conform uzantelor morfismul g, denumit si inversul lui h, este notat n continuare cu h1.Observam ca morfismele identitate sunt izomorfisme. In plus (1A)

1 = 1A.

Propozitie 3.4 Un morfism este izomorfism daca si numai daca are toate componentele bijective

Demonstratie: Fie h : A B un morfism de -algebre.Presupunem ca h este izomorfism, prin urmare exista morfismul h1 : B A cu proprietatile h;h1 = 1A si

h1;h = 1B. Rezulta ca pentru orice sort s S au loc egalitatile hs;h1s = 1As si h

1s ;hs = 1Bs , adica functia hs

este inversabila pentru orice s S, deci toate componentele hs ale lui h sunt bijectii.Reciproc, presupunem ca toate componentele hs ale lui h sunt bijectii. Prin urmare pentru orice s S exista

functia h1s : Bs As cu proprietatile hs;h1s = 1As si h

1s ;hs = 1Bs . De aici notand h

1 = {h1s }sS rezulta cah;h1 = 1A si h

1;h = 1B.Pentru a ncheia demonstratia mai trebuie aratat ca functia S-sortata h1 : B A este un morfism de -algebre

h1 : B A.Fie s1s2 . . . sn S

, s S, s1s2...sn,s si b1 Bs1 , b2 Bs2 , . . ., bn Bsn . Deoarece h este morfism deducem

hs(A(h1s1

(b1), h1s2

(b2), . . . , h1sn

(bn))) = B(hs1(h1s1

(b1)), hs2 (h1s2

(b2)), . . . , hsn(h1sn

(bn))) = B(b1, b2, . . . , bn).

3

Aplicand functia h1s ambilor membri deducem

A(h1s1

(b1), h1s2

(b2), . . . , h1sn

(bn)) = h1s (B(b1, b2, . . . , bn))

deci h1 : B A este morfism de -algebre.

Propozitie 3.5 Compunerea a doua izomorfisme este un izomorfism. In plus

(f ; g)1 = g1; f1

4

2 ALGEBRE LIBERE - APLICATII


March 11, 2008

1 Expresii

1.1 Ce este o expresie?

Conceptul de expresie asa cum este el folosit n nvatamantul preuniversitar nu are o definitie si un nteles precis.Vom da un exemplu care sa ilustreze acest fapt. La ntrebarea este x y z o expresie? raspunsul depinde decontextul n care a fost pusa ntrebarea. Daca operatia a fost declarata asociativa, atunci x y z este o expresie.In caz contrar ea nu este o expresie deoarece include o ambiguitate putand fi interpretata ca x (y z) sau (x y) zambele fiind expresii. In continuare notiunea de expresie va fi definita n ipoteza ca operatiile cu care lucram nu aunici o proprietate suplimentara.

Mai mentionam ca cele doua expresii de mai sus mai pot fi scrise n scrierea poloneza x yz si xyz sau nscrierea poloneza inversa xyz si xyz. Ne intereseaza o definitie a conceptului de expresie care sa fie independentade forma de scriere a acesteia.

Definitia 1.1 -algebra A = (As, A) se numeste liber generata de V A daca pentru orice -algebra D si pentruorice functie sortata f : V D, exista un unic morfism de -algebre f# : A D care extinde f .

-algebra A se numeste libera daca exista V A astfel ncat A este liber generata de V.

Definitia 1.2 Se numeste expresie un element dintr-o algebra libera.

Binenteles ca acest concept este nca dependent de signatura cu care lucram. In plus notiunea naiva de expresie neda intuitia necesara pentru ntelegerea conceptului de algebra libera: algebrele libere nu sunt altceva decat algebrede expresii.

Independenta de modul de scriere al expresiilor corespunde unicitatii abstractie de un izomorfism al algebreilibere pentru care este fixata multimea generatorilor.

1.2 Evaluarea expresiilor

Un alt concept deosebit de util atat n matematica cat si n informatica este cel de evaluare a unei expresii. Desi esteclar ca pentru a evalua o expresie este necesar sa dam valori variabilelor care apar n ea, mai putin evident este faptulca trebuie precizat si unde dam valori acestor variabile. Pentru a ilustra acest fapt mentionam ca expresia x?(yz)nu poate fi evaluata numai dand valori variabilelor x, y si z ntr-o multime daca multimea nu este nzestrata cu douaoperatii binare corespunzatoare simbolurilor de operatii binare ? si . In concluzie pentru a evalua o expresie estenecesar sa dam

1. o algebra n care se fac calculele si care are aceeasi signatura cu cea a expresiei

2. valori variabilelor din expresie.

Mentionam ca a da valori variabilelor din multimea X n algebra D este echivalent cu a da o functie v : X D.Pentru orice variabila x din X valoarea data lui x este v(x).

Vom nota cu T(X) algebra liber generata de multimea X de variabile. Incluziunea X T(X) este echivalentacu faptul intuitiv ca orice variabila este o expresie. Pentru orice algebra D si pentru orice functie v : X D exista,conform definitiei algebrelor libere, un unic morfism v# : T(X) D a carui restrictie la X coincide cu v.

Fixand algebra D vom constata ca exista o bijectie naturala ntre Alg(T(X),D) multimea morfismelor dealgebre de la T(X) la D si SetS(X,D) multimea functiilor S-sortate de la X la D. Fie

r : Alg(T(X),D) SetS(X,D)

1

functia restrictie, adica r(h) : X D este restrictia morfismului h la X . Proprietatea de mai sus a algebrei liberespune ca

(v SetS(X,D))(!v# Alg(T(X),D))r(v

#) = v

adica r este bijectie. Existenta acestei bijectii ne permite sa identificam elementele celor doua multimi ne mai facanddistinctie ntre un morfism v# de la T(X) la D si v, restrictia lui la X .

Daca mai sus scriam ca a da valori variabilelor din multimea X n algebra D este echivalent cu a da o functiev : X D acum spunem ca:A da valori variabilelor din multimea X n algebra D este echivalent cu a da un morfism v : T(X) D.

O alta consecinta a celor de mai sus este:Pentru a defini un morfism de la algebra liber generata de X la algebra D este suficient sa dam ofunctie de la X la D.

Definitia 1.3 Daca e T(X) este o expresie cu variabile din X si h : T(X) D morfismul prin care se dauvalori n D variabilelor, atunci h(e) este rezultatul evaluarii expresiei e pentru valorile variabilelor date de functiah : X D. 2

Pentru a ne convinge ca aceasta definitie modeleaza corect realitatea vom relua exemplul de mai sus privind expresiax?(yz). Sa evaluam aceasta expresie n multimea numerelor naturale unde ? este nmultirea si este adunarea.

Pentru valorile x = 2, y = 3 si z = 1 intuitiv obtinem 2 (3 + 1) = 8 iar cu definitia de mai sus unde

h : (T({x, y, z}), ?,) (N, ,+)

este morfismul definit prin h(x) = 2, h(y) = 3 si h(z) = 1 obtinem

h(x?(yz)) = h(x) h(yz) = h(x) (h(y) + h(z)) = 2 (3 + 1) = 8.

1.3 Semantica instructiunii de atribuire

Fie X multimea variabilelor utilizate n program. O instructiune de atribuire este de forma x := e unde x este ovariabila si e este o expresie, adica e T(X).

Fie D -algebra datelor cu care se fac calculele. Ne intereseaza partitia memoriei n care sunt memorate dateleutilizate n timpul executiei programului, date depozitate n celule ale memoriei care corespund variabilelor din X .Prin urmare starea memoriei este caracterizata n fiecare moment de o functie s : X D. Daca x este o variabilas(x) este valoarea din celula de memorie corespunzatoare lui x. Fie S multimea starilor memoriei, adica multimeafunctiilor de la multimea variabilelor X la multimea datelor D.

O functie partiala de la A la B este o functie definita numai pe o parte a lui A cu valori n B.Semantica unei instructiuni, sau mai general a unui program, este o functie partiala F de la multimea S a starilor

la ea insasi. Functia F este definita pentru starea s a memoriei daca si numai daca executia instructiunii nceputan starea s a memoriei se termina. Mai mult F (s) este starea memoriei n momentul terminarii executiei.

Vom defini S(x := e) semantica atribuirii x := e. Fie s : X D starea memoriei la nceputul executiei atribuiriisi s# : T(X) D unica extindere la un morfism a lui s. Observam ca s#(e) este rezultatul evaluarii expresiei en starea s a memorie. Prin urmare, prin definitie

S(x := e)(s)(y) =

{s#(e) daca y = xs(y) daca y 6= x.

2 Unicitatea abstractie de un izomorfism a algebrelor libere

Teorema 2.1 Doua algebre liber generate de aceeasi multime sunt izomorfe.

Demonstratie: Fie A = (As, A) si B = (Bs, B) doua -algebre liber generate de X . Notam cu iA : X A siiB : X B functiile incluziune ale lui X n A, respectiv n B. Demonstratia are patru pasi.

1. Deoarece algebra A este liber generata de X exista un morfism f : A B cu proprietatea iA; f = iB.Pasul 2 este asemanator cu primul, doar ca se inverseaza rolul algebrelor A si B. La fel vor fi si pasii 3 si 4.

2. Deoarece algebra B este liber generata de X exista un morfism g : B A cu proprietatea iB; f = iA.3. Deoarece iA; (f ; g) = (iA; f); g = iB; g = iA = iA; 1A si deoarece A este algebra liber generata de X deducem

f ; g = 1A.4. Deoarece iB; (g; f) = (iB; g); f = iA; f = iB = iB; 1B si deoarece B este algebra liber generata de X deducem

g; f = 1B.Deci f si g sunt izomorfisme inverse unul altuia.

2

Propozitie 2.2 Orice algebra izomorfa cu o algebra libera este algebra libera.

2.1 Algebre initiale

Definitia 2.3 O -algebra I se numete intiala daca pentru orice -algebra A exista un unic morfism

A : I A.

Observam ca o algebra este initiala daca si numai daca este liber generata de multimea vida.Din teoremele de mai sus rezulta ca:

-algebra initiala este unica abstractie facand de un izomorfism.

Acest fapt are aplicatii importante n informatica.Un tip de date se numeste abstract daca este unic determinat abstractie facand de un izomorfism. Se vede prin

urmare ca dand o signatura am dat implicit, prin algebra initiala corespunzatoare signaturii, un tip abstract de dare.Vom da un exemplu cunoscut din algebra de liceu. Se stie ca numerele ntregi formeaza un inel initial. Va invitam

sa reflectati asupra urmatoarei definitii a idei de numar ntreg.

Se numeste numar ntreg un element al inelului initial.

3 Tipuri abstracte de date - introducere

Un tip de date se numeste abstract daca este unic determinat abstractie facand de un izomorfism. Abstract nseamnade fapt ca nu ne intereseaza cum sunt scrise sau memorate datele.

Una dintre metodele prin care se poate defini un tip abstract de date este cel al algebrei initiale. Mai clar : estesuficient sa dam o signatura si eventual niste ecuatii, conditionate sau nu, deoarece algebra initiala, a carei existentaeste garantata de teoremele care vor fi prezentate mai tarziu, este unic determinata abstractie de un izomorfism, prinurmare este un tip abstract de date.

Tipul numerelor naturale este definit abstract ca fiind semiinelul initial.Tipul numerelor ntregi este definit abstract ca fiind inelul initial.

Definitiile de mai sus, desi corecte sunt ineficiente, deoarece nu face posibila executia de calcule. Prin urmaredorim alte definitii echivalente dar prin care calculatorul sa fie invatat sa faca calcule. Vom exemplifica pentrunumere naturale fara intra n prea multe detalii.

3.1 Tipul abstract al numerelor naturale

Consideram signatura cu un singur sort nat, o singura constanta de sort nat si o singura operatie unara cu argumentsi rezultat de sort nat:

sort nat .op 0 : nat .op s : nat nat .

Elementele algebrei initiale sunt

0, s(0), s(s(0)), s(s(s(0))), s(s(s(s(0)))), ...

si ele reprezinta numerele naturale 0 1 2 3 4 ...

Propozitie 3.1 Fie N = (N, 0N , sN) algebra definita prin: N este multimea numerelor naturale, 0N este numarulnatural zero si sN(n) = n+ 1 pentru orice numar natural n. Algebra N este initiala.

Demonstratie: Fie A = (A, 0A, sA) o alta algebra pentru signatura de mai sus. Definim funtia h : N A prininductie

h(0N) = OAh(n+ 1) = sA(h(n)) pentru orice numar natural n.

3

Prima egalitate de mai sus si h(sN (n)) = sA(h(n)) pentru orice numar natural n dovedesc ca h : N A esteun morfism.

Probam unicitatea. Fie g : N A un alt morfism. Aratam prin inductie ca g(n) = h(n) pentru orice n natural.g(0N) = 0A = h(0N ) sig(n+ 1) = g(sN (n)) = sA(g(n)) = sA(h(n)) = h(sN (n)) = h(n+ 1). 2

Propozitia anterioara ne arata cum pot fi definite numerele naturale prim metoda algebrei initiale ca tip abstractde date. Ea dovedeste corectitudinea definitiei de mai sus.

Deocamdata prin signatura de mai sus calculatorul nvata numerele naturale dar nu stie nca sa calculeze. Pentrunceput sa-l nvatam sa adune. Daca introducem n signatura o operatie binara +

op + : nat nat nat

nu realizam nimic altceva decat sa adauge la multimea de mai sus a numerelor natural foarte mult gunoi. De exemplu,deoarece calculatorul nu stie nca sa adune, 0 + 0 este un nou element de care nu avem nevoie. Il nvatam dandu-iurmatoarele doua reguli de rescriere precedate de o declarare de variabile

var X Y : nat .eq X + 0 = 0 .eq X + s(Y) = s(X+Y) .

Trebuie sa remarcam diferenta esentiala dintre o regula de rescriere si o egalitate. O regula de rescriere seaplica numai de la stanga la dreapta, deoarece simetria este unul dintre marii dusmani ai programarii prin rescriereconducand la neterminarea programelor.

Ce parere aveti despre comutativitate?

Sa vedem cum efectueaza masina adunarea 2 + 2, adica:

s(s(0)) + s(s(0)).

Calculatorul nu poate aplica decat a doua regula pentru X=s(s(0)) si Y=s(0) ajungand la

s( s(s(0)) + s(0) ).

Trebuie din nou aplicata a doua regula de rescriere pentru X=s(s(0)) si Y=0 ajungand la

s(s( s(s(0)) + 0 )).

Acum se poate aplica numai prima regula pentru X=s(s(0)) obtinand rezultatul s(s(s(s(0)))), adica 4. Calculatorulse opreste deoarece nu se mai pot face rescrieri.

Corectitudinea acestei definitii precum si a celei care urmeaza va fi facuta mai tarziu.Calculatorul va sti sa si nmulteasca daca mai introducem o operatie binara si doua reguli de rescriere

op * : nat nat nat .eq X * 0 = 0 .eq X * s(Y) = X*Y + X .

4

3 SUBALGEBRE


March 11, 2008

1 Parti stabile, Subalgebre

Ideea de parte stabila este foarte simpla deoarece este un concept natural. Concret, o parte P a unei algebre estestabila daca rezultatul aplicarii oricarei operatii din algebra unor elemente din P este tot n P.

Definitia 1.1 Fie A = (As, A) o -algebra si Ps As pentru orice s S. Partea P = {Ps}sS a lui A se numestestabila daca pentru orice s1s2 . . . sn S

, pentru orice s S, pentru orice s1s2...sn,s, pentru orice a1 Ps1 ,a2 Ps2 ,. . .,an Psn elementul A(a1, a2, . . . , an) este n Ps.

Observam ca orice parte stabila contine toate constantele, adica (s S)( ,s)As Ps.Vom arata n cele ce urmeaza ca partile stabile ale oricrei algebre formeaza o familie Moore. Pentru aceasta se

poate demonstra ca orice intersectie de parti stabile este o parte stabila. Lasam acest fapt ca exercitiu. Vom preferao cale mai dificila dar cu rezultat mult mai util n multe cazuri.

Fie A = (As, A) o -algebra si X A. Definim prin inductie sirul de parti ale lui A astfelX0 = X siXn+1s = X

ns {A(a) : w,s, a X

nw} pentru orice n N si orice s S.

Observam ca sirul {Xn}nN este crescator.

Definim partea X a lui A prin

X =

nN

Xn.

Propozitie 1.2 X este partea stabila generata de X.

Demonstratie: Cu alte cuvinte X este cea mai mica parte stabila a lui A care include X , adica trebuie sademonstram ca

1. X X

2. X este parte stabila

3. daca P este o parte stabila care include X atunci P include X

Prima incluziune este aprope evidenta deoarece X = X0 X.Probam ca X este parte stabila. Fie s1s2 . . . sn S

, s S, s1s2...sn,s si a1 Xs1 , a2 Xs2 , . . ., an Xsn .Pentru orice 1 i n din ai Xsi , adica ai

nN X

nsi

exista un numar natural ki cu proprietatea ai Xkisi.

Fie k cel mai mare dintre numerele k1, k2, . . . , kn. Deoarece sirul {Xn}n este crescator deducem ca ai X

ksi

pentru

orice 1 i n. Din definitia sirului {Xn}n deducem A(a1, a2, . . . , an) Xk+1s . Deoarece X

k+1 X deducem caA(a1, a2, . . . , an) Xs deci X este parte stabila.

Fie P o parte stabila a algebrei A cu proprietatea X P . Probam prin inductie ca Xn P pentru orice nnatural.

Daca n = 0 atunci X0 = X P.Presupunem Xn P si demonstram ca Xn+1 P. Fie a Xn+1s . Daca a X

ns din ipoteza de inductie deducem

a Ps. Altfel exista s1s2 . . . sk S, s S, si ai X

nsipentru orice 1 i k cu proprietatea a = A(a1, a2, . . . , ak).

Din ipoteza de inductie deducem ai Psi pentru orice 1 i k. Deoarece P este parte stabila deducem caA(a1, a2, . . . , ak) Ps, deci a Ps.

Deoarece Xn P pentru orice n natural rezulta canN X

n P , deci X P. 2

Definitia 1.3 Fie A o -algebra si X A. Daca X = A spunem ca X genereaza A sau ca A este generata de X .

1

Operatorul de nchidere asociat familiei Moore a partilor stabile are urmatoarele proprietati:

1. daca X Y sunt parti ale algebrei, atunci X Y ,

2. X = X pentru orice parte X a algebrei.

1.1 Inductie structurala

Aceasta metoda de a face inductie este folosita pentru a demonstra ca elementele unei algebre au o anumita propri-etate. Metoda se numeste structurala deoarece se bazeaza pe structura algebrei.

Fie A = (As, A) o -algebra, X o multime de generatori ai algebrei A si P o proprietate referitoare la elementelealgebrei A. Pentru a dovedi ca toate elementele algebrei A au proprietatea P este suficient ca sa dovedim ca

1. orice element din X are proprietatea P,

2. pentru orice s1s2 . . . sn S, s S, s1s2...sn,s daca a1 As1 , a2 As2 , . . ., an Asn sunt elemente

arbitrare cu proprietatea P, atunci A(a1, a2, . . . , an) are proprietatea P.

Ne vom convinge de corectitudinea inductiei structurale. Fie B submultimea lui A formata din toate elementelealgebrei A care au propritatea P.- Proprietatea 1 de mai sus ne asigura ca X B.- Proprietatea 2 de mai sus ne asigura ca B este parte stabila.

Prin urmare X B. Dar X = A deoarece X genereaza algebra A, prin urmare B = A, deci orice element din Aare proprietatea P.

1.2 Subalgebre

Conceptul de subalgebra este foarte apropiat de cel de parte stabila. Diferenta principala consta n faptul ca unaeste o algebra si alta este o multime.

O subalgebra a algebreiA = (As, A) este o alta algebra B = (Bs, B) cu proprietatileB A si B(b1, b2, . . . , bn) =A(b1, b2, . . . , bn) oricare ar fi s1s2 . . . sn S

, s S, s1s2...sn,s si b1 Bs1 , b2 Bs2 , . . ., bn Bsn .Observam ca daca algebra B este subalgebra a algebrei A, atunci B este o parte stabila a algebrei A.Reciproc, daca B este o parte stabila a algebrei A putem defini subalgebra B de suport B prin B(b1, b2, . . . , bn) =

A(b1, b2, . . . , bn) oricare ar fi s1s2 . . . sn S, s S, s1s2...sn,s si b1 Bs1 , b2 Bs2 , . . ., bn Bsn .

2 Morfisme si parti stabile

O pereche de morfisme cu acelasi domeniu si acelasi codomeniu se mai numeste si sageata dubla.

Definitia 2.1 Fie f : A B si g : A B doua morfisme. Numin nucleu de sageata dubla al morfismelor fsi g submultimea lui A notata Ker(f,g) si definita pentru orice sort s prin

Ker(f, g)s = {a As : fs(a) = gs(a)}.

Propozitie 2.2 Nucleul de sageata dubla este o parte stabila.

Demonstratie: Fie s1s2 . . . sn S, s S, s1s2...sn,s si a1 Ker(f, g)s1 , a2 Ker(f, g)s2 , . . .,

an Ker(f, g)sn . Pentru orice 1 i n deducem ca fsi(ai) = gsi(ai). Prin urmare

fs(A(a1, a2, . . . , an)) = B(fs1(a1), fs2(a2), . . . , fsn(an)) = B(gs1(a1), gs2(a2), . . . , gsn(an)) = gs(A(a1, a2, . . . , an)),

deci A(a1, a2, . . . , an) Ker(f, g)s

Corolar 2.3 Fie f : A B si g : A B doua morfisme si X o submultime a lui A. Daca restrictiile lui f si gla X coincid, atunci restrctiile lui f si g la X sunt egale.

Corolar 2.4 Fie f : A B si g : A B doua morfisme Daca restrictiile lui f si g la o multime de generatoriai algebrei A coincid, atunci f = g.

2

Propozitie 2.5 Fie h : A B un morfism de -algebre.

1. Daca P este o parte stabila a lui A, atunci h(P ) este o parte stabila a lui B.

2. Daca Q este o parte stabila a lui B, aunci, h1(Q) este o parte stabila a lui A.

3. Daca X este o parte a lui A, atunci h(X) = h(X).

Demonstratie:1. Prima proprietate spune ca imaginea directa a unei parti stabile printr-un -morfism este o parte stabila.Fie s1s2 . . . sn S

, s S, s1s2...sn,s si b1 hs1(Ps1), b2 hs2(Ps2 ), . . . , bn hsn(Psn). Pentru orice1 i n exista pi Psi astfel ncat bi = hsi(pi). Deoarece P este o parte stabila deducem A(p1, p2, . . . , pn) Ps.Observam ca

hs(As(p1, p2, . . . , pn)) = Bs(hs1(p1), hs2(p2), . . . , hsn(pn)) = Bs(b1, b2, . . . , bn).

Prin urmare Bs(b1, b2, . . . , bn) hs(Ps), deci h(P ) este parte stabila a algebrei B.2. A doua proprietate spune ca imaginea inversa a unei parti stabile printr-un -morfism este o parte stabila.Fie s1s2 . . . sn S

, s S, s1s2...sn,s si a1 h1s1

(Qs1), a2 h1s2

(Qs2), an h1sn

(Qsn). Deoarece Q esteparte stabila si hs1(a1) Qs1 , hs2(a2) Qs2 , . . . hsn(an) Qsn deducem B(hs1(a1), hs2(a2), . . . , hsn(an)) Qs.Deoarece

hs(As(a1, a2, . . . , an)) = Bs(hs1(a1), hs2(a2), . . . , hsn(an))

deducem ca As(p1, p2, . . . , pn) h1s (Qs), deci h

1(Q) este parte stabila.3. Din X X deducem h(X) h(X). Deoarece membrul drept este o parte stabila fapt ce rezulta din prima

proprietate deducem cah(X) h(X).

Din h(X) h(X) deducem h1(h(X)) h1(h(X)). Deoarece X h1(h(X)) rezulta ca X h1(h(X)).Deoarece membrul drept este conform proprietatii 2 o parte stabila deducem X h1(h(X)). Deoarece imagineadirecta este crescatare h(X) h(h1(h(X))). Deoarece h(h1(h(X))) h(X) deducem

h(X) h(X).

Din cele doua incluziuni de mai sus rezulta concluzia.

3

4 ALGEBRE LIBERE


March 11, 2008

1 Algebre libere si algebre Peano

Algebrele libere si algebrele Peano sunt doua concepte echivalente. Pentru a ntelege mai bine acest fapt vomexemplifica un fenomen asemanator din cazul mult mai simplu al monoizilor.

FieM un monoid si B M. Reamintim doua definitii echivalente pentru faptul ca monoidulM este liber generatde submultimea sa B.

Definitia 1.1 Pentru orice monoid N si orice functie f : B N exista un unic morfism f# :M N de monoizia carui restrictie la B este f .

Definitia 1.2 Pentru orice m M exista si sunt unice numarul natural n si elementele b1 B, b2 B, . . . , bn Bcu proprietatea m = b1b2 . . . bn.

Sa observam diferenta esentiala dintre cele doua definitii. Observam ca n definitia 1.1 nu apar de loc elemente,aparand numai concepte din afara monoidului M . Definitia 1.2 n schimb lucreaza numai cu elemente din interiorulmonoidului.

Comparand definitia data algebrelor libere cu cele doua de mai sus constatam ca definitia 1.1 este asemanatoare.Sunt atat de asemanatoare ncat pot fi generalizate la cel mai nalt nivel de abstractizare, cel al teoriei categoriilor.

Conceptul asemanator celui din definitia 1.2 este cel de algebra Peano, concept echivalent cu cel de algebra libera.Problema esentiala este de a demonstra existenta algebrelor libere, fapt care nu este simplu. Reamintim ca o

algebra libera este de fapt o algebra de expresii. Se poate demonstra ca expresiile formeaza o algebra Peano si apoiproba ca algebrele Peano sunt libere. Deoarece expresiile pot fi scrise n mai multe moduri, fiecare dintre acestescrieri poate conduce la o demonstratie. Deoarece textul se adreseaza unor informaticieni vom prefera reprezentareaexpresiilor ca arborii etichetati, local ordonati, n care frunzele sunt etichete cu variabile(generatori) sau nume deconstante. Restul nodurilor sunt etichetate cu nume de operatii ale caror argumente sunt date de subarborii avandradacinile drept succesori ale nodului.

1.1 Existenta algebrelor libere - varianta scurta

Definitia 1.3 Se numeste multime S-sortata de variabile o multime S-sortata X = {Xs}sS cu componenteledisjuncte doua cate doua.

Conditia de mai sus rezulta din faptul ca o variabila nu poate fi de doua sorturi diferite. Altfel spus fiecare variabilasi determina sortul. O definitie echivalenta ar fi o funtie f : X S. In acest caz Xs = f1(s) pentru orice s S.

Varianta scurta este scrisa pentru cei care au dificultati n a ntelege o demonstratie corecta dar mai dificila. Ceicare prefera varianta scurta pot sarii sectiunea urmatoare. Ceilalti sunt invitati sa sara direct la sectiunea urmatoare.

Plecam de la o signatura (S,) si o multime S-sortata de variabile X.Fie T(X) cea mai mica multime S-sortata cu urmatoarele proprietati:

1. Xs T(X)s pentru orice s S,

2. ,s T(X)s pentru orice s S,

3. Pentru orice n 1, pentru orice s1s2 . . . sn S, pentru orice s S, pentru orice s1s2...sn,s, dacati T(X)si pentru orice 1 i n, atunci (t1, t2, . . . , tn) T(X)s.

1

Multimea S-sortata T(X) devine o -algebra definind operatiile notate T dupa cum urmeaza:

1. T = daca ,s

2. T(t1, t2, . . . tn) = (t1, t2, . . . , tn) daca n 1, s1s2...sn,s si ti T(X)si pentru orice 1 i n.

Vom demonstra n cele ce urmeaza ca -algebra (T(X)s, T) este liber generata de X.

Fie A = (As, A) o -algebra si f : X A o functie S-sortata.Definim functia S-sortata f# : T(X) A prin

1. f#s (x) = fs(x) pentru orice x Xs si s S,

2. f#s () = A pentru orice ,s,

3. f#s ((t1, t2, . . . , tn)) = A(f#s1(t1), f

#s2(t2), . . . , f

#sn(tn)) pentru orice n 1, pentru orice s1s2 . . . sn S, pentru

orice s S, pentru orice s1s2...sn,s si orice ti T(X)si pentru orice 1 i n.

Din prima parte a definitiei de mai sus se vede ca restrictia functiei f# la X este chiar functia f.Din celelalte doua parti ale definitiei rezulta ca f# este un morfism de -algebre de la T(X) la A.

Unicitatea: Daca h : T(X) A este un morfism a carui restrictie la X este f , deoarece X este o multime degeneratori ai lui T(X) si deoarece h si f

# coincid pe X deducem ca h = f#.Unde-i greseala?

2 Algebre Peano

Definitia 2.1 O algebra A = (As, A) se numete Peano peste X A daca1. X genereaza algebra A,2. pentru orice w,s si orice a Aw, A(a) 6 Xs si3. ( w,s)(a Aw)( w,s)(a Aw) A(a) = A (a) w = w, = si a = a.

Teorema 2.2 Orice algebra Peano peste X este liber generata de X.

Demonstratie: Fie A = (As, A) o algebra Peano peste X A, B o alta algebra si h : X B o functie.Deoarece algebra A este generata de X rezulta ca

A =nN

Xn

unde X0 = X si pentru orice n N si orice s S

Xn+1s = Xns {A(a) : w,s, a X

nw}.

Definim prin inductie dupa n N sirul de functii hn : Xn B prin h0 = h si

hn+1s (a) =

{hns (a) daca a X

ns

B(hnw(a

)) daca a = A(a) 6 Xns unde w,s si a

Xnw

Corectitudinea acestei definitii rezulta din conditia 3 din definitia algebrei Peano.Observam ca sirul functiilor hn : Xn B este crescator, adica restrictia lui hn+1 la Xn este chiar hn. Mai

mult pentru orice m n restrictia lui hm la Xn este chiar hn.Definim functia g : A B pentru orice s S si orice a As prin

gs(a) = hns (a) daca n este cel mai mic numar natural cu proprietatea a X

ns .

Observam ca gs(a) = hms (a) pentru orice numar natural m cu proprietatea a X

ms .

Probam ca g : A B este morfism de algebre. Fie w,s si a Aw.Deoarece A(a) 6 X

0s exista n cel mai mic numar natural cu proprietatea A(a) X

n+1s X

ns . Rezulta ca

gs(A(a)) = hn+1s (A(a)).

2

Probam ca a Xnw. Deoarece A(a) Xn+1s X

ns exista

w,s si a Xnw astfel ncat A(a) = A(a). Rezulta

ca w = w, = si a = a, deci a Xnw. Prin urmare

gw(a) = hnw(a) si h

n+1s (A(a)) = B(h

nw(a))

decigs(A(a)) = B(h

nw(a)) = B(gw(a)).

Restrictia lui g la X = X0 este h0 = h.Unicitatea lui g este consecinta faptului ca X genereaza A. 2

3 Algebra arborilor de derivare

O gramatica independenta de context poseda doua multimi disjuncte, una a neterminalelor N si una a terminalelorT precum si multimea P N (N T ) a productiilor. Chiar daca conceptul de gramatica independenta de contextverifica si alte conditii, noi ne restrangem doar la cele de mai sus deoarece acestea sunt utile n cele ce urmeaza.

Fiecarei gramaticii independente de context G i se poate atasa o signatura:- neterminalele devin sorturi,- productiile devin nume de operatii,- daca (n, t0n1t1 . . . nktk) P unde literele n sunt neterminale si literele t sunt cuvinte cu litere terminale, atunci

(n, t0n1t1 . . . nktk) : n1n2 . . . nk n

adica operatia corespunzatoare lui (n, t0n1t1 . . . nktk) are ca rezultat un element de sortul indicat de neterminaluldin membrul stang al productiei, un numar de argumente egal cu numarul de neterminale din membrul drept alproductiei si sorturile argumentelor sunt chiar neterminalele din membrul drept al productiei.

O algebra a carei signatura este cea atasata gramaticii independente de context G se numeste G-algebra.

Un arbore de derivare ntr-o gramatica independenta de context are urmatoarele proprietati:

1. are noduri etichetate cu terminale sau neterminale, radacina fiind etichetata cu un neterminal;

2. este local ordonat: succesorii fiecarui nod sunt ntr-o ordine totala;

3. pentru orice nod, daca este etichetat cu un terminal atunci nu are succesor, iar daca este etichetat cu un netermi-nal n, atunci acesta si cuvantul format de etichetele succesorilor formeaza o productie (n, s1s2 . . . sk1sk) P .

Arborii de derivare ai unei gramatici independente de context G pot fi organizati ca o G-algebraA dupa cum urmeaza:- pentru orice neterminal n multimea An este formata din totalitatea arborilor de derivare care au radacina

etichetata cu n.- pentru productia p = (n, t0n1t1 . . . nktk) si arborii ai Ani arborele Ap(a1, a2, . . . , ak) este format astfel:

radacina este etichetata cu n, succesorii radacinii n numar egal cu numarul literelor din t0n1t1 . . . nktk sunt chiarliterele acestui cuvant si subarborele fiecarui nod etichetat cu ni este chiar ai.

Teorema 3.1 Algebra arborilor de derivare ai unei gramatici independente de context este algebra Peano peste

multimea vida.

Demonstratie: Pentru a proba ca A este generata de multimea vida este suficient sa demonstram ca A este singuraparte stabila a lui A. Fie P o parte stabila a lui A. Vom proba prin inductie dupa adancimea arborilor ca oricearbore este n P . Reamintim ca adancimea unui arbore este lungimea celei mai lungi ramuri din arbore. Fie m unnumar natural. Presupunem prin ipoteza de inductie ca orice arbore cu adancimea strict mai mica decat m este nP. Probam ca orice arbore de adancime m este n P . Fie a un arbore de adancime m. Analizand radacina si primulnivel al arborelui a deducem existenta unei productii p = (n, t0n1t1 . . . nktk) cu proprietatea

a = Ap(a1, a2, . . . , ak).

unde ai sunt subarborii lui a care au varfurile n succesorii radacinii lui a care sunt etichetati cu neterminale.Observam ca arborii a1, a2, . . . , ak au adancimea cu cel putin o unitate mai mica decat adancimea lui a, adica

strict mai mica decat m. Prin ipoteza de inductie rezulta ca ai Psi pentru orice 1 i k. Deoarece P este o partestabila deducem ca Ap(a1, a2, . . . , ak) Ps, deci a Ps.

3

A doua conditie din definitia algebrelor Peano

AP (a1, as, . . . , ak) 6

este evident adevarata.Trecem la ultima conditie. Fie p = (n, t0n1t1 . . . nktk) si q = (n, t

0s1t

1 . . . skt

k) doua nume deoperatii(productii) unde literele n si s sunt neterminale si literele t sunt cuvinte formate din terminale. Fie ai Anipentru 1 i k si bi Asi pentru 1 i k

astfel ncat

Ap(a1, a2, . . . , ak) = Aq(b1, b2, . . . , bk)

Egaland cuvintele formate cu etichetele succesorilor radacinilor din cei doi arbori egali deducem

t0n1t1 . . . nktk = t

0s1t

1 . . . sk t

k .

Reamintim ca prin definitia gramaticilor un element nu poate fi n acelasi timp si terminal si neterminal. Deoarecenumarul neterminalelor din cele doua cuvintre trebuie sa fie egal deducem egalitatea k = k. Deoarece primeleneterminale din cele doua cuvinte trebuie sa fie pe aceeasi pozitie deducem ca t0 = t

0 si n1 = s1. Rezulta ca

t1 . . . nktk = t

1 . . . skt

k.

Continuam rationamentul ca mai sus si deducem ti = t

i pentru 0 i k si ni = si pentru 1 i k. De aicideducem ca p = q.

In final egaland subarborii cu radacinile aflate pe aceeasi pozitie ale primului nivel rezulta ca ai = bi pentru orice1 i k. 2

Scriu randurile care urmeaza deoarece de mai multe ori cativa dintre studentii au contestat lipsa primului pas alinductiei n prima parte a demonstratiei de mai sus. El nu lipseste ci este pur si simplu inclus n demonstratia demai sus. Primul pas este cazul m = 0. Este evident ca prin ipoteza de inductie nu se presupune nimic deoarece nuexista arbori de adancime strict negativa. Arborele a de adancime 0 nu are decat radacina etichetata sa spunem cun, prin urmare p = (n, ), deci a = Ap. In concluzie Ap Pn deoarece P este parte stabila, deci a Pn.

4 Existenta algebrelor libere

Urmarim sa aratam ca pentru orice signatura si pentru multime S-sortata de variabile X exista o -algebra libergenerata de X pe care n cele ce urmeaza o vom nota cu T(X). Constructia algebrei libere care urmeaza este bazatape scrierea poloneza a expresiilor, adica un sir de semne de operatii si variabile n care semnul de operatie este plasatn fata argumentelor sale care trebuie sa-l urmeze. Productiile de forma (s, s1s2 . . . sn) unde s1s2...sn spun cadaca ei este expresie de sort si pentru orice 1 i n, atunci e1e2 . . . en este expresie de sort s. Productiile deforma (s, x) unde s S si x Xs spun ca orice variabila x de sort s este expresie de sort s.

Fie (S,) o signatura si X o multime S-sortata cu componentele disjuncte doua cate doua. Fara a micsorageneralitatea vom presupune ca si X sunt disjuncte.

Consideram gramatica independenta de context definita prin1. Multimea neterminalelor este S,2. Multimea terminalelor este X si3. Multimea productiilor este {(s, w)| w,s} {(s, x)|s S, x Xs}.

Notam cu A = (As, A(s,w), A(s,x)) algebra arborilor ei de derivare. Ea este algebra Peano peste multimea vida.Notam cu B = (As, B) algebra de signatura definita prin B = A(s,w) pentru orice w,s si cu i : X A

functia S-sortata definita pentru orice s S si x Xs prin is(x) = A(s,x). Observam ca functia i are toatecomponentele injective.

Teorema 4.1 -algebra B este Peano peste i(X).

Demonstratie:

1. Fie C A o parte stabila a algebrei B care include i(X). Observam ca C este o parte stabila a algebrei A.Deaorece A este Peano peste multimea vida rezulta ca C = A.In concluzie algebra B este generata de i(X).

4

2. Fie w,s si a Aw. Deoarece A(s,w)(a) 6= A(s,x) pentru orice s S si x Xs rezulta ca B(a) 6 i(X).

3. Fie w,s, a Aw, w,s a Aw cu B(a) = B(a). Din

A(s,w)(a) = A(s,w)(a)

deoarece A este algebra Peano deducem ca (s, w) = (s, w) si a = a. Mai observam ca = si w = w. 2Putem spune ca ne-am atins scopul deoarece -algebra B este liber generata de multimea i(X) care, deoarece

functia i este injectiva, este n bijectie cu X .

Propozitie 4.2 Orice algebra libera este Peano

Demonstratie: Fie L o -algebra liber generata de multimea X . Consideram o -algebra P Peano peste X .Deoarece si P este liber generata de X rezulta existenta unui izomorfism i : P L cu proprietatea i(x) = x pentruorice x X . Deci L este algebra Peano peste X .

5

5 SEMANTICA ALGEBREI INITIALE


March 22, 2008

Metoda semanticii algebrei initiale este o simplificare a metodei mai clasice a semanticii denotationale.Metoda semanticii algebrei intiale se aplica pentru limbaje definite printr-o gramatica independenta de context

G = (N, T, P, a), unde N este multimea neterminalelor, T mtimea terminalelor, P multimea productiilor si a ax-ioma gramaticii. Ea spune ca pentru a defini semantica limbajului gramaticii G este suficient sa dam oG-algebra S = (Sn, Sp) unde n este un neterminal si p o productie.

Pentru a ntelege afirmatia de mai sus trebuie sa intram putin n amanunte. Fie A algebra arborilor de derivare.Deoarece A este algebra intiala exista un unic morfism de G-algebre

M : A S.

Dat un cuvant c din limbajul gramaticii G exista un arbore de derivare arb cu radacina etichetata cu a a caruifrontiera este c. Semantica cuvantului c este prin definitie Ma(arb).

Mentionam ca metoda este bine definita numai pentru gramaticile neambigue, fapt care asigura unicitatea ar-borelui arb. Acest aspect este mai degraba legat de analiza sintactica.

Trecem la exemple care vor clarifica si mai mult ideile de mai sus.

1 Semantica unui sir de cifre ca numar natural

Vom considera o gramatica G care genereaza sirurile finite de cifre zecimale, considerate ca terminale. Gramaticaare doua neterminale si ultima fiind si axioma a gramaticii. Descriem n continuare productiilegramaticii carora le dam un nume

ci i pentru orice cifra zecimala in1 n2

Vom defini algebra semantica explicand de ce o definim astfel. Deoarece gramatica are doua neterminale, signaturaasociata are doua sorturi, prin urmare algebra semantica trebuie sa aiba ca suport doua multimi. Deoarece semanticaunei cifre, care nu este nimic altceva decat un semn, este numarul reprezentat de cifra. Prin urmare suportulcorespunzator neterminalului trebuie sa contina macar numerele de la zero la noua. Deci prin definitie

S = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.

Deoarece semantica unui sir finit de cifre este numarul natural pe care acest sir l reprezinta, suportul corespunzatorneterminalului trebuie sa contina macar multimea numerelor naturale. Deci prin definitie

S = este multimea numerelor naturale.

Sa trecem la definirea operatiilor algebrei semantice.Deoarece productia ci corespunzatoare cifrei i nu are nici un neterminal n membrul drept, operatia corespunza-

toare ei este o operatie fara argumente, adica un element din S

Sci este numarul natural reprezentat de cifra i.

Productia n1 spune ca orice cifra este un sir dr cifre. Deoarece valoarea numarului reprezentat de un sir de lungimeunu este egala cu valoarea numarului reprezentat de singura cifra din sir si semantica lor trebuie sa fie aceeasi. Deciprin definitie

Sn1 este functia incluziune de la S la S.

1

Productia n2 ne spune ca prin adaugarea la dreapta unui sir de cifre, sa spunem s1, a unei cifre, sa spunem c, seobtine un nou sir de cifre s2 = s1c. Operatia corespunzatoare productiei n2 trebuie sa fie o functie

Sn2 : S S S

definita pentru numele n si m prinSn2(n, m) = 10n + m

deoarece valoarea ca numar a sirului s2 este egala cu de zece ori valoarea ca numar a sirului s1 plus valoarea canumar a cifrei.

Cu aceasta semantica este complet definita. Vom exemplifica pentru sirul 023. Arborele de derivare pentru acestsir este

An2(An2(An1(Ac0), Ac2), Ac3).

Sa-i aplicam morfismul semantic acestui arbore.

M(An2(An2(An1(Ac0), Ac2), Ac3)) = Sn2(Sn2(Sn1(Sc0), Sc2), Sc3) = Sn2(Sn2(Sn1(0), 2), 3) = Sn2(Sn2(0, 2), 3) =

Sn2(10 0 + 2, 3) = Sn2(2, 3) = 10 2 + 3 = 23

Ce sa ntampla daca n membrul drept al productiei n2 scriem < cifra >< nat >?

2 Un calculator de buzunar

Vom da un alt exemplu, cel al unui minicalculator pe fata caruia se afla un mic ecran pe care se poate afisa un singurnumar si mai multe butoane:

ON pentru pornirea calculatoruluiOFF pentru oprirea calculatorului0 1 2 3 4 5 6 7 8 9 pentru cifrele zecimale+ pentru adunare si nmultireM pentru unica celula de memorie a calculatorului( ) pentru parantezele necesare n scrierea expresiilorIF , pentru o anumita instructiuneE pentru comanda de evaluarea a unei expresii

Vom considera o gramatica G care genereaza limbajul programelor care pot fi executate de minicalculator. Eaextinde gramatica din exemplul precedent.

Gramatica are cinci neterminale , , pentru expresii, pentru anumite portiuni deprograme si care este si axioma a gramaticii. Descriem n continuare productiile gramaticii carora ledam un nume

ci i pentru orice cifra zecimala in1 n2 r1 r2 Mr3 + r4 r5 IF ,,r6 ()r7 E OFFr8 E r9 ON

Pentru a da semantica este necesar sa explicam cum functioneaza calculatorul. Se porneste calculatorul apasandbutonul ON, moment n care se initializeaza unica celula de memorie cu zero. Se introduce o expresie care la apasareabutonului E se evalueaza. Rezultatul evaluarii este afisat pe ecran si introdus n unica celula de memorie n loculvechii valori. Se introduce alta expresie, se apasa butonul E si asa mai departe. La final se apasa butonul OFFpentru nchiderea calculatorului. Mai remarcam ca se calculeaza numai cu numere naturale.

2

Vom defini algebra semantica. Deoarece signatura asociata are cinci sorturi, algebra semantica trebuie sa aiba casuport cinci multimi, primele doua fiind cele de mai sus S si S.

Expresiile sunt facute pentru a fi evaluate, prin urmare prima idee ar fi ca semantica unei expresii sa fie un numar.Dar oare ce numar se obtine prin evaluarea expresiei M+3. Trebuie sa mentionam ca fiecare aparitie a lui M estenlocuita n timpul evaluarii cu valoarea care se afla n unica celula de memorie. Prin urmare rezultatul evaluariilui M+3 depinde de continutul celulei de memorie. Prin urmare semantica expresiei M+3 este functia f : N Ndefina prin f(x) = x + 3 care asociaza numarului x care se afla n celula de memorie rezultatul x + 3 al evaluariiacesteia. Prin urmare prin definitie S este multimea functiilor de la multimea numerelor naturale la ea nsasi.

O instructiune comanda evaluarea unui sir finit de expresii. Semantica instructiunii este, prin definitie, sirulnumerelor care apar pe ecran n timpul executiei instructiunii, adica un sir finit si nevid de numere naturale. Multimeaacestor siruri o notam cu N+. Rezultatul evaluarii depinde evident de valoarea din memorie din momentul nceperiiexecutiei instructiunii, prin urmare

S = {f : N N+ / f estefunctie.}

Un program difera de o instructiune prin faptul ca se introduce zero n celula de memorie nainte de executiainstructiunii pe care o contine, prin urmare sirul de numere care apar pe ecran n timpul executiei programului numai depinde de continutul memoriei, fiind un element din N+, deci S = N

+.

Definitiile pentru operatii, fara a mai repeta pe cele de mai sus sunt:

Sr1(n)(m) = nSr2(m) = mSr3(e1, e2)(m) = e1(m) + e2(m)Sr4(e1, e2)(m) = e1(m) e2(m)Sr5(e1, e2, e3)(m) = daca e1(m) = 0 atunci e2(m) altfel e3(m)Sr6(e) = eSr7(e)(m) = e(m)Sr8(e, )(m) = e(m)(e(m))Sr9() = (0)

unde am folosit urmatoarele notatii

m este un numar natural reprezentand continutul celulei de memorien este un numar naturale este o functie de la N la N reprezentand semantica unei expresii este o functie de la N la N+ reprezentand semantica unei instructiuni.

3

APLICATII ale metodei ALGEBREI INITIALE


February 14, 2010

1 Arbori de derivare

Un arbore de derivare ntr-o gramatica independenta de context are urmatoarele proprietati:1. are noduri etichetate cu terminale sau neterminale;2. este local ordonat: succesorii fiecarui nod sunt ntr-o ordine totala;3. pentru orice nod, daca este etichetat cu un terminal atunci nu are succesor, iar daca este etichetatcu un neterminal n, atunci acesta si cuvantul format de etichetele succesorilor formeaza o productie(n, s1s2 . . . sk1sk) P .

n

s s s s1 2 k-1 k

1.1 O gramatica pentru expresii

Definim o gramatica independenta de context pentru expresiile construite cu variabilele x, y si z,cu operatiile binare de adunare si nmultire si cu paranteze. Gramatica trebuie constrita respectandurmatoarele conditii privind expresiile:

1. nmultirile se fac naintea adunarilor2. adunarile se fac de la stanga la dreapta3. nmultirile de la dreapta la stanga.

Multimea terminalelor este {x, y, z, (, ),+, }. FieN = {V, F, T,E, P}multimea neterminalelor. Semnificatialor este urmatoarea:

V reprezinta variabileleF de la factor, reprezinta cele mai mici elemente folosite n constructia expresiilorT de la termen, reprezinta un produs de factoriE de la expresie, reprezinta o suma de termeniP de la program.

Continuam cu multimea regulilor(productiilor) gramaticii:

0. P E 1. V x 2. V y 3. V z 4. F V5. F (E) 6. T F 7. T F T 8. E T 9. E E + T

Observati productiile 7 si 9 pentru a vedea cum se precizeaza ordinea de executie a operatiilor de acelasifel. Neterminalul din membrul stang se afla n dreapta, respectiv n stanga semnului operatiei.

1

1.2 Un exemplu

Sa se construiasca arborele de derivare pentru expresia x+ y (x+ y) z + z.

P

E

E

E T

T

T

z

F

F

+

+

V

x

T*

V

y

F T*

( )E

E + T

T

F

V

x

F

V

y

F

V

F

V

z

Pentru a reface expresia, arborele se parcurge n inordine.Daca veti incerca sa construiti alt arbore de derivare pentru aceeasi expresie veti constata ca acest lucru

nu este posibil. Prin urmare modul de constructie al expresiei va impune o anumita ordine n evaluareaacesteia.

Folosind numerele care denumesc productiile ca nume ale operatiilor din algebra arborilor de derivare

2

arborele de mai sus este

A = 0(9[9{a, 7(4[2], 7[ 5{9(a,6[4(2)])},b ]) },b])

unde a = 8(6[4(1)]) si b = 6(4(3)).

0

9

9

8 7

6

6

4

4

1

7

2 5 6

9

8 6

6

4

1

4

2

4

3

4

3

3

2 Scrierea poloneza inversa

Semantica pe care o dam unui limbaj depinde de scopul pe care-l urmarim. Pentru a ilustra aceastaidee vom da doua semantici pentru expresiile definite mai sus.

Prima semantica va da scrierea poloneza inversa pentru expresii. A doua semantica va fi data nsectiunea urmatoare.

Algebra semantica va avea toate suporturile egale cu semigrupul liber generat de {x, y, z,+, }.Operatiile sunt urmatoarele:

0 = 4 = 5 = 6 = 8 sunt aplicatia identitate,

1 = x, 2 = y si 3 = z,

7(, ) = + si 9(, ) = .

Aplicand morfismul semantic arborelui A obtinem xyxy+z**+z+.

3 Compilare

Un compilator care va produce un program pentru evaluarea expresiilor si tiparirea rezultatului evalariiva fi modelat printr-un morfism.

Vom pune n evidenta elementele care apar n programele obtinute prin compilare. R este un registrudin memorie. P este un pointer catre primul loc liber al stivei utilizate n timpul evaluarii.

Presupunem ca limbajul de asamblare include urmatoarele instructiuni:

inc P operator de incrementare a pozitiei primului loc liber din stivadec P operator de decrementare a pozitiei primului loc liber din stivaAd R aduna valoarea din varful stivei prin continutul lui R si depune rezultatul n RMu R inmulteste valoarea din varful stivei prin continutul lui R si depune rezultatul n Rld R valoarea din varful stivei este depusa n Rst R valoarea din R este depusa n varful stiveiprint tipareste valoarea din varful stivei

Semantica unei expresii va fi programul care evalueaza expresia si imprima rezultatul evaluarii. Pentrudefinirea acesteia se va folosi metoda semanticii algebrei initiale.

Toate cele 5 suporturi ale algebrei semantice, corespunzatoare neterminalelor, sunt identice si coincidcu multimea bucatilor de program(siruri de instructiuni separate prin ;). Astfel de bucati de programevorfi notete cu litere grecesti.

Cele 10 operatii ale algebrei semantice, corespunzatoare productiilor sunt:

1S = st x ; inc P2S = st y ; inc P3S = st z ; inc P4S() = 5S() = 6S() = 7S(,) = ; ; dec P ; ld R ; dec P ; Mu R ; st R ; inc P8S() = 9S(,) = ; ; dec P ; ld R ; dec P ; Ad R ; st R ; inc P0S() = ; dec P ; print

Notam cu S algebra semantica de mai sus, cu A algebra arborilor de derivare si cu C : A S uniculmorfism de algebre existent. Morfismul C este modelarea algebrica a compilatorului.

4

Conform metodei semanticii algebrei initiale rezulta ca C(A) este programul care evalueaza si tiparesterezultatul pentru expresia x+ y (x+ y) z + z.

3.1 Program

Prezentam calculele care dovedesc afirmatia de mai sus.

C(a) = 8S(6S [4S(1S)]) = 1S si C(b) = 6S(4S(3S)) = 3S

Notand c = 7[ 5{9(a,6[4(2)])},b ]C(c) = 7S [ 5S{9S(1S ,6S [4S(2S)])},3S ] = 7S [ 9S(1S ,2S),3S ] =

9S(1S ,2S),3S ; dec P ; ld R ; dec P ; Mu R ; st R ; inc P =1S ; 2S ; dec P ; ld R ; dec P ; Ad R ; st R ; inc P ; 3S ; dec P ; ld R ; dec P ; Mu R ; st R ; inc P =

st x ; inc P; st y ; inc P ; dec P ; ld R ; dec P ; Ad R ; st R ; inc P ; st z ; inc P; dec P ; ld R ; dec P ;Mu R ; st R ; inc P

Deoarece A = 0(9[9{a, 7(4[2], c) },b]) deducemC(A) = 0S(9S [9S{1S , 7S(2S ,C(c)) },3S ]) = 0S(9S [9S{1S , 7S(2S ,C(c)) },3S ]) =9S [9S{1S , 7S(2S ,C(c)) },3S ] ; dec P ; print =9S{1S , 7S(2S ,C(c)) } ; 3S ; dec P ; ld R ; dec P ; Ad R ; st R ; inc P ; dec P ; print =1S ; 7S(2S ,C(c)) ; dec P ; ld R ; dec P ; Ad R ; st R ; inc P ; 3S ; dec P ; ld R ; dec P ; Ad R ; st R ;

inc P ; dec P ; print =1S ; 2S ; C(c) ; dec P ; ld R ; dec P ; Mu R ; st R ; inc P ; dec P ; ld R ; dec P ; Ad R ; st R ; inc P ;

3S ; dec P ; ld R ; dec P ; Ad R ; st R ; inc P ; dec P ; print =

st x ; inc P ; st y ; inc P ; st x ; inc P ; st y ; inc P ; dec P ; ld R ; dec P ; Ad R ; st R ; inc P ; st z ;inc P ; dec P ; ld R ; dec P ; Mu R ; st R ; inc P ; dec P ; ld R ; dec P ; Mu R ; st R ; inc P ; dec P ; ld R; dec P ; Ad R ; st R ; inc P ; st z ; inc P ; dec P ; ld R ; dec P ; Ad R ; st R ; inc P ; dec P ; print

3.2 Optimizare cod

Se obsrva ca programul de mai sus poate fi simplificat. Eliminand instructiunile inc P ; dec P alcaror efect cumulat este nul obtinem programul

st x ; inc P ; st y ; inc P ; st x ; inc P; st y ; ld R ; dec P ; Ad R ; st R ; inc P ; st z ; ld R ; dec P ;Mu R ; st R ; ld R ; dec P ; Mu R ; st R ; ld R ; dec P ; Ad R ; st R ; inc P ; st z ; ld R ; dec P ; Ad R ;st R ; print

Mai observam ca grupul de instructiuni st R ; ld R ; dec P are acelasi efect ca instruciunea dec Pceea ce conduce la programul

st x ; inc P ; st y ; inc P ; st x ; inc P; st y ; ld R ; dec P ; Ad R ; st R ; inc P ; st z ; ld R ; dec P ;Mu R ; dec P ; Mu R ; dec P ; Ad R ; st R ; inc P ; st z ; ld R ; dec P ; Ad R ; st R ; print

5

7 ALGEBRE CAT si ALGEBRE PROIECTIVE


May 24, 2008

Daca f : A B este o functie se numeste echivalenta nucleara a lui f , sau mai pe scurt nucleul lui f

Ker(f) = {(a, b) AA : f(a) = f(b)}.

Echivalenta nucleara a unei functii este o relatie de echivalenta. In cazul multisortat nucleul este luat pe compo-nente, adica pentru fiecare sort n parte.

1 Congruente

O relatie de echivalenta ntr-o -algebra (As, A) este de fapt o familie de relatii de echivalente, cate una pentrufiecare multime As. O congruenta este o relatie de echivalenta care este compatibila cu operatiile algebrei. De faptcompatibilatea trebuie ceruta numai pentru operatiile cu argumente caci pentru o constanta A A rezulta dinreflexivitate.

Definitia 1.1 O congruenta n -algebra (As, A) este o relatie de echivalenta cu proprietatea pentru orices1s2 . . . sn S, pentru orice s S, pentru orice s1s2...sn,s, daca ai bi n Asi pentru orice 1 i n, atunci

A(a1, a2, . . . an) A(b1, b2, . . . , bn).

Cea mai mica congruenta este relatia de egalitate. Cea mai mare congruenta este relatia totala.

Propozitie 1.2 Daca h : A B este un -morfism, atunci Ker(h) este o congruenta.

Demonstratie: Fie s1s2 . . . sn S, s S si s1s2...sn,s. Presupunem ca ai Ker(hsi) bi n Asi pentru orice1 i n. Rezulta ca hsi(ai) = hsi(bi) pentru orice 1 i n. Prin urmare

hs(A(a1, a2, . . . , an)) = B(hs1(a1), hs2(a2), . . . , hsn(an)) = B(hs1(b1), hs2(b2), . . . , hsn(bn)) = hs(A(b1, b2, . . . , bn))

prin urmare A(a1, a2, . . . , an) Ker(hs) A(b1, b2, . . . , bn) deci Ker(h) este congruenta.

Propozitie 1.3 Orice intersectie de congruente este tot o congruenta.

Demonstratie: Fie {k}kK o multime de congruente si

=kK

k .

Probam ca este congruenta.Fie s1s2 . . . sn S, fie s S, fie s1s2...sn,s si ai bi n Asi pentru orice 1 i n.Pentru orice k K deoarece k este congruenta, fiindca ai k bi n Asi pentru orice 1 i n deducem

A(a1, a2, . . . an) k A(b1, b2, . . . , bn).

Deci

A(a1, a2, . . . an) A(b1, b2, . . . , bn).

Aceasta propozitie ne spune ca multimea congruentelor unei algebre este o familie Moore. Incercati sa caracterizatioperatorul de nchidere asociat.

1

1.1 Congruente de grupuri

Grupurile sunt privite ca algebre cu trei operatii: una binara , una unara * si o constanta e. Doua conditii seimpun pentru conceptul de congruenta

1. a b si c d implica a c b d,

2. a b implica a b.

Practic ramane numai una deoarece a doua conditie este o consecinta a primeia: folosind reflexivitatea din a a,a b si b b deducem a a b a b b, prin urmare b a, deci a b.

Propozitie 1.4 In orice grup conceptul de congruenta este echivalent cu cel de subgrup normal

Demonstratie:

1 Data o congruenta clasa elementului neutru este un subgrup normal.2 Dat un subgrup normal N relatia definita prin

a b daca si numai daca a b N

este o congruenta. 2

Conceptul de parte stabila coincide cu cel de subgrup.Conceptul de morfism de -algebra coincide cu cel de morfism de grup.

1.2 Congruente de inele

Pentru simplicitate vom prefera cazul comutativ.Signatura conceptului de inel contine pe langa cele trei operatii corespunzatoare grupurilor nca doua simboluri

de aritate 2, respectiv 0 corespunzatoare structurii monoidului multiplicativ. Avand n vedere cazul grupurilor estesuficient sa punem conditia de congruenta numai pentru cele doua operatii binare.

Propozitie 1.5 In orice inel comutativ conceptul de congruenta este echivalent cu cel de ideal.

Demonstratie:

1 Data o congruenta clasa elementului neutru este un ideal.2 Dat un ideal N relatia definita prin

a b daca si numai daca a b N

este o congruenta. 2

Conceptul de parte stabila coincide cu cel de subinel.Conceptul de morfism de -algebra coincide cu cel de morfism de inel.

1.3 Concluzie

Conceptul de congruenta este cel important. Este un fapt ntamplator ca pentru anumite structuri algebricecongruentele pot fi caracterizate de unele substructuri particulare.

2

2 Algebre cat

Proprietatea de universalitate a multimii cat. Fie o relatie de echivalenta n multimea A. Fie A/ multimeacat si : A A/ surjectia naturala de factorizare. Pentru orice functie f : A B daca Ker(f), atunciexista o unica functie f# : A/ B cu proprietatea ; f# = f. 2

Fie (As, A) o -algebra si o congruenta. Definim operatiile algebrei cat

A/= ({As/}sS, A/)

pentru orice s1s2 . . . sn S, s S, s1s2...sn,s si ai Asi pentru orice 1 i n prin

A/ (a1, a2, . . . , an) = A(a1, a2, . . . , an).Teorema 2.1 Proprietatea de universalitate a algebrei cat. Pentru orice morfism de -algebre f : A Bdaca Ker(f), atunci exista un unic morfism de -algebre f# : A/ B cu proprietatea ; f# = f.

Demonstratie: Din proprietatea de universalitate a multimii cat deducem existenta unei unice functiif# : A/ B cu proprietatea ; f# = f. Observam ca f#s (a) = fs(a) pentru orice s S si a As. Maitrebuie sa demonstram ca functia f# este un morfism de -algebre.

Fie s1s2 . . . sn S, s S, s1s2...sn,s si ai Asi pentru orice 1 i n. Observam ca

f#s (A/ (a1, a2, . . . , an)) = f#s (

A(a1, a2, . . . , an)) = fs(A(a1, a2, . . . , an)) = B(fs1(a1), fs2(a2), . . . , fsn(an)) =B(f

#s1(a1), f

#s2(a2), . . . , f

#sn(an)).

Deci f# este morfism de -algebre. 2

Sa se arate ca pentru orice -morfism h : A B algebrele A/Ker(h) si h(A) sunt izomorfe.

3 Algebre proiective

Fie (S,) o signatura multisortata. Vom lucra n categoria -algebrelor Alg. Pentru simplicitate vom scrie pescurt algebra si morfism n loc de -algebra si respectiv morfism de -algebre.

Cei care nu sunt interesati de toate detaliile pot sari peste propozitia urmatoare dar n continuare pot lua dreptdefinitie pentru -algebre: epimorfism = morfism cu toate componentele surjective.

Intr-o categorie, un morfism e : A B se numeste epimorfism daca pentru orice pereche de morfisme f : B Csi g : B C daca e; f = e; g, atunci f = g.

Propozitie 3.1 Fie A si B doua (S,)-algebre si h : A B un (S,)-morfism. Morfismul h este epimorfism nA daca si numai daca hs este surjectiv pentru orice s S.

Demonstratie: Fie A = ({As}sS, {A}) si B = ({Bs}sS , {B}).() Fie C o (S,)-algebra sim, n : B C doua morfisme astfel ncat h;m = h;n. Rezulta ca hs;ms = hs;ns pentruorice s S. Deoarece pentru orice s S, hs este surjectiv rezulta ca hs este epimorfism n categoria multimilor, decims = ns. Am demonstrat ca m = n.() Fie C = {Cs}sS o multime S-sortata, cu Cs = Bs (Bs hs(As)) pentru orice s S. Simbolul indica oreuniune disjuncta de multimi.

Fie : B C functia incluziune de multimi S-sortate si r : B C definit prin

rs(b) =

{b, daca b hs(As)b daca b Bs hs(As)

pentru orice s S si b Bs (pentru b Bs hs(As) am notat cu b elementul care i corespunde n Cs).In continuare vom defini pe C o structura de (S,)-algebra astfel ncat si r sa devina morfisme de (S,)-algebre.Fie s1sn,s. Definim:

1) C(b1, . . . , bn) = B(b1, . . . , bn) daca bi Bsi pentru orice i [n];2) C(rs1(b1), . . . , rsn(bn)) = rs(B(b1, . . . , bn)) daca bi Bsi pentru orice i [n];3) n celelalte situatii operatia C poate fi definita oricum.

3

Sa demonstram ca definitia de mai sus nu este contradictorie.Fie b1 Bs1, . . ., bn Bsn astfel ncat rsi(bi) = bi Bsi pentru orice i [n]. Atunci bsi hsi(Asi) de unde

rezulta ca B(b1, . . . , bn) hs(As) si deci B(b1, . . . , bn) = rs(B(b1, . . . , bn)).Din 1) rezulta ca este morfism iar din 2) rezulta ca r este morfism.Am definit astfel o (S,)-algebra C = ({Cs}sS , {C}) si doua morfisme , r : B C. Se observa ca h = hr

deoarece pe h(A) cele doua morfisme actioneaza la fel. Deoarece h este epimorfism rezulta ca = r de unde obtinemBs = hs(As) pentru orice s S (daca exista s S astfel ncat Bs hs(As) 6= atunci exista b Bs hs(As) si(b) = b, r(b) = b deci 6= r ceea ce contrazice faptul ca h este epimorfism). Am demonstrat ca hs este surjectiepentru orice s S. 2

Intr-o categorie, un obiect P se numeste proiectiv daca pentru orice epimorfism e : A B si pentru oricemorfism f : P B exista un morfism g : P A astfel ncat g;e = f.

Propozitie 3.2 In Alg orice algebra libera este proiectiva.

Demonstratie: Fie A, B doua (S,)-algebre si X o multime S-sortata de variabile. Daca e : A B este unmorfism cu toate componentele surjective si f : T(X) B este un morfism oarecare trebuie sa demonstram caexista un morfism g : T(X) A astfel ncat g; e = f .

Pentru a defini morfismul g este suficient sa dam actiunea lui pe variabile.Fie s S si x Xs. Deoarece es este surjectiv, deci exista ax As astfel ncat fs(x) = es(ax). Definim g ca

fiind unicul morfism cu proprietatea ca gs(x) = ax pentru orice s S si pentru orice x Xs. Este evident faptul ca(g; e)s(x) = fs(x) pentru orice s S si orice x Xs. Deoarece morfismele g; e si f coincid pe generatorii algebreilibere T(X) rezulta ca g; e = f si demonstratia este ncheiata. 2

Comentariu. Faptul ca gs(x) poate fi ales arbitrar n e1s ({fs(x)}) nu garanteaza unicitatea lui g. 2

Lema 3.3 Orice subalgebra a unei algebre libere este algebra libera.

Demonstratie: Intr-o algebra definim relatia

a b daca si numai daca a = (. . . , b, . . .).

Observam ca n orice algebra libera relatia este noetheriana.Fie P o subalgebra a unei algebre libere L. Relatia este noetheriana si n subalgebra P .Fie X multimea tuturor elementelor din P care nu sunt rezultatul aplicarii vreunei operatii din P unor elemente

din P . Vom dovedi ca X, subalgebra generata de X , este chiar P . Presupunem prin absurd ca exista p0 P X.Deoarece p0 6 X el este rezultatul aplicarii cel putin al unei operatii. In plus cel putin unul dintre argumenteleacestei operatii nu este din X deoarece n caz contrar obtinem contradictia p0 X. Prin urmare exista p1 P Xastfel ncat p0 p1. Continuand rationamentul prin inductie ar rezulta ca relatia nu este noetheriana n P , ocontradictie.

Observam ca P este algebra Peano peste X . Chiar din definitia lui X rezulta ca rezultatul aplicarii unei operatiidin P unor elemente din P nu este n X . Ultima conditie din definitia algebrelor Peano este adevarata n P deoareceeste adevarata n L.

Deci P este liber generata de X deoarece este Peano peste X .

Propozitie 3.4 In Alg orice algebra proiectiva este libera.

Demonstratie: Fie P o algebra proiectiva. Fie : T(P ) P unicul morfism a carui restrictie la P este 1P ,identitatea lui P . Evident este epimorfism.

Deoarece P este o algebra proiectiva exista un morfism g : P T(P ) cu proprietatea g; = 1P . Obserevamca g este o injectie. Prin urmare algebra P este izomorfa cu subalgebra g(P ) a lui T(P ).

Algebra g(P ) este libera deoarece este subalgebra a unei algebre libere.Algebra P este libera deoarece este izomorfa cu o algebra libera.

4

8 SPRE ABSTRACTIZAREA TIPURILOR DE DATE


March 22, 2008

1 Ecuatii

Sa analizam conceptul de axioma asa cum apare el n algebra. De exemplu comutativitatea si asociativitatea se scriu

(xy)x?y = y?x (xyz)x?(y?z) = (x?y)?z.

Ce sunt acestea? Sunt egalitati de doua expresii cuantificate universal prin multimea variabilelor continute n celedoua expresii. Deci o astfel de axioma are forma

(X)l.= r

unde l si r sunt din algebra liber generata de multimea X de variabile.Ce nseamna ca o axioma este adevarata ntr-o algebra D? Intuitiv este necesar ca rezultatul evaluarii celor doua

expresii l si r n algebra D sa fie acelasi indiferent de valorile date n D variabilelor din X . Aceasta idee intuitivaconduce la:

Definitia 1.1 Axioma (X)l.= r este satisfacuta n algebra D daca si numai daca pentru orice morfism

h : T(X) D este adevarata egalitatea h(l) = h(r).

In continuare vom folosi pentru (X)l.= r termenul de ecuatie n locul celui de axioma, pentru a ne conforma cu

terminologia internationala.In plus vor intra n joc si asa zisele ecuatii conditionate. De exemplu

(xyz)(x y = x z y = z)

ceea ce corespunde axiomei de simplificare la stanga care este adevarata n orice grup sau n orice monoid liber.

2 Ecuatii conditionate

In logica ecuationala o axioma este o implicatie

a1 = c1, a2 = c2, . . . , an = cn a = c

unde ipoteza este o conjunctie de egalitati formale si concluzia o egalitate formala. Toata implicatia este cuantificatauniversal, fapt care nu apare scris mai sus. In acest cadru o axioma, numita n continuare si ecuatie conditionata alogicii ecuationale, poate fi scrisa sub forma

(X) a.=s c if H

unde a si c sunt elemente de acelasi sort s, iar H este o multime finita de egalitati formale din algebra liber generatade multimea X de variabile. Ipoteza implicatiei este data de multimea H .

Pentru a verifica daca o algebra D satisface axioma de mai sus se dau valori arbitrare variabilelor din X n D faptce poate fi facut printr-o functie arbitrara f : X D sau echivalent printr-un morfism arbitrar h : T(X) D.Apoi se evalueaza expresiile din H pentru a se verifica daca rezultatul evaluarii conduce la egalitati adevarate, cazn care trebuie ca hs(a) = hs(c). Deci -algebra D satisface ecuatia conditionata (X)a

.=s c if H fapt notat prin

D |= (X) a.=s c if H

daca si numai daca

(h : T(X) D) (u =t v H)ht(u) = ht(v) implica hs(a) = hs(c).

Credem ca este bine sa mentionam diferenta esentiala ntre semnele.=s si =, diferenta care va fi mentinuta constant

pe parcursul ntregului text. Egalul peste care s-a pus un punct (.=s) indica o egalitate formala care poate fi adevarata

sau falsa. Egalul = are semnificatia uzuala indicand deobicei o egalitate adevarata.

1

3 Necesitatea utilizarii cuantificatorilor n ecuatii

Vom ilustra printr-un exemplu necesitatea utilizarii cuantificatorilor n ecuatiile logiciiecuationale multisortate.

Fie signatura S = {a, bool} si = {g, F, T }. Rangurile simbolurilor de operatii sunt date prin desenul urmator :

a bool- g F

T

.

Vom lucra cu doua algebre.algebra initiala este I = (, {F, T }, Ig, IF , IT ) unde F 6= T , IF = F , IT = T si Ig : {F, T } este functia

incluziune.Pentru orice variabila x de sort a, -algebra liber generata de aceasta variabila T({x}, ) are suporturile {x} si

{g(x),F,T}.Are loc relatia I |= F = T ? Sau mai intuitiv: este egalitatea F = T adevarata n algebra I? Vom arata ca

raspunsul depinde de algebra libera n care este scrisa egalitatea.Sunt posibile cel putin doua variante.

1. I |= ()T = F h : I I morfism, hbool(F ) = hbool(T ),ceea ce este fals deoarece hbool(F ) = F 6= T = hbool(T ).

2. I |= (x)T = F h : T({x}, ) I morfism, hbool(F ) = hbool(T ),ceea ce este adevarat deoarece nu exista nici un morfism h : T({x}, ) I.

Am aratat ca I |= ()T = F este falsa si ca I |= (x)T = F este adevarata. Daca omitem cuantificatoriiobtinem: I |= T = F este falsa si I |= T = F este adevarata.

Contradictia obtinuta prin omiterea cuantificatorilor din fata egalitatii F = T arata ca n logica ecuationalamultisortata prezenta cuantificatorilor n ecuatii este necesara.

4 In primul rand semantica

Pentru orice algebra D = (Ds, D) notam cu

Sen(D) = {a.=s c : s S, a, c Ds}

multimea propozitiilor sale. Propozitiile sunt de fapt egalitati formale care pot fi adevarate sau false.Sa observam ca Sen(D) se poate identifica cu produsul cartezian DD. Poate cea mai buna reprezentare a unei

propozitii din D este un triplet format dintr-un sort s si doua elemente de sort s din D.

Definitia 4.1 O ecuatie conditionata este(X)l

.=s r if H

unde X este o multime S-sortata de variabile, l si r sunt doua elemente de sort s din T(X) iar H o multime finitade egalitati formale din T(X). 2

O ecuatie conditionata n care H = devine neconditionata si este numita pe scurt ecuatie. In acest caz scriem doar(X)l

.=s r n loc de (X)l

.=s r if .

Definitia 4.2 Algebra D satisface ecuatia conditionata (X)l.=s r if H , fapt notat prin

D |= (X)l.=s r if H

daca pentru orice morfism h : T(X) D pentru care hs(u) = hs(v) pentru orice u.=s v H , avem hs(l) = hs(r).

2

In cele ce urmeaza indicele din |= va fi omis. El va fi mentionat atunci cand este pericol de confuzie.Observam ca D |= (X)l

.=s r daca si numai daca hs(l) = hs(r) pentru orice morfism h : T(X) D.

In continuare fixam o multime de ecuatii conditionate, numite axiome.

Definitia 4.3 Spunem ca algebra D satisface sau ca D e o -algebra si scriem D |= daca D satisface toateecuatiile conditionate din .

Un morfism de -algebre ntre doua -algebre se numeste morfism de -algebre sau mai scurt -morfism. 2

2

5 Punctul de vedere local

Fixam o algebra A si lucram cu propozitii din Sen(A). Acesta este punctul local de vedere al logicii ecuationale.Cazul n care ne intereseaza propozitii din algebre diferite este numit global dar va fi putin folosit n acest curs. Incazul global o propozitie din D va fi scrisa (D)a

.=s c n loc de a

.=s c. Notatia fara cuantificatori folosita n cazul

local nu contrazice ceea ce am scris despre necesitatea utilizarii cuantificatorilor n ecuatii. Pur si simplu nu scriemcuantificatorul pentru ca fixand algebra A el va fi mereu acelasi (A) si deci l stim chiar daca nu-l vedem scris.

O alta idee pe care dorim sa o subliniem este folosirea unei algebre arbitrare A n locul unei algebre libere.Principalele rezultate privind rescrierile, care se refera atat la rescrierile de termeni cat si la rescrierile moduloecuatii, raman valabile n acest cadru mai general. Aceasta prezentare unitara a diverselor tipuri de rescriere estede fapt contributia autorului la modernizarea lectiilor despre rescriere. Exista n lume trei carti privind rescrieriile.Cea mai veche este Term Rewriting and All That, scrisa de Franz Baader si Tobias Nipkow.

Mentionam ca algebra A nu are legatura cu algebra T(X) folosita n vreo axioma (X)l =s r if H din .Mentionam si ca n axiome diferite putem folosi algebre libere diferite. Aceasta corespunde cazului practic, deexemplu scriem comutativitatea xy = yx ntr-o algebra libera cu doi generatori x si y iar asociativitatea (xy)z = x(yz)ntr-o algebra libera cu trei generatori x, y si z.

6 Semantica si Corectitudine

Vom lucra ntr-o -algebra A. Vom grupa ntr-o relatie toate tautologiile(propozitiile valide) din algebra ale logiciiecuationale.

Fie A relatia pe A definita prin

a A c daca si numai daca (h : A M |= )hs(a) = hs(c).

Daca nu exista pericol de confuzie vom prefera sa scriem n loc de A .Observam ca

={Ker(h) | h : A M |= }.

Deoarece nucleul unui morfism este o relatie de congruenta si deoarece orice intersectie de relatii de congruente esteo relatie de congruenta, deducem ca este o relatie de congruenta.

este numita congruenta semantica.

Definim regula de deductie a substitutiei utilizata atat n logica ecuationala cat si n rescrierea termenilor.

Sub Pentru orice (X) l.=s r if H si orice morfism h : T(X) A

(u.=s v H)hs(u)

.=s hs(v) implica hs(l)

.=s hs(r).

Lema 6.1 Pentru orice morfism f : A M |= , Ker(f) este nchis la Sub.

Demonstratie: Fie (X)l.=s r if H n si h : T(X) A un morfism cu proprietatea ca ht(u) Ker(f) ht(v)

pentru orice u.=t v H . Prin urmare (h; f)t(u) = (h; f)t(v) pentru orice u

.= v H . Deoarece

h; f : T(X) M |= rezulta ca (h; f)s(l) = (h; f)s(r), deci hs(l) Ker(f) hs(r).2

Propozitie 6.2 Congruenta semantica este nchisa la substitutie.

Demonstratie: Congruenta semantica este o intersectie de congruente nchise la substitutie. Deoarece o intersectiede congruente nchise la substitutii este o congruenta nchisa la substitutii rezulta ca este o congruenta nchisala substitutie. 2

Propozitie 6.3 Daca este o congruenta nchisa la substitutii, atunci A/ |= .

Demonstratie: Notam cu : A A/ morfismul de factorizare canonic.Fie (X)l

.=s r if H n si h : T(X) A/ un morfism astfel ncat ht(u) = ht(v) pentru orice u

.=t v H .

Cum T(X) este algebra proiectiva exista un morfism f : T(X) A astfel ncat f ; = h. Pentru orice u.=t v H

deoarece t(ft(u)) = t(ft(v)) deducem ft(u) ft(v).Deoarece este o congruenta nchisa la substitutii obtinem fs(l) fs(r). Prin urmare s(fs(l)) = s(fs(r)), de

unde hs(l) = hs(r). 2

Fie A factorizarea lui A prin congruenta si fie : A A morfismul cat.

3

Teorema 6.4 A |=

Demonstratie: Se aplica propozitiile 6.2 si 6.3. 2

Teorema 6.5 Pentru orice -algebra B si pentru orice morfism h : A B exista si este unic un morfismh# : A B astfel ncat ;h# = h.

Demonstratie: Este suficient sa aratam ca a c implica h(a) = h(c) si aplicam proprietatea de universalitate aalgebrei cat. Intr-adevar a c implica h(a) = h(c) deoarece h : A B |= . 2

Corolar 6.6 Daca A este -algebra initiala, atunci A este -algebra initiala.

Corolar 6.7 Pentru orice signatura si pentru orice multime de ecuatii conditionate exista o -algebra initiala.

Propozitie 6.8 Fie h : A B un morfism. Daca a A c, atunci h(a) B h(c).

Demonstratie: Fie f : B C |= . Din a A c folosind morfismul h; f : A C |= deducem (h; f)(a) =(h; f)(c), prin urmare f(h(a)) = f(h(c)). Deci h(a) B h(c).

7 Problema programarii prin rescriere

Principala problema este : poate o masina sa demonstreze ca a c?.Se stie ca n unele cazuri rescrierile ne dau o solutie.

8 Tipuri abstracte de date

Am vazut n lectiile precedente ca orice signatura determina prin algebra sa initiala un tip abstract de date. Tipulabstract de date al numerelor naturale a fost determinat de signatura formata din constanta 0 si operatia unaracunoscuta sub numele de succesor.

Acum am pus n evidenta un instrument mai puternic deoarece orice signatura mpreuna cu o multime deecuatii conditionate determina prin -algebra initiala, a carei existenta am dovedit-o mai sus, un tip abstract dedate.

8.1 Tipul abstract al numerelor naturale - continuare

Consideram signatura cu un singur sort nat, o singura constanta de sort nat si o singura operatie unara cu argumentsi rezultat de sort nat:

sort nat .op 0 : nat .op s : nat nat .

Elementele algebrei initiale sunt

0, s(0), s(s(0)), s(s(s(0))), s(s(s(s(0)))), ...

si ele reprezinta numerele naturale 0 1 2 3 4 ...

Propozitie 8.1 Algebra (N, 0N , sN ) definita prin: N este multimea numerelor naturale, 0N este numarul naturalzero si sN (n) = n+ 1 pentru orice numar natural n; este initiala.

Propozitia anterioara ne arata cum pot fi definite numerele naturale prim metoda algebrei initiale ca tip abstractde date.

Deocamdata prin signatura de mai sus calculatorul nvata numerele naturale dar nu stie nca sa calculeze. Sa-lnvatam sa adune si sa nmulteasca. La cele de mai sus adaugam.

op + : nat nat nat .var X Y : nat .eq X + 0 = 0 .

4

eq X + s(Y) = s(X+Y) .op * : nat nat nat .eq X * 0 = 0 .eq X * s(Y) = X*Y + X .

Trebuie sa mentionam ca egalitatiile de mai sus sunt folosite n doua moduri:a) ca ecuatii care mpreuna cu signatura de patru operatii formeaza o multime pentru a defini o structura

algebrica sib) ca reguli de rescriere n timpul executiei programelor.

Propozitie 8.2 Algebra N = (N, 0N , sN ,+N , N) este -algebra initiala.

Demonstratie: Fie A = (A,OA, sA,+A, A) o -algebra. Mentionam ca algebra A satisfac ecuatiile din , adica

1) a+A 0A = a pentru orice a din A,2) a+A sA(b) = sA(a+ b) pentru orice a, b din A,3) a A 0A = 0A pentru orice a din A,4) a A sA(b) = a A b+A a pentru orice a, b din A.

Vom proba ca exista un unic morfism de -algebre de la N la A.Sa ncepem cu unicitatea. Daca h : N A este un -morfism, atunci h : (N, 0N , sN ) (A, 0A, sA) este

morfism prin urmare coincide cu unicul morfism dat de propozitia de mai sus.Pentru a demonstra existenta nu avem decat o singura sansa si anume sa dovedim ca unicul morfism

h : (N, 0N , sN ) (A, 0A, sA) este si morfism de -algebre. Reamintim ca

h(0N ) = 0A si pentru orice n numar natural h(n+ 1) = sA(h(n)).

Probam ca h(n+N m) = h(n) +A h(m) prin inductie dupa m

h(n+N 0N) = h(n) = h(n) +A 0A = h(n) +A h(0N ) sih(n+N (m+1)) = h(sN (n+Nm)) = sA(h(n+Nm)) = sA(h(n)+Ah(m)) = h(n)+AsA(h(m)) = h(n)+Ah(m+1).

Probam ca h(n N m) = h(n) A h(m) prin inductie dupa m

h(n N 0N) = h(0N ) = 0A = h(n) A 0A = h(n) A h(0N ) sih(n N (m + 1)) = h(n N m +N n) = h(n N m) +A h(n) = (h(n) A h(m)) +A h(n) = h(n) A sA(h(m)) =

h(n) A h(m+ 1). 2

Propozitia anterioara demonstreaza corectitudinea definitiei de mai sus. Deoarece algebra N este initiala rezultaca ea este izomorfa cu -algebra initiala, deci specificatia de mai sus caracterizeaza prin -algebra sa initiala tipulde date al numerelor naturale.

5

2 LOGICA ECUATIONALA MULTISORTATA


April 26, 2008

Fie o multime de ecuatii conditionale si o -algebra A fixata.Multimea propozitiilor adevarate, tautologiile, din A este chiar congruenta semantica

= {a.=s b Sen(A) : (M |= )(f : A M)fs(a) = fs(b)}.

Conform traditiei mai scriem|= a

.=s b daca si numai daca a b

Cautam o multime corecta si completa de reguli de deductie pentru A.

1 Reguli de deductie, corectitudine

Definim prin RE multimea urmatoarelor reguli de deductie pentru logica ecuationala multisortata:

R a.=s a

S a.=s b implica b

.=s a

T a.=s b si b

.=s c implica a

.=s c

C Pentru orice s1s2...sn,s: ai.=si bi pentru 1 i n

implica A(a1, a2, . . . , an).=s A(b1, b2, . . . , bn).

Sub Pentru orice (X) l.=s r if H si pentru orice h : T(X) A

ht(u).=t ht(v) pentru orice u

.=t v H implica hs(l)

.=s hs(r)

Conform traditiei notam prin a.=s b faptul ca egalitatea formala a

.=s b este demonstrabila cu regulile de mai sus.

Observatia 1.1 Observam ca o multime de egalitati formale este nchisa la regula T daca si numai daca este o

relatie tranzitiva.

Mai observam ca astfel de observatii pot fi facute pentru oricare din regulile de mai sus.

Teorema 1.2 Regulile de deductie RE sunt corecte pentru .

Demonstratie: Deoarece este congruenta rezulta ea este nchisa la primele patru reguli, prin urmare ele suntcorecte pentru . Corectitudinea ultimei reguli rezulta din nchiderea congruentei semantice la substitutii. 2

Corolar 1.3 a.=s b implica |= a

.=s b. 2

Demonstratie: Deoarece congruenta semantica este nchisa laRE si deoarece multimea egalitatilor formale demon-strabile este cea mai mica multime nchisa la RE.

2 Completitudine

Pentru orice s S si a, b As se defineste relatia in A prin:

a b a.=s b.

Deoarece regulile R, S si T sunt n RE deducem ca este o echivalenta. Mai mult, deoarece C este n RE rezultaca este congruenta.

Fie A catul lui A prin si fie A : A A -morfismul canonic de factorizare. Deoarece este nchisa lasubstitutii rezulta:

1

Observatia 2.1 A |=

Teorema 2.2 Teorema de completitudine: |= a.=s b implica a

.=s b.

Demonstratie: Fie |= a.=s b. Din definitia tautologiilor deducem (h : A B |=) hs(a) = hs(b). Intrucat

A |= si A : A A este -morfism rezulta ca A(a) = A(b). Prin urmare a b, deci a.=s b. 2

In concluzie congruentele si coincid. Prin urmare algebra A si morfismul A coincid cu cele introdusentr-un mod numai aparent diferit n lectia precedenta. Proprietatea de universalitate a algebrei A demonstrataatunci ramane adevarata si n noul context.

Urmatorul pas dupa o teorema de completitudine care ne asigura existenta unei demonstratii pentru orice tautolo-gie este de a gasi aceste demonstratii. Informaticienii sunt ceva mai pretentiosi deoarece doresc ca acete demonstratiisa fie gasite de un calculator.

2

3 RESCRIERE LOCALA

VEC

May 26, 2008

Rescrierile sunt un fapt pe care-l ntalnim din primii ani de scoala. De exemplu n sirul de egalitati

2 (3 + 4) = 2 7 = 14

facem doua rescrieri(nlocuiri): 3+4 esre rescris n 7 si apoi 2*7 este rescris n 14. Aceste rescrieri sunt permise deregulile adunarii si nmultirii. Partea expresiei care ramane neschimbata deoarece rescrierea are loc n interiorul eise numeste context. La prima rescriere contextul este 2 z, unde z este un semn special care arata locul n care seface rescrierea. Deoarece a doua rescriere se face la varf contextul este z.

De obicei rescrierile se fac de la expresii mai complicate spre expresii mai simple. Rescrierea lui 3+4 n 7 esteceva firesc, pe cand rescrierea lui 7 n 3+4 este ceva artificial. Dece 3+4 si nu 2+5? Prin urmare spre deosebire deegalitate care este simetrica, rescrierea nu este simetrica.

Deoarece se doreste ca rescrierile sa fie facute de calculator, practica programarii ne da un argument foarteputernic mpotriva simetriei. Simetria este o regula care conduce la neterminarea programelor, deoarece dupa ce amrescris a n b putem rescrie pe b n a, pe a n b si asa mai departe.

Eliminarea simetriei dintre regulile de deductie este principala diferenta dintre calculul cu egalitati reflectat delogica ecuationala. Deoarece eliminarea simetriei duce la pierderea completitudinii, simetria va trebui nlocuita cualtceva pentru a reobtine completitudinea.

1 Preliminarii

Signatura , multimea de axiome si algebra A n care se fac rescrieri

Cazanescu Curs Programare Declarativa Si Logica (1)

Documents

Transcript of Cazanescu Curs Programare Declarativa Si Logica (1)