ASP con Potassco

Índice

1. Introducción
2. Conceptos teóricos

1 Introducción

1.1 Instalación e inicio

Estos apuntes son una introducción a la programación con conjuntos de respuestas (ASP del inglés Answer Set Programming) usando los sistemas de Potassco (the Potsdam Answer Set Solving Collection): gringo, clasp y clingo.
Están basados en la guía 2.0 de Potassco (copia local).
En Ubuntu 16.04 se instala con

sudo apt-get install gringo

Instala gringo (4.5.4-1) y clasp (3.1.4-1).
Se puede comprobar la versión conjuntos

gringo --version
clasp -- version

La ayuda se obtiene con

gringo --help

Formas de ejecutarlo

gringo [ opciones | ficheros ] | clasp [ opciones | número ]
clingo [ opciones | ficheros | número ]

donde número es el número de modelos (0 indica todos los modelos).

Para editar en Emacs se instala pasp-mode.
- C-c C-b llama clingo con el contenido del buffer.
- C-c C-x llama clingo con el contenido del buffer y alguna instancia.

1.2 Modelos estables básicos

Idea informal de los modelos estables: es un modelo en el que todo átomo tiene una razón para estar (para cada átomo del modelo existe una regla con dicho átomo en la cabeza y su cuerpo verdadero en el modelo).
Ejemplo de modelos estables de un programa proposicional:

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Programa
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

disco_ide         :- disco_duro, not disco_scsi.
disco_scsi        :- disco_duro, not disco_ide.
controladora_scsi :- disco_scsi.
disco_duro.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Modelos estables
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% > clingo ej_1.2_proposicional.lp 0
% clingo version 4.5.4
% Reading from ej_1.2_proposicional.lp
% Solving...
% Answer: 1
% disco_duro disco_ide
% Answer: 2
% disco_duro disco_scsi controladora_scsi
% SATISFIABLE
% 
% Models       : 2     
% Calls        : 1
% Time         : 0.021s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
% CPU Time     : 0.000s

Ejemplo de elección:

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% > Programa                                                                %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

a :- not b.
b :- not a.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% > Modelos estables                                                        %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Answer: 1
% a
% Answer: 2
% b

Ejemplo de elección excluyente:

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% > Programa                                                                %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

a :- not b.
b :- not a.
:- a, b.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% > Modelos estables                                                        %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Answer: 1
% a
% Answer: 2
% b

1.3 Un ejemplo práctico

Coloreado de grafos:

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% > Enunciado                                                               %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Colorear los nodos de un grafo con tres colores de forma que los nodos de
% cada arco tengan colores ditintos.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% > Hechos                                                                  %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% nodo(X) se verifica si X es un nodo del grafo.
nodo(a).
nodo(b).
nodo(c).
nodo(d).

% arco(X,Y) se verifica si hay un arco de X a Y.
arco(a,b).
arco(b,c).
arco(c,d).
arco(d,a).

% color(X) se verifica si X es un color.
es_color(rojo).
es_color(azul).
es_color(verde).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% > Programa                                                                %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Cada nodo tiene un color.
color(X,rojo) :- 
    nodo(X),
    not color(X,azul),
    not color(X,verde).
color(X,azul) :- 
    nodo(X),
    not color(X,rojo),
    not color(X,verde).
color(X,verde) :- 
    nodo(X),
    not color(X,rojo),
    not color(X,azul).

% Los nodos de un arco son de distinto color:
:-
    arco(X,Y),
    es_color(C),
    color(X,C),
    color(Y,C).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% § Presentación                                                            %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

#show color/2.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% > Modelos                                                                 %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% > clingo coloreado_1.lp 
% clingo version 4.5.4
% Reading from coloreado_1.lp
% Solving...
% Answer: 1
% color(a,rojo) color(b,verde) color(c,azul) color(d,verde)
% SATISFIABLE
% 
% Models       : 1+    
% Calls        : 1
% Time         : 0.002s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
% CPU Time     : 0.000s

2 Conceptos teóricos

2.1 Terminología básica

