4 P R I N C I P I O D E R E S O L U C I Ó N

Este capítulo introduce el mecanismo de inferencia utilizado por la mayoría de los sis-temas de programación lógica. Si seguimos considerando Prolog desde la perspectivade los sistemas formales, hemos descrito ya su lenguaje y su teoría de modelo; ahoradescribiremos su teoría de prueba. El mecanismo en cuestión es un caso particular dela regla de inferencia llamada principio de resolución [21]. La idea es acotar el usode este principio a programas definitivos, dando lugar a la resolución-SLD [13]. Esteprincipio constituye el fundamento de la semántica operacional de los programas defi-nitivos. La resolución-SLD se demostrará correcta con respecto a la teoría del modelodescrita en la clase anterior.

�.� ������������La programación lógica concierne el uso de la lógica (restringida a cláusulas) pararepresentar y resolver problemas. Este uso es ampliamente aceptado en InteligenciaArtificial (IA), donde la idea se resume como sigue: Un problema o sujeto de investi-gación puede describirse mediante un conjunto de fórmulas bien formadas (fbf), depreferencia en forma de cláusulas. Si tal descripción es lo suficientemente precisa, lasolución al problema o la respuesta a la pregunta planteada en la investigación, esuna consecuencia lógica del conjunto de fbf que describen el problema. Por lo tanto,encontrar que fbf � son consecuencia lógica de un conjunto de fbf �, es crucial paramuchas áreas de la IA, incluyendo la programación lógica. De forma que nos gusta-ría tener un procedimiento, algorítmico, que nos permita establecer si � |= � es elcaso, o no. Este es el tema del presente capítulo: un método decidible conocido comoprincipio de resolución [21].

En el caso de la lógica proposicional, la implicación lógica es decidible, es decir,existe un algoritmo que puede resolver el problema (contestar si ó no para cada casoparticular � |= �). Si n es el número de átomos distintos que ocurren en estas fbf,el número de interpretaciones posibles es finito, de hecho es 2n. Un algoritmo paracomputar � |= � simplemente busca si � es verdadero en todos los modelos de �.¿Qué sucede en el contexto de la lógica de primer orden?

La intuición nos dice que el procedimiento de decisión de la lógica proposicional noes adecuado en primer orden, pues en este caso podemos tener una cantidad infinitade dominios e interpretaciones diferentes. Lo que es peor, el teorema de Church [5, 26],muestra que la lógica de primer orden es indecidible:

Teorema 4 (Church) El problema de si � |= �, cuando � es un conjunto finito arbitrario defbf, y � es una fbf arbitraria, es indecidible.

Observen que el problema es indecidible para conjuntos arbitrarios de fbf y parauna fbf � arbitraria. No existe un algoritmo que en un número finito de pasos, de larespuesta correcta a la pregunta ¿Es � una consecuencia lógica de �?

39

40 ��������� �� ����������

Existen, sin embargo, procedimientos conocidos como procedimientos de pruebaque pueden ser de gran ayuda para computar este problema. La idea es que cuandoes el caso que � |= �, existen procedimientos que pueden verificarlo en un númerofinito de pasos. Por ello suele decirse que la lógica de primer orden es semi-decidible.Aunque parecería trivial, siendo que � |= �, preguntar ¿� |= �?, en realidad taltrivialidad es aparente. Podemos hacer la pregunta al procedimiento sin que nosotrossepamos que ese es el caso, y obtendremos una respuesta en un número finito depasos. Pero si es el caso que � 6|= � obtendremos la respuesta “no” (en el mejor delos casos) o el procedimiento no terminará nunca. Esto es infortunado y, peor aún,inevitable.

Esta sesión introduce el procedimiento de prueba utilizado ampliamente en la pro-gramación lógica: el principio de resolución propuesto por Robinson [21]. Si bien esteprocedimiento está orientado a un lenguaje más expresivo, nosotros nos concentra-remos en una versión del principio que aplica a programas definidos y se conocecomo resolución-SLD [13] (resolución lineal con función de selección para cláusulasdefinitivas).

�.� ¿��� �� �� ������������� �� ������?Hasta este momento, hemos abordado informalmente el concepto de procedimientode prueba como la manera de generar la prueba de que una fbf � es consecuencialógica de un conjunto de fbf �. Las fbf en � se conocen como premisas y � es laconclusión de la prueba.

