Programación lógica con restricciones

La programación lógica con restricciones es una forma de programación con restricciones , en la que la programación lógica se extiende para incluir conceptos de satisfacción de restricciones . Un programa lógico con restricciones es un programa lógico que contiene restricciones en el cuerpo de las cláusulas. Un ejemplo de una cláusula que incluye una restricción es . En esta cláusula, es una restricción; , , y son literales como en la programación lógica regular. Esta cláusula establece una condición bajo la cual se cumple la afirmación: es mayor que cero y tanto como son verdaderas.A(X,Y):-X+Y>0,B(X),C(Y)X+Y>0A(X,Y)B(X)C(Y)A(X,Y)X+YB(X)C(Y)

Al igual que en la programación lógica convencional, se consulta a los programas sobre la demostrabilidad de un objetivo, que puede contener restricciones además de literales. Una prueba para un objetivo se compone de cláusulas cuyos cuerpos son restricciones satisfacibles y literales que, a su vez, pueden demostrarse utilizando otras cláusulas. La ejecución la realiza un intérprete, que parte del objetivo y examina recursivamente las cláusulas intentando demostrarlo. Las restricciones encontradas durante este examen se almacenan en un conjunto denominado almacén de restricciones . Si se determina que este conjunto es insatisfacible, el intérprete retrocede , intentando utilizar otras cláusulas para demostrar el objetivo. En la práctica, la satisfacibilidad del almacén de restricciones puede comprobarse mediante un algoritmo incompleto, que no siempre detecta la inconsistencia.

Formalmente, los programas de lógica de restricciones son como los programas de lógica regulares, pero el cuerpo de las cláusulas puede contener restricciones, además de los literales de programación lógica regulares. Por ejemplo, X>0es una restricción, y se incluye en la última cláusula del siguiente programa de lógica de restricciones.

B ( X , 1 ):- X < 0. B ( X , Y ):- X = 1 , Y > 0. A ( X , Y ):- X > 0 , B ( X , Y ).

Al igual que en la programación lógica convencional, evaluar un objetivo como A(X,1)requiere evaluar el cuerpo de la última cláusula con Y=1. Como en la programación lógica convencional, esto a su vez requiere demostrar el objetivo B(X,1). A diferencia de la programación lógica convencional, esto también requiere que se cumpla una restricción: X>0, la restricción en el cuerpo de la última cláusula. (En la programación lógica convencional, no se puede demostrar que X>0 a menos que X esté vinculado a un término completamente definido , y la ejecución del programa fallará si no es así).

No siempre es posible determinar si una restricción se cumple en el momento en que se encuentra. En este caso, por ejemplo, el valor de Xno se determina cuando se evalúa la última cláusula. Como resultado, la restricción X>0no se cumple ni se infringe en este punto. En lugar de continuar con la evaluación de B(X,1)y luego comprobar si el valor resultante de Xes positivo, el intérprete almacena la restricción X>0y luego procede con la evaluación de B(X,1); de esta manera, el intérprete puede detectar la infracción de la restricción X>0durante la evaluación de B(X,1), y retroceder inmediatamente si esto ocurre, en lugar de esperar a que B(X,1)concluya la evaluación de .

En general, la evaluación de un programa de lógica de restricciones procede como un programa de lógica regular. Sin embargo, las restricciones encontradas durante la evaluación se colocan en un conjunto llamado almacén de restricciones. Como ejemplo, la evaluación del objetivo A(X,1)procede evaluando el cuerpo de la primera cláusula con Y=1; esta evaluación agrega X>0al almacén de restricciones y requiere B(X,1)que se demuestre el objetivo. Al intentar demostrar este objetivo, se aplica la primera cláusula, pero su evaluación agrega X<0al almacén de restricciones. Esta adición hace que el almacén de restricciones sea insatisfacible. El intérprete entonces retrocede, eliminando la última adición del almacén de restricciones. La evaluación de la segunda cláusula agrega X=1y Y>0al almacén de restricciones. Dado que el almacén de restricciones es satisfacible y no queda ningún otro literal por demostrar, el intérprete se detiene con la solución X=1, Y=1.

La semántica de los programas de lógica de restricciones se puede definir en términos de un intérprete virtual que mantiene un par${\displaystyle \langle G,S\rangle }$Durante la ejecución, el primer elemento de este par se denomina objetivo actual y el segundo, almacén de restricciones. El objetivo actual contiene los literales que el intérprete intenta demostrar y también puede contener algunas restricciones que intenta satisfacer; el almacén de restricciones contiene todas las restricciones que el intérprete ha considerado satisfacibles hasta el momento.