Def.: Los términos son las variables, las constantes y los términos compuestos de la forma \(f(t_1,\dots,t_n)\), donde \(f\) es un símbolo de función n-aria y \(t_1,\dots,t_n\) son términos.
Def.: Un átomo es una expresión de la forma \(p(t_1,\dots,t_n)\), donde \(p\) es un símbolo de predicado n-ario y \(t_1,\dots,t_n\) son términos. Como metavariables sobre átomos se usan \(a, b, \dots\).
Def.: Un átomo básico es un átomo sin variables.
Def.: Un término básico es un término sin variables.
Def.: Un literal es un átomo \(a\) o su negación not \(a\).
Def.: Un literal negativo es un literal de la forma not \(a\).
Def.: Una regla (general) es una expresión de la forma
\begin{equation} a ← L_1,\dots,L_n. \end{equation}
donde \(a\) es un átomo y los \(L_i \ (i \geq 0)\) son literales. Como metavariable sobre reglas se usa \(R\).
Def.: La cabeza de la regla anterior es \(a\).
Def.: El cuerpo de la regla anterior es \(\{L_1,\dots,L_n\}\).
Def.: Un hecho es una regla con el cuerpo vacío.
Def.: Una regla de Horn es una regla sin literales negativos.
Def.: Un programa lógico es un conjunto de reglas. Como metavariables para programas lógicos se usa \(P\).
Ej.: El programa \(P_1\) es

d(a).
d(b).
p(X) :- not q(X).
q(X) :- not p(X).

Def.: El universo de Herbrand de un programa lógico \(P\), \(UH(P)\), es el conjunto de términos básicos construibles con las constantes y funciones de \(P\).
Ej.: \(UH(P_1) = \{a,b\}\)
Def.: La base de Herbrand de un programa lógico \(P\), \(BH(P)\), es el conjunto de átomos básicos construibles con las constantes, funciones y predicados de \(P\).
Ej.: \(BH(P_1) = \{d(a), d(b), p(a), p(b), q(a), q(b)\}\)
Def.: Una instancia básica de un término (resp. átomo, literal o regla) de un programa \(P\) es la expresión obtenida sustituyendo todas sus variables por elementos de \(UH(P)\).
Def.: La instancia de Herbrand de un programa \(P\), \(IH(P)\), es el conjunto de todas las instancias básicas de sus reglas.
Ej.: La instancia de Herbrand de \(P_1\) es el programa \(P_2\):

d(a).
d(b).
p(a) :- not q(a).
p(b) :- not q(b).
q(a) :- not p(a).
q(b) :- not p(b).

Def.: Una interpretación de un programa \(P\) es un subconjunto de \(BH(P)\). Como metavariables sobre interpretaciones se usan \(I, M\).
Def.: El valor de un átomo \(a\) en una interpretación \(I\) de \(P\) es

I(a) = verdad, si a ∈ I;
     = falso,  si a ∉ I

Def.: La extensión de un predicado n-ario \(p\) del programa \(P\) en la interpretación \(I\) es \[ E_p = \{p(t_1,\dots,t_n) \in UH(P): I(p(t_1,\dots,t_n)) = \mbox{verdad}\} \]
Def.: La interpretación \(I\) satisface al átomo \(a\) si \(I(a)=\mbox{verdad}\). Se representa por \(I \models a\).
Def.: La interpretación \(I\) satisface al literal \(\mbox{no } a\) si \(I(a)=\mbox{falso}\). Se representa por \(I \models \mbox{no } a\).
Def.: La interpretación \(I\) satisface la regla básica \(R\) si no satisface algún literal del cuerpo de \(R\) o satisface la cabeza de \(R\). Se representa por \(I \models R\).
Def.: La interpretación \(I\) es un modelo de Herbrand del programa \(P\) si \(I\) satisface todas las reglas de \(IH(P)\). Se representa por \(I \models P\).
Ej.: \(\{d(a), d(b), p(a), q(b)\} \models P_1\).
Def.: Un modelo minimal de un programa \(P\) es un modelo de \(P\) tal que ningún de sus subconjuntos propio es modelo de \(P\).
Teor. (van Embden y Kowalski) Si \(P\) es un programa sin literales negativos, entonces \(P\) tiene un único modelo minimal. Se llama el menor modelo de Herbrand de \(P\) y se representa por \(MMH(P)\).
Def.: Sea \(P\) un programa básico positivo (sin literales negativos). El operador de consecuencia de \(P\), \(T_P\), es la aplicación del conjunto de las interpretaciones de \(P\) en el conjunto de las interpretaciones de \(P\) definida por \[ T_P(I) = \{h: (h ← a_1,\dots,a_n) \in P \mbox{ y } \{a_1,\dots,a_n\} \subseteq I\} \]
Teor.: Si \(P\) un programa básico positivo, entonces \(MMH(P)\) es el menor punto fijo de \(T_P\) comenzando con la interpretación vacía.
Ej.: El menor punto fijo del siguiente programa es \(\{a,b,c,d\}\).

