DATALOG
12
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
12
pages
Français
Ebook
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
tp, Supérieur, TP
Voir
- cours - matière potentielle : n°
- sémantique logique
- vérité de proplog…
- interprétation de herbrand
- ttftttftt …
- faiblesses de proplog proplog
- portée de qx dans qx
- bp
- atomes
- atome
- variable
- variables
- interprétation
- interprétations
NFP120 ---
an 8
Spécification Logique et Validation des Programmes Séquentiels
Cours n° 4
DATALOG
Nouvelle Syntaxe(informelle)
1
3 alphabets : Variables,Constantes et Prédicats Variables, ... }, X2 = {X1 : V Constantes :D = {a , b , c , ... } (univers du discours , univers de Herbrand) Prédicats{p , q , ... }: P = les prédicats sont des fonctions qui retournent T ou F les prédicats sont des noms de relation Les atomes de DATALOG sont de la forme : P(t1 , … , tn) où p est un prédicat d’arité n et où chaque ti (1<=i<=n) est un terme (variable ou constante)
3
Faiblesses de ProPlog
ProPlog permet d'exprimer paul_en_tp_CDI :- paul_a_CDL, paul_a_Syst . john_ en_tp_CDI :- john_a_CDL, john_a _Syst. ... mais pas ‘pour toutétudiant quelconque’ étudiant__en_tp_CDI:-étudiant__a_CDL,étudiant__a_Syst. où, le Domaine d'intérêt étant les étudiants, représentés par l'ensemble des constantesXÎ{ paul, john,...} "X :Xen_tp_CDI :- X a_CDL, X a_Syst. où , plus proche de la syntaxe fonctionnelle ‘classique’ : "X en_tp_CDI(X) :- a_CDL (X), a_Syst (X) . Cette règle doit avoir même sémantique que le programme ProPlog obtenu par les clauses propositionnelles construites avec tous les noms d'étudiants ci-dessus.
Nouvelle Syntaxe(informelle) 2
2
Domaine :(univers du discours)D = {a , b , c , ... } Variables, ... }, X2 = {X1 : V Prédicats, ... }{p , q : P =
constante::=élément de D variable::=élément de V symb_préd::=élément de P Définitions : terme ::= constante | variable atome ::= symb_préd'(' terme1','...',' termen')' clause ::= fait | règle fait ::= atome '.' règle ::= tête ':-' queue '.' tête ::= atome queue ::= atome | atome ',' queue
4
Syntaxe abstraite
(1) Catégories syntaxiques progr ,... : PROGRAMME a,b,c,... : D (Domaine du discours) X,Y,Z,... : V (Variables) t,t1,t2,... : T = D U V (Termes) p,q,r,... : P (Symboles de Prédicat) at,at1, ... : A (Atomes) cl,cl1, ... : Clause q,q1,q2, ... : Queue lt,lt1, ... : LT (Liste de Termes) (2) Définitions progr ::= cl | cl progr cl ::= at ‘.’ | at ‘:-’ q ‘.’ q ::= at | at ‘,’ q at ::= p’(’ lt ’)’ | a lt ::= t | t ‘,’ lt t ::= a | x
Attention notation post fixée
5
ATTENTION :notation post-fixée:= µ {X1 -> a, X2 -> b} µ (r(X1,X2) :- p(X1), r(X2,X3)) = (r(X1,X2)) :- (p(X1)) , (r(X2,X3)) µ µ µ = µ µ µ = r(X1,X2) :- p(X1) , r(X2,X3) r(a,b) :- p(a), r(b,X3)
Instance close par l’ instanciation µ q(a,b) :- p(a),p(b).( pas de variables)
7
Instanciation / Affectation / Liaison
Instanciation des variables(ou état): Fonction de l'ensemble des variables dans l'ensemble des constantes du domaine: :V |-> D µ exemple := µ {X1 -> a, X2 -> b} //liaisons On étend cette notion d'instanciation à : Instanciation d'une formule :
( r(X1,X2) :-
p(X1) = , r(X2,X3) )µ ( r(a,b) :- p(a), r(b, X3) )
Sémantique du Point Fixe
Sémantique de chaînage Avant
6
8
Sémantique du point fixe
Remarque : notation : q(t) pour q(t1,...,tn) Soit un programmePet calculer DEN (P): pf 1. choisir une règle deP: q(t):- q1(t1) ,..., qn(tn)
2. choisir une instanciation µ donnant une instance close de cette règle
3. si l’ensemble : {q1(t1) , ... , qn(tn }ÍDEN (P) courante µ)µ pf alors ajouter q(t) DEN (P) courante µ pf
4. q(t) est dans l'ensemble dénoté parPmoins un calcul luisi au µ assigne q(t) µ
Sémantique Logique
9
1 1
Sémantique du point fixe 2
exemple:(chaque formule est universellement quantifiée) p(a). p(c). r(b). q(X1,X2) :- p(X1),p(X2).
Sémantique de chaînage avant (ou du point fixe) : DEN (P) ={p(a) , p(c) , r(b) , q(a,a) , q(a,c) , q(c,a) , q(c,c)} pf
Sémantique logique :Interprétations
Soit C la clause DATALOG :p(c,X) :- g(X,n,c). Interprétation du programmeur A: I(c) : le chat a I(n) : : la nourriture a I(p(U,V)) =I: U aime V(p) (U,V) a a I(g(U,V,Z)) =IZ: U donne V à (g) (U,V,Z) a a Interprétation du programmeur B: I(c) : : l'entier 10 b I(n): : l'entier 5 b I(p(U,V)) =I: U est inférieur à V(p) (U,V) b b I(g(U,V,Z))=I(g) (U,V,Z): U + V est supérieur à Z b b
1 0
1 2
Satisfaction
Dans le monde A :Le chat aime toute personne qui lui« C : donne de la nourriture » L'interprétation A semble satisfaire la clause C en effet, l'interprétation A est un modèle de C : |="<- g(X,c,n))|= (l(c,X) X.(l(c,X) <- g(X,c,n)) ssi m pour toutm, instanciation des variables de la clause dans le domaine deI a
Dans le monde B :)»01>X<>5=01(X+X.«C: L'interprétation B ne satisfait pas la clause C: En effet il est possible de trouver une instanciation de X dans le domaine deItelle que la b formule soit fausse dans le monde de B exemple X = 6. Donc C peut être vraie dans certaines interprétations (ex: A) et fausse dans d'autres (ex: B).
Interprétation
Une interprétationIest la donnée • d'une structure algébrique <D, {}, {R1, R2, ...,Rn}> • d'une assignation-fonction i(notée également par abus de langage) I qui a toute constante assigne un elément de D ex:paul -->
claude -->
1 3
qui a tout prédicat d'arité n du langage , assigne une relation n-aire de la structure algébrique
ex: en_tp_CDI/1 --> en_tp_CDI = { , }
(autre définition : à tout symbole de prédicat n-aire on assigne n une fonction de D dans {T , F}(domaine sémantique des Booléens)
1 5
Structure algébrique
Triplet : Domaine + ensemble de fonctions + ensemble de relations exemples: < D = { , , ...} , F = {}, R = {AIME = {( , ), ( , ) , ( , ) }, en_tp_CDI = { , } } > < D = l'ensemble des chats, F = {}, R = { AIME = {...}, DONNE_A = {...} } > < D = N, F = {PLUS = {(0,0)->0, (0,1)->1,...}}, R = {INF ={(0,1),(0,2),...},SUP = {(1,0),...}} >
Sentence - formule close
1 4
Q étant un des quantificateurs{" , $} .la portée de QX dans QX.W est W . On dit que QX quantifie toute occurrence de X dans W qui ne soit déjà derrière un quantificateur de W ou dans sa portée ex :"X.($B(X))X. A(X) <- .Une occurrence de X est liée SSI elle est derrière un quantificateur ou dans sa portée . Sinon l'occurrence est libre ex :$Y. pere(Y,X) <- enfant(X) liée libre .Une sentence (ou formule close) est une formule bien formée (f.b.f.) dont toutes les occurrences de variables sont liées ex :"X.($Y.(pere(Y,X) <- enfant(X)) )
1 6
Satisfaction des sentences
une interprétation Soit I |= en_CDL(paul) ssi I (paul) =Îen_CDL(cf. Calcul Propositionnel) I |= ¬ W ssi |¹W I I
|= I
|= I
|= I
W1Ùet |=|= W1 W2 ssi II
W1 v W2 ssi |= W1 ou |= II
W1 <- W2 ssi si |= I
W2
W2
W2 alors |= I
Interprétation algébrique
W1
1 7
Interprétation : structure algébrique : domaine d'interprétation, ensemble de fonctions et ensemble de relations
Exemple : Den(P) = < {paul,john,claude}, {}, {ETUDIANT , A_INFO_GENE, A_MATH_GENE ,EN_INFO_PROG } > avec les relations ETUDIANT = { paul, john, claude }, A_INFO_GENE = { paul, john, claude }, A_MATH_GENE = { paul, john }, EN_INFO_PROG = { paul, john } associées à chaque symbole de prédicat.
1 9
Satisfaction des sentences (2)
Quantificateurs :
|="SSI quelque soit l'instanciation(X) .W mde X (libre I dans W) par un élément du domaine: |= (W)m I
|=$SSI pour au moins une instanciation(X) .W mde X I (libre dans W) par un élément du domaine: |= (W)m I
Evaluation
Une interprétation :I = < D={a1,a2,...}, {...},{...}>et une instanciationµ = {X1 --> a2,...}( valeur d'état des variables dans le domaine de l'interprétation) étant données :
l'évaluation d'un terme t par une interprétation I et une instanciationµ, (notéeval(I,µ)(t))est définie parval(I,µ)(X) = µ(X)et pour toute constante parval(I, µ)(c) = I(c)
1 8
2 0
Interprétation
Rappel : Interprétation < D, {}, {R1, R2, ..., Rn} >
< D = { , , ...} , F = {}, R = {en_tp_CDI = { }, ETUDIANT = { , } } >
Interprétation de Herbrand(2) Univers de Herbrand Up :Ensemble des constantes du programme (domaine) Up = {paul,john,claude} Base de Herbrand Bp :Ensemble des instances closes des atomes du programme Bp = { etudiant(paul), ..., a_CDL(paul), ..., ... en_tp_CDI(john), en_tp_CDI(claude } Interprétation de Herbrand : Sous-ensemble de Bp par exemple : Bp elle-même ou I ={ etudiant(paul), etudiant(john), a_CDL(paul), a_CDL(john), a_MATH1(paul), a_MATH1(john),
en_tp_CDI(paul) }
Cela revient à assigner la valeur T (true) aux seuls atomes de Den(P)
2 1
2 3
Interprétation de Herbrand
< D = Up= {paul,john,claude}, F = {}, R = {en_tp_CDI = {paul}, ETUDIANT = { paul,john } } > notée également : < D = Up= {paul,john,claude}, F = {}, I = {en_tp_CDI(paul), ..., etudiant(paul), etudiant(john)} >
modèle de Herbrand
2 2
exemple :Pp(a). p(c). r(Y). q(X1,X2) :- p(X1),p(X2). -modèles dep(a): toute interprétation qui contientp(a) exemples :{ }Bp ou pa) -modèles der(Y) :( c'est-à-dire de") toute interprétation qui Y.r(Y) contientr(c), ...pour toute constantec de Up -modèles de"x1,x2.q(x1,x2) <- p(x1)Ùp(x2)toute interprétation I telle que pour toute instancem, si p(X1).met p(X2).m, sont dans I alors q(X1,X2).m s'y trouve également exemple :Bp -modèle deP:Interprétation qui est un modèle de toutes les clauses deP exemple :, r(c) , q(a,a) , q(a,c) , q(c,a) ,, r(a) , r(b) Den(P) ={ p(a) , p(c) Bp ou q(c,c) }
2 4
2 7
2 8
T
T
F
F
2 6
F
Si Up = {a,b,c}
Den(P) = { p(a) , p(c), r(a) , r(b) , r(c) , q(a,a) , q(a,c) , q(c,a) , q(c,c) }
T
…
F
T
F
Le plus petit modèle de Herbrand est la sémantique logique et est identique à la sémantique du point fixe
retour sur ProPlog
(SLD)
r(c)
2 5
Sémantique logique : PPM de Herbrand
on peut faire le lien entre interprétation de Herbrand et table de vérité de ProPlog
T
Interprétation de Herbrand et ProPlog
F
F
p(c)
r(a)
T
F
F
F
T
T
…
p(a)
T
q(a,a) q(a,c)
opérationnelle
q(c,a) q(c,c)
T
T
F
T
Sémantique
T
T
r(b)
T
T
p(a). p(c). r(Y). q(X1,X2) :- p(X1),p(X2). Il existe au moins un modèle de Herbrand deP :Bp Bp = { p(a) , p(b), p(c), r(a), r(b) ,r(c), q(a,a), q(a,b), q(a,c), q(b,a), q(b,b), q(b,c), q(c,a), q(c,b) , q(c,c) } Il existe un plus petit modèle de Herbrand deP Den(P)= { p(a) , p(c), r(a), r(b) ,r(c), q(a,a), q(a,c), q(c,a), q(c,c) }
exemple :P p(a). p(c). r(Y). q(X1,X2) :- p(X1),p(X2).
Substitution
Une substitution est une fonctiondde l'ensemble des variables dans l'ensemble des termes . Termes = ConstantesUVariables Exemple :d= { X-> Z, Y -> b}
Le couple X->Z est appelé "liaison" (binding) de X Exemple : Soit F la clause :p(X) , q(X,Y) :- r(Y,Z) F.d:- p(X), r(Y,Z) ).= (q(X,Y) d = q(X,Y).d:- p(X).d, r(Y,Z).d = q(Z,b) :- p(Z), r(b,Z)
une substitution { Xi-> ti, ... } est dite pure si tous les ti sont des variables(d: V -> V) une substitution est dite close (fermée) si c'est une instanciation
C :
Exemple
anc(X,Y) :- par(X,Z), anc(Z,Y)
<= {X -> Y, Y -> U, Z -> V} d= {Y ->jean, U -> T, V -> T, X -> rené } <°d= { X -> Y.d, Y -> U.d, Z -> V.d, U -> T, V -> T } <°d= { X -> jean, Y -> T, Z -> T, U -> T, V -> T }
C.<°d :anc(jean,T) :- par(jean,T), anc(T,T) on obtient le même résultat par étape : C.<:- par(Y,V), anc(V,U) : anc(Y,U) puis (C.<).d :anc(jean,T) :- par(jean,T), anc(T,T)
2 9
3 1
Composition de substitutions
Soient<etd2substitutions
Leur composition
: (ATTENTION :)opf-tseéxi
<°d
correspond à l'application de<puis ded :F.<°d= (F.< !&d
<
d
= {X1 -> t1, ..., Xn -> tn}
= {Y1 -> t1', ..., Yp -> tp' }
<°d
= {X1 -> t1.d, ..., Xn -> tn.d,,Y1 -> t1', ..., Yp -> tp' }
dans laquelle on a supprimé les
Xi -> ti&d&Xi = titels que &d&/// (X -> X) et où ne figurent pas les Yj -> tj' tels que YjÎ{X1, ...,Xn }
Variante
E et F deux expressions sont des variantes l'une de l'autre
s’il existe<,s,2 substitutions telles que E = F.<et F = E .s
exemple:et E=p(U,V)F= p(X,Y) avec<= {X -> U, Y -> V} ets= {U ->X, V -> Y }
contre-exemple: p(X,Y) et p(U,U)
3 0
3 2
Renommage
Soient E une expression , V l'ensemble de ses variables un renommage de E est une substitution pure {X1 -> Y1, ..., Xn -> Yn} telle que {X1 , ..., Xn } inclu dans V les Yi sont toutes distinctes (V- {X1 , ..., Xn })Ç{Y1 , ..., Yn } =Æ Donc,on ne peut pas projeter les Xi sur d'autres variables de l'expression E, mais rien n'empêche de permuter des Xi
Si E et F sont des variantes, alors il existe des renommages<et stels que E = F.<et F = E .s
Unification
: une liste d'atomes, q1(t) ,..., qn(t) une substitution<telle queq1(t).<= ... = qn(t).<est appelée unificateur de q1(t) ,..., qn(t)
Si un tel unificateur existe, les atomes sont dits unifiables
exemple: soient les 3 atomes : {p(X,b,Z) , p(Y,W,a) , p(Y, b, Z)} < = { W --> b, X --> c, Y --> c, Z --> a }donne la même instance
3 3
p(c,b,a)
3 5
Substitution plus générale
<etsdeux substitutions : <est dite plus générale ques SSI il existelune substitution telle que : <°l=s (<est "un peu moins instanciée" ques) Cette relation n'est pas anti-symétrique ATTENTION : 2 substitutions<et<peuvent être telles que 1 2 <est plus générale que< 1 2 <est plus générale que< 2 1 à un renommage près (voir variantes)
Unificateur le plus général :mgu
jest l' Unificateur le plus général, le mgu (most general unifier) d'un ensemble d'atomes SSI quelque pour tout autre unificateur<il existe une substitutionstelle quej°s=<
3 4
3 6
Unificateur le plus général :mgu (2)
Exemple précédent :, p(Y, b, Z)}{p(X,b,Z) , p(Y,W,a) <= { W --> b, X --> c, Y --> c, Z --> a}n'est pas un mgu
j={ W --> b, X --> Y,Z --> a }est le mgu En effets= {Y -> c}est telle quej°s=< :
Si au moins un unificateur existe alors le mgu existe.
Algorithme d'unification
/* entrée: 2 expressions L = g(t1,...tn) et M= g'(t1',...tm') sortie: J= mgu(L,M) v échec */ ¹¹ if (g g' v n m) then return échec; else{J:= {}; i := 1; unif:= true; ¹ repeat if (ti.J ti'.J) then{ if (ti'.J est une variable) then{ J:= J°{ti'.J -> ti.J } }else{ if (ti.J est une variable) then{ J:= J°{ti.J -> ti'.J} }else{ unif := false; i := i+1; } }// sinon (ti.J == ti'.J) until (i > n v NOT unif); if unif then return J else return échec;}
3 7
3 9
Exemples
L = p(X,a,Z) M = p(V,W,b) Les substitutions - unificateurs de L et M sont : < 1= {X -> a, Z -> b, V-> a, W -> a}
< (
< )
< 4
< +
= {X -> b, Z -> b, V-> a, W -> a}
= {X -> V, Z -> b, W -> a}
= {X -> c, Z -> b, V-> c, W -> a}
= {X -> U, Z -> b, V-> U,W -> a, U-> K}
contre-exemple: unifiables
N = q(X,a,X,b)
et
M = q(Y,a,a,Y)
Exemple d'unification
L = p(X, Z, a, U)
M = p(Y, Y, V, W)
ne sont pas
Calcul de mgu(L, M) : <1= {} <(= {Y -> X } <-> X }°{X -> Z} = {Y -> Z , X -> Z}= {Y ) <4-> Z , X -> Z}°{V -> a} = {Y -> Z , X -> Z, V -> a }= {Y <-> Z , X -> Z, V -> a }°{W -> U}= {Y + = {Y -> Z , X -> Z, V -> a, W -> U }
=
mgu(L,M)
3 8
4 0
Rappel : on cherche à résoudre?- q (t) ,..., q (t). 1 n (iii) Si on arrive à :(?- .)jalorsSUCCES
j La restriction de aux seules variables de la question initiale est dite
5
15
i.e. le but initial :?- q ,...,q .est résolu pour la substitutionj(composition de 1 n toutes les substitutions de la branche succès).
5 6 7
4
1 2 3
?- et(paul), en_info_gene(paul), amg(paul)
1 {X --> paul} ?-en_info_prog(paul)
Arbre de recherche
Réponse calculée ou Substitution réponse
4 1
4 4
Exemple
echec
?- et(john), en_info_gene(john), amg(john)
?- en_info_gene(john), amg(john)
echec
echec
echec
SLD-résolution
SLD-résolution(2)
?- m(X), eIP(X) X = paul ; X = john ; No ?- eIP(claude). yes
amg(paul). amg(john). amg(claude).
aig(paul). aig(olivier). aig(john). aig(claude).
et(paul). et(john). et(claude).
succès {X --> paul}
4 2
?- en_info_gene(paul), amg(paul)
m( paul). m( olivier). m( john).
15
8 9 10 11
4 3
10
succès {X --> john}
10
?- amg(john)
?- amg(paul)
13
POUR résoudre?- q (t) ,..., q (t). 1 n (i) Choisir unq (t)(règle d'évaluation ou de sélection du littéral) i si (aucune règle renommée n'a une têteq (t')qui s'unifie avecq (t))alors i i échec(q (t)n'est pas dans Den(P)); i (ii)sinon choisir une de ces règles et soit :d= mgu(q (t),q (t')) i i (règle de recherche ou de sélection de la clause) si (cette règle est un fait) alors s’efface et la résolvante devient qi(t) d d d d ?- q1. ,...,qi-1. ,qi+1. ,...,qn. . sinon soit cette règle , et la résolvante devient qi:- r1,...,rm d d d d d d ?-q1. ,...,qi-1. ,r1. ,...,rm. ,qi+1. ,...,qn. oud ?-(q1,..,qi-1,r1,..,rm,qi+1,..,qn.)
8
2 {X --> olivier} ?-en_info_prog(olivier)
?-m(X),en_info_prog(X)
15
?- et(olivier,) en_info_gene(olivier), amg(olivier)
echec
echec
echec
Et donc , Équivalence des sémantiques
P|- (q ,...,qn).j<==>P|= (q1,...,qn).j sld1
eIP(X) :- et(X), aig(X), amg(X) .
f( claude).
3 {X --> john} ?-en_info_prog(john)
12 13 14
6
15
© 2010-2024 YouScribe
