Búsqueda de cláusulas del programa: noción de generalidad
El conjunto de las cláusulas es un retículo
C1 es más general que C2 iff para alguna sustitución ?: C1 ? ? C2
especialización: aplicar una sustitución y/o añadir un literal
generalización: aplicar una sustitución inversa y/o eliminar un literal
m(X,Y)
m(X,X)
m(X,[Y|Z])
m([X|Y],Z)
m(X,Y):-m(Y,X)
m(X,[X|Z])
m(X,[Y|Z]):-m(X,Z)
Búsqueda de cláusulas del programa: noción de generalidad
Una teoría G es más general que una teoría S iff G ?= S
G ?= S: en cada interpretación en la que G es cierto, S también lo es
“G implica lógicamente S”
Todas las frutas saben bien ?= Todas las manzanas saben bien
(asumiendo que las manzanas son frutas)
Búsqueda de cláusulas del programa: deducción versus inducción
Hay operadores deductivos ?- que implementan (o aproximan) ?=
resolución
Invertir estos operadores conduce a operadores inductivos
Técnica básica en muchos sistemas de programación lógica inductiva
Búsqueda de cláusulas del programa: varios marcos para la generalidad
Dependiendo de la forma de G y S
1 cláusula / cjto de cláusulas / cualquier teoría de primer orden
Dependiendo en el mecanismo deductivo ?- a invertir
Theta-subsunción
Resolución
Implicación
Métodos Bottom-up: theta-subsunción (Plotkin)
Subsunción
Sustitución: ? = {X1/t1,…,Xn/tn} es una asignación de los términos ti a las variables Xi
Subsunción: Sean C y D cláusulas.
C (?-)subsume D (C =? D) iff existe ? tal que C? ? D
Ejemplo: p(a,b)? r(b,a) es subsumida por p(X,Y)? r(Y,X)
p(X,Y)? r(Y,X) subsume p(X,Y)? r(Y,X),q(X)
Métodos Bottom-up: theta-subsunción (Plotkin)
Ejercicio: C1: father(X,Y) ?parent(X,Y).
C2: father(X,Y) ?parent(X,Y),male(X).
C3: father(luc,Y) ?parent(luc,Y).
C1 =? C2 (? ={ })
C1 =? C3 (? ={X/luc})
C2 =/? C3
C3 =/? C2
Métodos Bottom-up: theta-subsunción (Plotkin)
Ejercicio: C1: p(X,Y) ?q(X,Y).
C2: p(X,Y) ?q(X,Y),q(Y,X).
C3: p(Z,Z) ?q(Z,Z).
C4: p(a,a) ?q(a,a).
C1 =? C2 (? ={ })
C1 =? C3 (? ={X/Z,Y/Z})
C1 =? C4 (? ={X/a,Y/a})
C3 =? C4 (? ={Z/a})
Métodos Bottom-up: theta-subsunción (Plotkin)
Ejercicio: C1: p(f(X),g(X)) ?
C2: p(f(3),g(3)) ?
Ejercicio: C1: p(f(X),g(X)) ?
C2: p(f(3),g(Y)) ?
C1 =? C2 (? ={X/3})
C1 =/? C2 C2 =/? C1
Métodos Bottom-up: theta-subsunción (Plotkin)
Propiedades de la Q-subsunción
Correcta: si C =< D entonces C |= D
Incompleta: puede que C |= D y sin embargo C =/< D
C: p(f(X)) ? p(X)
D: p(f(f(X))) ? p(X)
Reflexiva, transitiva y antisimétrica
? relación de semi-orden
clases de equivalencia con un orden parcial
c1?c2 sii c1 =< c2 y c2 =< c1
Si c?[C] y d?[D] ? c =< d ó d =< c ó (c =/< d y d =/< c)
Métodos Bottom-up: theta-subsunción (Plotkin)
Las clases de equivalencia forman un retículo
p(X,Y) :- m(X,Y),r(X)
p(X,Y) :- m(X,Y), m(X,Z),r(X)
…
p(X,Y) :- m(X,Y),s(X)
p(X,Y) :- m(X,Y), m(X,Z),s(X)
…
p(X,Y) :- m(X,Y)
p(X,Y) :- m(X,Y), m(X,Z)
p(X,Y) :- m(X,Y),m(X,Z),m(X,U)
…
p(X,Y) :- m(X,Y),s(X),r(X)
p(X,Y) :- m(X,Y), m(X,Z),s(X),r(X)
…
lgg
glb
Métodos Bottom-up: generalización menos general – lgg (Plotkin)
Generalización menos general (lgg)
C es la generalización menos general (lgg) de D bajo ?-subsunción
si C =? D y para cada E tal que E =? D se cumple E =? C.
Computación de lgg
Cuando nos restringimos a átomos con el mismo signo y
el mismo símbolo de predicado (compatibles) la lgg es el
dual de la unificación
lgg(f1(l1,…,ln),f2(m1,…,mn)
= v si f1? f2
= f1 (lgg(l1,m1),…,lgg(ln,mn)) si f1= f2
Métodos Bottom-up: generalización menos general – lgg (Plotkin)
Ejemplo:
l = member(3,cons(2,cons(3,nil)))
l’ = member(3,cons(4,cons(5,cons(6,nil))))
m = member(3,cons(v2,4,cons(v3,5,vnil,cons(6,nil))))
m = member(3,cons(x,cons(y,z)))
Métodos Bottom-up: generalización menos general – lgg (Plotkin)
Ejercicio l: p(f(5,3),g(2,3))
l’: p(f(1,2),g(3,2))
l’’: p(f(1,4),g(5,4))
lgg = p(f(X,W),g(Y,Z))
Métodos Bottom-up: generalización menos general – lgg (Plotkin)
Sean C y D dos cláusulas. El lgg de C y D en el
orden de subsunción es
lgg(C,D)= ?lgg(l,m) | l?C y m?D y
l y m son compatibles}
Dadas dos cláusulas, el lgg es la cláusula simple más específica que es mas general que ambas.
Ejemplo: f(t,a)? p(t,a), m(t),f(a)
f(j,p)? p(j,p), m(j),m(p)
lgg = f(X,Y) ? p(X,Y),m(X),m(Z)
Métodos Bottom-up: generalización menos general – lgg (Plotkin)
Ejemplo rev([2,1],[3],[1,2,3])? rev([1],[2,3],[1,2,3])
rev([a],[ ],[a])? rev([ ],[a],[a])
Ejercicio a([1,2],[3,4],[1,2,3,4])? a([2],[3,4],[2,3,4])
a([a],[ ],[a])? a([ ],[ ],[ ])
lgg = rev([A,B],C,[D|E]) ? rev(B,[A|C]),[D|E])
A B C D E B A C D E
lgg = a([A|B],C,[A|D]) ? a(B,C,D)
Métodos Bottom-up: generalización menos general – lgg (Plotkin)
Ejercicio m(c,[a,b,c])? m(c,[b,c]), m(c,[c])
m([a],[a,b])? m(a,[a])
lgg = m(P,[a,b|Q]) ? m(P,[R|Q]),m(P,[P])
Métodos Bottom-up: generalización menos general relativa- rlgg (Plotkin)
Generalización menos general relativa (rlgg)
relativa a la teoría de conocimiento B
rlgg(e1,e2)=lgg(e1?B,e2?B)
Ejemplo: C1: uncle(X,Y):-brother(X,father(Y)).
C2: uncle(X,Y):-brother(X,mother(Y)).
B: parent(father(X),X).
parent(mother(X),X).
lgg(C1,C2) = uncle(X,Y):-brother(X,Z).
rlgg(C1,C2) = uncle(X,Y):-brother(X,U),parent(U,Y).
Métodos Bottom-up: generalización menos general relativa- rlgg (Plotkin)
Una cláusula C es más general que D con respecto a una
teoría T si T ? C |- D.
Un átomo A es una lgg de un átomo B con respecto a
una teoría T si existe un unificador ? tal que
T |- A? ? B (A=?T B).
Una cláusula C es una lgg de una cláusula D con
respecto a una teoría T (rlgg) si T |- C? ? D para
alguna sustitución ?.
Métodos Bottom-up: generalización menos general relativa- rlgg (Plotkin)
Problema: no siempre existe rlgg de un conjunto de
cláusulas con respecto a una teoría.
C1: q(f(a)).
C2: q(g(a)).
B: p(f(X),Y).
p(g(X),Y).
C : q(X):-p(X,g1(X)),…,p(X,gn(X)) es una generalización
Excepción: rlgg existe siempre si T es básica (GOLEM).
Métodos Bottom-up: generalización de Buntine
rlgg puede conducir a conclusiones contraintuitivas.
EJEMPLO:
C: pequeño(X):-gato(X).
D: muñeco_mascota(X):- de_peluche(X), gato(X).
P: mascota(X):- gato(X).
muñeco_mascota(X):-pequeño(X),de_peluche(X),mascota (X).
C =?P D
Si asumimos que una cláusula C es más general que
otra D si cualquier interpretación de C permite obtener las
mismas conclusiones que con D.
En el ejemplo anterior C no es más general que D.
Métodos Bottom-up: generalización de Buntine
Subsunción generalizada (cláusulas definidas)
Una cláusula C es más general que otra D w.r.t. un
programa P
C =?BP D
si para cualquier interpretación de Herbrand I modelo de P,
entonces TD(I) ? TC(I).
En el ejemplo anterior C y D no pueden compararse
ya que tienen distintas cabezas.
Métodos Bottom-up: generalización de Buntine
Visión operacional
Sean C y D cláusulas con variables disjuntas y sea P un
programa lógico. Sea ? una sustitución que asigna a las
variables de D nuevas constantes (que no aparecen en
C,D ni P).Entonces, C =?BP D sii existe una sustitución ?
tal que:
Chead ? = Dhead ? P ? Dbody ??? ? (Cbody ??)
Métodos Bottom-up: generalización de Buntine
Procedimiento: C es más general que D wrt P si C
puede convertirse en D aplicando repetidamente:
Transformar las variables en constantes o en otros términos
Añadir átomos al cuerpo
Evaluar parcialmente el cuerpo resolviendo cláusulas en P
contra un átomo del cuerpo.
Métodos Bottom-up: generalización de Buntine
Subsunción generalizada versus generalización de Plotkin.
C =?B? D sii C =? D
Subsunción generalizada versus generalización menos
general relativa.
C =?BP D sii C aparece en la raíz de una refutación en
la demostración de P ?? (C ? D)
=?BP un caso especial de rlgg
Métodos Bottom-up: resolución inversa
Resolución
C1 C2
?1 ?2
C
RESOLUCIÓN: C = C1 ? C2
?l1 ? C1 ? l2 ? C2 | C1 y C2 variables disjuntas ?
? = mgu(l1, l2) s.t. l1? = l2?, ? = ?1 ?2 ? l1?1 = l2?2
C=(C1-??l1?)? 1 ? (C2-?l2?)? 2
Métodos Bottom-up: resolución inversa
Ejemplo:
p(X)?q(X) y q(X) ? r(X,Y) conduce a p(X)? r(X,Y)
p(X)?q(X) y q(a) conduce a p(a)
Inversión de la resolución: obtención de C1 (o C2) a partir
de C y C2 (C1). No hay una solución única
EJEMPLO: C2 = B ? E,F
C = A ? E,F,C,D
C1 = A ? B,C,D
C1’ = A ? B,C,D,E
C1’’ = A ? B,C,D,F
C1’’’ = A ? B,C,D,E,F
Métodos Bottom-up: resolución inversa
El problema es aún más agudo para cláusulas de primer
orden
EJEMPLO:
C1 = ? mas_pesado(martillo,pluma)
C = ? mas_denso(martillo,pluma),mas_grande(martillo,pluma)
C2 = mas_pesado(martillo,pluma) ? mas_denso(martillo,pluma), mas_grande(martillo,pluma)
C’2 = mas_pesado(A,B) ? mas_denso(A,B), mas_grande(A,B)
Para generar C2 debemos decidir qué términos se convierten en variables y cómo
Métodos Bottom-up: resolución inversa
El operador V
C1 C2
?1 ?2
C
OPERADOR V: Produce C2 a partir de C y C1
dadas dos cláusulas C1 y C, el V-operador encuentra C2
tal que C es una instancia de un resolvente de C1 y C2.
Generaliza ?C1,C} a ?C1, C2}
Métodos Bottom-up: resolución inversa
Absorción
desde q?A y p ?A,B
inferir p ?q,B
Identificación
desde p?q,B y p ?A,B
inferir q ?A
p?q,B q ?A
p?A,B
p?q,B q ?A
p?A,B
Métodos Bottom-up: resolución inversa
Absorción: el cuerpo de C1 es absorbido en el cuerpo de C (después de una unificación) y reemplazado por su cabeza
EJEMPLO:
C:pajaro(tweety):-tiene_plumas(tweety), tiene_alas(tweety),tiene_pico(tweety).
C1:vuela(X):- tiene_plumas(X),tiene_alas(X).
? = ? X/tweety}
C2:pajaro(tweety):-vuela(tweety), tiene_pico(tweety).
Métodos Bottom-up: resolución inversa
Ejemplo: P={animal(tiburon)
nadar(tiburon)}
e={pez(tiburon)}
Encontrar dos cláusulas que tengan un resolvente del que pez(tiburon) es una instancia
Cláusula de entrada: una cláusula de P
(nadar(tiburon))
Cláusula central: Por ejemplo, la menos general
(pez(tiburon) ? nadar(tiburon))
P |/=e
Métodos Bottom-up: resolución inversa
Cláusula de entrada: una cláusula de P
(animal(tiburon))
Cláusula central: Por ejemplo, la menos general
(pez(X) ? animal)X),nadar(X)).
pez(x) ? animal(x), nadar(x) animal(tiburon)
pez(tiburon) ? nadar(tiburon) nadar(tiburon)
pez(tiburon)
Métodos Bottom-up: resolución inversa
Identificación: identificar parte del cuerpo de C2 en el cuerpo de C a través de una sustitución ?. Encontrar un literal l en el cuerpo de C2 que no ocurre en el de C. La identificación construye C1 con cabeza l y cuerpo la parte de C que no está en C2.
EJEMPLO: C:pajaro(tweety):-tiene_plumas(tweety), tiene_alas(tweety),tiene_pico(tweety).
C2: pajaro(tweety):- vuela(tweety),tiene_pico(tweety).
l: vuela(tweety)
C-C2: { tiene_plumas(tweety), tiene_alas(tweety)}
C1: vuela(tweety):- tiene_plumas(tweety), tiene_alas(tweety).
Métodos Bottom-up: resolución inversa
El operador W
C1 A C2
?C1 ?A,1 ?A,2 ?C2
B1 B2
OPERADOR W
Dadas dos cláusulas ?B1,B2} encontrar ?C1,A,C2} tal que B1 es una instancia de un resolvente de C1 y A, y B2 es una instancia de un resolvente de A y C2.
Generaliza ?B1, B2} a ?C1, A,C2}
Métodos Bottom-up: resolución inversa
Intra-construcción
desde p?A,B y p ?A,C
inferir q ?B y p?A,q y q?C
Inter-construcción
desde p?A,B y q ?A,C
inferir p ?r,B y r?A,q y q?r,C
p?r,B r ?A q ?r,C
p?A,B q?A,C
q?B p ?A,q q ?C
p?A,B p?A,C
Métodos Bottom-up: resolución inversa
Cuando l no está ni en B1 ni en B2, el operador W se inventa predicados.
Métodos Bottom-up: implicación inversa
Sean dos cláusulas C y D. decimos que C implica D
(C ? D) iff cada modelo de C es modelo de D (C ?? D).
C es una generalización bajo implicación de D.
la generalización bajo ?–subsunción es incompleta.
C ?? D y C =/? D
Inversión implicación es una forma completa de generalización.
? indecidible
? computacionalmente caro
? cláusulas recursivas
Métodos Bottom-up: implicación inversa
Diferencia entre implicación y ?–subsunción: cláusulas ambivalentes.
Una cláusula es ambivalente sii contiene un par (C, ?D) de literales ambivalentes, es decir, C y D tienen el mismo símbolo de predicado y signo.
p(X):-p(X).
q(a):-q(s(s(a))).
Sean C y D no ambivalentes. Entonces, C ? D sii C =? D.
Métodos Bottom-up: implicación inversa
RELACIÓN ENTRE IMPLICACIÓN Y RESOLUCIÓN
C ? D
? D es una tautología
? C =? D
? E =? D y E se obtiene resolviendo C consigo
misma.
 Página anterior | Volver al principio del trabajo | Página siguiente  |