a.
b.
c :- a.
d :- c, b.
e :- f.

El cálculo anterior se puede hacer con gringo y clingo

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% > Programa                                                                %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

a.
b.
c :- a.
d :- c, b.
e :- f.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% > Forma básica                                                            %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% > gringo -t ej_4.2.lp 
% ej_4.2.lp:15:6-7: info: atom does not occur in any rule head:
%   f
% 
% a.
% b.
% c.
% d.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% > Modelo                                                                  %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% > clingo ej_4.2.lp 
% clingo version 4.5.4
% Reading from ej_4.2.lp
% ej_4.2.lp:15:6-7: info: atom does not occur in any rule head:
%   f
% 
% Solving...
% Answer: 1
% a b c d
% SATISFIABLE
% 
% Models       : 1     
% Calls        : 1
% Time         : 0.001s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
% CPU Time     : 0.000s

2.2 Semántica de modelo estable

Def.: Sea \(P\) un programa básico y \(M \subseteq BH(P)\). El reducto de \(P\) respecto de \(M\), \(P^M\), es el programa positivo obtenido eliminando en \(P\)
- las reglas con literales negativos \(\mbox{no } a\) tales que \(a \in M\)
- los literales negativos de las restantes reglas.
Def.: Sea \(P\) un programa básico y \(M \subseteq BH(P)\). Se dice que \(M\) es un modelo estable de \(P\) si \(M = MMH(P^M)\).
Ej.: Los modelos estables del siguiente programa son \(\{a\}\) y \(\{b\}\)

a :- not b.
b :- not a.

Se puede calcular con clingo

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% > Programa                                                                %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

a :- not b.
b :- not a.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% > Reductos                                                                %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% El reducto del programa respecto de {} es
%    a.
%    b.
% cuyo menor modelo de Herbrand {a,b}. Por tanto, {} no es un modelo estable
% del programa. 
% 
% El reducto del programa respecto de {a} es
%    a.
% cuyo menor modelo de Herbrand {a}. Por tanto, {a} es un modelo estable del
% programa. 
% 
% El reducto del programa respecto de {b} es
%    b.
% cuyo menor modelo de Herbrand {b}. Por tanto, {b} es un modelo estable del
% programa. 
% 
% El reducto del programa respecto de {a,b} es el programa vacío, cuyo menor
% modelo de Herbrand {}. Por tanto, {a,b} no es un modelo estable del programa.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% > Modelos estables                                                        %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% > clingo 0 ej_4.3.lp 
% clingo version 4.5.4
% Reading from ej_4.3.lp
% Solving...
% Answer: 1
% a
% Answer: 2
% b
% SATISFIABLE
% 
% Models       : 2     
% Calls        : 1
% Time         : 0.001s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
% CPU Time     : 0.000s

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% > Comentario                                                              %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Aunque {a,b} es un modelo del programa, no es un modelo estable.

Def.: Sea \(P\) un programa y \(M \subseteq BH(P)\). Se dice que \(M\) es un modelo estable de \(P\) si \(M\) es un modelo estable de \(IH(P)\).