La prueba suele consistir de un pequeño número de transformaciones en los cualesnuevas fbf son derivadas de las premisas y de fbf previamente derivadas. Derivaruna fbf implica construirla a partir de las premisas y otras fbf derivadas, siguiendoalguna regla de inferencia. Toda regla de inferencia formaliza alguna forma naturalde razonamiento. Por ejemplo, el modus ponens es usado comúnmente en matemáticas,su expresión es:

�, �!

donde la línea superior expresa las premisas y la línea inferior la conclusión.Es posible ligar varias aplicaciones del modus ponens para construir una prueba.

Por ejemplo, si tenemos el programa lógico � = {p(a),q(b) p(a), r(b) q(b)} esposible derivar la fbf r(b) como sigue:

1. Derivar q(b) a partir de p(a) y q(b) p(a).

2. Derivar r(b) a partir de q(b) y r(b) q(b).

La secuencia anterior es una prueba de que r(b) puede ser derivada de �.Es evidente que si usamos modus ponens, la conclusión es una consecuencia lógica

de las premisas: {�,� ! } |= . A esta propiedad del modus ponens se le conocecomo consistencia (soundness). En general un procedimiento de prueba es consistentesi todas las fbf que pueden ser derivadas de algún conjunto de fbfs � usando elprocedimiento, son consecuencias lógicas de �. En otras palabras, un procedimiento

�.� ������� � ��������� ������� 41

de prueba es consistente si y sólo si sólo permite derivar consecuencias lógicas de laspremisas.

Una segunda propiedad deseable de los procedimientos de prueba es su completez.Un procedimiento de prueba es completo si toda fbf que es una consecuencia lógicade las premisas �, puede ser derivada usando el procedimiento en cuestión. El modusponens por si mismo, no es completo. Por ejemplo, no existe secuencia alguna deaplicaciones del modus ponens que deriven la fbf p(a) de � = {p(a)^ p(b)}, cuando esevidente que � |= p(a).

La regla � es completa, pero no válida. !Nos permite extraer cualquier conclusión,a partir de cualquier premisa! Esto ejemplifica que obtener completitud es sencillo,pero obtener completitud y correctez, no lo es.

�.� ������� � ��������� �������Recordemos que los enunciados en los programas lógicos tienen la estructura generalde la implicación lógica:

↵0 ↵1, . . . ,↵n (n > 0)

donde ↵0, . . . ,↵n son fbfs atómicas y ↵0 puede estar ausente (para representar cláu-sulas meta). Consideren el siguiente programa definitivo � que describe un mundodonde los padres de un recién nacido están orgullosos, Juan es el padre de Marta yMarta es una recién nacida:

orgulloso(X) padre(X, Y), recien_nacido(Y).padre(X, Y) papa(X, Y).padre(X, Y) mama(X, Y).

papa(juan,marta).recien_nacido(marta).

Observen que el programa describe únicamente conocimiento positivo, es decir, noespecifica quién no está orgulloso. Tampoco que significa para alguien no ser padre.

Supongamos que deseamos contestar la pregunta ¿Quién está orgulloso? Esta pre-gunta concierne al mundo descrito por nuestro programa, esto es, concierne al modeloprevisto para �. La respuesta que esperamos es, por supuesto, juan. Ahora, recuer-den que la lógica de primer orden no nos permite expresar enunciados interrogativos,por lo que nuestra pregunta debe formalizarse como una cláusula meta (enunciadodeclarativo):

orgulloso(Z).

que es una abreviatura de 8Z¬orgulloso(Z) (una cláusula definitiva sin cabeza), quea su vez es equivalente de:

42 ��������� �� ����������

¬9Z orgulloso(Z).

