Programare Logica Explicatii

7/22/2019 Programare Logica Explicatii

1/6

Definitia 1.1.1. : M = {M[s]} cu s apartinand lui S multime S-sortata. Multimea S este multimea sorturilor, adica a tipurilor. De exemplu, S ar putea sa fie: S = {Int , Float, String} iar multimea M sa fie de forma M = { {1,5,7,213} , {4.3 , 7 , 9.21 } , {"abc" , "7" , "rtvf" , "a" } } M[s] ar putea fi, in acest caz, M[Int] sau M[Float] sau M[String].

Daca N = { {1,6,3} , {5.1} , {"7" , "ert"} } , atunci, operatiile uzuale cu multimi, exemplificate, sunt de forma:

M reunit N = { M[Int] reunit N[Int] , M[Float] reunit N[Float] , M[String] reunit N[String] } = { {1,5,7,231,6,3} , {4.3,7,9.21,5.1} , {"abc","7","rtvf","a","ert"} } M intersectat N = { M[Int] intersectat N[Int] , M[Float] intersectat N[Float] , M[String] intersectat N[String] }

= { {1} , {Vid} , {"7"} } M x N = { M[Int] x N[Int] , M[Float] x N[Float] , M[String] x N[String]} = { { (1,1) , (5,1) , ... , (1,6) , ... } , { (4.3 , 5.1) , (7 , 5.1) , ... } , { ("abc" , "7") , ("7" , "7") , ... } }

Definitia 1.1.2. : O functie S-sortata f : M -> X este o familie de functii f[s].

O functie S-sortata ar putea arata asa: X = {{ {2,10,14,426,16,3} , {-0.7 , 2 , 4.21 , 0.543} , {"abcxyz" , "7xyz" , "rtvfxyz" , "axyz" , "e2"} }} f = { ( f1 : M[Int] -> N[Int] , f1(x) = 2*x ) , ( f2 : M[Float] -> N[Float] , f2(x) = x - 5 ) , ( f3 : M[String] -> N[String] , f3(x) = x + "xyz" ) } Imaginea functiei f , adica daca aplicam f intregii multimi M, ar arataasa: Imgf = { {2,10,14,426} , {-0.7 , 2 , 4.21} , {"abcxyz" , "7xyz" , "rtvfxyz" , "axyz"} } inclus in X. Fiecarei submultimi a lui M i se aplica functia corespunzatoare. Definitia 1.1.3. : O signatura algebrica este ( S , {E[s1...sn,s]s1...sn apartin S* si s apartine S } ) - E este Sigma

S* inseamna un sir de elemente din S, ar putea sa fie S^0, adica sirul vid, S^1 adica un singur element din S, S^3 adica 3 elemente din S, etc S este multimea tipurilor ( sorturi ) iar E operatii, fiecare cu signatura sa. Pentru exemplul cu spatiul vectorial:

S = {R , V} unde R reprezinta sortul numerelor reale iar V sortul vectorilor. E = { {0,1} , {-_ , | _ |}R-R , {-_ , || _ ||}V-R , { _+_ , _-_ , _*_ ,

_/_}RR-R , { _x_ }VV-V , {_o_}RV-V } R-R inseamna ca s1 este R ( aritate 1 , sort R ) iar tipul returnat, s,este tot R. RV-V inseamna ca s1 este R, s2 este V iar s este V.

_ denota prezenta unui argument. Avem operatii fara argumente, adica constante, 0 si 1. Avem, operatii cu un singur argument de sort R, -_ si | _ | ( modul ). Putem aplica operatia - unui numar real ( de sort R ) si ne este returnat tot un numar real. Putem efectua operatia _o_ ( produsul cu scalar ) folosind ca prim argument un numar real, ca al doilea argument un vector si ne va fi returnat tot un vector. Sau, putem aplica norma ( || || ) unui vector si primim un numar real, marimea.


2/6

Apare si un exemplu de supraincarcare de operatori. De exemplu, avem operatia - unara cat si operatia - binara.