2.3 Transformación básica (en inglés, grounding)

Def.: Dos programas lógicos son equivalentes si tienen los mismos modelos estables.
Def.: Una transformación básica es una aplicación \(T\) que transforma cada programa lógico \(P\) en otro \(T(P)\) que es básico y equivalente a \(P\).
Def.: La transformación básica \(T\) es local si existe una transformación \(T'\) de reglas en programas tal que para cada programa lógico \(P\), \(T(P) = \bigcup_{R \in P}T'(R)\).
Def.: Sea \(P\) un programa. Una sustitución (en inglés, variable binding) es una aplicación del conjunto de las variables de \(P\) en \(UH(P)\).
Nota: El tamaño de \(IH(P)\) suele ser exponencial en el tamaño de \(P\).
Nota: Generalmente, muchas de las reglas de \(IH(P)\) tiene su cuerpo insatisfacible, pudiéndose eliminar sin perder la equivalencia del programa.

Ej. de cálculo de la forma básica de un programa

Una forma básica del programa es

d(a).
e(b).
e(c).
p(X) :- d(X), not q(X).
q(X) :- d(X), not p(X).

Su instanciación de Herbrand es

d(a).
e(b).
e(c).
p(a) :- d(a), not q(a).
p(b) :- d(b), not q(b).
p(c) :- d(c), not q(c).
q(a) :- d(a), not p(a).
q(b) :- d(b), not p(b).
q(c) :- d(c), not p(c).

Al no ser posible deducir \(d(b)\) ni \(d(c)\), el programa anterior es equivalente a

d(a).
e(b).
e(c).
p(a) :- d(a), not q(a).
q(a) :- d(a), not p(a).

Que. a su vez, es equivalente a

d(a).
e(b).
e(c).
p(a) :- not q(a).
q(a) :- not p(a).

Se puede calcular con gringo

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% > Programa                                                                %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

d(a).
e(b).
e(c).
p(X) :- d(X), not q(X).
q(X) :- d(X), not p(X).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% > Forma básica                                                            %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% > gringo -t ej_instanciacion_1.lp 
% d(a).
% e(b).
% e(c).
% p(a):-not q(a).
% q(a):-not p(a).

2.4 Predicados de dominio

2.4.1 Definición de predicados de dominio

Def.: Sea \(P\) un programa lógico. El grafo de dependencia de \(P\) es un grafo etiquetado \(G_P = (V_P,E_P)\)
- \(V_P = \{p: p \mbox{ es un predicado de } P\}\) y
- \((a,b,e) \in E_P\) syss existe una regla en \(P\) con el predicado \(a\) en la cabeza y el predicado \(b\) en el cuerpo y la etiqueta \(e \in \{+,-\}\) indica si \(b\) ocurre en un literal positivo o negativo del cuerpo de la regla (un arco pude tener las dos etiquetas).
Def.: Sea \(P\) un programa y \(a\) y \(b\) dos predicados de \(P\). Se dice que \(a\) depende de \(b\) si hay un camino de \(a\) a \(b\) en el grafo de dependencia de \(P\).
Ej.: Se considera el siguiente programa

hombre(a).
mujer(b).
padre(a,b).
antecesor(X,Y) :- hombre(X), antecesor(X,Z), padre(Z,Y).
antecesor(X,Y) :- padre(X,Y).
hijo(X,Y) :- padre(Y,X), hombre(X).
hija(X,Y) :- padre(Y,X), mujer(X).

Ej.: En el programa anterior
- antecesor depende de antecesor y padre,
- hijo depende de padre y hombre e
- hija depende de padre y mujer.
Def.: Sea \(P\) un programa y \(q\) un predicado de \(P\). Se dice que \(q\) es un predicado de dominio de \(P\) si todo camino en el grafo de dependencia de \(P\) que comienza en \(q\) carece de ciclos con arcos negativos.
Nota: Los predicados de las cabezas de las reglas extendidas no son predicados de dominio.
Ej.: Todos los predicados del programa anterior son predicados de dominio.
En el siguiente programas, todos los predicados son de dominio salvo interesante, insulso y par_interesante

