2 logica predicatelor de ordinul i

Upload: lucian-eu

Post on 15-Oct-2015

25 views

Category:

Documents


1 download

TRANSCRIPT

  • 5/26/2018 2 Logica Predicatelor de Ordinul I

    1/45

    1 Logica predicatelor de ordinul I

    Prof. univ. dr. Dumitru

    GHEORGHIU

  • 5/26/2018 2 Logica Predicatelor de Ordinul I

    2/45

    Sintaxa LPOILimbajul LPOI:n operatori propoziionali: (negaie), & (conjuncie),

    (disjuncie), (condiional), (bicondiional)n constante individuale: a, b, c, ...n variabile individuale: x, y, z, n simboluri de funcii: f, g, h,

    n

    simboluri de predicate: F, G, H, ...n cuantorul universal, ", citit pentru orice, i

    cuantorul existenial, $, citit existn semne tehnice: (, ), [, ], {, }

    2

  • 5/26/2018 2 Logica Predicatelor de Ordinul I

    3/45

    Sintaxa LPOIn Fiecare simbol de funcie sau de predicat are o aritaten 1,

    datde numrul de argumente care pot sapardupsimbolulrespectiv

    n Dacn= 1, Feste unar, dacn= 2, Feste binar, dacn= 3, Feste ternar etc.

    n Se numete termen:n orice constantindividual;n orice variabilindividual;n dacfeste un simbol de funcie de aritate ni t1, , tnsunt

    termeni, ft1, , tneste un termen.n DacFeste un simbol de predicat de aritate ni t1, , tnsunt

    termeni, Ft1, , tneste un atom.

    3

  • 5/26/2018 2 Logica Predicatelor de Ordinul I

    4/45

    Sintaxa LPOIn Se numete formula LPOI orice ir de simboluri construit

    conform urmtoarelor reguli:

    (R1) Orice atom este o formul(R2) DacAeste o formul, atunci Aeste o formul(R3) DacAi Bsunt formule, atunciA&Beste formul(R4) DacAeste o formuli xeste o variabilindividualcareapare nA, atunci "xAi $xAsunt formule

    n Operatorii , , . Pentru oricare douformuleAi B:n ABprescurteaz(A& B)n ABprescurteaz(AB)n ABprescurteaz[(AB) & (BA)]

    4

  • 5/26/2018 2 Logica Predicatelor de Ordinul I

    5/45

    Sintaxa LPOIn Fab, Fxy, "xFxy, $xFxy, "x$yFxy, $x(Fx Gx) i "xFx

    $xFxsunt formule ale LPOIn ntr-o formulde forma QxA, unde Qeste un cuantor,Ase

    numete domeniul cuantorului Qn n $yFxy, domeniul cuantorului existenial este Fxyn n "x$yFxy, fiecare cuantor are ca domeniu Fxyn n "x($yFyFx), domeniul cuantorului universal este $yFy

    Fxi domeniul cuantorului existenial este Fyn Daco variabil, x, apare n domeniul unei formule QxA, atunci

    se spune cxeste legat de cuantorul Qn Variabilele care nu sunt legate se numesc libere

    5

  • 5/26/2018 2 Logica Predicatelor de Ordinul I

    6/45

    Sintaxa LPOIn O formuln care nu apare nici o variabilliberse numete

    propoziie sau formulnchisn O formuln care apare cel puin o variabilliberse numete

    formuldeschisn "x(Fx&Gxyz) i "x$y(FxGxyz) sunt formule deschise, iar Fa,

    FaGabi "x$y$z(FxGxyz) sunt propoziiin Una i aceeai apariie a unei variabile individuale nu poate fi

    legatde cuantori diferii, ca n "x(Fx $xFx)n Una i aceeai variabilnu poate saparatt liber, ct i

    legatn aceeai formul, ca n $xFxGxyn Daceste nclcatcel puin una dintre aceste restricii, atunci

    se spune cs-a comis eroarea coliziunii variabilelor

    6

  • 5/26/2018 2 Logica Predicatelor de Ordinul I

    7/45

    Sintaxa LPOIn Se numete redenumire operaia prin care ntr-o formulA, o

    variabilxlegatde un cuantor Qse nlocuiete n tot domeniulcuantorului Qcu o variabily, cu condiiile:

    1.ynu apare libernAi2. dacQapare n domeniul altui cuantor, Q , atunci ytrebuie sdifere de variabila legatde Q

    n "x(Fx $xFx). Prin aplicarea redenumirii obinem:n "y(Fy $xFx) saun "x(Fx $yFy)

    n $xFxGxy. Prin aplicarea redenumirii obinem:n $zFzGxy

    7

  • 5/26/2018 2 Logica Predicatelor de Ordinul I

    8/45

    Semantica LPOIn O structur Mpentru o propoziie A constdin:

    n un univers non-vid Umpreuncun

    o atribuire de funcii i relaii simbolurilor de predicate dinA

    ,conform aritii acestora in o atribuire de indivizi din Uconstantelor individuale din A

    n O structur Mpentru o propoziie A este un tuplu (U, P1, , Pn,d1, , dm), unde:n Ueste universul structurii,n P1, , Pnsunt funcii i relaiile atribuite simbolurilor de

    predicate F1, , Fndin A conform aritii acestora in d1, , dmsunt indivizii din Uatribuii constantelor c1, , cm

    din A

    8

  • 5/26/2018 2 Logica Predicatelor de Ordinul I

    9/45

    Semantica LPOIn O structurMeste un model al unei propoziii A, dacA ia

    valoarea 1n Mn "x$yFyx= pentru orice xexistyastfel cxstn relaia Fcu yn Fie structura (Z,

  • 5/26/2018 2 Logica Predicatelor de Ordinul I

    10/45

    Semantica LPOIn O propoziie este realizabil, dacare cel puin un model i este

    nerealizabil, dacnu are nici un modeln O propoziie A este valid, dacorice structureste un model al

    propoziiei A. Cu alte cuvinte, A este valid, dacia valoarea 1indiferent de universul Uconsiderat i de interpretareasimbolurilor de predicate i a constantelor individuale din A

    n "xFxFaeste valid: dacoriceindivid dintr-un univers Uareo proprietate F, atunci individul particular din Ula care se refer

    constanta individualaare proprietatea Fn Fa $xFxeste valid: dacindividul particular din Ula care se

    referconstanta individualaare proprietatea F, atunci existcel puin un individ n Ucare are proprietatea F

    10

  • 5/26/2018 2 Logica Predicatelor de Ordinul I

    11/45

    Semantica LPOIn O propoziie Beste consecinlogica

    propoziieiA,AB, dacorice model al

    propoziieiAeste model al propoziiei Bn Se spune cdoupropoziiiA, Bsunt

    echivalente logic,AB, dacorice model alformuleiAeste model al formulei Bi reciproc

    n Teorema nlocuirii este valabili pentrulogica predicatelor (cu propoziien loc deformul)

    11

  • 5/26/2018 2 Logica Predicatelor de Ordinul I

    12/45

    Unele reguli semantice ale LPOIn FieA(x) o formuln care xeste liber. Urmtoarele dou

    echivalene sunt generalizri ale regulilor lui De Morgan:

    (1) $xA(x) "xA(x) importarea (2) "xA(x) $xA(x) importarea

    n 1. "x$y"z[(Fxy&Gyz) Hxyz]2. $x$y"z[(Fxy&Gyz) Hxyz] din 1, prin (2)

    3. $x"y"z[(Fxy&Gyz) Hxyz] din 2, prin (1)4. $x"y$z[(Fxy&Gyz) Hxyz] din 3, prin (2)

    12

  • 5/26/2018 2 Logica Predicatelor de Ordinul I

    13/45

    Unele reguli semantice ale LPOIn FieA(x) i B(x) formule n care xeste liber:

    (3)"xA(x) &"xB(x) "x(A(x) &B(x))

    (4)$xA(x) $xB(x) $x(A(x) B(x))

    n FieA(x) o formuln care xeste liberi Co formulcare nuconine variabila x:

    (5)"xA(x) &CC&"xA(x) "x(A(x) &C)(6)"xA(x) CC "xA(x) "x(A(x) C)(7)$xA(x) &CC&$xA(x) $x(A(x) &C)(8)$xA(x) CC $xA(x) $x(A(x) C)

    13

  • 5/26/2018 2 Logica Predicatelor de Ordinul I

    14/45

    Unele reguli semantice ale LPOIn Un prefix este omogen, daceste alctuit din cuantori de

    acelai feln Un prefix este eterogen, daceste alctuit din cuantori de tip

    diferitn Orice prefix omogen este comutativ:

    (9) "x"yA(x, y) "y"xA(x, y)(10) $x$yA(x, y) $y$xA(x, y)

    n Un prefix eterogen nu este comutativ:"x$yIubete(x, y) = oricine iubete pe cineva$x"yIubete(x, y) = cineva iubete pe oricine

    14

  • 5/26/2018 2 Logica Predicatelor de Ordinul I

    15/45

    Forme normale prenexen O propoziie n formnormalprenex (FNP) este o propoziie

    de forma Q1x1Q2x2QnxnA, unde fiecare Qieste un cuantor ($sau ") iAeste o formulcare nu conine cuantori

    n Secvena Q1x1Q2x2Qnxnse numete prefix, iarAse numetematrice

    n "x$y"z[(FxyGyz) Hxyz] este n FNPn "x$y"zeste prefixul propoziiei, [(FxyGyz) Hxyz] este

    matricea propoziiein Algoritmul de aducere a unei propoziii la FNP folosete

    echivalenele logice (1)(8)n FieAo propoziie iA FNP a propoziieiA.Aeste echivalent

    logic cuA

    15

  • 5/26/2018 2 Logica Predicatelor de Ordinul I

    16/45

    Forme normale prenexen "xFx $xGx

    1. Eliminm :"xFx $xGx

    2. Importm :$xFx $xGx

    3. Redenumim pe xdin prima parte a disjunciei ca y:$yFy $xGx

    4. Aducem $yn fa, conform (8):$y(Fy $xGx)5. Aducem $xn fa, conform (8):

    $y$x(FyGx) FNP

    16

  • 5/26/2018 2 Logica Predicatelor de Ordinul I

    17/45

    Forme normale prenexen "x$yFxy&$y"xFxy1. Redenumim pe xi pe yn prima parte a conjunciei, respectiv,ca zi w:

    "z$wFzw&$y"xFxy2. Aducem "zn fa, conform (5):

    "z($wFzw&$y"xFxy)3. Aducem $wn fa, conform (7):

    "z$w(Fzw&$y"xFxy)4. Aducem $yn fa, conform (8):

    "z$w$y(Fzw&"xFxy)5. Aducem "xn fa, conform (5):

    "z$w$y"x (Fzw& Fxy) FNP

    17

  • 5/26/2018 2 Logica Predicatelor de Ordinul I

    18/45

    Forme normale Skolemn O propoziie n formnormalSkolem este o propoziie n FNP

    din care cuantorii existeniali sunt eliminai din prefix, de ladreapta la stnga, prin urmtorul algoritm:

    1. Dac$ nu este precedat de vreun cuantor universal, atunci$ se elimini n locul variabilei legate de $ se pune, peste totunde ea apare, o constantindividualcare nu apare npropoziie;2. Dac$ este precedat de ncuantori universali, atunci $ se

    elimini n locul variabilei legate de $ se pune, peste tot undeea apare, o funcie de nargumente care nu apare npropoziie, unde cele nargumente sunt, n ordine, variabilelelegate de cei ncuantori universali.

    18

  • 5/26/2018 2 Logica Predicatelor de Ordinul I

    19/45

    Forme normale Skolemn $x"y"z(Fxy&Gxz). Prin skolemizare obinem

    "y"z(Fay&Gaz)n "x"y$z(Fxy&Gxz). Prin skolemizare obinem

    "x"y(Fxy& Gxf(x,y))n FieAo propoziie iA FNS a propoziieiA.Aeste

    nerealizabilddacA este nerealizabil

    n

    Propoziiile aduse la FNS pot fi scrise fr", ntructpresupunem corice variabileste cuantificatuniversal

    n Fxy& Gxf(x,y)

    19

  • 5/26/2018 2 Logica Predicatelor de Ordinul I

    20/45

    Forme clauzalen Pentru a aplica metoda rezoluiei n LPOI, propoziiile se aduc la

    forma clauzal (FC) prin urmtorii pai:

    1. Se elimini , nlocuind BCcu (BC) & (CB) i BCcu BC2. Se aduc pe termeni, nlocuind (B &C) cu B C,(BC)cu B& C, $xA(x) cu "xA(x) i "xA(x) $xA(x)3. Se elimin, nlocuind Bcu B

    4. Se standardizeazvariabilele prin redenumire, astfel nctfiecare cuantor slege propria sa variabil. De exemplu, $yFydevine $zFz, dacyapare deja n domeniul altui cuantor5. Se aduce propoziia la FNP

    20

  • 5/26/2018 2 Logica Predicatelor de Ordinul I

    21/45

    Forme clauzale6. Se elimincuantorii existeniali din prefix prin skolemizare7. Se scrie propoziia frcuantori universali8. Se aduce propoziia la FNC, folosind algoritmul de normalizaredin LPCn Fiecare pas pstreazechivalena logic, cu excepia pasului 6

    (skolemizarea), care pstreaznumai realizabilitatean "x{[Fx"y(FyFxy)] & "y(GxyFy)}

    1. Eliminm :"x{[Fx "y(FyFxy)] & "y(GxyFy)}2. Importm :"x{[Fx "y(FyFxy)] & $y(GxyFy)}

    21

  • 5/26/2018 2 Logica Predicatelor de Ordinul I

    22/45

    Forme clauzale3. De Morgan pentru :"x{[Fx "y(FyFxy)] & $y(Gxy& Fy)}4. Eliminm :"x{[Fx "y(FyFxy)] & $y(Gxy& Fy)}5. Standardizm variabilele:"x{[Fx "y(FyFxy)] & $z(Gxz& Fz)}6. Aducem formula la FNP:

    "x"y$z[(Fx FyFxy) & Gxz& Fz]7. Eliminm $zi scriem propoziia frcuantorii universali:(Fx FyFxy) & Gxf(x, y) & Ff(x, y) FC

    22

  • 5/26/2018 2 Logica Predicatelor de Ordinul I

    23/45

    Metoda rezoluiei n LPOIn Un literal este un atom sau negaia unui atomn Se numesc literali complementari doi literali care nu diferntre

    ei dect prin aceea cunul este i cellalt nu este precedat de

    negaien Fxyi Fxy, Gxf(y) i Gxf(y) sunt perechi de literali

    complementarin Rezolventul n Fxyal clauzelor {Fxy, Gz} i {Fxy, Hw} este

    clauza {Gz,Hw}n Se numete clauza vid, , mulimea vidde literali. Pentru

    orice atom x, poate fi obinutnumai ca rezolvent al clauzelor{x}i {x}

    n Rezolventul n Fxyal clauzelor {Fxy} i {Fxy} este

    23

  • 5/26/2018 2 Logica Predicatelor de Ordinul I

    24/45

    Metoda rezoluiei n LPOIn Pentru a obine literali complementari n clauze la

    care vrem saplicm rezoluia se recurge la unificare

    n

    Unificarea este o operaie de substituire uniformavariabilelor n doi literali, astfel nct sse obinliterali complementari

    n O variabilxpoate fi substituitcu un termen t, x/ t,numai dacxnu apare n t

    n Substituia poate fi vid, n sensul cse poatesubstitui o variabilcu ea nsi i dacapar numaiconstante, atunci nu se substituie, de fapt, nimic

    24

  • 5/26/2018 2 Logica Predicatelor de Ordinul I

    25/45

    Metoda rezoluiei n LPOIn Fie clauzele unitare {Px} i {Pf(x)}. Pentru a aplica rezoluia,

    procedm dupcum urmeaz:

    n

    Redenumim variabila xdin Pf(x) ca yi obinem {Pf(y)}n Unificm atomii Pxi Pf(y) prin x/ f(y) i obinem Pf(y),

    care este complementarul lui Pf(y), unde substituia estevid

    n Rezolventul n Pf(y) al clauzelor {Pf(y)} i {Pf(y)} este

    Sobservm c, dacnu am fi redenumit variabila x, nu am fiputut efectua unificarea, deoarece Pxi Pf(x) nu pot fiunificate

    25

  • 5/26/2018 2 Logica Predicatelor de Ordinul I

    26/45

    Metoda rezoluiei n LPOIn n anumite cazuri, unificarea trebuie sfie combinatcu o alt

    operaie, numitfactorizaren Dacdoi sau mai muli literali (cu acelai semn) dintr-o clauz

    pot fi unificai, atunci clauza astfel obinut, din care sunteliminai literalii-duplicat, se numete factor al clauzei iniiale

    n Pentru a obine prin rezoluie {Faf(a)} din {Fxa, Fxy, Fyx}i {Fzf(z), Fza}, procedm dupcum urmeaz:n Factorizm {Fxa, Fxy, Fyx} prin x/a, y/ai obinem

    {Faa, Faa, Faa} , care se reduce la factorul {Faa}n Unificm Faai Fzaprin z/ai obinem {Faf(a), Faa}n Rezolventul n Faaal clauzelor {Faa} i {Faf(a), Faa} este

    {Faf(a)}

    26

  • 5/26/2018 2 Logica Predicatelor de Ordinul I

    27/45

    Metoda rezoluiei n LPOIn Pentru a stabili daco propoziieAeste sau nu valid:

    1. Negm propoziiaA(Aeste validddac Aestenerealizabil)2.Aducem Ala FC, considernd apoi clauzele ca mulimi deliterali i ntreaga formulca o mulime de clauze3. Standardizm din nou variabilele prin redenumire, astfelnct fiecare clauzsconinnume de variabile care nu aparn nici o altclauz

    4. Efectum rezoluii, precedate eventual de unificri ifactorizri5. Dacobinem , atunci Aeste nerealizabil, deciAestevalid

    27

  • 5/26/2018 2 Logica Predicatelor de Ordinul I

    28/45

    Metoda rezoluiei n LPOIn Sse arate c"x$y(Fyx Fyy) este valid

    1. Negm propoziia:"x$y(Fyx Fyy)2. Eliminm :"x$y[(Fyx Fyy) & (FyyFyx)3. Eliminm :"x$y[(Fyx Fyy) & (FyyFyx)

    4. Eliminm :"x$y[(Fyx Fyy) & (FyyFyx)5. Importm :$x"y[(Fyx Fyy) & (FyyFyx)

    28

  • 5/26/2018 2 Logica Predicatelor de Ordinul I

    29/45

    Metoda rezoluiei n LPOI6. Eliminm :$x"y[(Fyx Fyy) & (FyyFyx)]7. Eliminm $xprin skolemizare i scriem formula fr"y:(Fya Fyy) & (FyyFya) FC8. Avem urmtoarele clauze:{Fya, Fyy}, {Fzz,Fza}9. Factorizm prima clauzprin y/ai a doua clauzprin z/a:

    {Faa}, {Faa}10. Rezolventul n Faaal acestor douclauze este

    Ce obineam dacnu am fi aplicat factorizarea?

    29

  • 5/26/2018 2 Logica Predicatelor de Ordinul I

    30/45

    Metoda rezoluiei n LPOIn Pentru a decide dac{A1, ,An} B:

    n formm conjunciaA1 &&An& Bn aducem aceastconjuncie la FNC in aplicm metoda rezoluiei asupraA1 &&An& B

    n Dacobinem , atunci {A1, ,An} Bn Sse deciddac"x(FxGx) "xFx "xGx

    1. "x(FxGx) & ("xFx"xGx)

    2. Eliminm :"x(FxGx) &("xFx"xGx)3. De Morgan pentru i eliminarea :"x(FxGx) &"xFx&"xGx

    30

  • 5/26/2018 2 Logica Predicatelor de Ordinul I

    31/45

    Metoda rezoluiei n LPOI4. Importm :"x(FxGx) &"xFx&$xGx5. Standardizm variabilele prin redenumire:"x(FxGx) &"yFy&$zGz6. Aducem propoziia la FNP:"x"y $z[(FxGx) &Fy& Gz]7. Eliminm $zi scriem propoziia frcuantorii universali:

    (FxGx) &Fy& Gf(x, y) FC8. {Fx,Gx}, {Fy}, {Gf(x, y)}9. Redenumim n {Gf(x, y)} pe xca zi pe yca w:{Fx,Gx}, {Fy}, {Gf(z, w)}

    31

  • 5/26/2018 2 Logica Predicatelor de Ordinul I

    32/45

    Metoda rezoluiei n LPOI{Fx,Gx}, {Fy}, {Gf(z, w)}

    10. Unificm literalii Fxi Fyprin y/x:

    {Fx,Gx}, {Fx}11. Rezolventul n Fxal clauzelor {Fx,Gx} i {Fx} este {Gx}12. Unificm literalii Gf(z, w)i Gxprin x/f(z, w):{Gf(z, w)}, {Gf(z, w)}13. Rezolventul n Gf(z, w) al clauzelor {Gf(z, w)}, {Gf(z, w)}

    este ntruct am obinut , "x(FxGx) "xFx "xGx

    32

  • 5/26/2018 2 Logica Predicatelor de Ordinul I

    33/45

    Probleme ale formalizrii

    33

    Propoziiacategoric

    Forma logic Formula

    Toi Fsunt G Pentru orice x, dacxeste Fatunci xeste G

    "x(FxGx)

    Nici un Fnu este G Pentru orice x, dacxeste F, atunci xnu

    este G

    "x(Fx Gx)

    Unii Fsunt G Existcel puin un x

    astfel nct xeste Fixeste G

    $x(Fx& Gx)

    Unii Fnu sunt G Existcel puin un xastfel nct xeste Fi

    xnu este G

    $x(Fx& Gx)

  • 5/26/2018 2 Logica Predicatelor de Ordinul I

    34/45

    Probleme ale formalizriin Orice informatician priceput este specialist apreciat

    1. Fx= xeste informatician Hx= xeste specialist

    Gx= xeste priceput Ix= x este apreciat2. Pentru orice x, dacFxi Gx, atunci Hxi Ix3. "x[(Fx& Gx) (Hx& Ix)]

    n Tot ce-i bun este ilegal, imoral sau ngra

    1. Fx= xeste bun Hx= xilegalGx= xeste imoral Ix= xngra

    2. Pentru orice x, dacFx, atunci Gxsau HxsauIx3. "x[Fx (GxHxIx)]

    34

  • 5/26/2018 2 Logica Predicatelor de Ordinul I

    35/45

    Probleme ale formalizriin Deputaii i senatorii primesc indemnizaie

    1. Fx= xeste deputat Hxy= xprimete y

    Gx= xeste senator Iy= y este indemnizaie2. Pentru orice x, dacFxsauGx, atunci existyastfel nct Iyi Hxy3. "x[(FxGx) $y(Iy& Hxy)

    Dacam fi pus Fx& Gxn loc de FxGx, am fi obinut"x[(Fx&Gx) $y(Iy&Hxy),

    ceea ce ar fi nsemnat c oricine este att deputat, ct isenator (n acelai timp) primete indemnizaie

    35

  • 5/26/2018 2 Logica Predicatelor de Ordinul I

    36/45

    Probleme ale formalizriin Orice guvern adopthotrri i ordonane

    1. Fx= xeste guvern Hy= yeste hotrre

    Gxy= xadopty Iy= y este ordonan2. Pentru orice xexistyastfel nct dacFxi (Hysau Iy),atunci Gxy3. "x$y{[Fx& (HyIy)] Gxy}

    Dacam fi pus "yn loc de $y, am fi obinut"x"y{[Fx& (HyIy)] Gxy},

    ceea ce ar fi nsemnat corice guvern adopttoate hotrrilei ordonanele din univers.

    36

  • 5/26/2018 2 Logica Predicatelor de Ordinul I

    37/45

    Analiza bazelor de date n LPOIn O bazde date (sau bazde cunotine) este o

    colecie de fapte i reguli

    n

    Un fapt enuno informaie care este necondiionatadevratdespre o situaie de interesn O regul enuno informaie care este condiionat

    adevratdespre o situaie de interesn Bazele de date pot fi utilizate punndntrebri despre

    informaiile pe care le conin

    37

  • 5/26/2018 2 Logica Predicatelor de Ordinul I

    38/45

    Analiza bazelor de date n LPOIn BD1: 1. Anca este mama Ioanei fapt

    2. Anca este n via fapt3. Orice mam este printe regul4. Orice printe n via este mai

    n vrst dect progenitura sa regul

    n BD1n LPOI:1. Mam(Anca,Ioana)2. n via(Anca)3. "x"y(Mam(x,y) Printe(x,y))4. "x"y((Printe(x,y) & n via(x)) n

    vrst(x,y))

    38

  • 5/26/2018 2 Logica Predicatelor de Ordinul I

    39/45

    Analiza bazelor de date n LPOIn ntrebare: Anca este mai n vrst dect Ioana?

    n Avem de demonstrat:n vrst(Anca,Ioana) el

    n Aducem la FC:1. {Mam(Anca,Ioana)}2. {n via(Anca)}3. {Mam(x,y),Printe(x,y)}4. {Printe(z,w),n via(z)),n vrst(z,w)}5. Negaia elului: {n vrst(Anca,Ioana)}

    39

  • 5/26/2018 2 Logica Predicatelor de Ordinul I

    40/45

    Analiza bazelor de date n LPOI1. Unificm literalii

    Mam(Anca,Ioana), Mam(x,y), Printe(x,y)prin x/Ancai y/Ioana:

    {Mam(Anca,Ioana)}, {Mam(Anca,Ioana), Printe(Anca,Ioana)}

    2. Rezolventul n Mam(Anca,Ioana) din clauzele obinute n 1 este{Printe(Anca,Ioana)}

    3. Unificm literaliiPrinte(Anca,Ioana), Printe(z,w), n via(z),n vrst(z,w)

    prin z/Ancai w/Ioana:{Printe(Anca,Ioana)}, {Printe(Anca,Ioana), nvia(Anca), n vrst(Anca,Ioana)}

    40

  • 5/26/2018 2 Logica Predicatelor de Ordinul I

    41/45

    Analiza bazelor de date n LPOI{Printe(Anca,Ioana)}, {Printe(Anca,Ioana), nvia(Anca), n vrst(Anca,Ioana)}

    4. Rezolventul n Printe(Anca,Ioana) din clauzele obinute n 3 este{n via(Anca),n vrst(Anca,Ioana)}

    5. Rezolventul n n via(Anca) din {n via(Anca)}i clauzele obinuten 4 este

    {n vrst(Anca,Ioana)}

    6. Rezolventul nn v

    rst(Anca,Ioana) din negaia elului, {

    nvrst(Anca,Ioana)}i clauza obinutn 5 este

    ntruct am obinut , din BD1 rezultcAnca este mai n vrstca Ioana

    41

  • 5/26/2018 2 Logica Predicatelor de Ordinul I

    42/45

    Analiza bazelor de date n LPOIn ntrebare: Fa de cine este Anca mai n vrst?

    n Avem de demonstrat:$xn vrst(Anca,x) el

    n Negaia elului: $xn vrst(Anca,x)

    n FC:1. {Mam(Anca,Ioana)}2. {n via(Anca)}3. {Mam(x,y),Printe(x,y)}4. {Printe(z,w),n via(z)),n vrst(z,w)}5. Negaia elului: {n vrst(Anca,u)}

    42

  • 5/26/2018 2 Logica Predicatelor de Ordinul I

    43/45

    Analiza bazelor de date n LPOIn n pasul 5 de mai sus am obinut

    {n vrst(Anca,Ioana)}

    n Unificm literaliin vrst(Anca,Ioana), n vrst(Anca,u)

    prin u/Ioana:

    {n vrst(Anca,Ioana)}, {n vrst(Anca,Ioana)}

    Rezolventul n n vrst(Anca,Ioana) din aceste dou

    clauze este n ntruct demonstrarea elului a cerut u/Ioana, rspunsul la

    ntrebarea puseste Ioana

    43

  • 5/26/2018 2 Logica Predicatelor de Ordinul I

    44/45

    Analiza bazelor de date n LPOIn ntrebare: Cine este mai n vrst fa de cine?

    n Avem de demonstrat:$x$yn vrst(x,y) el

    n Negaia elului: $x$yn vrst(x,y)

    n FC:1. {Mam(Anca,Ioana)}2. {n via(Anca)}3. {Mam(x,y),Printe(x,y)}4. {Printe(z,w),n via(z)),n vrst(z,w)}5. Negaia elului: {n vrst(u,v)}

    44

  • 5/26/2018 2 Logica Predicatelor de Ordinul I

    45/45

    Analiza bazelor de date n LPOIn n pasul 5 de mai sus am obinut

    {n vrst(Anca,Ioana)}

    n Unificm literaliin vrst(Anca,Ioana), n vrst(u,v)

    prin u/Anca, v/Ioana:

    {n vrst(Anca,Ioana)}, {n vrst(Anca,Ioana)}

    Rezolventul n n vrst(Anca,Ioana) din aceste dou

    clauze este n ntruct demonstrarea elului a cerut u/Anca, v/Ioana,

    rspunsul la ntrebarea puseste Anca este mai nvrst dect Ioana

    45