cuya lectura es “Nadie está orgulloso”, esto es, la respuesta negativa a la consultaoriginal – ¿Quién está orgulloso? La meta ahora es probar que este enunciado es falsoen todo modelo del programa � y en particular, es falso en el modelo previsto para �,puesto que esto es una forma de probar que � |= 9Z orgulloso(Z). En general paratodo conjunto de fbf cerradas � y una fbf cerrada �, tenemos que � |= � si � [ {¬�}es no satisfacerle (no tiene modelo).

Por lo tanto, nuestro objetivo es encontrar una substitución ✓ tal que el conjunto �[{¬orgulloso(Z)✓} sea no satisfacerle, o de manera equivalente, � |= 9Z orgulloso(Z)✓.

El punto inicial de nuestro razonamiento es asumir la meta G0 – Para cualquier Z,Z no está orgulloso. La inspección del programa � revela que una regla describe unacondición para que alguien esté orgulloso:

orgulloso(X) padre(X, Y), recien_nacido(Y).

lo cual es lógicamente equivalente a:

8(¬orgulloso(X)) ¬(padre(X, Y)^ recien_nacido(Y)))

Al renombrar X por Z, eliminar el cuantificador universal y usar modus ponens conrespecto a G0, obtenemos:

¬(padre(Z, Y)^ recien_nacido(Y))

o su equivalente:

padre(Z, Y), recien_nacido(Y).

al que identificaremos como G1. Un paso en nuestro razonamiento resulta en rempla-zar la meta G0 por la meta G1 que es verdadera en todo modelo �[ {G0}. Ahora soloqueda probar que �[ {G1} es no satisfacible. Observen que G1 es equivalente a la fbf:

8Z8Y(¬padre(Z, Y)_¬recien_nacido(Y))

Por lo tanto, puede probarse que la meta G1 es no satisfacible para �, si en todomodelo de � hay una persona que es padre de un recién nacido. Entonces, verificamosprimero si hay padres con estas condiciones. El programa contiene la cláusula:

padre(X, Y) papa(X, Y).

que es equivalente a:

8(¬padre(X, Y)) ¬papa(X, Y))

�.� ������� � ��������� ������� 43

por lo que G1 se reduce a:

papa(Z, Y), recien_nacido(Y).

que identificaremos como G2. Se puede mostrar que no es posible satisfacer la nuevameta G2 con el programa �, si en todo modelo de � hay una persona que es papá deun recién nacido. El programa declara que juan es padre de marta:

papa(juan,marta).

así que sólo resta probar que “marta no es una recién nacida” no se puede satisfacerjunto con �:

recien_nacido(marta).

pero el programa contiene el hecho:

recien_nacido(marta).

equivalente a ¬recien_nacido(marta)) f lo que conduce a una refutación.Este razonamiento puede resumirse de la siguiente manera: para probar la existen-

cia de algo, suponer lo contrario y usar modus ponens y la regla de eliminación delcuantificador universal, para encontrar un contra ejemplo al supuesto.

Observen que la meta definitiva fue convertida en un conjunto de átomos a serprobados. Para ello, se seleccionó una fbf atómica de la meta p(s1, . . . , sn) y una cláu-sula de la forma p(t1, . . . , tn) A1, . . . An para encontrar una instancia común dep(s1, . . . , sn) y p(t1, . . . , tn), es decir, una substitución ✓ que hace que p(s1, . . . , sn)✓y p(t1, . . . , tn)✓ sean idénticos. Tal substitución se conoce como unificador. La nuevameta se construye remplazando el átomo seleccionado en la meta original, por losátomos de la cláusula seleccionada, aplicando ✓ a todos los átomos obtenidos de estamanera.

El paso de computación básico de nuestro ejemplo, puede verse como una reglade inferencia puesto que transforma fórmulas lógicas. Lo llamaremos principio deresolución SLD para programas definitivos. Como mencionamos, el procedimientocombina modus ponens, eliminación del cuantificador universal y en el paso final un reduc-tio ad absurdum.

Cada paso de razonamiento produce una substitución, si se prueba en k pasos quela meta definida en cuestión no puede satisfacerse, probamos que:

(A1, . . . Am)✓1 . . . ✓k

es una instancia que no puede satisfacerse. De manera equivalente, que:

� |= (A1 ^ · · ·^Am)✓1 . . . ✓k

44 ��������� �� ����������

Observen que generalmente, la computación de estos pasos de razonamiento noes determinista: cualquier átomo de la meta puede ser seleccionado y pueden habervarias cláusulas del programa que unifiquen con el átomo seleccionado. Otra fuentede indeterminismo es la existencia de unificadores alternativos para dos átomos. Es-to sugiere que es posible construir muchas soluciones (algunas veces, una cantidadinfinita de ellas).

Por otra parte, es posible también que el atomo seleccionado no unifique con ningu-na cláusula en el programa. Esto indica que no es posible construir un contra ejemplopara la meta definida inicial. Finalmente, la computación puede caer en un ciclo y deesta manera no producir solución alguna.

�.� ������������Una substitución remplaza variables por términos, por ejemplo, podemos remplazarla variable X por el término f(a) en la cláusula p(X)_ q(X), y así obtener la nuevacláusula p(f(a))_ q(f(a)). Si asumimos que las cláusulas están cuantificadas univer-salmente, decimos que está substitución hace a la cláusula original, “menos general”.Mientras que la cláusula original dice que V(p(X)) = t y que V(q(X)) = t para cual-quier X en el dominio, la segunda cláusula dice que esto sólo es cierto cuando cuandoV(X) = f(a). Observen que la segunda cláusula es consecuencia lógia de la primera:p(X)_ q(X) |= p(f(a))_ q(f(a))

Definición 26 (Substitución) Una substitución ✓ es un conjunto finito de la forma:

{X1/t1, . . . ,Xn/tn}, (n > 0)

donde las Xi son variables, distintas entre si, y los ti son términos. Decimos que ti substi-tuye a Xi. La forma Xi/ti se conoce como ligadura de Xi. La substitución ✓ se dice se dice debase (grounded) si cada término ti es un término base (no incluye variables)..

La substitución dada por el conjunto vacío, se conoce como substitución de identi-dad o substitución vacía y se denota por ✏. La restricción de ✓ sobre un conjunto devariables Var es la substitucion {X/t 2 ✓ | X 2 Var}.

Ejemplo 8 {Y/X,X/g(X, Y)} y {X/a, Y/f(Z),Z/(f(a),X1/b} son substituciones. La restric-ción de la segunda substitución sobre {X,Z} es {X/a,Z/f(a)}.

Definición 27 (Expresión) Una expresión es un término, una literal, o una conjunción odisyunción de literales. Una expresión simple es un término o una literal.

Observen que una cláusula es una expresión. Las substituciones pueden aplicarse alas expresiones, lo que significa que las variables en las expresiones serán remplazadasde acuerdo a la substitución.

Definición 28 Sea ✓ = {X1/t1, . . . ,Xn/tn} una substitución y ↵ una expresión. Entonces↵✓, la ocurrencia (instance) de ↵ por ✓, es la expresión obtenida al substituir simultáneamenteXi por ti para 1 6 i 6 n. Si ↵✓ es una expresión de base, se dice que es una ocurrencia basey se dice que ✓ es una substitución de base para ↵. Si ⌃ = {↵1, . . . ,↵n} es un conjunto finitode expresiones, entonces ⌃✓ denota {↵1✓, . . . ,↵n✓}.

�.� ������������ 45

Ejemplo 9 Sea ↵ la expresión p(Y, f(X)) y sea ✓ la substitución {X/a, Y/g(g(X))}. La ocu-rrencia de ↵ por ✓ es ↵✓ = p(g(g(X)), f(a). Observen que X e Y son simultáneamente rem-plazados por sus respectivos términos, lo que implica que X en g(g(X)) no es afectada porX/a.

Si ↵ es una expresión cerrada que no es un término, por ejemplo, una literal, o unaconjunción o disyunción de literales, y ✓ es una substitución, lo siguiente se cumple:

↵ |= ↵✓

por ejemplo: p(X)_¬q(Y) |= p(a)_¬q(Y) donde hemos usado la substitución {X/a}.Podemos aplicar una substitución ✓ y luego aplicar una substitución �, a lo cual se

llama composición de las substituciones ✓ y �. Si ese es el caso, primero se aplica ✓ yluego �. Las composiciones pueden verse como mapeos del conjunto de variables enel lenguaje, al conjunto de términos.

Definición 29 (Composición) Sean ✓ = {X1/s1, . . . ,Xm/sm} y � = {Y1/t1, . . . Yn/tn}dos substituciones. Consideren la secuencia:

X1/(s1�), . . . ,Xm/(sm�), Y1/t1, . . . , Yn/tn

Si se borran de esta sencuencia las ligaduras Xi/si� cuando Xi = si� y cualquier ligaduraYj/tj donde Yj 2 {X1, . . . ,Xm}. La substitución consistente en las ligaduras de la secuenciaresultante es llamada composición de ✓ y �, se denota por ✓�.

Ejemplo 10 Sea ✓ = {X/f(Y),Z/U} y � = {Y/b,U/Z}. Construimos la secuencia de liga-duras X/(f(Y)�),Z/(u)�, Y/b,U/Z lo cual es X/f(b),Z/Z, Y/b,U/Z. Al borrar la ligaduraZ/Z obtenemos la secuencia X/f(b), Y/b,U/Z = ✓�.

Definición 30 (Ocurrencia) Sean ✓ y � dos substituciones. Se dice que ✓ es una ocurrenciade �, si existe una substitución �, tal que �� = ✓.

Ejemplo 11 La substitución ✓ = {X/f(b), Y/a} es una ocurrencia de la substitución � ={X/f(X), Y/a}, puesto que �{X/b} = ✓.

Algunas propiedades sobre las substituciones incluyen:

Proposición 3 Sea ↵ una expresión, y sea ✓, � y � substituciones. Las siguientes relacionesse cumplen:

1. ✓ = ✓✏ = ✏✓

2. (↵✓)� = ↵(✓�)

3. ✓�)� = ✓(��)

46 ��������� �� ����������

�.� �����������Uno de los pasos principales en el ejemplo de la sección 4.3, consistió en hacer quedos fbf atómicas se vuelvan sintácticamente equivalentes. Este proceso se conoce comounificación y posee una solución algorítmica.

Definición 31 (Unificador) Sean ↵ y � términos. Una substitución ✓ tal que ↵ y � seanidénticos (↵✓ = �✓) es llamada unificador de ↵ y �.

Ejemplo 12

unifica(conoce(juan,X), conoce(juan,maria)) = {X/maria}

unifica(conoce(juan,X), conoce(Y,Z)) = {Y/juan,X/Z}

= {Y/juan,X/Z,W/pedro}

= {Y/juan,X/juan,Z/juan}

Definición 32 (Generalidad entre substituciones) Una substitución ✓ se dice más gene-ral que una substitución �, si y sólo si existe una substitución � tal que � = ✓�.

Definición 33 (MGU) Un unificador ✓ se dice el unificador más general (MGU) de dostérminos, si y sólo si ✓ es más general que cualquier otro unificador entre esos términos.

Definición 34 (Forma resuelta) Un conjunto de ecuaciones {X1 = t1, . . . ,Xn = tn} estáen forma resuelta, si y sólo si X1, . . . ,Xn son variables distintas que no ocurren en t1, . . . , tn.

Existe una relación cercana entre un conjunto de ecuaciones en forma resuelta y elunificador más general de ese conjunto: Sea {X1 = t1, . . . ,Xn = tn} un conjunto deecuaciones en forma resuelta. Entonces {X1/t1, . . . ,Xn/tn} es un MGU idempotentede la forma resuelta.

Definición 35 (Equivalencia en conjuntos de ecuaciones) Dos conjuntos de ecuacionesE1 y E2 se dicen equivalentes, si tienen el mismo conjunto de unificadores.

La definición puede usarse como sigue: para computar el MGU de dos términos ↵ y�, primero intente transformar la ecuación {↵ = �} en una forma resuelta equivalente.Si esto falla, entonces mgu(↵,�) = fallo. Sin embargo, si una forma resuelta {X1 =t1, . . . ,Xn = tn} existe, entonces mgu(↵,�) = {X1/t1, . . . ,Xn/tn}. Un algoritmo paraencontrar la forma resuelta de un conjunto de ecuaciones es como sigue:

Ejemplo 13 El conjunto {f(X,g(Y)) = f(g(Z),Z)} tiene una forma resuelta, puesto que:

) {X = g(Z),g(Y) = Z}

) {X = g(Z),Z = g(Y)}

) {X = g(g(Y)),Z = g(Y)}