numero(0..5).
par(0).
par(X+1) :- numero(X), impar(X).
impar(X+1) :- numero(X), par(X).
multiplo_de_2(X) :- par(X).
interesante(X) :- numero(X), not insulso(X).
insulso(X) :- numero(X), not interesante(X).
par_interesante(X) :- par(X), interesante(X).

2.4.2 Transformación básica y predicados de dominio

Nota: En la transformación básica de gringo se usan los predicados de dominio para buscar las posibles sustituciones.

Ejemplo

Se considera el programa

d(a,b).
d(b,c).
d(c,a).
p(X,Y,Z) :- d(X,Y), d(Y,Z), not q(X,Y,Z).
q(X,Y,Z) :- d(X,Y), d(Y,Z), not p(X,Y,Z).

El predicado de dominio del programa anterior es §d§ y una forma básica es

d(a,b).
d(b,c).
d(c,a).
q(b,c,a) :- d(b,c), d(c,a), not p(b,c,a).
q(a,b,c) :- d(a,b), d(b,c), not p(a,b,c).
q(c,a,b) :- d(c,a), d(a,b), not p(c,a,b).
p(b,c,a) :- d(b,c), d(c,a), not q(b,c,a).
p(a,b,c) :- d(a,b), d(b,c), not q(a,b,c).
p(c,a,b) :- d(c,a), d(a,b), not q(c,a,b).

Su cálculo con gringo es

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% > Programa                                                                %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

d(a,b).
d(b,c).
d(c,a).
p(X,Y,Z) :- d(X,Y), d(Y,Z), not q(X,Y,Z).
q(X,Y,Z) :- d(X,Y), d(Y,Z), not p(X,Y,Z).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% > Forma básica                                                            %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% > gringo -t ej_instanciacion_2.lp 
% d(a,b).
% d(b,c).
% d(c,a).
% p(c,a,b):-not q(c,a,b).
% p(a,b,c):-not q(a,b,c).
% p(b,c,a):-not q(b,c,a).
% q(c,a,b):-not p(c,a,b).
% q(a,b,c):-not p(a,b,c).
% q(b,c,a):-not p(b,c,a).

Ejemplo

Se considera el programa

p(X,Y) :- d1(X,Y), not q(X,Y).
q(X,Y) :- d1(X,Y), not p(X,Y).
d1(X,Y) :- d2(X), d3(Y), not d4(X).
d2(a).
d2(b).
d3(c).
d4(a).

los predicados de dominio son d1, d2, d3 y d4. Una forma básica es

d4(a).
d3(c).
d2(a).
d2(b).
d1(b,c) :- d2(b), d3(c), not d4(b).
q(b,c) :- d1(b,c), not p(b,c).
p(b,c) :- d1(b,c), not q(b,c).

Su cálculo con gringo es

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% > Programa                                                                %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

p(X,Y) :- d1(X,Y), not q(X,Y).
q(X,Y) :- d1(X,Y), not p(X,Y).
d1(X,Y) :- d2(X), d3(Y), not d4(X).
d2(a).
d2(b).
d3(c).
d4(a).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% > Forma básica                                                            %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% > gringo -t ej_instanciacion_3.lp 
% d2(a).
% d2(b).
% d3(c).
% d4(a).
% d1(b,c).
% p(b,c):-not q(b,c).
% q(b,c):-not p(b,c).

2.4.3 Construcción de predicados de dominios

Teor.: Las operaciones del álgebra relacional sobre predicados de dominio produce predicados de dominio

% Unión de P y Q:
u(X) :- p(X).
u(X) :- q(X).

% Intersección de P y Q:
i(X) :- p(X), q(X).

% Diferencia de P y Q:
d(X) :- p(X), not q(x).

% Producto cartesiano de P y Q:
c(X,Y) :- p(X), q(Y).

% Cruce de P y Q:
j(X,Y,Z) :- p(X,Y), q(Y,Z).

% Diferencia simétrica
s(X) :- p(X), not q(X).
s(X) :- q(X), not p(X).