Una introducción a la programación con conjuntos de respuesta. Aplicaciones

TRABAJO FIN DE GRADO FACULTAD DE MATEM ´ ATICAS Departamento de Ciencias de la Computaci´on e Inteligencia Artificial Una introducci´on a la programaci´on con conjuntos de respuesta. Aplicaciones Presentado por: Marina Jim´ enez N´ u˜ nez Dirigido por: Andr´ es Cord´ on Franco Mar ´ ıa Jos´ e Hidalgo Doblado ´ Indice general Abstract 3 Agradecimientos 4 Introducci´on 5 1. Introducci´on a CLINGO 8 1.1. Sintaxis y sem´antica de programas ASP . . . . . . . . . . . . 8 1.1.1. Sem´antica informal . . . . . . . . . . . . . . . . . . . . 15 1.1.2. Sem´antica formal . . . . . . . . . . . . . . . . . . . . . 19 1.2. Sintaxis del sistema CLINGO . . . . . . . . . . . . . . . . . . 26 1.2.1. Algunas generalidades . . . . . . . . . . . . . . . . . . 26 1.2.2. Disyunci´on ........................ 28 1.2.3. Constantes boolenas . . . . . . . . . . . . . . . . . . . 28 1.2.4. Funciones aritm´eticas . . . . . . . . . . . . . . . . . . . 29 1.2.5. Predicados de igualdad y orden . . . . . . . . . . . . . 29 1.2.6. Intervalos ......................... 31 1.2.7. Agrupaci´on ........................ 31 1.2.8. Condicionales . . . . . . . . . . . . . . . . . . . . . . . 32 1 1.2.9. Restricciones . . . . . . . . . . . . . . . . . . . . . . . 33 2. Propiedades de los programas en ASP 35 2.1. Conjuntos de respuesta: Existencia, unicidad y propiedades . . 35 3. Bases de conocimiento 45 3.1. Introducci´on............................ 45 3.2. Modelizaci´on de un barrio . . . . . . . . . . . . . . . . . . . . 46 3.3. Modelizaci´on de las relaciones familiares . . . . . . . . . . . . 51 3.3.1. Definici´on recursiva de antepasado . . . . . . . . . . . 51 3.3.2. Definici´on de hijo ´unico . . . . . . . . . . . . . . . . . 53 3.4. Modelizaci´on de un conjunto de medios de transporte . . . . . 55 4. Representaci´on por defecto 60 4.1. Representaci´on por defecto y tipos de excepciones . . . . . . . 60 4.2. Modelizaci´on de la informaci´on con valores nulos . . . . . . . . 69 4.3. Prioridad entre defectos . . . . . . . . . . . . . . . . . . . . . 73 4.4. Defectos en bases de conocimiento jer´arquicas . . . . . . . . . 77 5. El paradigma de programaci´on ASP 83 5.1. Ciclos hamiltonianos de un grafo . . . . . . . . . . . . . . . . 83 5.2. Sudokus .............................. 89 6. Aplicaciones 94 6.1. PuzzleNurikabe.......................... 94 6.2. Puzzle Heyawake . . . . . . . . . . . . . . . . . . . . . . . . . 102 6.3. PuzzleMasyu...........................110 2 Abstract The main objective of this paper is to present the answer set programming paradigm as a tool to model and solve combinatorial problems, in general, and especially NP-complete or NP-hard problems. First, in chapters 1 and 2, we are going to focus on carrying out a theorical development to help us learning how to program in ASP and, in particular, in CLINGO, and some properties that ASP programs have. In the following chapters, 3 and 4, we are going to study representations of real situations and problems to apply these results then to relevant mathematical problems in chapter 5. Finally, in chapter 6, we study puzzles in which deciding whether there is a solution to them is a NPcomplete problem. 3 Agradecimientos En primer lugar, me gustar´ıa agradecer a mis tutores Andr´es Cord´on Franco y Mar´ıa Jos´e Hidalgo Doblado la ayuda y el apoyo que me han ofrecido durante todo el proceso de realizaci´on de este trabajo. En segundo lugar, quisiera agradecer a mis compa˜neros la infinita paciencia que han demostrado tener y el haberme ayudado siempre. Gracias a los que han empezado esta etapa conmigo y a los que he encontrado por el camino y me han acompa˜nado hasta el fin de la misma. Por ´ultimo, dar las gracias a mis hermanos y a mis padres. Nunca encontrar´e las palabras para agradeceros el cari˜no que he recibido durante todos estos a˜nos. Gracias por confiar en m´ı hasta cuando yo misma no lo hice. Sois mi mayor suerte, mi mayor orgullo y mi ejemplo a seguir por y para siempre. 4 Introducci´on El principal objetivo del presente trabajo es presentar el paradigma de la programaci´on con conjuntos de respuestas como una herramienta para modelizar y resolver problemas combinatorios, en general, y muy especialmente problemas NP-completos o NP-duros. En la actualidad, es generalmente aceptado que la clase de complejidad computacional P, que comprende los problemas computacionales resolubles por alg´un algoritmo en tiempo polinomial, captura la noci´on de “problema tratable” (esto es, problemas que pueden resolverse en un tiempo de ejecuci´on “razonable” incluso para entradas de tama˜no grande). La clase de complejidad NP comprende aquellos problemas computacionales tales que, dado un candidato, verificar si es o no una soluci´on del problema puede hacerse en tiempo polinomial (pero, a priori, no se sabe si encontrar una soluci´on del problema puede tambi´en conseguirse en tiempo polinomial). Determinar si las clases P y NP son o no iguales es el famoso problema P versus NP, uno de los principales problemas abiertos en la Matem´atica actual. Dentro de la clase NP, destacan un tipo de problemas muy relevantes: los problemas NP-completos. Un problema A se dir´a NP-completo si: 1) pertenece a la clase NP y 2) cualquier otro problema en la clase NP es reducible (en tiempo polinomial) a dicho problema A. Los problemas NP-completos constituyen, por tanto, la clase de los problemas “m´as dif´ıciles” dentro de la clase NP. Es bien conocido que hay multitud de problemas matem´aticos interesantes que resultan ser NP-completos. M´as generalmente, un problema A se dir´a NP-duro (o NP-hard) si cualquier problema en la clase NP es reducible (en tiempo polinomial) a dicho problema A, aunque ahora A no tiene por qu´e pertenecer a NP. De nuevo, la clase de problemas NP-duros captura la idea de “problemas computacionales presumiblemente dif´ıciles de resolver”. La programaci´on con conjuntos de respuesta (o Answer Set Programming, cuyo acr´onimo es ASP) es una programaci´on distinta a la tradicional (se enmarca en el campo de la programaci´on declarativa) cuyo principal enfoque es buscar soluci´on a problemas de b´usqueda dif´ıciles, principalmente problemas NP-completos o NP-duros. 5 Para el desarrollo del trabajo, necesitamos adentrarnos un poco m´as en la programaci´on con conjuntos de respuesta, es decir, necesitamos saber qu´e son los programas de ASP, qu´e elementos los forman y qu´e propiedades tienen estos programas y sus soluciones, los denominados conjuntos de respuesta. Esto es lo que se estudia en los cap´ıtulos 1 y 2 de este trabajo. En el cap´ıtulo 1, abordamos la sintaxis y la sem´antica, tanto formal como informal, de los programas de ASP, en la que se exponen algunos ejemplos para ilustrar el contenido. Adem´as, en el cap´ıtulo se habla tambi´en acerca de la sintaxis de los programas de ASP en CLINGO, sistema que usaremos a lo largo del trabajo para representar y resolver los problemas que se van contemplando. En el cap´ıtulo 2, nos centramos en estudiar las propiedades de los programas de ASP y de sus soluciones. Para el cap´ıtulo 1 y 2, se usa principalmente informaci´on procedente de [GK14], [Lif08], [Lif19], [GKK+19], [GL88] y los apuntes de la p´agina web [HD21] que mencionamos en la bibliograf´ıa. Para abordar nuestro objetivo, la b´usqueda de soluciones para problemas NP-hard, necesitamos aprender a representar problemas reales. Nos centramos en esto mismo en el cap´ıtulo 3: en este, vemos c´omo construir las denominadas bases de conocimiento, en las que se estudia c´omo representar situaciones reales, a trav´es de diversos ejemplos, en los que intentamos mostrar la importancia de la representaci´on de todo el conocimiento, incluido el que se posee por sentido com´un, y tambi´en se muestra c´omo representar situaciones en las que la informaci´on no es completa o posee una estructura jer´arquica. En el cap´ıtulo 4, se estudian las situaciones en las que aparecen defectos, es decir, situaciones que se rigen por expresiones como generalmente, habitualmente, etc, y las excepciones que nos podemos encontrar en este tipo de circunstancias, recuperando los ejemplos que se exponen en el cap´ıtulo 3 y a˜nadi´endoles algunos defectos. Para estas secciones, seguimos principalmente el libro [GK14] y la p´agina web [HD21]. Mientras que en los cap´ıtulos 3 y 4 nos centramos principalmente en la representaci´on del problema o situaci´on que se contempla y en encontrar elementos que verifiquen ciertas reglas, en el cap´ıtulo 5, el enfoque cambia: el objetivo es buscar soluciones a problemas a trav´es de reducirlos a encontrar programas de ASP cuyos conjuntos de respuesta nos den estas mismas soluciones. Exponemos c´omo se pueden plantear estos programas con el estudio de un problema matem´atico famoso, el encontrar los ciclos hamiltonianos de un grafo, y un puzzle, el sudoku. Para este cap´ıtulo, se vuelve a usar tanto la p´agina web [HD21] como el libro [GK14]. Finalmente, en el cap´ıtulo 6, planteamos algunos puzzles interesantes en 6 la programaci´on con conjuntos de respuesta desde un punto de vista computacional y dada su representaci´on. Estos puzzles son el Nurikabe, el puzzle Heyawake y por ´ultimo, el puzzle Masyu. Con estos puzzles, tratamos totalmente nuestro objetivo, ya que decidir cu´ando hay una soluci´on para estos puzzles y cu´ando no constituye un problema NP-completo (problema NP y NP-hard al mismo tiempo). Para este cap´ıtulo, se sigue muy de cerca la referencia [CKK+07]. Para ilustrar nuestros programas, se han resuelto algunos ejemplos de puzzles extra´ıdos de aplicaciones y p´aginas web para la generaci´on aleatoria de los mismos. Para este trabajo, no se necesitan conocimientos previos sobre la programaci´on con conjuntos de respuesta ni acerca del sistema CLINGO, pues el desarrollo te´orico necesario para la comprensi´on del trabajo se realiza a lo largo del mismo. 7 Cap´ıtulo 1 Introducci´on a CLINGO CLINGO es un sistema desarrollado en la Universidad de Postdam con la finalidad de representar y resolver problemas en el marco de la programaci´on de conjunto de respuesta (en ingl´es, Answer Set Programming, de donde proceden las siglas ASP). En este cap´ıtulo, nos centraremos en presentar los elementos esenciales de este lenguaje para poder entender los restantes cap´ıtulos de este trabajo. Para una informaci´on completa de este sistema se puede visitar la p´agina web: https://potassco.org. 1.1. Sintaxis y sem´antica de programas ASP ASP es un tipo de programaci´on declarativa orientada a la resoluci´on de problemas combinatorios. A trav´es de un conjunto de reglas, se describen los objetos de un dominio y las relaciones que hay entre estos objetos. Para poder definir qu´e es un programa de ASP, veamos primero los elementos que pueden aparecer en estos programas, que son las constantes, las funciones, los predicados y las variables. El conjunto de los nombres de las constantes del programa se denominar´a O, y de igual forma, denotaremos como F,PyVal conjunto de los nombres de las funciones, los predicados y las variables respectivamente. Los predicados expresan las relaciones que hay entre los objetos o propiedades de los mismos. Se denomina signatura a Σ =< O, F, P, V > Veamos algunos ejemplos. 8 •Satisface la regla: p(a) or p(b) ←p(c), not q(c). pues no satisface el cuerpo. •Satisface la regla: p(a) ← ¬p(b). pues satisface el cuerpo y la cabeza de la regla. •No satisface: p(b) ←p(a), not p(c), not -p(c). pues satisface el cuerpo de la regla y no satisface la cabeza. Las restricciones, como dec´ıamos antes, son reglas que no poseen cabeza. Por tanto, para que un conjunto L satisfaga una restricci´on, alguno de los literales extendidos del cuerpo de la regla debe no satisfacerse en L. Ejemplo 10. El conjunto L={p(a)}satisface la restricci´on: ←p(a),¬q(b),not p(c), not ¬q(a). 1.1.1. Sem´antica informal La definici´on que vimos antes de conjunto de respuesta es una definici´on informal. En esta secci´on, vamos a estudiar algunos ejemplos de programas y de sus conjuntos de respuestas correspondientes. Ejemplo 1. a←b. % Cree a si cree b b. % Cree b La segunda regla del programa nos obliga a creer b. Como los conjuntos de respuesta del programa deben satisfacer todas las reglas, por la primera regla estamos obligados a creer a. As´ı, el conjunto {a b}constituye un conjunto de respuesta del programa pues satisface todas las reglas, no contiene contradicciones y verifica el principio de racionalidad. Por otro lado, el conjunto {a b c}verifica tambi´en todas las reglas y no contiene contradicciones, pero no es un conjunto de respuesta pues no verifica el principio de racionalidad (no debe creer nada que no est´e obligado a creer, y sin embargo no hay ninguna regla que obligue a creer c). 15 Ejemplo 2 (Negaci´on cl´asica). ¬a← ¬b. ¬b. Los conjuntos de respuesta del programa deben satisfacer todas las reglas. Para ello, deben contener a ¬b(si no, no se satisfacer´ıa la segunda regla). Para satisfacer la primera, como ya satisfacen el cuerpo, deben satisfacer la cabeza, luego tambi´en deben contener a ¬a. Por tanto, el conjunto {¬b¬a} es un conjunto de respuesta para el programa, ya que satisface las reglas, no contiene contradicciones y verifica el principio de racionalidad. Ejemplo 3 (Disyunci´on epist´emica). a or b. %Cree a o cree b. Tanto {a}y{b}como {a b}son conjuntos que satisfacen las reglas del programa, pero solo los dos primeros son conjuntos de respuesta pues el tercero no satisface el principio de racionalidad (cree m´as de lo que est´a obligado a creer). Esto no significa que la disyunci´on epist´emica sea excluyente, de hecho el programa: a or b. a. b. tiene como conjunto de respuesta a {a b}, lo cual ser´ıa una contradicci´on si la disyunci´on fuese excluyente (al ser excluyente, se podr´ıa creer aob, pero no los dos a vez). Podemos expresar la disyunci´on excluyente a trav´es del siguiente programa: a or b. ¬a or ¬b. En cuyo caso los conjuntos de respuesta son {a¬b}y{b¬a}. Ejemplo 4 (Restricciones). a or b ←c. c. ←a. 16 La segunda regla nos obliga a creer c. La primera nos indica que si se cree c, se cree aob, luego los conjuntos {c a}y{c b}son posibles conjuntos de respuesta. Pero por la tercera nos es imposible creer a, luego el ´unico conjunto de respuesta de este programa es {c b}. Ejemplo 5 (Negaci´on por defecto). Supongamos el programa: p(a) ←not p(b). Este programa nos obliga a creer p(a) si p(b) no pertenece al conjunto de certezas. Como no hay ninguna regla que tenga a p(b) en la cabeza, no tenemos por qu´e creer p(b), luego se verifica el cuerpo de la regla. Para satisfacer la cabeza, se debe creer p(a). De este modo, {p(a)}constituye el ´unico conjunto de respuesta del programa. Si consideramos ahora el siguiente programa m´as completo: p(a) ←not p(b). p(d) ←not p(c). p(c) ←not p(e). p(b). La cuarta regla nos obliga a creer p(b). Como se cree p(b), el cuerpo de la primera regla no se verifica. Como no hay ninguna regla que tenga a p(e) en su cabeza, se satisface el cuerpo de la tercera regla, por tanto p(c) formar´a parte del conjunto de respuesta. Como se cree p(c), no se verifica el cuerpo de la segunda regla. As´ı, s´olo estamos obligados a creer p(b) y p(c). El conjunto de respuesta de este programa es por tanto {p(c) p(b)}. Pasemos ahora a definir qu´e se entiende por consecuencia de un programa. Un programa P implica un conjunto de literales L si L est´a contenido en todos los conjuntos de respuesta de P. Se dice entonces que L es una consecuencia de P y se denota por P L. En la l´ogica cl´asica, la relaci´on de implicaci´on tiene la propiedad de ser mon´otona, es decir, aunque a˜nadamos nuevas hip´otesis adicionales a un teorema, las consecuencias del teorema original se mantienen. Sin embargo, la relaci´on de implicaci´on que acabamos de definir no es mon´otona: al a˜nadir nueva informaci´on al programa P, puede ocurrir que las consecuencias de P disminuyan. 17 Siguiendo con el segundo programa del Ejemplo 5, podemos ver que los literales p(b) y p(c) son consecuencias de este, sin embargo, al a˜nadirle una nueva regla: p(a) ←not p(b). p(d) ←not p(c). p(c) ←not p(e). p(b). p(e). p(c) deja de ser una consecuencia. Se denomina consulta a una conjunci´on o disyunci´on de literales. A las consultas que carecen de variables se les llama b´asicas. La respuesta a una consulta ser´a: 1. Si la consulta es conjuntiva, L1∧. . . ∧Ln, entonces: Si P {L1,. . . ,Ln}, entonces la respuesta es s´ı. Si existe alg´un ital que P Li, entonces la respuesta es no. En otro caso, la respuesta es desconocido. 2. Si la consulta es disyuntiva, L1or . . . or Ln, entonces: Si existe alg´un ital que P Li, entonces la respuesta es s´ı. Si P {L1,. . . ,Ln}, entonces la respuesta es no. En otro caso, la respuesta es desconocido. 3. Si la consulta es de la forma p(X1, . . . , Xn) donde los Xison variables, entonces la respuesta es una lista de t´erminos t1, . . . , tnde manera que Pp(t1, . . . , tn). donde Ldenota el literal complementario de L. Consideramos el siguiente ejemplo: Ejemplo 6 (Hip´otesis del mundo cerrado). Se considera el programa: p(a) ←not q(a). 18 Como q(a) no aparece como cabeza de ninguna regla, se verifica el cuerpo de la ´unica regla del programa y por tanto el ´unico conjunto de respuesta que posee es {p(a)}. Veamos las respuestas a las siguientes consultas: ¿p(a)? La respuesta es s´ı, pues p(a) es consecuencia del programa. ¿q(a)? La respuesta es desconocido, pues ni q(a) ni ¬q(a) son consecuencias del programa. ¿p(a) or q(a)? Como el programa implica p(a), la respuesta es s´ı. ¿p(a) ∧q(a)? La respuesta es desconocido, pues p(a) es consecuencia del programa pero ni q(a) ni ¬q(a) son consecuencias. Consideremos ahora el programa a˜nadiendo una regla m´as, la cual se denomina hip´otesis del mundo cerrado: p(a) ←not q(a). ¬q(X) ←not q(X). Debemos entender esta regla como: si q(X) no pertenece al conjunto de certezas del programa entonces q(X) es falso. Esto implica que cada vez que se tenga un t´ermino b´asico t,q(t) o ¬q(t) va a pertencer al conjunto de respuesta. As´ı, el ´unico conjunto de respuesta del programa es {p(a) ¬q(a)} y por tanto las respuestas a las consultas anteriores ahora son: ¿p(a)? La respuesta es s´ı, pues p(a) es consecuencia del programa. ¿q(a)? La respuesta es no, pues ¬q(a) es consecuencia del programa. ¿p(a) or q(a)? La respuesta es s´ı porque el programa implica p(a). ¿p(a) ∧q(a)? La respuesta es no, pues el programa implica ¬q(a). 1.1.2. Sem´antica formal Para ver la definici´on formal de conjunto de respuesta, usamos la noci´on de consistencia: Un conjunto L de literales b´asicos es consistente si no contiene literales complementarios. Adem´as, debemos tener en cuenta si el programa contiene o no contiene negaci´on por defecto. 19 Conjuntos de respuesta I: programas sin negaci´on por defecto. Consideremos en primer lugar ´unicamente programas cuyas reglas no contienen negaci´on por defecto. En estas condiciones, un conjunto L es un conjunto de respuesta para un programa P si: 1. L es consistente. 2. L satisface las reglas del programa. 3. L es minimal: ning´un subconjunto propio de L satisface todas las reglas de P. A continuaci´on vamos a ver varios ejemplos, retomando algunos descritos con anterioridad en la Secci´on 1.1.1: Ejemplo 7 (Ejemplo 1 de la Secci´on 1.1.1) a←b. b. El conjunto L={a b}es un conjunto de respuesta para este programa pues: Es consistente, no contiene literales complementarios. Satisface todas reglas del programa: satisface la regla de cuerpo vac´ıo pues b∈L. Para satisfacer la primera regla, como satisface el cuerpo de la regla, debe satisfacer la cabeza, lo cual ocurre pues a∈L. Es minimal: el conjunto ∅no satisface la segunda regla. Lo mismo ocurre con {a}. Por otro parte, el conjunto {b}no satisface la primera. De este modo, no hay subconjuntos propios de Lque satisfagan todas las reglas. Adem´as es el ´unico conjunto de respuesta que posee el programa: si existiese otro conjunto Mdistinto a Lde manera que fuese tambi´en un conjunto de respuesta del programa, entonces para satisfacer todas las reglas, Ltendr´ıa que estar contenido en M. Pero entonces Lser´ıa un subconjunto propio de Mque satisfacer´ıa todas las reglas del programa, luego Mno ser´ıa minimal y por tanto llegar´ıamos a una contradicci´on. Algunas observaciones acerca del programa: 20 G¿Es auna consecuencia del programa? S´ı. G¿Es buna consecuencia del programa? S´ı. G¿Es ¬auna consecuencia del programa? No. G¿Es ¬buna consecuencia del programa? No. Ejemplo 8 (Ejemplo 3 de la Secci´on 1.1.1: disyunci´on epist´emica.) Consideramos de nuevo el programa: a or b. Los conjuntos L1={a}yL2={b}son conjuntos de respuesta para este programa: satisfacen las reglas, son minimales (el ´unico subconjunto propio que poseen ambos conjuntos es ∅, que no satisface la regla) y son consistentes. Con esta definici´on formal de conjunto de respuesta se puede ver tambi´en que el conjunto {a b}no es un conjunto de respuesta del programa: No es minimal, pues los subconjuntos {a}y{b}son propios y satisfacen las reglas del programa. Si nos planteamos algunas de las consultas anteriores, tenemos que: G¿Es auna consecuencia del programa? Desconocido, pues para ser consecuencia, adeber´ıa pertenecer a todos los conjuntos de respuesta del programa pero a /∈ {b}, y por otro lado, el programa tampoco implica a¬a G¿Es buna consecuencia del programa? Desconocido: al igual que antes, el programa no implica a bpues este no pertenece al conjunto de respuesta {a}, y tampoco implica a ¬b. Otro programa cuyas reglas contienen disyunci´on epist´emica es el siguiente: a or ¬a. b←a. b← ¬a. Veamos que los conjuntos de respuesta del programa son L1={b a}y L2={b¬a}: 21 1. Ambos conjuntos son consistentes. 2. Verifican las reglas: L1satisface la primera regla pues contiene al t´ermino a, satisface la segunda regla pues verifica tanto el cuerpo, ya que contiene al t´ermino a, como la cabeza, porque contiene a b, y satisface la tercera regla al no satisfacer su cuerpo. De manera an´aloga podemos ver que L2satisface todas las reglas del programa. 3. Son minimales: todos los t´erminos presentes en L1son necesarios para satisfacer las reglas del programa, as´ı que este no puede contener subconjuntos propios que verifiquen todas las reglas. Con el mismo razonamiento obtenemos que L2es minimal. Como ya comentamos en la Secci´on 1.1, aor ¬ano es una tautolog´ıa. As´ı, si consideramos el programa anterior sin la primera regla, el ´unico conjunto de respuesta es ∅, ya que nada nos obliga a creer que ao¬asea cierto, luego no se verifica el cuerpo de ninguna de las dos reglas. Ejemplo 9. Consideremos el siguiente programa P: p(a) ←q(a). ¬p(a). El conjunto L={¬p(a)}es un conjunto de respuesta del programa pues es consistente, satisface todas las reglas del programa y es minimal (el ´unico subconjunto propio que tiene es el ∅, que no satisface la segunda regla). De manera an´aloga que en el ejemplo anterior, se puede ver que de hecho es el ´unico conjunto de respuesta del programa. Podemos plantear las siguientes consultas: ¿¬p(a)? La respuesta es s´ı, pues P ¬p(a). Por este motivo, la respuesta a la consulta ¿p(a)? es no. Las consultas ¿q(a)? y ¿¬q(a)? obtienen la misma respuesta: desconocido, pues ni q(a) ni su complementario son consecuencias del programa. Anotaci´on: Este ejemplo muestra la diferencia con la implicaci´on cl´asica. Mientras que en nuestro caso el literal ¬q(a) no es una consecuencia, si hubi´esemos utilizado la implicaci´on cl´asica s´ı ser´ıa una consecuencia. 22 Conjuntos de respuesta II: programas con negaci´on por defecto. Consideremos ahora programas P cuyas reglas pueden contener negaci´on por defecto. Denotamos por PSel programa reducido de P respecto del conjunto de literales b´asicos S, que se forma eliminando para cada literal I∈S todas las reglas del programa que contienen a not Iy eliminando de las restantes reglas las premisas que contengan negaci´on por defecto. En esta situaci´on, S es un conjunto de respuesta de P si lo es de ground(P)S. Ejemplo 10. Sea el programa Q: Regla 1: p(a) or q(a) ←r(a), not p(b), not q(b). Regla 2: p(a) ← ¬r(a), p(b), not q(b). Regla 3: q(a) ←not q(b), not r(b). Regla 4: p(b) ←not q(a), r(b). Regla 5: ¬r(b). Regla 6: p(a) ←q(a), ¬r(b). y el conjunto S={r(a), p(b), q(a),¬r(b)}. Entonces, el programa reducido de Q respecto de S es: p(a) ← ¬r(a), p(b). (Proviene de la regla 2) q(a). (Proviene de la regla 3) ¬r(b). (Regla 5, no conten´ıa negaci´on por defecto) p(a) ←q(a), ¬r(b). (Regla 6, no conten´ıa negaci´on por defecto) La regla 1 del programa Q ha sido eliminada pues conten´ıa al literal extendido not p(b) yp(b)∈S. Por el mismo motivo se elimina la regla 4, pues aparece en ella not q(a) yq(a)∈S. De este modo, para comprobar que S es un conjunto de respuesta de un programa P cualquiera, debemos: 1. Calcular ground(P). 2. Calcular ground(P)S. 3. Comprobar que S es consistente y satisface todas las reglas de ground(P)S. 23 4. Comprobar que S es minimal, es decir, ning´un subconjunto propio de S satisface todas las reglas de ground(P)S. Proseguimos con algunos ejemplos: Ejemplo 11 (Ejemplo 5 de la Secci´on 1.1.1: negaci´on por defecto.) Sea P: p(a) ←not p(b). Tomemos el conjunto S={p(a)}.El programa reducido de P respecto de S, PS, es: p(a). ya que como no hay ninguna regla que contenga a not p(a), empezamos directamente a eliminar las premisas que contienen negaci´on por defecto de las reglas. El conjunto S es el ´unico conjunto de respuesta para el programa PSluego es conjunto de respuesta del programa P. Veamos ahora el siguiente programa Qdel Ejemplo 5 de la secci´on 1.1.1: p(a) ←not p(b). p(d) ←not p(c). p(c) ←not p(e). p(b). Sea L={p(b) p(c)}. Para obtener el programa reducido de Qrespecto L, eliminamos la primera y la segunda regla, que contienen a los literales extendidos not p(b) ynot p(c), y despu´es de las reglas restantes eliminamos las premisas que contienen negaci´on por defecto, como not p(e). As´ı, QLtiene la forma: p(c). p(b). Como el conjunto L es conjunto de respuesta del programa reducido, L es conjunto de respuesta del programa Q. Cabe destacar que algunos programas de ASP no poseen conjuntos de respuesta. A estos programas se les denomina inconsistentes. 24 1.2.6. Intervalos Para construir intervalos, se usan expresiones de la forma s..r, donde suponemos que s <=r, que representan la sucesi´on de n´umeros naturales consecutivos entre s y r. Vemos un ejemplo de intervalos en un c´odigo: pares iguales(X,Y) :- X=0..2, Y=0..2, X=Y. Obtenemos los pares (X,X) con X entre 0 y 2. En este ejemplo, los intervalos se encuentran en el cuerpo de la regla por lo que se expanden de forma disyuntiva. Si el intervalo aparece en la cabeza de la regla, se expande de forma conjuntiva. Por ejemplo, el hecho: p(2..5). se expande al conjunto de hechos: p(2). p(3). p(4). p(5). 1.2.7. Agrupaci´on En los programas puede aparecer el mismo s´ımbolo de predicado o funci´on varias veces evaluado en distintos argumentos. Este es el caso del ejemplo que se expone en la secci´on 1.2.5: constante(a). constante(ab). constante(ac). entero(2). entero(3). entero(1). es mayor(X,Y) :- X>Y, constante(X), constante(Y). En este ejemplo, los predicados constante() oentero() aparecen m´as de una vez en el programa evaluados en argumentos diferentes. La agrupaci´on se usa para escribir de forma compacta los argumentos de predicados o funciones, evitando as´ı el uso reiterado de estos. Para ello, separamos los argumentos con ";". De esta forma, el c´odigo anterior puede reescribirse como: 31 constante(a;ab;ac). entero(2;3;1). es mayor(X,Y) :- X>Y, constante(X), constante(Y). es mayor enteros(X,Y) :- X>Y, entero(X), entero(Y). Como ocurr´ıa en el caso de los intervalos, dependiendo de si la agrupaci´on se encuentra en la cabeza o en el cuerpo de la regla, se expande de forma conjuntiva o disyuntiva, respectivamente. 1.2.8. Condicionales Para escribir condicionales en CLINGO, se usa el s´ımbolo “:”. Los condicionales son de la forma: L0:L1, . . . , Ln donde los Ljpara todo j=0 . . . n son literales. A L1, . . . , Lnse le denomina condici´on. Los literales que forman la condici´on se encuentran separados por comas, al igual que los literales que aparecen en el cuerpo de las reglas. Para no confundir los literales que aparecen despu´es de un condicional con los literales que constituyen la condici´on, se usa el s´ımbolo “;” al final de la condici´on. Esto es, supongamos que tenemos el programa: elemento(1..4). consecutivos(X,Z):- elemento(X), #false : elemento(Y), X<Y, Y<Z; elemento(Z), X<Z. Hemos usado ";"para evitar la confusi´on entre los literales que pertenecen a la condici´on del condicional y los que no. El condicional en esta regla evita que se verifique el predicado consecutivos(X,Z) cuando existe un n´umero intermedio entre X y Z. En las reglas de los programas aparecen variables que no se encuentran sujetas a ning´un condicional. Estas variables se denominan globales y en el proceso de instanciaci´on, se sustituyen por t´erminos antes que las variables que s´ı est´an sujetas a condicionales. Es por esta raz´on que no debemos nombrar a las variables que aparecen en las expresiones condicionales de forma que se puedan confundir con las globales. 32 1.2.9. Restricciones Las restricciones son expresiones de la forma: s1<1α{t1:L1;. . . ;tn:Ln}<2s2 donde: Los elementos tiyLison tuplas de t´erminos y literales respectivamente. Si alguna de las tuplas de literales est´a vac´ıa, s´olo aparece la tupla de t´erminos que la precede (suponemos que no est´a vac´ıa) y no aparecen los dos puntos. s1ys2son t´erminos y <1y<2son predicados de comparaci´on. αes una funci´on que se aplica a las tuplas de t´erminos que se encuentran dentro de las llaves una vez se hayan evaluado los condicionales. CLINGO trata a los elementos que aparecen entre las llaves como elementos de un conjunto. Por ello, si aparece un condicional repetido dentro de las llaves, se trata como un ´unico elemento. Los predicados <1y<2pueden ser reemplazados por “<=”, en cuyo caso obtenemos una cota superior o inferior para el conjunto. αpuede ser alguna de las funciones siguientes: #count, que nos da el n´umero de elementos que posee el conjunto. #sum: Suma de los pesos de las tuplas de t´erminos del conjunto (con peso, nos referimos al primer elemento de la tupla). Tambi´en αpuede ser #sum+, en cuyo caso se suman solo los pesos positivos. #min y #max, que nos dan el m´ınimo elemento y el m´aximo del conjunto, respectivamente. Veamos ahora un ejemplo. Supongamos que queremos ver las distintas formas de invertir en 4 empresas de manera que obtengamos m´ınimo 1000 euros. Esto lo podemos escribir en CLINGO a trav´es de la restricci´on: 33 1000 <=#sum {300 : empresa 1; 250: empresa 2; 600: empresa 3; 250: empresa 4}. Si se decide invertir en la empresa 1 y en la empresa 3, el conjunto se reduce a {300,600}. Como al aplicar la suma obtenemos 900, no se verifica el predicado de comparaci´on y por tanto no se verifica la restricci´on, luego no es una posible soluci´on. Para que CLINGO nos de todas las soluciones, al llamarlo debemos incluir un cero (supongamos que hemos llamado al archivo donde se encuentra el programa Ejemplo Restricciones): % clingo Ejemplo Restricciones.lp 0 Esto nos da: % Reading from Ejemplo Restricciones.lp % Solving... % Answer: 1 % empresa 1 empresa 4 empresa 3 % Answer: 2 % empresa 1 empresa 2 empresa 3 % Answer: 3 % empresa 1 empresa 2 empresa 4 empresa 3 34 Cap´ıtulo 2 Propiedades de los programas en ASP A lo largo de este cap´ıtulo, vamos a exponer algunas de las propiedades que poseen los programas de ASP. Adem´as, estudiaremos cu´ando un programa de ASP es consistente, es decir, posee alg´un conjunto de respuesta, y los requisitos bajos los cuales este conjunto de respuesta es ´unico. 2.1. Conjuntos de respuesta: Existencia, unicidad y propiedades Consideremos un programa P en ASP compuesto por reglas de la forma: A0or .. . or Ai←Ai+1, . . . , Am,not Am+1,...,not An donde los Aipara i= 0 . . . n son literales. Sean L1yL2dos conjuntos de respuesta distintos de P. Entonces, se verifica que L16⊆ L2yL26⊆ L1(los conjuntos no pueden compararse respecto a la inclusi´on). Observaci´on: Si un conjunto unitario, por ejemplo L={a}, es un conjunto de respuesta para P, no pueden existir otros conjuntos de respuesta de P que contengan al t´ermino a, pues si existiese un conjunto Mtal que a∈Mentonces L⊆My esto no puede ocurrir como acabamos de ver. Por el mismo razonamiento, si ∅es un conjunto de respuesta de P, entonces es el ´unico 35 conjunto de respuesta de P pues todo conjunto Lverifica que ∅ ⊆ L. Consideremos ahora programas de ASP cuyas reglas no contienen negaci´on cl´asica ni restricciones, es decir, programas que solo poseen reglas de la forma: A0or .. . or Ai←Ai+1, . . . , Aj,not Aj+1,..., not Am.(2.1) donde los Asson ´atomos para todo s≥0. Este tipo de programas se denominan normales. Ejemplo 1. El siguiente programa de una regla: p(a) ←not p(a). es un programa normal, ya que no posee restricciones ni negaci´on cl´asica y adem´as, es inconsistente. Con esto, vemos que no podemos asegurar la existencia de conjuntos de respuesta para programas normales. Sin embargo, para algunos tipos de programas normales podremos garantizar no s´olo la existencia, sino tambi´en la unicidad de conjuntos de respuesta. En primer lugar, estudiemos los denominados programas positivos. Definici´on 1 (Programas positivos) Se dice que un programa P es positivo si sus reglas no poseen negaci´on por defecto, es decir, si sus reglas tienen la forma: A0or .. . or Ai←Ai+1, . . . , Aj.(2.2) donde los Asson ´atomos y s≥0. Ejemplo 2. El siguiente programa es un programa positivo: estudiante(juan,colegio). estudiante(ana,univ). estudiante(marta, instituto). 36 estudiante(marco, univ). universitario(X) ←estudiante(X, univ). Para estudiar si este programa posee alg´un conjunto de respuesta, usamos la proposici´on: Proposici´on 1 Sea P un programa positivo. Entonces, P es consistente. M´as a´un, si las reglas de P no contienen disyunci´on, entonces P posee un ´unico conjunto de respuesta. Como el programa anterior no posee disyunci´on en sus reglas, usando la proposici´on que acabamos de ver podemos asegurar que el programa posee un ´unico conjunto de respuesta. Ejemplo 3. En el caso del programa (lo escribimos con la sintaxis de CLINGO para poder utilizarlo): estudiante(ana;juan). colegio(X);universidad(X) :- estudiante(X). sabemos que tiene al menos un conjunto de respuesta porque es positivo, pero como posee disyunci´on en sus reglas, no podemos asegurar que posea un ´unico conjunto de respuesta. De hecho, CLINGO nos devuelve cuatro conjuntos de respuesta para este programa: % Answer: 1 % estudiante(ana) estudiante(juan) colegio(ana) universidad(juan) % Answer: 2 % estudiante(ana) estudiante(juan) colegio(ana) colegio(juan) % Answer: 3 % estudiante(ana) estudiante(juan) universidad(ana) universidad(juan) % Answer: 4 % estudiante(ana) estudiante(juan) universidad(ana) colegio(juan) Ejemplo 4. Sea el programa: r(a,b). r(b,c). 37 r(Y,X) ←r(X,Y). r(X,Z) ←r(X,Y),r(Y,Z). Este programa es positivo y por lo tanto es consistente. Como no posee disyunci´on epist´emica en las reglas, podemos asegurar tambi´en que el programa tiene un ´unico conjunto de respuesta. Obs´ervese que el anterior programa positivo construye el cierre sim´etrico y transitivo de la relaci´on binaria r/2. Veamos ahora las nociones de programas estratificados ylocalmente estratificados, para los que tambi´en vamos a poder exponer algunos resultados de existencia y unidad de conjuntos de respuesta. Definici´on 2 (Grafo de dependencia) Consideremos un programa P cuyas reglas son de la forma (2.1). Sea Q el conjunto formado por los nombres de predicados del programa P. Se denomina grafo de dependencia de P al grafo cuyos nodos son los s´ımbolos de predicado presentes en Q y cuyas aristas son de la forma (p1, p2,+) o(p1, p2,−), donde p1yp2son s´ımbolos de predicado, que se denominan respectivamente arco positivo y negativo y que aparecen en el grafo seg´un: 1. Si existe una regla r en P verificando que su cabeza contiene un ´atomo formado por el s´ımbolo de predicado p1y su cuerpo contiene un ´atomo formado por p2, entonces el arco (p1, p2,+) aparece en el grafo. 2. Si existe una regla r en P verificando que su cabeza contiene un ´atomo formado por el s´ımbolo de predicado p1y su cuerpo contiene un literal de la forma not I, con I el ´atomo formado por el s´ımbolo de predicado p2, entonces el arco (p1, p2,−)aparece en el grafo. Definici´on 3 (Funci´on de nivel) Sea P un programa normal sin variables. Las funciones || || que asocian a cada elemento del conjunto de los ´atomos b´asicos de P un n´umero natural se denominan funciones de nivel para P. Observaciones: 1. Dos nodos p1yp2de un mismo grafo de dependencia pueden aparecer conectados por un arco positivo (p1, p2,+) y uno negativo (p1, p2,−) simult´aneamente. 38 2. Sea D=p1or . . . or pnuna disyunci´on epist´emica de at´omos de un programa P y sea || || la funci´on de nivel para el programa. Entonces, ||D|| =min{||p1||,...,||pn||}. Ejemplo 5. Sea el programa normal: p(a) or p(c) ←not p(b). p(c) ←p(d), not p(a). p(d). El conjunto de ´atomos b´asicos del programa es {p(a),p(b),p(c),p(d)}. Tenemos que la siguiente funci´on es un ejemplo de funci´on de nivel para el programa P: ||p(a)|| = 2, ||p(b)|| = 2, ||p(c)|| = 3, ||p(d)|| = 0 Definici´on 4 (Programas estratificados) Sea P un programa de la forma (2.1) y sea G su grafo de dependencia. Se dice que P es un programa estratificado si G no contiene ning´un ciclo negativo, esto es, ciclos que contienen al menos un arco negativo. Definici´on 5 (Programas localmente estratificados) Sea un programa P cuyas reglas son de la forma: A0or .. . or Ai←Ai+1, . . . , Aj,not Aj+1,..., not Am. y sea ground(P)el programa formado por reglas r de la forma: r: A0or .. . or Ai←Ai+1, . . . , Aj,not Aj+1,..., not Am. Entonces se dice que P est´a localmente estratificado si existe una funci´on de nivel || || para ground(P)de manera que para cada regla r del programa ground(P), se verifica: 1. ||Ak|| ≤ ||cabeza(r)|| para todo Akcon i<k≤j. 2. ||Ak|| <||cabeza(r)|| para todo Akcon j < k ≤m. 39 Sigamos con los ejemplos. Ejemplo 6. Consideramos el programa R: p(a) ←q(a). t(a) ←not q(b). q(a). Los nodos del grafo de dependencia de R son p,qyt. El arco (p, q, +) debe aparecer en el grafo porque en la primera regla se encuentra p(a) en la cabeza y q(a) en el cuerpo. Del mismo modo, el arco (t, q, −) debe aparecer en el grafo pues en la cabeza de la segunda regla aparece t(a) y en su cuerpo, not q(b). Como no contiene ciclos negativos, el programa R est´a estratificado. Ejemplo 7. Consideremos el programa S: q(b) ←q(a). q(a). Las funciones: ||q(s)||1=1 si s=b 0 si s=a||q(s)||2=0 si s=b 1 si s=a son funciones de nivel para el programa S. Sin embargo, || ||2no verifica las condiciones de la Definici´on 5, pues para la regla 1 no se verifica ||q(a)||2= 1 ≤ ||q(b)||2= 0. A´un as´ı, se tiene que S es un programa localmente estratificado pues || ||1si verifica las condiciones de la definici´on. Observaciones: 1. Los programas que no contienen negaci´on cl´asica ni negaci´on por defecto est´an localmente estratificados (una funci´on de nivel || || para estos programas que verifica las condiciones de la Definci´on 5 es la funci´on que asocia cada ´atomo pkque aparece en las reglas con el n´umero 0, es decir, ||pk|| = 0). En este caso se encuentra el programa S que acabamos de ver en los ejemplos. 2. Si un programa est´a estratificado, entonces tambi´en est´a localmente estratificado; sin embargo, el rec´ıproco no es cierto. El programa R 40 vecinos(X,Y) :- residencia B(X), residencia B(Y), not convivientes(X,Y). Sin embargo, al ejecutar el c´odigo (las tres reglas conjuntamente) obtenemos: % Answer: 1 %vecinos(julia,julia) vecinos(marta,julia) vecinos(manuel,julia) % vecinos(rocio,julia) vecinos(marta,marta) vecinos(manuel,marta) % vecinos(rocio,marta) vecinos(julia,manuel) vecinos(marta,manuel) %vecinos(manuel,manuel) vecinos(rocio,manuel) vecinos(julia,rocio) % vecinos(marta,rocio) vecinos(rocio,rocio) Nota: hemos usado la directriz #show para que s´olo salgan los hechos relacionados con el predicado vecinos. Los hechos recalcados no deber´ıan aparecer en el conjunto de respuesta ya que una persona no puede ser su propio vecino y adem´as tanto Roc´ıo y Manuel como Marta y Julia son convivientes, luego carece de sentido que sean a su vez vecinos. El problema reside en que: 1. No hemos modelizado el conocimiento ´ımplicito de que una persona no puede ser vecina de s´ı misma. 2. No hemos modelizado lo que sabemos por sentido com´un: la relaci´on “ser conviviente” es una relaci´on sim´etrica, es decir, si a es conviviente con b, b es conviviente con a, por tanto, ni a puede ser vecino de b, ni b de a. Car´acter sim´etrico de la relaci´on convivientes/2. A˜nadimos la siguiente regla al programa, que representa el car´acter sim´etrico de la relaci´on convivientes: convivientes(X,Y) :- convivientes(Y,X). Veamos un segundo intento (ya definitivo) de representaci´on de la relaci´on vecinos. Definimos vecinos/2 de la siguiente forma: X e Y son vecinos si ambos residen en el barrio B, no son la misma persona y no consta que sean convivientes. De esta manera, la regla queda como: 47 vecinos(X,Y) :- residencia B(X), residencia B(Y), not convivientes(X,Y), X != Y. y obtenemos la siguiente salida proporcion´andole a CLINGO el programa completo: % Answer: 1 % vecinos(manuel,julia) vecinos(rocio,julia) vecinos(manuel,marta) % vecinos(rocio,marta) vecinos(julia,manuel) vecinos(marta,manuel) % vecinos(julia,rocio) vecinos(marta,rocio) Obtenemos por tanto la siguiente informaci´on nueva: 1. Manuel y Roc´ıo son vecinos de Julia y Marta. 2. Julia y Marta son vecinas de Manuel y Roc´ıo. A˜nadiendo nueva informaci´on a la base de conocimientos. Sabemos ahora que: 1. Alberto reside en el barrio B. 2. No tenemos conocimiento de que Alberto viva con nadie m´as. Modelizamos la informaci´on usando de nuevo los predicados persona/1 yresidencia B/1: persona(alberto). residencia B(alberto). Si le preguntamos al programa: ¿son Marta y Alberto convivientes?, su respuesta es desconocido, pues no aparecen los literales convivientes(marta,alberto) ni -convivientes(marta,alberto) en el conjunto de respuesta. Sin embargo, nosotros no tenemos constancia de que Marta y Alberto sean convivientes, y por tanto en nuestro d´ıa a d´ıa trabajar´ıamos con la hip´otesis de que no lo son a menos que se nos indicase lo contrario. Modelizamos este conocimiento a trav´es de la hip´otesis del mundo cerrado: si no se tiene constancia de que dos personas distintas son convivientes, entonces no lo son. A˜nadimos as´ı la siguiente regla al programa: 48 -convivientes(X,Y) :- not convivientes(X,Y), persona(X), persona(Y), X!=Y. Obtenemos como salida: % vecinos(julia,alberto) vecinos(marta,alberto) % vecinos(manuel,alberto) vecinos(rocio,alberto) % vecinos(alberto,julia) vecinos(manuel,julia) % vecinos(rocio,julia) vecinos(alberto,marta) % vecinos(manuel,marta) vecinos(rocio,marta) % vecinos(alberto,manuel) vecinos(julia,manuel) % vecinos(marta,manuel) vecinos(alberto,rocio) % vecinos(julia,rocio) vecinos(marta,rocio) % -convivientes(julia,alberto) -convivientes(marta,alberto) % -convivientes(manuel,alberto) -convivientes(rocio,alberto) % -convivientes(alberto,julia) -convivientes(manuel,julia) % -convivientes(rocio,julia) -convivientes(alberto,marta) % -convivientes(manuel,marta) -convivientes(rocio,marta) % -convivientes(alberto,manuel) -convivientes(julia,manuel) % -convivientes(marta,manuel) -convivientes(alberto,rocio) % -convivientes(julia,rocio) -convivientes(marta,rocio) Hemos obtenido as´ı la siguiente informaci´on nueva sobre Alberto: 1. Alberto es vecino de Julia, Roc´ıo, Marta y Manuel. 2. Alberto no convive con Roc´ıo, Julia, Manuel, ni Marta. Esta regla adem´as no provoca contradicciones, es decir, supongamos ahora que se sabe que Alberto reside en el barrio B y que convive con Marta. De nuevo, modelizamos esta relaci´on a trav´es del predicado convivientes/2: convivientes(alberto,marta). Obtenemos as´ı la salida: % vecinos(julia,alberto) vecinos(manuel,alberto) vecinos(rocio,alberto) % vecinos(alberto,julia) vecinos(manuel,julia) vecinos(rocio,julia) % vecinos(manuel,marta) vecinos(rocio,marta) vecinos(alberto,manuel) % vecinos(julia,manuel) vecinos(marta,manuel) vecinos(alberto,rocio) % vecinos(julia,rocio) vecinos(marta,rocio) 49 % -convivientes(julia,alberto) -convivientes(manuel,alberto) % -convivientes(rocio,alberto) -convivientes(alberto,julia) % -convivientes(manuel,julia) -convivientes(rocio,julia) % -convivientes(manuel,marta) -convivientes(rocio,marta) % -convivientes(alberto,manuel) -convivientes(julia,manuel) % -convivientes(marta,manuel) -convivientes(alberto,rocio) % -convivientes(julia,rocio) -convivientes(marta,rocio) Aunque sin la regla anterior CLINGO nos devolv´ıa -convivientes(alberto,marta) en el conjunto de respuesta, el incluirla no provoca contradicci´on pues la adici´on de la nueva regla hace que el literal anterior no aparezca en el conjunto de respuesta al no verificarse el cuerpo de la regla del que procede. Algunas anotaciones de la regla (suponiendo que Alberto y Marta son convivientes): 1. Cuando CLINGO nos devuelve el conjunto de respuesta de este programa, en ´el nos aparece el literal -convivientes(alberto,julia). Esto es porque el sentido com´un no s´olo nos dice que la relaci´on “ser convivientes” es sim´etrica sino que tambi´en es transitiva: si X es conviviente con Y e Y es conviviente con Z, entonces X y Z son convivientes, y esta informaci´on no aparece reflejada en el programa. La modelizamos a trav´es de la regla: convivientes(X,Z) :- convivientes(X,Y), convivientes(Y,Z), X!=Z. Es necesario poner que X y Z no son la misma persona: en caso contrario, como se verificar´ıa convivientes(alberto,marta) y, por la simetr´ıa, convivientes(marta,alberto), se obtendr´ıa convivientes(alberto,alberto), que no queremos que aparezca en el conjunto de respuesta ya que una persona no convive consigo misma. 2. Si en vez de la regla anterior, hubi´esemos puesto la regla: -convivientes(X,Y) :- not convivientes(X,Y), X!=Y. CLINGO nos hubiese devuelto el siguiente mensaje de error (hemos llamado al archivo con las reglas del programa Ejemplo Vecinos.lp): % Ejemplo Vecinos.lp:6:1-51: error: unsafe variables in: % (-convivientes(X,Y)):-#inc base;X!=Y;not convivientes(X,Y). % Ejemplo Vecinos.lp:6:15-16: note: ‘X’ is unsafe 50 % Ejemplo Vecinos.lp:6:17-18: note: ‘Y’ is unsafe que nos indica que las variables X e Y no son seguras. Una variable Z se dice segura si aparece al menos una vez en el cuerpo de la regla sin estar influenciada por la negaci´on por defecto not. En nuestro caso, las variables X e Y aparecen afectadas por not y por el operador “!=”, que tampoco nos sirve para hacer la regla segura. Por eso, debemos incluir en la regla los literales persona(X) ypersona(Y). 3.3. Modelizaci´on de las relaciones familiares 3.3.1. Definici´on recursiva de antepasado Tenemos el siguiente marco familiar: 1. Antonio y Luisa son los padres de Rosa. 2. Rosa y Marcos tienen un hijo llamado Lucas. 3. Roc´ıo y Lucas son los padres de Julieta. 4. Nerea y Pedro son los padres de Roc´ıo. 5. Suponemos que X no es el padre o la madre de Y si no tenemos constancia de estos hechos. Modelicemos esta informaci´on conocida. Para clasificar los elementos, usamos el predicado persona/1: persona(nerea;pedro;rocio;marcos;antonio;luisa;rosa;lucas; julieta). Para representar las relaciones entre ellos, usamos los predicados padre/2 ymadre/2: padre(pedro,rocio;antonio,rosa;marcos,lucas;lucas,julieta). madre(nerea,rocio;rocio,julieta;luisa,rosa;rosa,lucas). 51 Al igual que en la Secci´on 3.2, usamos la hip´otesis del mundo cerrado para modelizar el siguiente conocimiento: si no tenemos constancia de que X sea padre (o madre) de Y, entonces X no es padre (respectivamente madre) de Y. Incluimos por tanto las siguientes dos reglas al programa: -padre(X,Y) :- not padre(X,Y), persona(X), persona(Y). -madre(X,Y) :- not madre(X,Y), persona(X), persona(Y). Nota: tenemos que incluir los literales persona(X) y persona(Y) para que la regla sea segura pues tanto X como Y se ven afectadas por la negaci´on por defecto. Concepto: Progenitor. Usando los predicados padre/2 ymadre/2, definimos tambi´en el predicado progenitor/2: X es progenitor de Y si es padre o madre de Y. Modelizamos el conocimiento con las reglas: progenitor(X,Y) :- padre(X,Y). progenitor(X,Y) :- madre(X,Y). Obtenemos con estas reglas la siguiente informaci´on: %progenitor(pedro,rocio) progenitor(antonio,rosa) progenitor(marcos,lucas) % progenitor(lucas,julieta) progenitor(nerea,rocio) progenitor(rocio,julieta) % progenitor(luisa,rosa) progenitor(rosa,lucas) Concepto: Antepasado. Definimos ahora la relaci´on antepasado de la siguiente forma recursiva: Si X es progenitor de Y, entonces X es antepasado de Y. Si X es antepasado de Y e Y es progenitor de Z, entonces X es antepasado de Z. Implementamos esta informaci´on a trav´es de las siguientes reglas: antepasado(X,Y) :- progenitor(X,Y). antepasado(X,Z) :- progenitor(Y,Z),antepasado(X,Y). 52 Completamos la informaci´on utilizando la hip´otesis del mundo cerrado: si no tenemos constancia de que X sea antepasado de Y, entonces X no es antepasado de Y. -antepasado(X,Y) :- not antepasado(X,Y),persona(X), persona(Y). Veamos el modelo que nos da CLINGO: % antepasado(pedro,rocio) antepasado(antonio,rosa) antepasado(marcos,lucas) % antepasado(lucas,julieta) antepasado(nerea,rocio) antepasado(rocio,julieta) % antepasado(luisa,rosa) antepasado(rosa,lucas) antepasado(pedro,julieta) % antepasado(antonio,lucas) antepasado(marcos,julieta) % antepasado(nerea,julieta) antepasado(luisa,lucas) antepasado(rosa,julieta) % antepasado(antonio,julieta) antepasado(luisa,julieta) Obtenemos informaci´on nueva, como: 1. Pedro, Marco, Nerea, Rosa, Antonio y Luisa son antepasados de Julieta. 2. Antonio y Luisa son antepasados de Lucas. 3.3.2. Definici´on de hijo ´unico Poseemos los datos de dos familias: La primera est´a formada por Nerea y Pedro, que tienen una hija, Irene. La segunda est´a formada por Josefa y Rodrigo, que tienen dos hijos, Marcos y Mario. Veamos c´omo podemos implementar la informaci´on. Para clasificar los elementos volvemos a usar el predicado persona/1 junto con el predicado genero/2: persona(nerea;irene;pedro;josefa;rodrigo;marcos;mario). genero(irene,mujer;nerea,mujer;josefa,mujer). genero(pedro,hombre;marcos,hombre;mario,hombre;rodrigo,hombre). Para modelizar las relaciones entre ellos, usamos los predicados padre/2 ymadre/2: 53 padre(pedro,irene;rodrigo,mario;rodrigo,marcos). madre(nerea,irene;josefa,marcos;josefa,mario). Si le preguntamos ahora a CLINGO si Nerea es el padre de Marcos, su respuesta es desconocido, pues ni padre(nerea,marcos) ni -padre(nerea,marcos) pertenecen al conjunto de respuesta del programa. Pero sabemos que Nerea no puede ser el padre de Marcos, porque Nerea es una mujer. Para representar este conocimiento impl´ıcito, usamos las dos reglas siguientes: -padre(X,Y) :- genero(X,mujer),persona(Y), X!=Y. -madre(X,Y) :- genero(X,hombre),persona(Y), X!=Y. Concepto: progenitor. De nuevo, implementamos en la base de conocimiento la relaci´on progenitor: X es progenitor de Y si X es padre o madre de Y. progenitor(X,Y) :- padre(X,Y). progenitor(X,Y) :- madre(X,Y). Concepto: hermanos. Supongamos que queremos saber qui´enes de los individuos son hermanos. Tenemos que modelizar la relaci´on hermanos: X e Y son hermanos si no son la misma persona y tienen los mismos padres. La definici´on queda representada usando el predicado hermanos/2: hermanos(X,Y) :- padre(F,X), padre(F,Y), madre(M,X),madre(M,Y), X != Y. La relaci´on hermanos es sim´etrica y transitiva: hermanos(X,Y) :- hermanos(Y,X). hermanos(X,Z) :- hermanos(X,Y),hermanos(Y,Z), X != Z. Si le proporcionamos este programa a CLINGO, nos devuelve (nos fijamos s´olo en el predicado hermanos): %hermanos(mario,marcos) hermanos(marcos,mario) 54 As´ı, CLINGO nos proporciona la informaci´on que nos interesaba conocer: Marcos y Mario son hermanos. Completitud de la informaci´on de la base de conocimiento. Utilizamos la hip´otesis del mundo cerrado para representar lo siguiente: si no tenemos constancia de que X e Y sean hermanos, entonces X e Y no son hermanos. -hermanos(X,Y) :- not hermanos(X,Y), persona(X), persona(Y). Conceptos: hijo e hijo ´unico. Nos interesa saber qui´enes de los individuos son hijos ´unicos. Para ello, definamos primero la relaci´on hijo. Usando el predicado progenitor/2, modelizamos la relaci´on hijo: X es hijo de Y si Y es un progenitor de X. hijo(X,Y) :- progenitor(Y,X). Por ´ultimo, representemos la relaci´on “ser hijo ´unico”: X es hijo ´unico si es hijo de alguien y no tiene hermanos (su progenitor no tiene m´as hijos): hijoUnico(X) :- hijo(X,Y), #false: Z !=X, hijo(Z,Y). De esta manera, proporcion´andole a CLINGO todas las reglas anteriores, obtenemos la salida: %hijoUnico(irene) Y obtenemos as´ı la informaci´on que busc´abamos: Irene es hija ´unica. 3.4. Modelizaci´on de un conjunto de medios de transporte En este ´ultimo ejemplo, vamos a ver c´omo modelizar una base jer´arquica de conocimiento: los medios de transporte. 55 Disponemos de la siguiente informaci´on: 1. Los veh´ıculos se dividen en mar´ıtimos y no mar´ıtimos. 2. Los submarinos, los veleros y las lanchas son veh´ıculos mar´ıtimos. 3. Los autobuses y las caravanas son veh´ıculos no mar´ıtimos. 4. Desvaste es una caravana concreta. 5. Ultramar es un veh´ıculo mar´ timo concreto. Estudiemos c´omo modelizar este conocimiento jer´arquico del que disponemos. Usaremos el predicado clase/1 para enumerar las clases que constituyen la jerarqu´ıa: clase(vehiculo;mar;no mar;submarino;velero;lancha; autobus;caravana). Para describir la jerarqu´ıa entre ellas, usamos el predicado subclase de/2, que representa la contenci´on inmediata o directa entre clases: subclase de(mar,vehiculo). subclase de(no mar,vehiculo). subclase de(submarino,mar). subclase de(velero,mar). subclase de(lancha,mar). subclase de(autobus,no mar). subclase de(caravana,no mar). Concepto: subclase. Vamos a modelizar la clausura transitiva de la relaci´on subclase de/2: 1. Si C1 es subclase directa de C2, entonces C1 es subclase de C2. 2. Si C1 es subclase directa de C2 y C2 es subclase de C3, entonces C1 es subclase de C3. 56 Representaci´on del defecto 1. Sigamos con el ejemplo. Para representar el defecto “normalmente, los vecinos son amigos”, usamos la regla: amigos(X,Y) :- vecinos(X,Y), not ab(d amigos(X,Y)), not -amigos(X,Y). La relaci´on “ser amigos” es sim´etrica: amigos(X,Y) :- amigos(Y,X). Adem´as, si X no es amigo de Y, Y tampoco es amigo de X: -amigos(X,Y) :- -amigos(Y,X). La informaci´on que disponemos acerca de que Marta y Manuel no son amigos es una excepci´on fuerte, y se representa a trav´es de la regla: -amigos(marta,manuel). De esta manera, el programa ya no es inconsistente y se obtiene la siguiente salida: % -amigos(marta,manuel) -amigos(manuel,marta) amigos(rocio,marta) % amigos(marta,rocio) Obteniendo as´ı informaci´on acerca de qui´enes de los sujetos son amigos: Marta y Roc´ıo son amigas. Modelizaci´on de nueva informaci´on. Se dispone ahora de la siguiente informaci´on: 1. Se sabe si algunas de las personas del barrio se conocen entre ellas. 2. Se sabe que dos personas que no se conocen no pueden ser amigas. Para modelizar esta informaci´on, se usa el predicado conocidos/2, que representa que X conoce a Y e Y conoce a X. 63 La relaci´on “ser conocidos” es sim´etrica: si se verifica que X e Y son conocidos, tanto X conoce a Y como Y conoce a X, luego tambi´en se verifica que Y y X son conocidos. Representamos el car´acter sim´etrico de la informaci´on a trav´es de: conocidos(X,Y) :- conocidos(Y,X). Por motivos similares, si no se verifica que X e Y sean conocidos, tampoco puede verificarse que Y y X sean conocidos, lo que representamos con la regla: -conocidos(X,Y) :- -conocidos(Y,X). Representemos ahora la excepci´on fuerte: si X e Y no se conocen, entonces no pueden ser amigos. -amigos(X,Y) :- -conocidos(X,Y). De este modo, si no se tiene constancia de que X e Y se conozcan, entonces no debe aplicarse el defecto 1 ya que X e Y pueden ser una excepci´on. Representamos esta excepci´on d´ebil a trav´es de la regla: ab(d amigos(X,Y)) :- not conocidos(X,Y), persona(X), persona(Y). Veamos entonces qu´e nuevo conocimiento obtenemos seg´un la informaci´on sobre el predicado conocidos/2 de la que se disponga: Ejemplo 1. Se posee la siguiente informaci´on acerca de conocidos/2: Marta y Manuel se conocen. Marta y Manuel no son amigos. Representamos esta informaci´on con las reglas: conocidos(manuel, marta). -amigos(marta, manuel). Obtenemos la salida (fij´andonos en el predicado amigos/2 y-amigos/2): % -amigos(marta,manuel) -amigos(manuel,marta) Como no tenemos constancia de que Marta y Roc´ıo se conozcan, no obtenemos informaci´on sobre si son o no amigas. 64 Ejemplo 2. Se posee la siguiente informaci´on: Marta y Manuel se conocen. Marta y Manuel no son amigos. Marta y Roc´ıo se conocen. A˜nadimos a las dos reglas anteriores la regla: conocidos(marta,rocio). Obtenemos as´ı: % -amigos(marta,manuel) -amigos(manuel,marta) amigos(rocio,marta) % amigos(marta,rocio) Luego disponemos de nueva informaci´on: Marta y Roc´ıo son amigas. Ejemplo 3. Se posee la siguiente informaci´on: Marta y Manuel se conocen. Marta y Manuel no son amigos. Marta y Roc´ıo no se conocen. CLINGO nos proporciona el conjunto de respuesta: % -amigos(marta,manuel) -amigos(marta,rocio) -amigos(rocio,marta) % -amigos(manuel,marta) Y conseguimos de este modo nueva informaci´on: Marta y Roc´ıo no son amigas. Modelizaci´on de una excepci´on fuerte usando el axioma de cancelaci´on. Aunque antes se haya modelizado una excepci´on fuerte sin el axioma de cancelaci´on (pues no era necesario), en otras ocasiones debemos 65 implementarlo tambi´en en el programa. Veamos un ejemplo. Supongamos que poseemos la siguiente informaci´on: 1. Marta, Manuel y Roc´ıo viven en el barrio B. 2. Manuel y Roc´ıo viven juntos. 3. Defecto 1: normalmente, los vecinos el barrio B son amigos. 4. Las personas de la casa c1 y las personas de la casa c2 no son amigas. 5. Manuel vive en la casa c1. 6. Una persona no puede vivir en m´as de una casa. 7. Se conoce informaci´on sobre qui´enes de los sujetos, aparte de Manuel, viven en c1 o c2. Representamos las dos casas usando el predicado casa/1: casa(c1). casa(c2). Representamos que Manuel vive en la casa c1 con el predicado vivirEn/2: vivirEn(manuel,c1). Una propiedad acerca de la relaci´on “vivir en” es que si una persona X vive en una casa C y es conviviente con otra persona Y, entonces Y vive en C: vivirEn(Y,C) :- vivirEn(X,C), convivientes(X,Y). Usando la siguiente regla, modelizamos que una persona no puede vivir en m´as de una casa: -vivirEn(X,C) :- vivirEn(X,C1), C!=C1, casa(C). Representemos ahora la excepci´on fuerte: si una persona vive en c1 y otra persona vive en c2, entonces no son amigas. Se usa para ello la regla siguiente: -amigos(X,Y) :- vivirEn(X,c1),vivirEn(Y,c2). Necesitamos acompa˜nar la regla con el axioma de cancelaci´on para representar que si no tenemos constancia de que ni X ni Y viven en c1 o c2, 66 entonces puede que X e Y no sean amigos. Por tanto, usamos las siguientes dos reglas: ab(d amigos(X,Y)) :- not -vivirEn(X,c1), not -vivirEn(Y,c2), persona(X), persona(Y). ab(d amigos(X,Y)) :- not -vivirEn(Y,c1), not -vivirEn(X,c2), persona(X), persona(Y). Veamos como antes qu´e conocimiento nuevo podemos obtener seg´un la informaci´on que poseamos del predicado vivirEn/2. Ejemplo 1. Se dispone de la siguiente informaci´on: Marta, Manuel y Roc´ıo se conocen entre ellos. Marta no vive en c2. Representamos que Marta, Manuel y Roc´ıo se conocen entre ellos: conocidos(marta,manuel;marta,rocio;manuel,rocio). Representamos ahora que Marta no vive en c2: -vivirEn(marta,c2). En este caso, obtenemos la salida: % amigos(manuel,marta) amigos(rocio,marta) amigos(marta,manuel) % amigos(marta,rocio) Luego hemos obtenido la siguiente informaci´on: 1. Marta y Roc´ıo son amigas. 2. Marta y Manuel son amigos. Ejemplo 2. Se dispone de la siguiente informaci´on: 67 Marta, Manuel y Roc´ıo se conocen entre ellos. Marta vive en c2. Representamos el conocimiento a trav´es de las reglas: conocidos(marta,manuel;marta,rocio;manuel,rocio). vivirEn(marta,c2). Obtenemos la salida: % -amigos(manuel,marta) -amigos(rocio,marta) -amigos(marta,manuel) % -amigos(marta,rocio) Luego obtenemos la siguiente informaci´on: 1. Marta y Manuel no son amigos. 2. Roc´ıo y Marta no son amigas. Ejemplo 3. No disponemos informaci´on acerca de d´onde vive Marta. En este caso, no obtenemos en el conjunto de respuesta nada acerca de si Marta es amiga o no de Manuel y Roc´ıo. Esto es porque se aplica el axioma de cancelaci´on anterior, que a˜nadimos a la excepci´on fuerte. Si no lo hubi´esemos considerado, el defecto se aplicar´ıa y el agente considerar´ıa que son amigos entre ellos. Caso especial: defectos con informaci´on completa. Sea el defecto d: “normalmente, los elementos de c verifican la propiedad p” y supongamos que se tiene un conjunto ede excepciones. Si la informaci´on que se tiene sobre ees completa, entonces el axioma de cancelaci´on en las excepciones d´ebiles se reduce a: ab(d(X)) :- e(X). y en las excepciones fuertes, dicho axioma puede ser omitido. 68 En el ejemplo descrito anteriormente, si hubi´esemos tenido una lista con las personas que viven en la casa c1y con las personas que viven en la casa c2, la excepci´on fuerte se hubiese representado ´unicamente por la regla: -amigos(X,Y) :- vivirEn(X,c1),vivirEn(Y,c2). pues una persona de la que no se conoce d´onde vive deja de ser una posible excepci´on ya que, al ser la informaci´on sobre las personas que viven en c1o c2completa, si viviese en una de estas casas, el agente lo sabr´ıa. 4.2. Modelizaci´on de la informaci´on con valores nulos Los defectos pueden usarse tambi´en para modelizar informaci´on en la que aparecen valores nulos, esto es, constantes que indican que el valor de una variable o funci´on es desconocido. Supongamos que tenemos una empresa con varios departamentos, y disponemos de la siguiente informaci´on: 1. Nuria es la encargada del departamento D1. 2. Luis es el encargado del departamento D2. 3. En los departamentos D3yD4se va a contratar a una persona como encargado entre las que lo soliciten. 4. Defecto 1: normalmente, si una persona no est´a en la lista de encargados junto a un departamento, no se encarga de ese departamento. 5. Los solicitantes de los puestos vacantes son Nuria y Marcos. La lista de los encargados con sus respectivos departamentos es la siguiente: Persona Departamento Nuria D1 Luis D2 Vacante D3 Vacante D4 69 En este ejemplo, “Vacante” es un valor nulo que nos indica que las personas encargadas de los departamentos D3yD4est´an por determinar. Veamos c´omo modelizar esta informaci´on. En primer lugar, representamos los elementos que intervienen en el ejemplo con los predicados persona/1 ydepartamento/1: persona(nuria;luis;marcos). departamento(d1;d2;d3;d4). Representamos la informaci´on de la lista de encargados con el predicado encargado/2: encargado(nuria,d1;luis,d2;vacante,d3;vacante,d4). y modelizamos tambi´en con el predicado solicitante/1 los sujetos que han solicitado los puestos vacantes: solicitante(nuria;marcos). Representamos el defecto 1 a trav´es de la regla: -encargado(X,D) :- persona(X), departamento(D), not ab(d encargado(X,D)), not encargado(X,D). que se lee como “si no tenemos constancia de que X pueda ser una excepci´on del defecto y tampoco tenemos constancia de que X sea la persona encargada del departamento D, es decir, no tenemos constancia de que X sea una excepci´on, entonces X no es la persona encargada del departamento D”. Sin embargo, los encargados de los departamentos D3yD4est´an por determinar: se contratar´a a alg´un solicitante aunque sus nombres no aparezcan en la lista junto a estos departamentos. Esta informaci´on por tanto es una excepci´on d´ebil del defecto 1 y se modeliza con la regla: ab(d encargado(X,D)) :- solicitante(X), encargado(vacante,D). Esta regla representa el siguiente conocimiento: “si X es un solicitante, entonces puede ser un encargado de los departamentos D con puestos vacantes aunque su nombre no aparezca en la lista junto a ellos”. De esta manera, obtenemos la siguiente salida: 70 % encargado(nuria,d1) encargado(luis,d2) encargado(vacante,d3) % encargado(vacante,d4) -encargado(nuria,d2) -encargado(luis,d1) % -encargado(luis,d3) -encargado(luis,d4) -encargado(marcos,d1) % -encargado(marcos,d2) As´ı, se dispone de la siguiente informaci´on nueva: Nuria no se encarga del departamento D2. Luis no se encarga de los departamentos D1,D3yD4. Marcos no se encarga de los departamentos D1yD2. No obtenemos informaci´on sobre si Nuria y Marcos son o no encargados de los departamentos D3yD4ya que son los solicitantes, figuran como posibles excepciones. Tambi´en podr´ıamos haber representado la informaci´on del siguiente modo: Persona Departamento Nuria D1 Luis D2 Vacante D3 Vacante D4 {Nuria, Marcos}D3 {Nuria, Marcos}D4 donde ahora el valor nulo “Vacante” nos indica que los encargados de los departamentos D3yD4est´an por contratar y el valor nulo “{Nuria, Marcos}” nos indica qui´enes son los posibles encargados de los susodichos departamentos. Para representar esta informaci´on, sustituimos las dos ´ultimas reglas del programa: solicitante(nuria;marcos). ab(d encargado(X,D)) :- solicitante(X), encargado(vacante,D). por las reglas: encargado(nuria,d3) | encargado(marcos,d3). encargado(nuria,d4) | encargado(marcos,d4). 71 que representan, a trav´es de la disyunci´on epist´emica, que Nuria y Marcos podr´ıan ser los encargados de los departamentos D3yD4. Se obtienen cuatro posibles soluciones: %Answer: 1 % encargado(nuria,d1) encargado(luis,d2) encargado(vacante,d3) % encargado(vacante,d4) -encargado(nuria,d2) -encargado(luis,d1) % -encargado(luis,d3) -encargado(luis,d4) -encargado(marcos,d1) % -encargado(marcos,d2) encargado(nuria,d3) encargado(marcos,d4) %Answer: 2 % encargado(nuria,d1) encargado(luis,d2) encargado(vacante,d3) % encargado(vacante,d4) -encargado(nuria,d2) -encargado(luis,d1) % -encargado(luis,d3) -encargado(luis,d4) -encargado(marcos,d1) % -encargado(marcos,d2) encargado(nuria,d3) encargado(nuria,d4) %Answer: 3 % encargado(nuria,d1) encargado(luis,d2) encargado(vacante,d3) % encargado(vacante,d4) -encargado(nuria,d2) -encargado(luis,d1) % -encargado(luis,d3) -encargado(luis,d4) -encargado(marcos,d1) % -encargado(marcos,d2) encargado(marcos,d3) encargado(marcos,d4) %Answer: 4 % encargado(nuria,d1) encargado(luis,d2) encargado(vacante,d3) % encargado(vacante,d4) -encargado(nuria,d2) -encargado(luis,d1) % -encargado(luis,d3) -encargado(luis,d4) -encargado(marcos,d1) % -encargado(marcos,d2) encargado(marcos,d3) encargado(nuria,d4) Todos los conjuntos de respuesta nos proporcionan la siguiente informaci´on: 1. Ni Luis ni Marcos son los encargados del departamento D1. 2. Ni Nuria ni Marcos son los encargados del departamento D2. 3. Luis no se encarga de los departamentos D3yD4. En la primera soluci´on, obtenemos: Nuria es la encargada del departamento D3. Marcos es el encargado del departamento D4. 72 -pertenece(X,C2) :- pertenece(X,C1), hermanas(C1,C2). Modelizaci´on de defectos y excepciones. Representamos los colores a trav´es del predicado color/1: color(naranja;blanco;negro;azul). Antes de empezar con la representaci´on de los defectos, modelizamos la siguiente informaci´on conocida: un elemento s´olo puede ser de un color. -deColor(X,C) :- deColor(X,C1), C1 !=C, color(C), color(C1). Representamos el defecto 1, “en general, las caravanas son blancas”, como sigue: deColor(X,blanco) :- pertenece(X,caravana), not ab(d1(X)), not -deColor(X,blanco). Representamos el defecto 2, “los veh´ıculos no mar´ıtimos son habitualmente de color negro”, a trav´es de la regla: deColor(X,negro) :- pertenece(X,no mar), not ab(d2(X)), not -deColor(X,negro). Para modelizar el defecto 3: los autobuses normalmente son naranjas, se utiliza: deColor(X, naranja) :- pertenece(X,autobus), not ab(d3(X)), not -deColor(X,naranja). Representamos el defecto 4, “normalmente, los autobuses tur´ısticos son de color azul”, con la regla: deColor(X,azul) :- pertenece(X,turistico), not ab(d4(X)), not -deColor(X,azul). Y por ´ultimo, se modeliza el defecto 5, “en general, los veh´ıculos mar´ıtimos son blancos”, con la regla: 79 deColor(X,blanco) :- pertenece(X,mar), not ab(d5(X)), not -deColor(X,blanco). La informaci´on acerca de si X es una caravana no es completa: si no tenemos constancia de que X, que es un veh´ıculo no mar´ıtimo, no es una caravana, puede ser una excepci´on del defecto 2 (puede que no sea de color negro). Esto se representa a trav´es de una excepci´on d´ebil: ab(d2(X)) :- not -pertenece(X,caravana), elemento(X). De la misma manera, la informaci´on sobre si X es un autob´us o un autob´us tur´ıstico no es completa. Por este motivo, si no tenemos constancia de que X no sea alguno de estos veh´ıculos, puede que X sea una excepci´on de los defectos 2 y 3 respectivamente. Representamos de nuevo la informaci´on como excepciones d´ebiles: ab(d2(X)) :- not -pertenece(X,autobus), elemento(X). ab(d3(X)) :- not -pertenece(X,turistico), elemento(X). Veamos entonces qu´e informaci´on nos proporciona CLINGO sobre los colores de la caravana Desvaste y el veh´ıculo mar´ıtimo Ultramar. Obtenemos la salida: % deColor(desvaste,blanco) deColor(ultramar,blanco) De este modo, hemos conseguido los siguientes datos acerca de Ultramar y Desvaste: Desvaste es de color blanco. Ultramar es de color blanco. Este conocimiento es consiste pues Desvaste era una caravana, luego se ha aplicado el defecto 1, y Ultramar era un veh´ıculo mar´ıtimo, lo que quiere decir que se ha aplicado el defecto 5. Adici´on de un nuevo elemento a la informaci´on conocida. Veamos qu´e informaci´on obtenemos acerca del color de un nuevo elemento, Levi, que es un veh´ıculo no mar´ıtimo, seg´un la informaci´on que se disponga sobre este. 80 Ejemplo 1. S´olo conocemos que Levi es un veh´ıculo no mar´ıtimo. Representamos esta informaci´on con las reglas: elemento(levi). es un(levi,no mar). En la salida, no obtenemos informaci´on sobre el color de Levi, pues puede ser una excepci´on del defecto 2 (no hemos especificado que no es una caravana, autob´us o autob´us tur´ıstico). Ejemplo 2. Si especificamos ahora que Levi es un autob´us: es un(levi,autobus). Seguimos sin obtener informaci´on de su color, ya que no hemos especificado que no sea un autob´us tur´ıstico. Ejemplo 3. Si ahora especificamos que es un autob´us tur´ıstico: es un(levi,turistico). Obtenemos: % deColor(levi,azul) Luego se obtiene que Levi es azul. Esto es gracias al defecto 4, que tiene prioridad respecto a los defectos 2 y 3. Es decir, aunque anteriormente vimos que la prioridad entre defectos se pod´ıa representar mediante excepciones fuertes, en este caso, se ha representado a trav´es de excepciones d´ebiles (a trav´es de estas, hemos representado que el defecto 4 tiene preferencia sobre el defecto 3 y que el defecto 3 tiene preferencia sobre el defecto 2). De esta manera, se observa que la informaci´on m´as espec´ıfica tiene preferencia sobre la informaci´on menos espec´ıfica. En general, si tenemos C1 subclase de C2, y los defectos: “normalmente, los elementos de C2 tienen la propiedad P” y “normalmente, los elementos de C1 no tienen la propiedad P”, entonces el segundo defecto predomina sobre el primero. Esto es lo que 81 se conoce como principio de especificidad. 82 Cap´ıtulo 5 El paradigma de programaci´on ASP En las secciones anteriores, nos hemos centrado en la modelizaci´on de bases de conocimiento en ASP con la finalidad de obtener elementos que verificasen ciertos predicados o para ver la veracidad o falsedad de ciertas afirmaciones. En esta secci´on, se pretende mostrar c´omo se pueden usar las bases de conocimiento en ASP para encontrar soluciones a distintos problemas reduci´endolos a encontrar conjuntos de respuestas de programas de ASP. El procedimiento de resoluci´on de problemas a trav´es de reducirlos a encontrar conjuntos de respuesta de programas en ASP es lo que se denomina el paradigma de programaci´on ASP. En nuestro caso, vamos a construir bases de conocimiento cuyos conjuntos de respuesta den soluci´on a los dos problemas siguientes: hallar los ciclos hamiltonianos de un grafo y encontrar la soluci´on de sudokus. 5.1. Ciclos hamiltonianos de un grafo Nuestro objetivo es construir un programa de ASP cuyos conjuntos de respuestas sean los ciclos hamiltonianos de un grafo dirigido G. Un ciclo hamiltoniano de un grafo G es un camino que pasa por todos los v´ertices o nodos del grafo una sola vez y empieza y termina en el mismo v´ertice o nodo. 83 Para representar el grafo, se usan los predicados: inicial/1, donde inicial(v0) nos indica que el nodo v0es el nodo del que se parte (y por tanto, debe ser tambi´en el ´ultimo nodo en visitarse). nodo/1, para representar los nodos del grafo. arco/2, donde arco(v0,v1) representa el arco del grafo G que parte del nodo v0y accede al nodo v1. Los ciclos hamiltonianos (que ser´an los conjuntos de respuesta del programa) se representan por conjuntos en(v0,v1), en(v1,v2), . . . , en(vk,v0), donde el predicado en(vi,vj) representa que el arco que parte de viy accede avjpertenece al ciclo hamiltoniano < v0, v1, v2, ...vk, v0>. Para que un conjunto en(v0,v1), en(v1,v2), . . . , en(vk,v0) forme un ciclo hamiltoniano de G, se debe cumplir: 1. Se accede y se sale de un v´ertice como m´aximo una vez. 2. Debe contener a todos los nodos del grafo. Se representa que se accede como m´aximo una vez a cada v´ertice V del grafo de la siguiente manera: si el arco que parte desde uno de los nodos V1 del grafo y accede a V ya est´a en el ciclo hamiltoniano, es decir, se verifica en(V1,V), entonces no puede existir otro v´ertice V2 distinto de V1 tal que el arco que parte de V2 y accede a V est´e en el ciclo hamiltoniano. La regla que modeliza esta informaci´on es: -en(V2,V) :- en(V1,V), V1 != V2, nodo(V1), nodo(V2), nodo(V). De manera an´aloga, representamos que s´olo se sale de un v´ertice V una ´unica vez: si el arco que parte de V y llega a V1 est´a en el ciclo hamiltoniano, entonces cualquier otro arco que parta de V y llegue a un v´ertice V2 distinto a V1 no puede estar en el ciclo hamiltoniano. Esta informaci´on queda recogida por la regla: -en(V,V2) :- en(V,V1), V1 != V2, nodo(V1), nodo(V2), nodo(V). Representemos la otra condici´on que debe verificar un ciclo hamiltoniano: debe contener a todos los nodos del grafo. 84 Para representar este conocimiento, primero debemos definir la relaci´on alcanzable: el nodo V es alcanzable en el ciclo que se est´e considerando si existe un arco que parte del v´ertice inicial y accede a V o si en el ciclo existe un arco que parte de un v´ertice V1 alcanzable y accede a V. Este conocimiento se representa a trav´es del predicado alcanzable/1, que es recursivo: alcanzable(V) :- en(V1,V), inicial(V1), nodo(V). alcanzable(V) :- en(V1,V), alcanzable(V1), nodo(V). Para completar la informaci´on sobre los v´ertices que son y no son alcanzables, usamos la hip´otesis del mundo cerrado: si no tenemos constancia de que un v´ertice sea alcanzable, entonces supondremos que no es alcanzable. -alcanzable(V) :- not alcanzable(V), nodo(V). De esta manera, se representa que el ciclo debe pasar por todos los nodos con la restricci´on siguiente, que impide la presencia de nodos no alcanzables en el conjunto de respuesta: :- -alcanzable(V), nodo(V). Con estas condiciones, CLINGO es capaz de determinar cu´ando un ciclo es hamiltoniano y cu´ando no. Ahora, necesitamos representar los posibles candidatos a ciclos hamiltonianos, es decir, los posibles caminos que podemos formar en G. Para ello, siempre que exista un arco en G que parta de V1 y acceda a V2, se considerar´a la opci´on de incluirlo o no en el ciclo. Modelizamos esta informaci´on usando la disyunci´on: en(V1,V2) | -en(V1,V2) :- arco(V1,V2). Veamos algunos ejemplos de grafos y sus ciclos hamiltonianos. Ejemplo 1. Consideremos el grafo dirigido G de la figura 5.1. Queremos encontrar los ciclos hamiltonianos que parten del nodo a. Para describir a este grafo, usamos los predicados nodo/1 yarco/2: nodo(a;b;c;d;e). arco(a,b;b,a;b,c;c,d;d,e;e,b;e,a;a,c). 85 y con el predicado inicial/1, indicamos el nodo del que queremos que parta: inicial(a). CLINGO nos devuelve para este grafo dos conjuntos de respuesta, que son los ´unicos ciclos hamiltonianos que posee el grafo: %Answer: 1 % en(a,b) en(b,c) en(c,d) en(d,e) en(e,a) %Answer: 2 % en(b,a) en(c,d) en(d,e) en(e,b) en(a,c) Figura 5.1: grafo G Vemos que ambos conjuntos satisfacen los requisitos para ser ciclos hamiltonianos: acceden y parten de todos los nodos una ´unica vez y empiezan y terminan en el v´ertice a. Ejemplo 2. Consideremos los dos grafos de la figura 5.2. De nuevo, queremos hallar los ciclos hamiltonianos de ambos grafos que parten del nodo a. Estos dos grafos son el mismo salvo por un arco: el grafo J1posee un arco que parte del nodo c y accede al nodo i y el grafo J2no posee este arco. Esto hace que en J2no se pueda acceder a los nodos h, i, f, g, d y e, luego en este caso no debemos obtener ning´un ciclo hamiltoniano. 86 (a) Grafo J1(b) Grafo J2 Figura 5.2: grafos J1yJ2 Modelizamos el grafo J1a trav´es de las reglas: nodo(a;b;c;d;e;f;g;h;i). arco(a,b;b,a;b,c;c,i;d,a;d,e;e,d;e,a;f,e;f,g;g,h; g,f;g,d;h,f;h,g;i,g;i,h). inicial(a). Para este grafo, obtenemos como soluci´on tres ciclos hamiltonianos: %Answer: 1 % en(a,b) en(b,c) en(c,i) en(d,a) en(e,d) en(f,e) en(g,f) en(h,g) en(i,h) %Answer: 2 % en(a,b) en(b,c) en(c,i) en(d,a) en(e,d) en(f,e) en(g,h) en(h,f) en(i,g) %Answer: 3 % en(a,b) en(b,c) en(c,i) en(d,e) en(e,a) en(f,g) en(g,d) en(h,f) en(i,h) Modelizamos ahora el grafo J2: nodo(a;b;c;d;e;f;g;h;i). arco(a,b;b,a;b,c;d,a;d,e;e,d;e,a;f,e;f,g;g,h;g,f;g,d;h,f; h,g;i,g;i,h). 87 inicial(a). CLINGO nos devuelve: %UNSATISFIABLE En efecto, como dijimos, este grafo no posee ciclos hamiltonianos pues estos recorren todos los nodos del grafo y J2contiene algunos nodos a los que no se puede acceder. Para generar los candidatos a ciclos hamiltonianos, tambi´en podemos modificar el programa anterior como sigue: se sustituye la ´ultima regla que acabamos de exponer, que se utiliza como hemos visto para generar los posibles caminos candidatos a ser ciclos hamiltonianos, por una regla que se denomina regla de elecci´on. Las reglas de elecci´on tienen dos formas: s1<1{p(X) : q(X)}<2s2:- cuerpo. s1<1{p(c1); . . . ;p(cr)}<2s2:- cuerpo. donde s1ys2son enteros no negativos los cuales pueden omitirse y <1y <2son predicados de comparaci´on. La primera regla a˜nade a los conjuntos de respuesta del programa ciertos conjuntos S formados por ´atomos p(t) de manera que s1≤ |S| ≤ s2y tales que si un ´atomo p(t)∈S, entonces el correspondiente q(t) debe pertenecer al conjunto de respuesta. Esto es, la primera regla est´a generando un predicado p en funci´on de un predicado qpreviamente definido. La segunda regla permite la adici´on a los conjuntos de repuesta de conjuntos S formados por ´atomos p(ci) entre los que se encuentran en la cabeza de la regla de manera que s1≤ |S| ≤ s2. En nuestro caso, reemplazamos la ´ultima regla del programa para hallar los ciclos hamiltonianos de un grafo por la regla: {en(V1,V2) : arco(V1,V2)}. con la que se est´a definiendo el predicado en/2 en funci´on del predicado arco/2 de forma que para cada arco de G, se plantea incluirlo o no en el ciclo que se est´e considerando. 88 si es NP y NP-hard al mismo tiempo. Se puede probar que el Nurikabe es un problema NP-hard, y decidir si existe soluci´on del Nurikabe es un problema NP-completo. Para m´as informaci´on, puede visitarse el siguiente enlace: enlace. Las reglas del Nurikabe son: 1. Todas las celdas numeradas deben permanecer blancas. 2. Toda celda blanca debe pertenecer a una isla. 3. Cada isla debe contener una ´unica celda numerada. 4. Cada isla debe estar formada por el n´umero de celdas blancas que indique la casilla numerada que contiene. 5. Las celdas blancas de cada isla deben estar ortogonalmente conectadas. 6. Dos islas no pueden estar conectadas. 7. Todas las celdas negras deben estar conectadas ortogonalmente. 8. Ning´un subconjunto de celdas negras puede formar un cuadrado 2x2. Se puede visitar tambi´en el siguiente enlace para encontrar m´as informaci´on sobre las reglas del Nurikabe: enlace. Adem´as, este nos permite jugar en l´ınea, lo que puede resultar de utilidad para generar m´as ejemplos de puzzles Nurikabe aparte de los que vamos a exponer. Comencemos pues con la modelizaci´on de los puzzles Nurikabe. Supongamos que nos dan una cuadr´ıcula rectangular de dimensi´on nxm (n filas y m columnas). Se representa la cuadr´ıcula describiendo las celdas que est´an numeradas con el predicado numerada/3, donde numerada(X,Y,A) se verifica si la celda que ocupa la posici´on (X,Y) en la cuadr´ıcula, con X la fila e Y la columna, contiene el n´umero A (por tanto, esta celda va a pertener a una isla de tama˜no A). Para representar las filas y las columnas de la cuadr´ıcula, se usa el predicado fila/1 ycol/1: fila(1..n). col(1..m). 95 Se representan los dos colores de celdas que podemos tener con el predicado color/1, donde brepresenta el color blanco y nrepresenta el color negro: color(n). color(b). Vamos a generar todas las posibles cuadr´ıculas que se pueden considerar seleccionando subconjuntos de celdas que permanecer´an blancas y pintando de negro las celdas restantes. Para generar las cuadr´ıculas, se usa el predicado celda/3, de forma que celda(C,X,Y) representa que la celda que est´a en la posici´on (X,Y) es de color C. A trav´es de una regla de elecci´on, se generan los conjuntos de celdas que permanecer´an blancas: {celda(b,X,Y)}1 :- fila(X), col(Y). Para pintar las restantes celdas de negro, usamos la siguiente regla: celda(n,X,Y) :- not celda(b,X,Y), fila(X), col(Y). Ahora, vamos a implementar las reglas para eliminar las cuadr´ıculas que no las verifiquen. REGLA 1. Debemos modelizar la regla 1: “todas las celdas numeradas deben permanecer blancas”. Representamos la regla con una restricci´on, de manera que para verificarse no puede ocurrir que una celda (X,Y) sea negra y a su vez est´e numerada: :- numerada(X,Y,A), celda(n,X,Y). REGLAS 2 Y 5. Para la implementaci´on de 2 y 5, usamos la regla 3: por las reglas 2, 3 y 5, sabemos que cada celda blanca debe pertenecer a una isla, que cada isla debe contener una ´unica celda numerada y que las celdas blancas de cada isla se conectan ortogonalmente. Por tanto, toda celda blanca debe estar conectada ortogonalmente a una celda numerada. Para representar este conocimiento, vamos a definir antes algunos conceptos. 96 Primero, vamos a definir la relaci´on “ser adyacentes”: las celdas adyacentes a una celda (X,Y) son las celdas (X+1,Y), (X-1,Y), (X,Y+1), (X,Y-1). Representamos que la celda (X,Y) y la celda (U,V) son adyacentes usando el predicado ady/4: ady(X,Y,U,V) :- fila(X), fila(U), col(Y), col(V), |X-U|+|Y-V| == 1. Nota: tambi´en se puede denominar ortogonal, pues representa que dos celdas est´an conectadas ortogonalmente. Proseguimos modelizando cu´ando dos celdas se van a conectar ortogonalmente a trav´es de un color. Para ello, introducimos el predicado conectadas/4, que se verifica si: 1. conectadas(C,X,Y,X,Y) se verifica si (X,Y) es una celda de color C. Es decir, vamos a considerar que una celda (X,Y) de color C est´a conectada consigo misma a trav´es del color C. 2. conectadas(C,X,Y,U,V) se verifica si la celda (U,V) es de color C y si existe una celda intermedia que es adyacente a (U,V) y est´a conectada ortogonalmente a trav´es del color C a (X,Y). El predicado est´a definido por recursi´on, as´ı que lo representamos con las reglas: conectadas(C,X,Y,X,Y) :- celda(C,X,Y). conectadas(C,X,Y,U,V) :- celda(C,U,V), conectadas(C,X,Y,X1,Y1), ady(X1,Y1,U,V). Finalmente, para representar que toda celda blanca debe estar conectada ortogonalmente a una celda numerada, se define el predicado conectadaB/2, donde conectadaB(X,Y) se verifica si (X,Y) est´a conectada ortogonalmente a trav´es del color blanco a una celda numerada, e imponemos que toda celda blanca verifique el predicado conectadaB/2 a trav´es de una restricci´on: 97 conectadaB(X,Y) :- conectadas(b,X,Y,U,V), celda(b,X,Y), numerada(U,V,A). :- celda(b,X,Y), not conectadaB(X,Y). REGLAS 3 Y 6. Para representar las reglas 6 y 3, usamos la regla 2: se tiene que cada isla contiene una ´unica celda numerada, que toda celda blanca pertenece a una isla y que dos islas no pueden estar conectadas. Esto implica que dos celdas numeradas no van poder estar conectadas ortogonalmente a trav´es del color blanco porque sino, dos islas distintas estar´ıan conectadas. :- conectadas(b,X,Y,U,V), numerada(X,Y,A), numerada(U,V,M), (X,Y) != (U,V). REGLA 4. Para la regla 4: “cada isla debe estar formada por el n´umero de celdas blancas que indique la casilla numerada que contiene”, vamos a definir qu´e se considera por isla. La isla estar´a formada por una casilla numerada (X,Y), supongamos que es tal que se verifica numerada(X,Y,A), y por exactamente A celdas blancas que se conectan ortogonalmente a trav´es del color blanco a la celda numerada. Es decir, el cardinal del conjunto de celdas blancas que se conectan ortogonalmente a (X,Y) debe ser exactamente A. Como por la regla 3, cada isla contiene una ´unica celda numerada, identificamos la isla con la celda numerada: isla(X,Y) :- numerada(X,Y,A), A {conectadas(b,X,Y,U,V)}A, fila(X), col(Y). Todas las celdas numeradas deben definir una isla: :- numerada(X,Y,A), not isla(X,Y). REGLA 7. Veamos c´omo representar la regla 7: “todas las celdas negras deben estar conectadas ortogonalmente”. Para ello, usamos de nuevo una restricci´on: no pueden existir dos celdas (X,Y) y (U,V) de color negro que no est´en conec98 tadas ortogonalmente a trav´es del color negro. :- celda(n,X,Y), celda(n,U,V), not conectadas(n,X,Y,U,V). REGLA 8. Por ´ultimo, representemos la regla 8: “ning´un subconjunto de celdas negras puede formar un cuadrado 2x2”. Para ello, definimos primero cu´ando un subconjunto de celdas negras define un cuadrado: si tenemos una celda (X,Y) negra, est´a define un cuadrado cuando las celdas (X,Y+1), (X+1,Y) y (X+1,Y+1) tambi´en son negras. cuadradoN(X,Y) :- celda(n,X,Y), celda(n,X,Y+1), celda(n,X+1,Y), celda(n,X+1,Y+1). Finalmente, se impide que cualquier celda forme un cuadrado de celdas negras usando una restricci´on: :- cuadradoN(X,Y). Como al principio todas las celdas de la cuadr´ıcula son blancas, la soluci´on del Nurikabe ser´a el conjunto de celdas que finalmente se han pintado de negro. As´ı, definimos el predicado celdaNegra/2, que se verifica si la celda est´a pintada de negro: celdaNegra(X,Y) :- celda(n,X,Y). Por tanto, la soluci´on a nuestro problema nos la dar´a el conjunto de literales de la forma celdaNegra(X,Y) que aparezca en el conjunto de respuesta: #show celdaNegra/2. Veamos ahora algunos ejemplos de puzzles Nurikabe. Ejemplo 1. En este ejemplo, vamos a considerar el Nurikabe de la figura 6.1. Vamos a describir este puzzle con usando el predicado numerada/3: numerada(2,1,2). numerada(3,3,2). numerada(3,5,4). numerada(5,2,2). numerada(5,6,3). numerada(6,4,2). numerada(8,4,3). numerada(9,2,6). numerada(10,7,4). Para cargar el fichero, debemos especificarle a CLINGO el n´umero de 99 filas y columnas de la cuadr´ıcula (lo que denominamos como n y m, respectivamente). Guardando el c´odigo del Nurikabe en el archivo nurikabe.lp y el fichero con la descripci´on de la cuadr´ıcula en el archivo con nombre nurikabe1.lp, cargamos los archivos como: clingo nurikabe.lp nurikabe1.lp -c n=11 -c m=8 y nos devuelve la soluci´on del puzzle: %celdaNegra(1,1) celdaNegra(4,1) celdaNegra(5,1) celdaNegra(6,1) %celdaNegra(7,1) celdaNegra(8,1) celdaNegra(9,1) celdaNegra(10,1) %celdaNegra(11,1) celdaNegra(1,2) celdaNegra(2,2) celdaNegra(3,2) %celdaNegra(4,2) celdaNegra(7,2) celdaNegra(11,2) celdaNegra(1,3) %celdaNegra(4,3) celdaNegra(5,3) celdaNegra(6,3) celdaNegra(7,3) %celdaNegra(8,3) celdaNegra(9,3) celdaNegra(11,3) celdaNegra(1,4) %celdaNegra(2,4) celdaNegra(3,4) celdaNegra(4,4) celdaNegra(7,4) %celdaNegra(9,4) celdaNegra(11,4) celdaNegra(1,5) celdaNegra(4,5) %celdaNegra(5,5) celdaNegra(6,5) celdaNegra(9,5) celdaNegra(11,5) %celdaNegra(1,6) celdaNegra(3,6) celdaNegra(4,6) celdaNegra(6,6) %celdaNegra(7,6) celdaNegra(8,6) celdaNegra(9,6) celdaNegra(10,6) %celdaNegra(11,6) celdaNegra(1,7) celdaNegra(3,7) celdaNegra(6,7) %celdaNegra(11,7) celdaNegra(1,8) celdaNegra(2,8) celdaNegra(3,8) %celdaNegra(4,8) celdaNegra(5,8) celdaNegra(6,8) celdaNegra(7,8) %celdaNegra(8,8) celdaNegra(9,8) celdaNegra(10,8) celdaNegra(11,8) (a) Nurikabe nivel medio (b) Soluci´on Figura 6.1: puzzle Nurikabe y su soluci´on 100 Ejemplo 2. Estudiemos ahora la soluci´on del Nurikabe de la figura 6.2. Figura 6.2: puzzle Nurikabe nivel medio Describamos el puzzle de nuevo con el predicado numerada/3: numerada(2,2,2). numerada(2,5,2). numerada(3,7,2). numerada(4,3,2). numerada(5,4,2). numerada(6,3,2). numerada(7,7,6). numerada(8,1,4). numerada(9,5,4). numerada(10,6,2). Ahora, guardamos el c´odigo de la descripci´on en el fichero nurikabe2.lp. Cargando de nuevo los archivo como: clingo nurikabe.lp nurikabe2.lp -c n=10 -c m=7 nos devuelve la soluci´on del Nurikabe: %celdaNegra(1,1) celdaNegra(2,1) celdaNegra(3,1) celdaNegra(4,1) %celdaNegra(5,1) celdaNegra(6,1) celdaNegra(1,2) celdaNegra(3,2) %celdaNegra(5,2) celdaNegra(7,2) celdaNegra(8,2) celdaNegra(9,2) %celdaNegra(10,2) celdaNegra(1,3) celdaNegra(3,3) celdaNegra(5,3) %celdaNegra(7,3) celdaNegra(10,3) celdaNegra(1,4) celdaNegra(2,4) %celdaNegra(3,4) celdaNegra(4,4) celdaNegra(6,4) celdaNegra(7,4) %celdaNegra(8,4) celdaNegra(10,4) celdaNegra(1,5) celdaNegra(4,5) %celdaNegra(6,5) celdaNegra(8,5) celdaNegra(10,5) celdaNegra(1,6) %celdaNegra(2,6) celdaNegra(3,6) celdaNegra(4,6) celdaNegra(5,6) 101 %celdaNegra(6,6) celdaNegra(8,6) celdaNegra(9,6) celdaNegra(1,7) %celdaNegra(4,7) celdaNegra(9,7) 6.2. Puzzle Heyawake El Heyawake es un puzzle que se juega en una cuadr´ıcula rectangular dividida en celdas. Adem´as, la cuadr´ıcula se divide a su vez en habitaciones rectangulares de diversos tama˜nos. Al comienzo, las celdas de la cuadr´ıcula son blancas y algunas habitaciones contienen una celda numerada. El objetivo es decidir qu´e celdas deben permanecer blancas y qu´e celdas se pintan de negro de acuerdo a las reglas que se exponen a continuaci´on. Al igual que el Nurikabe, decidir si existe una soluci´on del puzzle Heyawake es un problema NP-completo. Las reglas del puzzle son las siguientes: 1. Dos celdas negras no pueden ser adyacentes ni vertical ni horizontalmente. 2. Todas las celdas blancas deben estar conectadas ortogonalmente. 3. En las habitaciones en las que se encuentre una celda numerada, el n´umero de la celda indica c´uantas celdas de la habitaci´on deben pintarse de negro. 4. Una habitaci´on sin celda numerada puede contener cualquier n´umero de celdas negras. 5. Un camino recto de celdas blancas no puede atravesar m´as de dos habitaciones. De nuevo, podemos visitar el siguiente enlace para obtener m´as informaci´on sobre las reglas del juego y poder jugar en l´ınea: enlace. Veamos entonces c´omo se puede modelizar el puzzle. Primero, vamos a describir la cuadr´ıcula dada. Supongamos que la cuadr´ıcula que consideramos tiene dimensiones nxm (n filas y m columnas) y est´a dividida en r habitaciones. 102 Para describir la cuadr´ıcula, a cada habitaci´on se le asigna una etiqueta y se representa a trav´es del predicado hab/4: supongamos que tenemos una habitaci´on delimitada por las celdas (X1,Y1), (X1,Y2), (X2,Y1) y (X2,Y2) a la que se le asigna una etiqueta A, entonces, esto se representa como hab(A,X1,Y1,X2,Y2). La etiqueta A que podemos asignarle a cada habitaci´on ir´a de 0 a r-1, y se representa por el predicado etiqueta/1. fila(1..n). col(1..m). etiqueta(0..r-1). Algunas de las habitaciones contienen una celda numerada y otras no. Para representarlo, usamos el predicado contiene/2, de manera que contiene(A,N) representa que la habitaci´on cuya etiqueta es A contiene una celda numerada con el n´umero N. Para representar que la habitaci´on A no tiene celda numerada, se usa contiene(A,-1). Estudiemos entonces el programa que nos dar´a la soluci´on del Heyawake. Vamos a generar las distintas cuadr´ıculas candidatas a ser soluci´on atendiendo a las reglas 3 y 4, contemplando todas las maneras de pintar celdas de negro en cada habitaci´on de la cuadr´ıcula (la celda numerada tambi´en puede pintarse de negro esta vez). Para ello, definimos primero el “tama˜no de la habitaci´on”: una habitaci´on con una celda numerada con el n´umero N tendr´a tama˜no N, y una habitaci´on sin celda numerada tendr´a tama˜no -1. El tama˜no de la habitaci´on nos indica cu´antas celdas de la habitaci´on pueden pintarse de negro. Usamos el predicado dimHab/4 para representar el tama˜no de la habitaci´on: dimHab(N,X1,Y1,X2,Y2) :- hab(A,X1,Y1,X2,Y2), contiene(A,N). REGLAS 3 Y 4. Veamos c´omo representar las reglas 3 y 4. Para ello, usamos el predicado celdaNegra/2 donde celdaNegra(X,Y) indica, como antes, que la celda (X,Y), donde X es la fila e Y la columna, se ha pintado de negro. Usamos tambi´en el predicado dentrohab/3, donde dentrohab(X,Y,A) representa que la celda (X,Y) est´a dentro de la habitaci´on A: dentrohab(X,Y,A) :- hab(A,X1,Y1,X2,Y2), X1<=X, X<=X2, Y1<=Y, Y<=Y2, fila(X), col(Y). 103 Generemos todas las posibles maneras de pintar celdas de negro en una habitaci´on que contiene una celda numerada atendiendo a la regla 3. Usamos una regla de elecci´on: N{celdaNegra(X,Y):dentrohab(X,Y,A)}N :- hab(A,X1,Y1,X2,Y2), dimHab(N,X1,Y1,X2,Y2), N>0. Ahora, generamos todas las posibles formas de pintar celdas de negro en una habitaci´on que no tiene ninguna celda numerada de acuerdo a la regla 4. {celdaNegra(X,Y):dentrohab(X,Y,A)}:- hab(A,X1,Y1,X2,Y2), dimHab(-1,X1,Y1,X2,Y2). Las celdas restantes que no hayamos pintado de negro permanecer´an blancas: celdaBlanca(X,Y) :- not celdaNegra(X,Y), fila(X), col(Y). Implementemos las reglas que quedan para descartar las cuadr´ıculas que no las verifican. REGLA 1. Tenemos que modelizar la regla 1: “dos celdas negras no pueden ser adyacentes ni vertical ni horizontalmente”. Como ya hicimos, usamos el predicado ady/4 para representar que dos celdas son adyacentes. Dada una celda (X,Y), sus adyacentes son las celdas (X+1,Y), (X-1,Y),(X,Y+1), (X,Y-1). Por tanto, definimos el predicado con la regla: ady(X1,Y1,X2,Y2) :- fila(X1), fila(X2), col(Y1), col(Y2), |X1-X2| + |Y1-Y2| == 1. Representamos que dos celdas negras no pueden ser adyacentes ni vertical ni horizontalmente a trav´es de la restricci´on: 104 yblanco/2, donde negro(X,Y) nos indica que la celda que se encuentra en la fila X y en la columna Y contiene un c´ırculo negro y, an´alogamente, blanco(X,Y) nos indica que la celda (X,Y) contiene un c´ırculo blanco. Veamos ahora como generar la l´ınea soluci´on del puzzle. Para representar las filas y las columnas de la cuadr´ıcula, se usa como anteriormente los predicados col/1 yfila/1: col(1..m). fila(1..n). Ahora, vamos a considerar todos los segmentos posibles que podemos tener atravesando las celdas del tablero. Las direcciones que pueden llevar estos segmentos son la horizontal y la vertical, y lo representamos con el predicado direc/1, donde direc(h) representa que el segmento lleva direcci´on horizontal y direc(v), que lleva direcci´on vertical. direc(h). direc(v). Para representar los segmentos, vamos a considerar el predicado seg/3, donde seg(h,X,Y) se verifica si se pinta un segmento horizontal que atraviesa las celdas (X,Y) y (X,Y+1), y seg(v,X,Y) se verifica si se pinta un segmento vertical que atraviesa las celdas (X,Y) y (X+1,Y). Generamos as´ı los posibles segmentos que podr´ıamos dibujar en las celdas de la cuadr´ıcula usando una regla de elecci´on: {seg(S,X,Y)}:- direc(S), fila(X), col(Y). Como seg(S,X,Y) se verifica si se atraviesa (X,Y) y alguna de las celdas (X+1,Y) o (X,Y+1), seg´un si el segmento es vertical u horizontal respectivamente, en las celdas de la ´ultima columna no se podr´an realizar segmentos horizontales que partan de ellas, pues no existir´an las celdas de la forma (X,m+1), y del mismo modo, tampoco se podr´an realizar segmentos verticales que partan de las celdas de la ´ultima fila, pues no existir´an celdas de la forma (n+1,Y). Representamos esto a trav´es de las siguientes dos reglas: :- seg(h,X,m), fila(X). :- seg(v,n,Y), col(Y). Esto nos da los posibles conjuntos candidatos a ser soluci´on del puzzle Masyu. Ahora, debemos implementar las reglas, que eliminar´an los conjuntos de segmentos que no resuelvan el puzzle. 111 Primero, representemos que la l´ınea soluci´on del puzzle debe pasar por todos los c´ırculos de la cuadr´ıcula, ya sean blancos o negros. Para representar esto, vamos a usar dos predicados: 1. Usamos el predicado circulo/2 donde circulo(X,Y) se verifica si la celda (X,Y) contiene un c´ırculo blanco o negro: circulo(X,Y) :- blanco(X,Y), fila(X), col(Y). circulo(X,Y) :- negro(X,Y), fila(X), col(Y). 2. Usamos el predicado pasaPor/2 donde pasaPor(X,Y) representa que alguno de los segmentos que componen la soluci´on pasa por (X,Y). pasaPor(X,Y) :- seg(S,X,Y), fila(X), col(Y), direc(S). pasaPor(X,Y+1) :- seg(h,X,Y), Y<m, fila(X), col(Y). pasaPor(X+1,Y) :- seg(v,X,Y), X<n, fila(X), col(Y). Finalmente, se representa que la l´ınea soluci´on debe pasar por todas las celdas que contienen c´ırculos mediante una restricci´on: :- circulo(X,Y), not pasaPor(X,Y). Implementemos ahora las reglas. REGLA 1. Debemos representar que la l´ınea soluci´on forma un ´unico camino cerrado que entra y sale de cada celda que atraviesa una ´unica vez. Para representar que entra y sale de cada celda que atraviesa una ´unica vez, vamos a imponer que la celda sea atravesada ´unicamente por dos segmentos, ya sea alg´un segmento que parte de la misma celda en direcci´on vertical u horizontal u otro segmento que parta de la celda (X-1,Y) en direcci´on vertical o de (X,Y-1) en direcci´on horizontal. Por tanto, el cardinal del conjunto formado por estos cuatro segmentos es exactamente 2. :- 3 {seg(h,X,Y); seg(v,X,Y); seg(v,X-1,Y); seg(h,X,Y-1)}, pasaPor(X,Y). :- {seg(h,X,Y); seg(v,X,Y); seg(v,X-1,Y); seg(h,X,Y-1)}1, pasaPor(X,Y). 112 Se debe pintar una ´unica l´ınea que sea la soluci´on del puzzle. Esto quiere decir que si la l´ınea soluci´on pasa por dos celdas, podemos llegar de una a otra recorri´endola. Para representar esto, debemos definir antes el predicado ady/4, que representa cu´ando dos celdas van a ser adyacentes: una celda va a ser adyacente a (X,Y) si podemos llegar a la celda a trav´es de un segmento que parte de (X,Y) y que forma parte de la l´ınea soluci´on. As´ı, se define ady/4 a trav´es de las reglas: ady(X,Y,X+1,Y) :- seg(v,X,Y), X<n. ady(X,Y,X,Y+1) :- seg(h,X,Y), Y<m. Si (X,Y) es adyacente a una celda (W,Z), la celda (W,Z) ser´a adyacente a (X,Y). Para representar la simetr´ıa de la relaci´on, usamos: ady(X,Y,W,Z) :- ady(W,Z,X,Y). Representaremos que si la l´ınea soluci´on atraviesa dos celdas, se puede llegar de una a otra recorriendo la l´ınea usando el predicado alcanzable/4, que se define como sigue: 1. Supondremos que toda celda que atraviesa la l´ınea soluci´on es alcanzable desde ella misma. alcanzable(X,Y,X,Y) :- pasaPor(X,Y), fila(X), col(Y). 2. Supondremos que la celda (W,Z) es alcanzable desde la celda (X,Y) si existe una celda (X1,Y1) de manera que (X,Y) y (X1,Y1) son adyacentes y (W,Z) es alcanzable desde (X1,Y1). alcanzable(X,Y,W,Z) :- ady(X1,Y1,X,Y), alcanzable(X1,Y1,W,Z), fila(X), col(Y), fila(X1), col(Y1), fila(W), col(Z). Finalmente, para representar que dada dos celdas por las que la l´ınea soluci´on pasa, siempre debemos llegar de una a otra recorri´endola, usamos una restricci´on: :- pasaPor(X,Y), pasaPor(W,Z), not alcanzable(X,Y,W,Z). 113 REGLA 2. El camino debe atravesar las celdas con c´ırculos blancos en l´ınea recta, es decir, supongamos que (X,Y) es una celda que contiene un c´ırculo blanco, entonces si de (X,Y) parte un segmento horizontal, a (X,Y) lo debe atravesar otro segmento horizontal, que debe partir de (X,Y-1), y si de (X,Y) parte un segmento vertical, a (X,Y) lo debe atravesar un segmento vertical, esta vez partiendo de (X-1,Y). Para representar esto, se usa una restricci´on, que impedir´a que se d´e cualquier otra posibilidad que no sean las que acabamos de exponer: :- 1 {seg(h,X,Y); seg(h,X,Y-1)}, 1 {seg(v,X,Y); seg(v,X-1,Y)}, blanco(X,Y). Adem´as, la l´ınea soluci´on debe girar 90 grados en la celda anterior o posterior en el camino a la celda que contiene el c´ırculo blanco. Es decir, si la celda (X,Y) contiene un c´ırculo blanco, de ella parte un segmento horizontal y adem´as es atravesada por otro segmento horizontal que parte de (X,Y-1), no puede ocurrir que (X,Y-1) sea atravesada por un segmento horizontal a la vez que de (X,Y+1) parta un segmento horizontal. :- blanco(X,Y), seg(h,X,Y), seg(h,X,Y-1), seg(h,X,Y-2), seg(h,X,Y+1). De la misma manera, si la celda (X,Y) que contiene el c´ırculo blanco fuese atravesada por un segmento vertical que parte de (X-1,Y) y adem´as, de ella partiese un segmento vertical, no podr´ıa partir a la vez un segmento vertical de (X-2,Y) y de (X+1,Y). Usamos para representarlo la restricci´on: :- blanco(X,Y), seg(v,X,Y), seg(v,X-1,Y), seg(v,X+1,Y), seg(v,X-2,Y). REGLA 3. Por ´ultimo, vamos a modelizar la regla 3. Primero, representemos que el camino debe realizar giros de 90 grados en las celdas que contengan c´ırculos negros. Para ello, supongamos que (X,Y) es una celda que contiene un c´ırculo negro. Entonces, si de (X,Y) parte un segmento vertical, no puede ocurrir que de (X-1,Y) parta otro segmento vertical, porque si no la celda queda recorrida en l´ınea recta. De igual modo, si de (X,Y) parte un segmento horizontal, no puede ocurrir que de (X,Y-1) parta un segmento horizontal, por el mismo 114 motivo. Usando restricciones, lo representamos a trav´es de las reglas: :- negro(X,Y), seg(v,X,Y), seg(v,X-1,Y), fila(X), col(Y). :- negro(X,Y), seg(h,X,Y), seg(h,X,Y-1), fila(X), col(Y). Para representar que las celdas anterior y posterior en el camino a la celda que contiene el c´ırculo negro (que estamos suponiendo que es (X,Y)) deben ser atravesadas en l´ınea recta, se usan cuatro restricciones: 1. Si de la celda (X,Y) parte un segmento horizontal, entonces la celda siguiente en el camino a (X,Y) es (X,Y+1) y para que sea por tanto atravesada el l´ınea recta, de ella no debe partir ni acceder nig´un segmento vertical: :- negro(X,Y), seg(h,X,Y), 1 {seg(v,X,Y+1); seg(v,X-1,Y+1)}. 2. Si de la celda (X,Y-1) parte un segmento horizontal que atraviesa a (X,Y), entonces (X,Y-1) es la celda anterior en el camino a (X,Y) y por tanto, ni de ella ni de (X-1,Y-1) deben partir segmentos verticales para que la l´ınea soluci´on atraviese (X,Y-1) en l´ınea recta. :- negro(X,Y),seg(h,X,Y-1), 1 {seg(v,X,Y-1); seg(v,X-1,Y-1)}. 3. Si de la celda (X,Y) parte un segmento vertical, la celda siguiente a (X,Y) en el camino es (X+1,Y), luego para que esta se recorra en l´ınea recta, no puede ocurrir que parta de ella un segmento horizontal o parta de (X+1,Y-1) un segmento horizontal. :- negro(X,Y), seg(v,X,Y), 1 {seg(h,X+1,Y); seg(h,X+1,Y-1)}. 4. Si de la celda (X-1,Y) parte un segmento vertical, esta es la celda anterior a la celda (X,Y) en el camino, luego no puede ocurrir que sea atravesada por un segmento horizontal ni que de ella parta un segmento horizontal. :- negro(X,Y),seg(v,X-1,Y), 1 {seg(h,X-1,Y-1); seg(h,X-1,Y)}. La soluci´on del Masyu vendr´a dada por los segmentos que finalmente se pinten en la cuadr´ıcula y cumplan las reglas, luego nos fijamos ´unicamente en los literales formados por el predicado seg/3 en el conjunto de respuesta: #show seg/3. Como hemos hecho en los puzzles anteriores, vamos a ver algunos ejemplos de puzzle Masyu y sus soluciones. 115 (a) Masyu nivel normal (b) Soluci´on Figura 6.5: puzzle Masyu y su soluci´on Ejemplo 1. Estudiemos primero la soluci´on del puzzle Masyu de la figura 6.5. Describimos la cuadr´ıcula representando las celdas que poseen un c´ırculo blanco o negro con los predicados negro/2 yblanco/2: blanco(1,4). negro(2,5). blanco(3,1). blanco(3,6). negro(4,2). negro(5,7). blanco(6,2). blanco(7,5). negro(8,3). blanco(8,5). negro(8,7). Guardando el c´odigo del puzzle Masyu en el archivo masyu.lp, la descripci´on de la cuadr´ıcula en el archivo masyuNormal.lp y ejecutando CLINGO de la siguiente manera: clingo masyu.lp masyuNormal.lp -c n=8 -c m=8 obtenemos la soluci´on del puzzle: %seg(h,1,3) seg(h,1,4) seg(h,1,5) seg(h,1,6) seg(h,1,7) seg(h,2,1) seg(h,2,3) %seg(h,2,4) seg(h,2,6) seg(h,4,2) seg(h,4,3) seg(h,4,5) seg(h,5,1) seg(h,5,4) %seg(h,5,5) seg(h,5,6) seg(h,6,3) seg(h,6,4) seg(h,6,5) seg(h,6,7) seg(h,7,1) %seg(h,7,4) seg(h,7,5) seg(h,8,1) seg(h,8,2) seg(h,8,4) seg(h,8,5) seg(h,8,6) %seg(v,1,3) seg(v,1,8) seg(v,2,1) seg(v,2,2) seg(v,2,5) seg(v,2,6) seg(v,2,7) %seg(v,2,8) seg(v,3,1) seg(v,3,2) seg(v,3,5) seg(v,3,6) seg(v,3,7) seg(v,3,8) %seg(v,4,1) seg(v,4,4) seg(v,4,7) seg(v,4,8) seg(v,5,2) seg(v,5,8) seg(v,6,2) %seg(v,6,3) seg(v,6,6) seg(v,6,7) seg(v,7,1) seg(v,7,3) seg(v,7,4) seg(v,7,7) 116 Ejemplo 2. Ahora, estudiamos la soluci´on del puzzle de la figura 6.6. Figura 6.6: puzzle Masyu nivel dif´ıcil Describimos el puzzle a trav´es de las reglas: blanco(1,9). negro(2,1). blanco(2,3). blanco(2,6). blanco(2,7). blanco(3,8). blanco(4,2). blanco(4,3). blanco(4,4). negro(4,6). blanco(5,6). blanco(5,7). negro(6,1). blanco(7,3). blanco(7,5). blanco(7,7). blanco(7,10). blanco(8,2). blanco(8,6). negro(9,5). blanco(9,6). negro(9,9). blanco(10,2). Guardando esta descripci´on en masyuDificil.lp y ejecutando CLINGO: clingo masyu.lp masyuDificil.lp -c n=10 -c m=10 se obtiene la soluci´on siguiente del puzzle: %seg(h,1,4) seg(h,1,5) seg(h,1,7) seg(h,1,8) seg(h,1,9) seg(h,2,1) seg(h,2,2) %seg(h,2,3) seg(h,3,2) seg(h,3,4) seg(h,3,7) seg(h,3,8) seg(h,4,6) seg(h,4,7) %seg(h,4,8) seg(h,5,1) seg(h,5,3) seg(h,5,5) seg(h,5,6) seg(h,5,7) seg(h,5,9) %seg(h,6,1) seg(h,6,2) seg(h,6,3) seg(h,6,5) seg(h,6,6) seg(h,6,7) seg(h,6,9) %seg(h,7,2) seg(h,7,3) seg(h,7,6) seg(h,7,7) seg(h,7,8) seg(h,9,2) seg(h,9,3) %seg(h,9,4) seg(h,9,7) seg(h,9,8) seg(h,10,1) seg(h,10,2) seg(h,10,3) %seg(h,10,4) seg(h,10,5) seg(h,10,7) seg(h,10,8) seg(h,10,9) seg(v,1,4) %seg(v,1,6) seg(v,1,7) seg(v,1,10) seg(v,2,1) seg(v,2,6) seg(v,2,7) seg(v,2,10) 117 %seg(v,3,1) seg(v,3,2) seg(v,3,3) seg(v,3,4) seg(v,3,5) seg(v,3,6) seg(v,3,9) %seg(v,3,10) seg(v,4,1) seg(v,4,2) seg(v,4,3) seg(v,4,4) seg(v,4,5) seg(v,4,10) %seg(v,5,8) seg(v,5,9) seg(v,6,1) seg(v,6,4) seg(v,6,5) seg(v,6,10) seg(v,7,1) %seg(v,7,2) seg(v,7,5) seg(v,7,6) seg(v,7,9) seg(v,7,10) seg(v,8,1) seg(v,8,2) %seg(v,8,5) seg(v,8,6) seg(v,8,9) seg(v,8,10) seg(v,9,1) seg(v,9,6) seg(v,9,7) %seg(v,9,10) 118 Bibliograf´ıa [CKK+07] Merve Cayli, Ayse G¨ul Karatop, Ahmet Emrah Kavlak, Hakan Kaynar, Ferhan Ture, and E. Erdem, Solving challenging grid puzzles with answer set programming, 2007. [GK14] Michael Gelfond and Yulia Kahl, Knowledge representation, reasoning, and the design of intelligent agents, Cambridge University Press, New York, 2014, The answer-set programming approach. [GKK+19] Martin Gebser, Roland Kaminski, Benjamin Kaufmann, Marius Lindauer, Max Ostrowski, Javier Romero, Torsten Schaub, Sven Thiele, and Philipp Wanko, Potassco user guide, 2019. [GL88] Michael Gelfond and Vladimir Lifschitz, The stable model semantics for logic programming, Proceedings of International Logic Programming Conference and Symposium (Robert Kowalski, Bowen, and Kenneth, eds.), MIT Press, 1988, pp. 1070–1080. [HD21] Mar´ıa Jos´e Hidalgo Doblado, L´ogica computacional y teor´ıa de modelos,https://www.glc.us.es/~mjoseh/LCyTM2020/ index.php/L%C3%B3gica_computacional_y_teor%C3%ADa_de_ modelos_(curso_2020-21), Curso 2020-2021. [Lif08] Vladimir Lifschitz, What is answer set programming?, vol. 3, 2008, pp. 1594–1597. [Lif19] Vladimir Lifschitz, Answer set programming, Springer International Publishing, 2019. 119