Un alt exemplu ar putea sa fie S = {Int , String} si E = { {count(_)}String-Int , {duplicate(_,_)Int,String-String} } count("abc") = 3 , primeste deci ca argument un String si dupa o reguladata returneaza un Int. duplicate(2,"abc") = "abcabc" , primeste ca argument un Int si un String si returneaza un String. Definitia 1.1.4. : O sigma algebra Ar ( Ar inseamna A rond ) = ( {A[s]}s din S , {A[o]}o din E ) unde o este sigma mic. {A[s]} este ca M de sus, o multime S-sortata, adica o multime de multimi, fiecare cu elemente de un anumit sort. {A[o]} este o multime de multimie de functii ( operatii ) cu signatura o. De exemplu, daca am aveam E = { {0,1} , {-_ , | _ |}R-R , {-_ , || _ ||}V-R , { _+_ , _-_ , _*_ , _/_}RR-R , { _x_ }VV-V , {_o_}RV-V }, un element o a lui E ar fi RR-R, iar A[o] ar fi o functie cu signatura RR-R. Un exemplu de functie cu signatura RR-R este +. Algebra defineste si regulile de calcul, de exemplu, in algebra Ar, operatia + cu signatura RR-R poate sa intoarca suma numerelor, pe cand in algebra Br, operatia + cu signatura RR-R poate sa intoarca su

ma numerelor plus 5. Atat timp cand signatura este respectata, functiile pot return ce dorim noi.

o : s1s2...sn -> s pe exemplu este o : RR -> R A[o] : As1 x As2 x ... x Asn -> As este A[o] : R x R -> R. A[o] poate fi + , - , * sau / deci {A[o]} este {+,-,*,/}.

Definitiile lui + , - , * si / tin de fiecare algebra in parte. Chiar daca atat in Ar cat si in Br avem aceleasi operatii ( intrucat ambele folosesc acelasi E ).

Daca in Ar avem + apartinand A[o] si +(a,b) := a+b in Br putem avea +(a,b) := a+b+5.

Morfisme de Algebre Multi-Sortate: Exemplu de morfism de sigma algebre. Fie S = {Int , String} si E = { {count(_)}String-Int , {duplicate(_,_)Int,String-String} } si doua algebre Ar si Br care folosec S si E ( adica in aceste algebre se utilizeaza sorturile din S si operatii cu signaturile prezentate in E )

h = { ( h1 : A[Int] -> B[Int] , h1(x) = Ceva1 ) , ( h2 : A[String] -> B[String] , h2(x) = Ceva2 ) }

Ca h sa fie morfism, toate urmatoarele trebuie sa fie adevarate:

1. h1( countA(a) ) = countB( h2(a) ) 2. h2( duplicateA(a,b) ) = duplicateB( h1(a) , h2(b) )

operatieA ( de exemplu countA ) inseamna operatia asa cum este definitain algebra A. Idem pentru B.

De exemplu , daca A = { {0,1,2,3,4,5} , {"","a","ab","abc"} } si B = { {0,1,2} , {"","x","xy","xyz","A","B"} } si h1(x) = 0 si h2(x) = "" iar countA(str) numara vocalele din str, countB(str) numara consoanele din str si duplicateA(str,times) = str de times ori , duplicateB(str,times) = st


3/6

r de times+1 ori, h va fi morfism.

De exemplu:

h1( countA("abc") ) = h1( 1 ) = 0 countB( h2("abc") ) = countB( "" ) = 0

h2( duplicateA(3,"ab") ) = h2( "ababab" ) = "" duplicateB( h1(3) , h2("ab") ) = duplicateB( 0 , "" ) = ""

Propozitia 1.1.6. : Compunerea ca functii S-sortate a doua morfisme de Sigma Algebre este un morfism de Sigma Algebre: Demonstratia a fost facuta aplicand definitia morfismmului. Definitia 1.1.7. : Morfismul de Sigma Algebre h : Ar -> Br este izomorfism dacaexista morfismul g : Br -> Ar cu h;g = 1A si g;h = 1B. Adica daca h este bijectiva. Exemplul de mai sus nu este izomorfism, pentru ca dupa ce ajung din A[Int] cu h1 in B[Int] nu am un mod unic de a ma intoarce in A[int], adica nu exista h1^(-1). ( In 0 ajung si cu 1 si 2. Din 0 daca vreu sa ma intorc, nu pot, pentru ca nu stiu din ce element am venit ) Ca h sa fie izomorfism, fiecare componenta a sa ( in exemplul de mai sus, atat h1 cat si h2 ) trebuie sa asocieze un element din A[Sort] cu un singur element din B[Sort], adica sa fie functii bijective

. Demonstratia propozitiei 1.1.8. : Un morfism este izomorfism daca si numai dacaare toate componentele bijective:

Demonstratia are doua parti.

1. De la Stanga la Dreapta. Presupundem ca h este izomorfism si aratam ca h^(-1) are toate componentele bijective. Se foloseste proprietatea h;h^(-1) = 1A ( 1A este identitatea lui A, adica 1A(x) = x, oricare x din A ). Este adevarat, daca h asociaza lui "a" pe "x", h^(-1) il va asocia pe "a" lui "x".Compunerea lor e h^(-1)( h(a) ) = h^(-1)( x ) = a iar 1A( a ) = a, deci h;h^(-1)