�.� ����������� 47

Algoritmo 1 Unifica(E)1: function Unifica(E) . E es un conjunto de ecuaciones2: repeat3: (s = t) seleccionar(E)4: if f(s1, . . . , sn) = f(t1, . . . , tn) (n > 0) then5: remplazar (s = t) por s1 = t1, . . . , sn = tn6: else if f(s1, . . . , sm) = g(t1, . . . , tn) (f/m 6= g/n) then7: return(fallo)8: else if X = X then9: remover la X = X

10: else if t = X then11: remplazar t = X por X = t

12: else if X = t then13: if subtermino(X,t) then14: return(fallo)15: else remplazar todo X por t16: end if17: end if18: until No hay accion posible para E

19: end function

Ejemplo 14 El conjunto {f(X,g(X),b) = f(a,g(Z),Z)} no tiene forma resuelta, puesto que:

) {X = a,g(X) = g(Z),b = Z}

) {X = a,g(a) = g(Z),b = Z}

) {X = a,a = Z,b = Z}

) {X = a,Z = a,b = Z}

) {X = a,Z = a,b = a}

) fallo

Ejemplo 15 El conjunto {f(X,g(X)) = f(Z,Z)} no tiene forma resuelta, puesto que:

) {X = Z,g(X) = Z}

) {X = Z,g(Z) = Z}

) {X = Z,Z = g(Z)}

) fallo