Inicialmente, el objetivo actual es el objetivo y el almacén de restricciones está vacío. El intérprete procede eliminando el primer elemento del objetivo actual y analizándolo. Los detalles de este análisis se explican más adelante, pero al final este análisis puede producir una terminación exitosa o un fallo. Este análisis puede implicar llamadas recursivas y la adición de nuevos literales al objetivo actual y nuevas restricciones al almacén de restricciones. El intérprete retrocede si se produce un fallo. Se produce una terminación exitosa cuando el objetivo actual está vacío y el almacén de restricciones es satisfacible.

Los detalles del análisis de un literal eliminado del objetivo son los siguientes. Después de eliminar este literal del principio del objetivo, se comprueba si es una restricción o un literal. Si es una restricción, se añade al almacén de restricciones. Si es un literal, se elige una cláusula cuyo encabezado tenga el mismo predicado que el literal; la cláusula se reescribe reemplazando sus variables por nuevas variables (variables que no aparecen en el objetivo): el resultado se denomina variante nueva de la cláusula; el cuerpo de la variante nueva de la cláusula se coloca entonces al principio del objetivo; la igualdad de cada argumento del literal con el correspondiente del encabezado de la variante nueva también se coloca al principio del objetivo.

Durante estas operaciones se realizan algunas comprobaciones. En particular, se verifica la consistencia del almacén de restricciones cada vez que se añade una nueva restricción. En principio, si el almacén de restricciones no es satisfacible, el algoritmo podría retroceder. Sin embargo, comprobar la insatisfacibilidad en cada paso sería ineficiente. Por este motivo, se puede utilizar un verificador de satisfacibilidad incompleto. En la práctica, la satisfacibilidad se comprueba mediante métodos que simplifican el almacén de restricciones, es decir, lo reescriben en una forma equivalente pero más sencilla de resolver. Estos métodos a veces, pero no siempre, pueden demostrar la insatisfacibilidad de un almacén de restricciones insatisfacible.

El intérprete ha demostrado el objetivo cuando el objetivo actual está vacío y el almacén de restricciones no se detecta como insatisfacible. El resultado de la ejecución es el conjunto actual de restricciones (simplificadas). Este conjunto puede incluir restricciones tales como:${\displaystyle X=2}$que fuerzan las variables a un valor específico, pero también pueden incluir restricciones como${\displaystyle X>2}$que solo vinculan variables sin darles un valor específico.

Formalmente, la semántica de la programación lógica con restricciones se define en términos de derivaciones . Una transición es un par de pares objetivo/almacén, como se indica.${\displaystyle \langle G,S\rangle \rightarrow \langle G',S'\rangle }$. Dicho par indica la posibilidad de pasar del estado${\displaystyle \langle G,S\rangle }$para declarar${\displaystyle \langle G',S'\rangle }$Dicha transición es posible en tres casos posibles:

• un elemento de G es una restricción C , y tenemos${\displaystyle G'=G\backslash \{C\}}$y${\displaystyle S'=S\cup \{C\}}$En otras palabras, una restricción puede moverse del objetivo al almacén de restricciones.
• un elemento de G es un literal${\displaystyle L(t_{1},\ldots ,t_{n})}$, existe una cláusula que, reescrita usando nuevas variables, es${\displaystyle L(t_{1}',\ldots ,t_{n}')\mathrel {{:}{-}} B}$, el conjunto${\displaystyle G'}$es G con${\displaystyle L(t_{1},\ldots ,t_{n})}$reemplazado por${\displaystyle t_{1}=t_{1}',\ldots ,t_{n}=t_{n}',B}$, y${\displaystyle S'=S}$En otras palabras, un literal puede ser reemplazado por el cuerpo de una nueva variante de una cláusula que tenga el mismo predicado en la cabeza, agregando el cuerpo de la nueva variante y las igualdades de términos anteriores al objetivo.
• Arena​${\displaystyle S'}$son equivalentes según la semántica de restricción específica

Una secuencia de transiciones es una derivación. Un objetivo G puede probarse si existe una derivación de${\displaystyle \langle G,\emptyset \rangle }$a${\displaystyle \langle \emptyset,S\rangle }$para algún almacén de restricciones satisfacible S. Esta semántica formaliza las posibles evoluciones de un intérprete que elige arbitrariamente el literal del objetivo a procesar y la cláusula para reemplazar los literales. En otras palabras, un objetivo se demuestra bajo esta semántica si existe una secuencia de elecciones de literales y cláusulas, entre las muchas posibles, que conducen a un objetivo vacío y un almacén satisfacible.

Los intérpretes procesan los elementos objetivo en orden LIFO : los elementos se agregan al principio y se procesan desde el principio. También seleccionan la cláusula de la segunda regla según el orden en que se escriben y reescriben el almacén de restricciones cuando este se modifica.

El tercer tipo de transición posible consiste en reemplazar el almacén de restricciones por uno equivalente. Este reemplazo se limita a aquellos realizados mediante métodos específicos, como la propagación de restricciones . La semántica de la programación lógica con restricciones es paramétrica no solo al tipo de restricciones utilizadas, sino también al método para reescribir el almacén de restricciones. Los métodos específicos utilizados en la práctica reemplazan el almacén de restricciones por uno más sencillo de resolver. Si el almacén de restricciones es insatisfacible, esta simplificación puede detectar dicha insatisfacibilidad en algunos casos, pero no siempre.

El resultado de evaluar un objetivo frente a un programa de lógica de restricciones se define si el objetivo se demuestra. En este caso, existe una derivación del par inicial a un par donde el objetivo está vacío. El almacén de restricciones de este segundo par se considera el resultado de la evaluación. Esto se debe a que el almacén de restricciones contiene todas las restricciones que se suponen satisfacibles para demostrar el objetivo. En otras palabras, el objetivo se demuestra para todas las evaluaciones de variables que satisfacen estas restricciones.

La igualdad por pares de los argumentos de dos literales se suele denotar de forma compacta mediante${\displaystyle L(t_{1},\ldots ,t_{n})=L(t_{1}',\ldots ,t_{n}')}$: esta es una abreviatura de las restricciones${\displaystyle t_{1}=t_{1}',\ldots ,t_{n}=t_{n}'}$Una variante común de la semántica para la programación lógica con restricciones añade${\displaystyle L(t_{1},\ldots ,t_{n})=L(t_{1}',\ldots ,t_{n}')}$directamente al almacén de restricciones en lugar de al objetivo.

Se utilizan diferentes definiciones de términos, generando diferentes tipos de programación lógica de restricciones: sobre árboles, reales o dominios finitos. Un tipo de restricción que siempre está presente es la igualdad de términos. Estas restricciones son necesarias porque el intérprete agrega t1=t2al objetivo cada vez que un literal P(...t1...)se reemplaza con el cuerpo de una cláusula variante nueva cuyo encabezado es P(...t2...).

El almacén de restricciones contiene las restricciones que actualmente se consideran satisfacibles. Puede considerarse como la sustitución actual para la programación lógica regular. Cuando solo se permiten términos de árbol, el almacén de restricciones contiene restricciones de la forma t1=t2; estas restricciones se simplifican mediante la unificación, lo que da como resultado restricciones de la forma variable=term; tales restricciones son equivalentes a una sustitución.

Sin embargo, el almacén de restricciones también puede contener restricciones de la forma t1!=t2, si se permite la diferencia !=entre términos. Cuando se permiten restricciones sobre dominios reales o finitos, el almacén de restricciones también puede contener restricciones específicas del dominio como X+2=Y/2, etc.

El almacén de restricciones extiende el concepto de sustitución actual de dos maneras. Primero, contiene no solo las restricciones derivadas de igualar un literal con el inicio de una nueva variante de una cláusula, sino también las restricciones del cuerpo de las cláusulas. Segundo, contiene no solo restricciones de la forma variable=valuesino también restricciones sobre el lenguaje de restricciones considerado. Mientras que el resultado de una evaluación exitosa de un programa lógico regular es la sustitución final, el resultado para un programa lógico de restricciones es el almacén de restricciones final, que puede contener restricciones de la forma variable=valuepero también restricciones arbitrarias.

Las restricciones específicas del dominio pueden llegar al almacén de restricciones tanto desde el cuerpo de una cláusula como al igualar un literal con un encabezado de cláusula: por ejemplo, si el intérprete reescribe el literal A(X+2)con una cláusula cuyo nuevo encabezado variante es A(Y/2), la restricción X+2=Y/2se agrega al almacén de restricciones. Si una variable aparece en una expresión de dominio real o finito, solo puede tomar un valor en los reales o en el dominio finito. Dicha variable no puede tomar como valor un término formado por un functor aplicado a otros términos. El almacén de restricciones es insatisfacible si una variable está obligada a tomar tanto un valor del dominio específico como un functor aplicado a términos.

Tras añadir una restricción al almacén de restricciones, se realizan diversas operaciones sobre este. El tipo de operaciones que se realizan depende del dominio y las restricciones consideradas. Por ejemplo, se utiliza la unificación para igualdades de árboles finitos, la eliminación de variables para ecuaciones polinómicas sobre números reales y la propagación de restricciones para garantizar una forma de consistencia local en dominios finitos. Estas operaciones tienen como objetivo simplificar la comprobación de satisfacibilidad y la resolución del almacén de restricciones.

Como resultado de estas operaciones, la adición de nuevas restricciones puede modificar las antiguas. Es fundamental que el intérprete pueda deshacer estos cambios al retroceder. El método más sencillo consiste en que el intérprete guarde el estado completo del almacén cada vez que realiza una elección (escoge una cláusula para reescribir un objetivo). Existen métodos más eficientes para permitir que el almacén de restricciones vuelva a un estado anterior. En particular, se pueden guardar los cambios realizados en el almacén de restricciones entre dos puntos de elección, incluyendo los cambios realizados en las restricciones antiguas. Esto se puede lograr simplemente guardando el valor anterior de las restricciones que se han modificado; este método se denomina retroceso . Un método más avanzado consiste en guardar los cambios realizados en las restricciones modificadas. Por ejemplo, una restricción lineal se modifica cambiando su coeficiente: guardar la diferencia entre el coeficiente antiguo y el nuevo permite revertir un cambio. Este segundo método se denomina retroceso semántico , ya que se guarda la semántica del cambio en lugar de solo la versión anterior de las restricciones.

Los literales de etiquetado se utilizan en variables sobre dominios finitos para comprobar la satisfacibilidad o la satisfacibilidad parcial del almacén de restricciones y para encontrar una asignación satisfactoria. Un literal de etiquetado tiene la forma labeling([variables]), donde el argumento es una lista de variables sobre dominios finitos. Siempre que el intérprete evalúa dicho literal, realiza una búsqueda sobre los dominios de las variables de la lista para encontrar una asignación que satisfaga todas las restricciones relevantes. Normalmente, esto se hace mediante una forma de retroceso : las variables se evalúan en orden, probando todos los valores posibles para cada una de ellas, y se retrocede cuando se detecta una inconsistencia.

El primer uso del literal de etiquetado consiste en comprobar la satisfacibilidad, total o parcial, del almacén de restricciones. Cuando el intérprete añade una restricción al almacén, solo impone una forma de consistencia local. Esta operación puede no detectar inconsistencias, incluso si el almacén de restricciones es insatisfacible. Un literal de etiquetado sobre un conjunto de variables impone una comprobación de satisfacibilidad de las restricciones sobre dichas variables. En consecuencia, al utilizar todas las variables mencionadas en el almacén de restricciones, se comprueba la satisfacibilidad del mismo.

El segundo uso del literal de etiquetado consiste en determinar una evaluación de las variables que satisfaga el almacén de restricciones. Sin el literal de etiquetado, las variables solo reciben valores cuando el almacén de restricciones contiene una restricción de la forma especificada X=valuey cuando la consistencia local reduce el dominio de una variable a un único valor. Un literal de etiquetado sobre algunas variables obliga a que estas variables se evalúen. En otras palabras, después de considerar el literal de etiquetado, a todas las variables se les asigna un valor.

Por lo general, los programas de lógica de restricciones se escriben de tal manera que los literales de etiquetado se evalúan solo después de que se hayan acumulado tantas restricciones como sea posible en el almacén de restricciones. Esto se debe a que los literales de etiquetado imponen la búsqueda, y la búsqueda es más eficiente si hay más restricciones que satisfacer. Un problema de satisfacción de restricciones se resuelve típicamente mediante un programa de lógica de restricciones con la siguiente estructura:

resolver ( X ):- restricciones ( X ), etiquetado ( X ) restricciones ( X ):- ( todas las restricciones del CSP )

Cuando el intérprete evalúa el objetivo solve(args), coloca el cuerpo de una nueva variante de la primera cláusula en el objetivo actual. Dado que el primer objetivo es constraints(X'), se evalúa la segunda cláusula, y esta operación mueve todas las restricciones en el objetivo actual y, finalmente, en el almacén de restricciones. labeling(X')A continuación, se evalúa el literal, lo que fuerza una búsqueda de una solución en el almacén de restricciones. Dado que el almacén de restricciones contiene exactamente las restricciones del problema original de satisfacción de restricciones, esta operación busca una solución del problema original.

Un programa de lógica de restricciones dado puede reformularse para mejorar su eficiencia. Una primera regla es que los literales de etiquetado deben colocarse después de que se hayan acumulado tantas restricciones sobre los literales etiquetados en el almacén de restricciones. Si bien en teoría es equivalente a , la búsqueda que se realiza cuando el intérprete encuentra el literal de etiquetado se realiza en un almacén de restricciones que no contiene la restricción . Como resultado, puede generar soluciones, como , que luego se descubre que no satisfacen esta restricción. Por otro lado, en la segunda formulación la búsqueda se realiza solo cuando la restricción ya está en el almacén de restricciones. Como resultado, la búsqueda solo devuelve soluciones que son consistentes con ella, aprovechando el hecho de que las restricciones adicionales reducen el espacio de búsqueda.A(X):-labeling(X),X>0A(X):-X>0,labeling(X)X>0X=-1

Una segunda reformulación que puede aumentar la eficiencia es colocar restricciones antes de los literales en el cuerpo de las cláusulas. Nuevamente, y son en principio equivalentes. Sin embargo, la primera puede requerir más cálculo. Por ejemplo, si el almacén de restricciones contiene la restricción , el intérprete evalúa recursivamente en el primer caso; si tiene éxito, entonces descubre que el almacén de restricciones es inconsistente al agregar . En el segundo caso, al evaluar esa cláusula, el intérprete primero agrega al almacén de restricciones y luego posiblemente evalúa . Dado que el almacén de restricciones después de la adición de resulta ser inconsistente, la evaluación recursiva de no se realiza en absoluto.A(X):-B(X),X>0A(X):-X>0,B(X)X<-2B(X)X>0X>0B(X)X>0B(X)

Una tercera reformulación que puede aumentar la eficiencia es la adición de restricciones redundantes. Si el programador sabe (por cualquier medio) que la solución de un problema satisface una restricción específica, puede incluir esa restricción para causar inconsistencia en el almacén de restricciones lo antes posible. Por ejemplo, si se sabe de antemano que la evaluación de B(X)dará como resultado un valor positivo para X, el programador puede agregar X>0antes de cualquier ocurrencia de B(X). Como ejemplo, A(X,Y):-B(X),C(X)fallará en el objetivo A(-2,Z), pero esto solo se descubre durante la evaluación del subobjetivo B(X). Por otro lado, si la cláusula anterior se reemplaza por , el intérprete retrocede tan pronto como la restricción se agrega al almacén de restricciones, lo que sucede incluso antes de que comience la evaluación de .A(X,Y):-X>0,A(X),B(X)X>0B(X)

Las reglas de manejo de restricciones se definieron inicialmente como un formalismo independiente para especificar solucionadores de restricciones, y posteriormente se integraron en la programación lógica. Existen dos tipos de reglas de manejo de restricciones. Las reglas del primer tipo especifican que, bajo una condición dada, un conjunto de restricciones es equivalente a otro. Las reglas del segundo tipo especifican que, bajo una condición dada, un conjunto de restricciones implica otro. En un lenguaje de programación lógica con restricciones que admita reglas de manejo de restricciones, un programador puede usar estas reglas para especificar posibles reescrituras del almacén de restricciones y posibles adiciones de restricciones al mismo. A continuación se muestran ejemplos de reglas:

A(X) <=> B(X) | C(X) A(X) ==> B(X) | C(X)

La primera regla indica que, si B(X)se deduce del almacén, la restricción A(X)puede reescribirse como C(X). Por ejemplo, N*X>0puede reescribirse como X>0si el almacén implica que N>0. El símbolo <=>se asemeja a la equivalencia en lógica e indica que la primera restricción es equivalente a la segunda. En la práctica, esto implica que la primera restricción puede reemplazarse por la segunda.

La segunda regla especifica que la segunda restricción es consecuencia de la primera, si la restricción intermedia se deduce del almacén de restricciones. Por lo tanto, si A(X)está en el almacén de restricciones y B(X)se deduce de este, entonces C(X)se puede añadir al almacén. A diferencia del caso de equivalencia, se trata de una adición y no de una sustitución: se añade la nueva restricción, pero la anterior permanece.

La equivalencia permite simplificar el almacén de restricciones reemplazando algunas por otras más simples; en particular, si la tercera restricción en una regla de equivalencia es true, y la segunda restricción se deduce, la primera restricción se elimina del almacén. La inferencia permite añadir nuevas restricciones, lo que puede llevar a demostrar la inconsistencia del almacén de restricciones y, en general, puede reducir la cantidad de búsqueda necesaria para establecer su satisfacibilidad.

Las cláusulas de programación lógica junto con las reglas de manejo de restricciones se pueden usar para especificar un método para establecer la satisfacibilidad del almacén de restricciones. Se usan diferentes cláusulas para implementar las diferentes opciones del método; las reglas de manejo de restricciones se usan para reescribir el almacén de restricciones durante la ejecución. Como ejemplo, se puede implementar el retroceso con propagación unitaria de esta manera. Sea holds(L)una cláusula proposicional, en la que los literales en la lista Lestán en el mismo orden en que se evalúan. El algoritmo se puede implementar usando cláusulas para la elección de asignar un literal a verdadero o falso, y reglas de manejo de restricciones para especificar la propagación. Estas reglas especifican que holds([l|L])se puede eliminar si l=truesigue del almacén, y se puede reescribir como holds(L)si l=falsesigue del almacén. De manera similar, holds([l])se puede reemplazar por l=true. En este ejemplo, la elección del valor para una variable se implementa usando cláusulas de programación lógica; sin embargo, se puede codificar en reglas de manejo de restricciones usando una extensión llamada reglas de manejo de restricciones disyuntivas o CHR ^∨ .

La estrategia estándar de evaluación de programas lógicos es descendente y en profundidad : a partir del objetivo, se identifican varias cláusulas que podrían demostrarlo, y se realiza una recursión sobre los literales de sus cuerpos. Una estrategia alternativa consiste en partir de los hechos y utilizar cláusulas para derivar nuevos hechos; esta estrategia se denomina ascendente . Se considera mejor que la descendente cuando el objetivo es producir todas las consecuencias de un programa dado, en lugar de demostrar un único objetivo. En particular, encontrar todas las consecuencias de un programa de la manera estándar descendente y en profundidad puede no terminar, mientras que la estrategia de evaluación ascendente sí termina.

La estrategia de evaluación ascendente mantiene el conjunto de hechos probados hasta el momento durante la evaluación. Este conjunto está inicialmente vacío. En cada paso, se derivan nuevos hechos aplicando una cláusula del programa a los hechos existentes y se añaden al conjunto. Por ejemplo, la evaluación ascendente del siguiente programa requiere dos pasos:

A ( q ). B ( X ):- A ( X ).

El conjunto de consecuencias está inicialmente vacío. En el primer paso, A(q)es la única cláusula cuyo cuerpo puede probarse (porque está vacío) y, A(q)por lo tanto, se añade al conjunto actual de consecuencias. En el segundo paso, como A(q)se ha probado, la segunda cláusula puede utilizarse y B(q)se añade a las consecuencias. Como no se puede probar ninguna otra consecuencia a partir de {A(q),B(q)}, la ejecución finaliza.

La ventaja de la evaluación ascendente sobre la descendente radica en que los ciclos de derivaciones no generan un bucle infinito . Esto se debe a que añadir una consecuencia al conjunto actual de consecuencias que ya la contiene no tiene efecto alguno. Por ejemplo, añadir una tercera cláusula al programa anterior genera un ciclo de derivaciones en la evaluación descendente:

A ( q ). B ( X ):- A ( X ). A ( X ):- B ( X ).

Por ejemplo, al evaluar todas las respuestas al objetivo A(X), la estrategia descendente produciría las siguientes derivaciones:

A ( q ) A ( q ):- B ( q ), B ( q ):- A ( q ), A ( q ) A ( q ):- B ( q ), B ( q ):- A ( q ), A ( q ):- B ( q ), B ( q ):- A ( q ), A ( q )