= 1A. Daca exista h^(-1) inseamna ca exista h^(-1) pentru fiecare sort, adica fiecare functie componenta are o inversa, deci toate functiile componente sunt bijectii.

2. De la Dreapta la Stanga. Presupundem ca toate componentele lui h sunt bijectii. Aratam ca exista h^(-1) si ca acest h^(-1) este morfism de sigma algebre. Faptul ca exista h^(-1) e simplu, pur si simplu punem toti h^(-1)[Sort] ( adica inversul pe fiecare sort in parte ) intr-o multime si numim acea multime h^(-1). Trebuie de asemenea sa aratam ca acest h^(-1) este morfim. Acest lucru este demonstrat luand o operatie generica, o, si evdem daca fiecare h^(-1)[So

rt] indeplineste conditiile de morfism. Propozitia 1.1.9. Compunerea a doua izomorfisme este un izomorfism. Demonstratia se face similar demonstratiei 1.1.6. , aplicand definitia compunerii si a izomorfismului, adica ca f;f^(-1) = Identitate. Definitia 1.2.1. : Sigma-algebra Ar = (As,Ao) se numeste liber generata de V inclus A daca pentru orice Sigma- algebra Dr si pentru orice functie sortata f : V


4/6

-> D, exista un unic mor sm de S-algebre f# : Ar -> Dr care extinde f. V este multimea variabilelor, A\V este multimea expresiilor ( Deci o variabila este o expresie ) , f : V -> D este functia care da valori variabilelor ( f(x) = y inseamnaca in algebra D, variabila x are valoarea y ) iar f# este functia care evalueaza expresii folosind regulile de calcul ale algebrei Dr. Faptul ca f# extinde f inseamna ca foloseste valorile date de f in evaluarea expresiilor. Restrictia lui f# la V inseamna ca evaluand o variabila ii dam valori. Evaluarea Expresiilor: 1. Algebra D. Aceeasi signatura inseamna ca folosesc acelasi E ( Sigma ). 2. Functia f de mai sus, sau v de mai jos. f si v reprezinta acelasi lucru, doar s-a schimbat notatia.

v : X -> D este functia f de mai sus, doar ca multimea variabilelor este notata cu X. v da valori variabilelor din X in algebra D. Daca algebra D1 ar fi o subrutina, si algebra D2 ar fi alta subrutina, aceeasi variabila, x din X poate sa ia valoarea 1 in subprogramul D1 sivaloarea 2 in subprogramul D2.

TE(X) este multimea A de mai sus, iar morfismul v# este functia prin care se dau valori expresiilor, adica se evalueaza.

Faptul ca exista o bijectie intre Alg(TE(X),D) si Set(X,D) inseamna ca fiecare expresie evalueaza unic, in functie de valorile date. O expresie nu poate evalua si la 3 si la 42.5 date aceleasi valori variabilelor.

