2 logica predicatelor de ordinul i
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