Este algoritmo termina y regresa una forma resuelta equivalente al conjunto deecuaciones de su entrada; o bien regresa fallo si la forma resuelta no existe. Sin embar-go, el computar subtermino(X, t) (verificación de ocurrencia) hace que el algoritmosea altamente ineficiente. Los sistemas Prolog resuelven este problema haciéndo casoomiso de la verificación de ocurrencia. El standard ISO Prolog (1995) declara que el

48 ��������� �� ����������

resultado de la unificación es no decidible. Al eliminar la verificación de ocurrencia esposible que al intentar resolver X = f(X) obtengamos X = f(f(X)) · · · = f(f(f . . . )). Enla practica los sistemas Prolog no caen en este ciclo, pero realizan la siguiente substi-tución {X/f(1)}. Si bien esto parece resolver el problema de eficiencia, generaliza elconcepto de término, substitución y unificación al caso del infinito, no consideradoen la lógica de primer orden, introduciéndo a su vez inconsistencia.

�.� ����������-���El método de razonamiento descrito informalmente al inicio de esta sesión, puederesumirse con la siguiente regla de inferencia:

8¬(↵1 ^ · · ·^↵i-1 ^↵i ^↵i+1 ^ · · ·^↵m) 8(�0 �1 ^ · · ·^�n)

