Home >Documents >logica computationala

logica computationala

Date post:20-Oct-2015
Category:
View:54 times
Download:4 times
Share this document with a friend
Description:
logica computationala
Transcript:
  • CAPITOLUL 1

    Elemente de teoria mulimilor

    In paragraful nti al acestui capitol prezentm cteva noiuni i proprieti ale

    calculului propoziional, absolut necesar pentru demonstrarea propoziiilor de teoria mulimilor referitoare la operaiile finite cu mulimi. Paragraful al doilea conine definirea operaiilor cu mulimi (reuniune, intersecie, complementar, etc.) i proprietile lor principale.

    Elementele foarte sumare ale calculului predicatelor sunt expuse n 3, pentru a fi folosite n continuare n stabilirea proprietilor operaiilor infinite cu mulimi.

    Relaiile i funciile sunt subiectul paragarfului 4, iar produsul cartezian infinit i proprietatea sa de universalitate sunt prezentate n 5.

    Am considerat necesar s introducem un paragraf privind operaiile cu cardinali, insistnd asupra mulimilor numrabile. Ultimul paragraf se ocup cu relaiile de ordine i preordine. Plasarea acestui paragraf n acest capitol este necesar pentru enunarea axiomei lui Zorn, care este o axiom a teoriei mulimilor.

    Nu am dezvoltat extensiv acest capitol, prezentnd numai un minim necesar pentru tratarea capitolelor urmatoare. O serie de proprieti au fost date sub form de exerciii. Precizm c punctul de vedere adoptat este acela al teoriei naive a mulimilor.

    1. Calculul propoziional n calculul propoziional se studiaz propoziiile1) din punctul de vedere al

    adevrului sau falsitii lor, nelundu-le n considerare coninutul lor. Fr ndoial, legile logicii sunt expresii ale unor legi naturale obiective, ns neconsiderarea coninutului este necesar pentru a surprinde relaiile logice ale fenomenelor naturale n toat generalitatea lor.

    Vom nota propoziiile prin literele p, q, r, . Pentru orice propoziie p, definim valoarea ei logic v(p) prin:

    =

    falsa este p propozitia daca ,0 adevarata este p propozitia daca ,1

    v(p)

    Deci, pentru noi, o propoziie p este perfect determinat dac i cunoatem

    valoarea logic v(p). Dac p,q sunt dou propoziii oarecare, atunci conjuncia lor pq este

    propoziia p i q, iar valoarea ei de adevr este dat de

    =

    falsa este q p, lepropozitiidin unaputin cel daca 0,adevaratesimultan sunt q p, daca 1,

    q)v(p

    1) n acest capitol conceptul de propoziie este cel uzual.

  • Cu alte cuvinte, v(pq)=1 dac i numai dac v(p)=1 i v(q)=1. Disjuncia pq a propoziiilor p,q este propoziia p sau q, iar valoarea ei

    logic este definit prin: v(pq)=1 dac i numai dac v(p)=1 sau v(q)=1. Negaia a unei propoziii p are urmtoarea valoare de adevr: p

    =

    falsa este p daca 1,adevarata este p daca 0,

    p)v(

    Date dou propoziii p,q, implicaia qp este propoziia p implic q a

    crei valoare de adevr este:

    ===

    restin 1,0 v(q)si 1 v(p)daca ,0

    q)v(p

    Echivalena pq a dou propoziii p,q este propoziia p echivalent cu q a

    crei valoare de adevr este dat de v(p)=1 dac i numai dac v(p)=v(q). Aceste definiii pot fi concentrate n urmtoarele tabele de adevr.

    v(p) v(q) v(pq) 1 1 1 1 0 0 0 1 0 0 0 0

    v(p) v(q) v(pq) 1 1 1 1 0 1 0 1 1 0 0 0

    conjuncia disjuncia

    v(p) v(q) v(pq)1 1 1 1 0 0 0 1 0 0 0 1

    v(p) v(q) v(pq) 1 1 1 1 0 0 0 1 1 0 0 1

    implicaia echivalena

  • v(p) v(p) 1 0 0 1

    negaia Urmtoarele propoziii sunt adevrate, pentru orice propoziii p, q, r: 1. ; p)(qq)(p p);(qq)(p 2. r)];(q[pr]q)[(p r)];(q[pr]q)[(p 3. p;p)(p p;p)(p 4. r)];(pq)[(pr)](q[p r)];(pq)[(pr)](q[p 5. p;q)](p[p p;q)](p[p 6. p);(p p;p 7. );(q)(p q);p(q)(p qp 8. q);p(q)(p q);p(q)(p 9. p;p 10. q);p(q)(p 11. p)];(qq)[(pq)(p 12. .p)q(q)(p Vom arta, de exemlu, c prima propoziie de la 7 este adevrat. Calculm

    valoarea logic a propoziiei (pq) (pq) pentru orice valoare 0 sau 1 pe care o pot lua propoziiile componente p, q. Sistematizm acest calcul prin urmtorul tabel:

    v(p) v(q) v(pq) v((pq)) v(p) v(q) v(pq) v((pq))v(pq) 1 1 1 0 0 0 0 1 1 0 0 1 0 1 1 1 0 1 0 1 1 0 1 1 0 0 0 1 1 1 1 1

    n toate cazurile am obinut valoarea 1. Demonstraia se face n aceeai manier pentru toate proprietile 1- 12. 2. Mulimi, operaii cu mulimi Pentru noi, conceptul de mulime va avea semnificaia uzual de colecie,

    grmad etc. Vom nota mulimile prin literele A, B, C, X, Y, Z etc. Obiectele din care este format o mulime se vor numi elemente. Elementele unei mulimi vor fi notate a, b, c,.. x, y, z etc.

    Faptul c elementul x face parte din mulimea A va fi notat xA i se va citi: x aparine mulimii A.

    Vom extinde conceptul de mulime prin considerarea mulimii vide , care este mulimea fr nici un element.

  • Mulimea A este inclus n mulimea B, dac orice element al lui A este i element al lui B. Scriem aceasta prescurtat A B. Definiia incluziunii A B poate fi dat i astfel:

    xA xB Reuniunea a dou mulimi A i B este mulimea AB definit de

    x AB [xA][xB] Un alt mod de a scrie aceast definiie este:

    AB ={x / (xA)(xB)} n cele ce urmeaz vom omite parantezele, scriind astfel:

    AB ={x / xA xB}. Intersecia a dou mulimi A i B este mulimea AB definit de: x AB [xA] [xB] Aceast definiie poate fi dat sub forma: AB ={x / xA xB}. Diferena a dou mulimi A i B este definit astfel: AB ={x / xA xB}. OBSERVAIE. Prin xB am notat propoziia (xB). Dac AB se spune c A este o parte (sau o submulime ) a lui B. Prin

    convenie, este submulime a oricrei mulimi. Pentru orice mulime A, vom nota cu P(A) mulimea tuturor prilor lui A.

    P(A) = {B / B A}

    Fiind dat o mulime A i o parte a sa B, definim complementara (B)CA a lui B n raport cu A prin

    CA(B)= AB ={x / xA xB}. n teoria mulimilor, conceput astfel, se pot ivi paradoxuri de urmtorul tip. Paradoxul lui Russell: Presupunem c A={x / xx} este o mulime. Atunci

    pentru orice x, vom avea xA xx n particular, pentru x=A vom avea AA AA ceea ce este evident contradictoriu. Din cauza paradoxurilor, suntem condui la a considera colecii care nu sunt

    neaprat mulimi, numite clase. Spre exemplu vom vorbi de clasa tuturor mulimilor, care nu mai este o mulime.

    PROPOZIIA 1: Pentru orice mulimi A,B,C sunt verificate urmtoarele

    relaii: (1) ABBA A;BBA == (2) C;B)(AC)(BA C;B)(AC)(BA == (3) C);(AB)A(C)(BAC);(AB)A(C)(BA == (4) A;AA A;AA == (5) A;B)(AA A;B)(AA == (6) ;A A;A == (7) A=B A];[BB][A (8) A;A

  • (9) C;AC][BB][A (10) A;B-A B;AABA (11) D)];(BC)[(AD)](BC)[(AD][CB]A[ (12) A];B[AB]B[AB][A == (13) B);-(A-ABA = (14) B;AA)-(BA =(15) A-(A B;-AB) =(16) C;-B)(AC)-(BA = Demonstraie: Vom stabili, de exemplu prima din relaiile (3): C).(AB)(AC)(BA =Aplicnd propoziia 4, 1, rezult echivalenele: x C]B[xA)(xC)(BA C)](xB)[(xA)(x C)](xA)[(xB)](xA)[(x C]A[xB]A[x U C)(AB)(Ax A rezultat: C)(AB)(AxC)(BAx , ceea ce este acelai

    lucru cu egalitatea ce trebuie demonstrat. n acelai mod se demonstreaz toate relaiile enumerate mai sus. Propoziia 2: Dac B, C sunt mulimi ale lui A, atunci avem relaiile: (17) (B);C(C)CCB AA (18) (C);C(B)CC)(BC BAA = (19) (C);C(B)CC)(BC AAA =(20) A.)(C;(A)C AA == Lsm demonstraia acestor relaii pe seama cititorului. Dac sunt date mulimile atunci definim,A...,A,A n21 intersecia i reuniunea

    lor astfel: { })A(x...)A(x)A(x |xA...A n21n1 = { })A(x...)A(x)A(x |xA...A n21n1 = se mai folosesc i notaiile:

    n1

    n

    1iin1

    1i A...AA ;A...AA ==

    ==UI

    n

    i

    .

    Menionm urmtoarele proprieti:

    (21) ;B][AB]A[n

    1ii

    1i II

    ===

    n

    i

    (22) ;][A][1

    i1

    UUn

    i

    n

    ii BBA

    ===

    (23) ;)(AC][C1

    iA1

    A IUn

    i

    n

    iiA

    ===

  • (24) .)(AC]A[C1

    iA1

    iA UIn

    i

    n

    i ===

    Fie A, B dou mulimi oarecare. Produsul cartezian al mulimilor A i B este mulimea A x B definit astfel : { }.B)(yA)(x |y)(x,BA x =

    In general, produsul cartezian a n mulimi este n1,...AA{ }.)A(x...)A(x)A(x |)x,...,(xx...xAA nn2211n1n1 = Se folosesc notaiile:

    .x...xAAA n11

    i ==

    n

    i

    n1n x...xAAA = , dac A.A...AA n21 ====

    Produsul cartezian are urmtoarele proprieti: (25) xB);(AxB)(A)xBA(A 2121 =(26) xB);(AxB)(A)xBA(A 2121 = (27) xB);(AxB)(A)xBA(A 2121 = (28) Dac sunt nevide, atunci 2121 B,B,A,A ];B[B]A[A]xBAxB[A 21212211 === (29) dac A= ,AxB = sau B= 3. Calculul predicatelor n calculul propoziional nu ne-am interesat de structura propoziiilor, care au

    fost considerate ca nite ntregi, preocupndu-ne de valoarea lor logic. Considernd propoziia Socrate este muritor, observm n alctuirea lui un

    individ, Socrate i o proprietate muritor. Propoziiile Platon este muritor i Aristotel este muritor au aceeai form i difer doar individul despre care se afirm c este muritor.

    Toate aceste propoziii au forma x este muritor. n general, vom considera expresii de forma x are proprietatea P, pe care le vom nota P(x).

    Aceste expresii le vom numi predicate(Hilbert i Bernays, Grundlagen der Mathematik, vol.1, 1934) sau funcii propoziionale(Russel si Whitehead,Principia Mathematica, vol.1, 1910).

    n Principia Mathematica, acest concept este definit astfel:printr-o funcie propoziional nelegem ceva care conine o variabil x i exprim o propoziie de ndat ce lui x i se atribuie o valoare.

    Cu alte cuvinte, un predicat P(x) devine o propoziie P(a) dac i se atribuie lui x o valoare determinat a. Propoziia P(a) poate fi adevrat sau fals.

    Vom presupune c x ia valori ntr-o mulime A de indivizi, astfel nct pentru orice a A , P(A) est

Click here to load reader

Embed Size (px)
Recommended