( "v SetS(X,D))($!v# Alg S(TS(X),D))r(v#) = v

Orice valori am da variabilelor ( adica orice v am alege ) , exista un unic mod de a evalua o expresie ( unic v# )

pentru care evaluarea variabilelor coincide cu valoarea lor ( r(v#) = v). Asta e un mod complicat de a spune ca daca v(x) = 4, si v#(x) = 4, pentru ca x este o expresie, ca orice variabila. Din cauza asta nu mai este nevoie sa facem distinctia intre v si v#. Adica, daca inainte, pentru a evalua o expresie, de exemplu, x?(yTz), trebuia sa scriem:

v#( x?(yTz) ) = v#( v(x)?(v(y)Tv(z)) ) = v#( 2?(3T1) ) = 2*(3+1) = 8. (Intai dadea valori variabilelor cu functia v si prin v# exprimam regulile de calcul )

Acum putem scrie direct:

h(x?(yz)) = h(x) h(yz) = h(x) (h(y) + h(z)) = 2 (3 + 1) = 8.Exemplul cu instructiunea de atribuire: Sem(x:=e)(s)(y) va evalua expresia e ( s#(e) ) daca y este variabila careia vrem sa ii atribuim expresia. Vrem sa ii atribuim lui x, deci y = x. Daca y nu e x, atunci ii atribuim lui y valoarea pe care o are deja, adica s(y). Teorema 1.2.4. : Doua algebre liber generate de aceeasi multime sunt izomorfe. Primii 2 pasi au la baza faptul ca atat A cat si B sunt algebre liber ge


5/6

nerate. La pasul 1, algebra B joaca rolul algebrei D din exemplele de mai sus. La pasul 2, A este algebra D. Ultimii doi pasi arata ca g ( morfismul de la B la A ) este de fapt f^(-1), adica cele doua algebre sunt izomorfe. Acest lucru se face folosind Propozitia 1.1.6. ( Din propozitia asta stim ca este corect sa facem acele compuneri ) Teorema 1.2.5. : Orice algebra izomorfa cu o algebra libera este algebra libera. Demonstratia porneste de la faptul ca V este inclus in A si exista un izomorfism h de la A la B. Deci, exista in B o submultime h(V). Se ia o alta algebra, C si o functie de la h(V) la C, f. Se mai ia si ofunctie g de la V la C ( deci prin g dam valori variabilelor in C ) si o definim prin g = h;f. g este defapt drumul V->h(V)->C. Din cauza faptului ca A este algebra libera si avem o functie g de la Vla C, inseamna ca avem si un g# de la A la C. Adica, putem evalua expresii din A in algebra C. Inversand rolurile lui B cu A ( h^(-1) , putem face asta pentru ca suntizomorfe ) vedem ca putem evalua expresii din B in C, prin morfismul h^(-1);g. Daca acest morfism este unic, demonstratia se incheie. Facem asta luand un morfism si aratabd ca este h^(-1);g. Propozitia 1.2.6. : O S-algebra I se numeste initiala daca pentru orice S-algebra A

exista un unic mor sm aA : I - A.Adica daca din I, algebra initiala, pot sa fac un singur morfism catre orice alta algebra, aceasta e initiala. Propozitia 1.2.7. : Fie N = (N,0N,sN) algebra de nita prin: N este multimea numerelor naturale, 0N este numarul natural zero si sN(n) = n + 1 pentru orice numarnatural n. Algebra N este initiala. Demonstratia se face aratand cele doua conditii de la porpozitia anterioara. Se ia o algebra A oarecare cu aceeasi signatura, E. Se arata ca exista un morfism de la I la A si ca acesta e unic. 1. Existenta: Aplicam operatia elementelor rezultate din morfism ( in loc de 0 = 0 si s(n) = n+1 avem h(0) = 0A si s(h(n)) = h(n+1) )

2. Unicitatea: Unicitatea este probata luand un alt morfism si aratand ca este defapt h. Definitia 1.3.1. Operatorul de inchidere: Exemplu de operator de inchidere: Operatorul modul ( | | ). P = { 0 , 1 , 2 , 3, 4 , 5 } 1. Extensivitate: | 1 |


6/6

) , ... } ...

Demonstratia Propozitiei 1.3.10: 1. Evident

2.2.1. Se alege o operatie cu o signatura oarecare:

Fie s1s2 ...sn S , s S, s S 1 2... n, 2.2. Se iau din Xbarat argumentele care vor fi folosite in opera

tias : a1 Xs1, a2 Xs2, ..., an Xsn

2.3. Fiecare din argumente ( ai ) se va gasi intr-un X^k ( Nu eacelasi k pentru toti, gen a1 se gaseste in X^2 , a2 se gaseste in X^6 ) Dar, pentru ca Xbarat e reuniune, toti se vor gasi in X^celMaiMareK. ( Daca a1 apartine X^2 atunci va apartine si lui X^6, unde e si a2.) Adica, va exista un k astfel incat toate argumentele operatiei alese se vor gasi. De aia il ia pe cel mai mare.

Pentru orice 1 i n din ai Xsi, adica ai SnN Xn si, rezultaexista un numar natural ki cu proprietatea ai Xki si . Fie k cel mai mare dintre

numerele k1,k2,...,kn. Deoarece sirul {Xn}n este crescator deducem ca ai Xk si2.4. Aplicand operatia, vom obtine un rezultat care sigur sigur

e in X^(k+1) care e in Xbarat. Deci e parte stabila. 3. Ia un element, a , din X^(n+1) , care nu se stie inca daca fa

ce parte din P sau nu. Cum ceva din X^n se regaseste in X^(n+1) , va exista o operatie care va da a, din ipotezainductiva ( Gen a poate fi ori un element din X^n ori un element din X^(n+1)\X^n ) , iar rezultatul, a, va face parte din P, conform faptului ca P e parte stabila ( Ps pentru ca a e de sort s, iar Ps apartine P ). Deci ceva din X^(n+1) apartine P, deci inductia e completa.

Programare Logica Explicatii

Documents

Transcript of Programare Logica Explicatii