8¬(↵1 ^ · · ·^↵i-1 ^�1 ^ · · ·^�n ^↵i+1 ^ · · ·^↵m)✓

o, de manera equivalente, usando la notación de los programas definitivos:

↵1, . . . ,↵i-1,↵i,↵i+1, . . . ,↵m �0 �1, . . . ,�n

(↵1, . . . ,↵i-1,�1, . . . ,�n, . . . ,↵m)✓

donde:

1. ↵1, . . . ,↵m son fbf atómicas.

2. �0 �1, . . . ,�n es una cláusula definitiva en el programa � (n > 0).

3. MGU(↵i,�0) = ✓.

La regla tiene dos premisas: una meta y una cláusula definitivas. Observen quecada una de ellas está cuantificada universalmente, por lo que el alcance de los cuan-tificadores es disjunto. Por otra parte, solo hay un cuantificador universal para laconclusión, por lo que se requiere que el conjunto de variables en las premisas seadisjunto. Puesto que todas las variables en las premisas están cuantificadas, es siem-pre posible renombrar las variables de la cláusula definitiva para cumplir con estacondición.

La meta definida puede incluir muchas fbf atómicas que unifican con la cabezade alguna cláusula en el programa. En este caso, es deseable contar con un mecanis-mo determinista para seleccionar un átomo ↵i a unificar. Se asume una función queselecciona una submeta de la meta definida (función de selección).

La regla de inferencia presentada es la única necesaria para procesar programasdefinitivos. Esta regla es una versión de la regla de inferencia conocida como princi-pio de resolución, introducido por J.A. Robinson en 1965. El principio de resoluciónaplica a cláusulas. Puesto que las cláusulas definitivas son más restringidas que lascláusulas, la forma de resolución presentada se conoce como resolución-SLD (resolu-ción lineal para cláusulas definitivas con función de selección).

El punto de partida de la aplicación de esta regla de inferencia es una meta definidaG0:

↵1, . . . ,↵m (m > 0)

�.� ����������-��� 49

De esta meta, una submeta ↵i será seleccionada, de preferencia por una función deselección. Una nueva meta G1 se construye al seleccionar una cláusula del programa�0 �1, . . . ,�n (n > 0) cuya cabeza �0 unifica con ↵i, resultando en ✓1. G1 tiene laforma:

(↵1, . . . ,↵i-1,�1, . . . ,�n, . . . ,↵m)✓1

Ahora es posible aplicar el principio de resolución a G1 para obtener G2, y asísucesivamente. El proceso puede terminar o no. Hay dos situaciones donde no esposible obtener Gi+1 a partir de Gi:

1. cuando la submeta seleccionada no puede ser resuelta (no es unificable con lacabeza de una cláusula del programa).

2. cuando Gi = ⇤ (meta vacía = f).

Definición 36 (Derivación-SLD) Sea G0 una meta definitiva, � un programa definitivo yR una función de selección. Una derivación SLD de G0 (usando � y R) es una secuenciafinita o infinita de metas:

G0↵0 G1 . . . Gn-1

↵n-1 Gn

Para manejar de manera consistente el renombrado de variables, las variables enuna cláusula ↵i serán renombradas poniéndoles subíndice i.

Cada derivación SLD nos lleva a una secuencias de MGUs ✓1, . . . , ✓n. La composi-ción

✓ =

�✓1✓2 . . . ✓n si n > 0

✏ si n = 0

de MGUs se conoce como la substitución computada de la derivación.

Ejemplo 16 Consideren la meta definida orgulloso(Z) y el programa discutido en laclase anterior.

G0 = orgulloso(Z).

↵0 = orgulloso(X0) padre(X0, Y0), recien_nacido(Y0).

La unificación de orgulloso(Z) y orgulloso(X0) nos da el MGU ✓1 = {X0/Z}. Asuma-mos que nuestra función de selección es tomar la submeta más a la izquierda. El primer pasode la derivación nos conduce a:

G1 = padre(Z, Y0), recien_nacido(Y0).

↵1 = padre(X1, Y1) papa(X1, Y1).

50 ��������� �� ����������

En el segundo paso de la resolución el MGU ✓2 = {X1/Z, Y1/Y0} es obtenido. La derivacióncontinua como sigue:

G2 = papa(Z, Y0), recien_nacido(Y0).

↵2 = papa(juan,marta).

G3 = recien_nacido(marta).

↵3 = recien_nacido(marta).

G4 = ⇤la substitución computada para esta derivación es:

✓1✓2✓3✓4 = {X0/Z}{X1/Z, Y1/Y0}{Z/juan, Y0/marta}✏

= {X0/juan,X1/juan, Y1/marta,Z/juan, Y0/marta}

Las derivaciones SLD que terminan en la meta vacía (⇤) son de especial importanciapues corresponden a refutaciones a la meta inicial (y proveen las respuestas a la meta).

Definición 37 (Refutación SLD) Una derivación SLD finita:

G0↵0 G1 . . . Gn-1

↵n-1 Gn

donde Gn = ⇤, se llama refutación SLD de G0.

Definición 38 (Derivación fallida) Una derivación de la meta definitiva G0 cuyo últimoelemento no es la meta vacía y no puede resolverse con ninguna cláusula del programa, esllamada derivación fallida.

Definición 39 (Arbol-SLD) Sea � un programa definitivo, G0 una meta definitiva, y R unafunción de selección. El árbol-SLD de G0 (usando � y R) es un árbol etiquetado, posiblementeinfinito, que cumple las siguientes condiciones:

• La raíz del árbol está etiquetada por G0.

• Si el árbol contiene un nodo etiquetado como Gi y existe una cláusula renombrada↵i 2 � tal que Gi+1 es dervidada de Gi y ↵i via R, entonces el nodo etiquetado comoGi tiene un hijo etiquetado Gi+1 El arco que conecta ambos nodos está etiquetado como↵i.

Por ejemplo: orgulloso(Z)

padre(Z, Y0), recien_nacido(Y0)

papa(Z, Y0), recien_nacido(Y0)

recien_nacido(marta)

⇤

mama(Z, Y0), recien_nacido(Y0)

�.� ����������� �� �� ����������-��� 51

�.� ����������� �� �� ����������-���Definición 40 (Consistencia) Sea � un programa definitivo, R una función de selección, y✓ una substitución de respuesta computada a partir de � y R para una meta ↵1, . . . ,↵m.Entonces 8((↵1 ^ · · ·^↵m)✓) es una consecuencia lógica del programa �.

Definición 41 (Compleción) Sea � un programa definitivo, R una función de seleccióny ↵1, . . . ,↵m una meta definitiva. Si � |= 8((↵1 ^ · · · ^ ↵m)�), entonces existe unarefutación de ↵1, . . . ,↵m vía R con una substitución de respuesta computada ✓, tal que(↵1 ^ · · ·^↵m)� es un caso de (↵1 ^ · · ·^↵m)✓.