Upload
ow-en
View
121
Download
0
Embed Size (px)
Citation preview
Editado y corregido por Eliécer Pineda Ballesteros Página 1
Programación Lógica Lenguaje Prolog y Visual Prolog
INTRODUCCIÓN A LA
PROGRAMACIÓN LÓGICA
Y
VISUAL PROLOG V 5.21
Inteligencia Artificial y
Sistemas Expertos
1 Material recopilado de las páginas personales de la profesora Nieves Pavón de la Universidad
de Huelva y el profesor Omar Valdivia de la Universidad de Santiago de Chile. Texto editado por
Eliécer Pineda Ballesteros. Webs: http://www.uhu.es/nieves.pavon/pprogramacion/practicas/ y
www.comenius.usach.cl/gvillarr/cursoia/Guias/Guia%201%20VPI.doc
Editado y corregido por Eliécer Pineda Ballesteros Página 2
Programación Lógica Lenguaje Prolog y Visual Prolog
ÍNDICE
1 Lenguaje PROLOG: Conceptos ............................................................................................... 6
2 Bases del lenguaje PROLOG.................................................................................................... 6
2.1 Metodología declarativa frente a metodología imperativa. ......................................................................... 6
2.2 Ventajas e inconvenientes. ........................................................................................................................ 7
3 Definición de Hechos, Metas y Predicados en PROLOG ...................................................... 7
3.1 Construcción de Bases de Conocimientos en PROLOG ......................................................................... 10
3.2 Consultas sobre la Base de Conocimientos ............................................................................................ 12
3.3 Ejemplos .................................................................................................................................................. 15
4 Definición y funcionamiento de la Máquina PROLOG ......................................................... 20
4.1 Unificación ............................................................................................................................................... 20
4.2 Backtracking ............................................................................................................................................ 21
5 Sintaxis Básica de VISUAL PROLOG .................................................................................... 24
5.1 Aritmética de VISUAL PROLOG .............................................................................................................. 24
6 Datos simples y Estructuras de Datos: DOMINIOS ............................................................. 27
6.1 OBJETOS COMPUESTOS ...................................................................................................................... 27
6.2 ÁRBOLES ................................................................................................................................................ 28
6.3 LISTAS .................................................................................................................................................... 30
6.4 MATRICES .............................................................................................................................................. 34
7 Manipulación del Control en Prolog ...................................................................................... 36
8 Corte (!) y fail............................................................................................................................ 36
8.1 El Corte "!" ............................................................................................................................................... 36
8.2 El predicado fail ....................................................................................................................................... 39
8.3 Implementación de la negación y predicado repeat ................................................................................. 40
9 Aplicaciones actuales del Lenguaje PROLOG ..................................................................... 43
9.1 Inteligencia Artificial ................................................................................................................................. 43
9.2 Sistemas Expertos ................................................................................................................................... 49
Editado y corregido por Eliécer Pineda Ballesteros Página 3
Programación Lógica Lenguaje Prolog y Visual Prolog
9.3 Compiladores ........................................................................................................................................... 50
9.4 Miscelánea ............................................................................................................................................... 52
10 Líneas Futuras ......................................................................................................................... 53
11 Introducción. ............................................................................................................................ 56
11.1 Conceptos básicos................................................................................................................................... 56
11.2 Resolución y unificación. Métodos. .......................................................................................................... 59
12 Entorno De Desarrollo De Visual Prolog .................................... ¡Error! Marcador no definido.
12.1 Secciones De Un Programa En Visual Prolog ............................................ ¡Error! Marcador no definido.
12.2 Directivas de compilación ........................................................................... ¡Error! Marcador no definido.
12.3 Sección de constantes ................................................................................ ¡Error! Marcador no definido.
12.4 Sección de dominios ................................................................................... ¡Error! Marcador no definido.
12.5 Dominios de Objetos Compuestos ............................................................. ¡Error! Marcador no definido.
12.6 Dominios de Objetos Compuestos Functorless .......................................... ¡Error! Marcador no definido.
12.7 Sinónimos de Dominios Estándar ............................................................... ¡Error! Marcador no definido.
12.8 Dominios tipo Lista...................................................................................... ¡Error! Marcador no definido.
12.9 Dominios tipo Predicado ............................................................................. ¡Error! Marcador no definido.
12.10 Sección de la base de datos ......................................................... ¡Error! Marcador no definido.
12.11 Sección de definición de predicados ............................................ ¡Error! Marcador no definido.
12.12 Tipos de predicados ..................................................................... ¡Error! Marcador no definido.
12.13 Cómo conseguir la coherencia entre reglas y predicados en el aspecto determinista ........ ¡Error! Marcador no definido.
12.14 Sección de cláusulas .................................................................... ¡Error! Marcador no definido.
12.15 Sección de meta u objetivo ........................................................... ¡Error! Marcador no definido.
12.16 Ejemplo ......................................................................................... ¡Error! Marcador no definido.
13 El Entorno De Desarrollo De Visual Prolog ............................... ¡Error! Marcador no definido.
13.1 Aplicaciones orientadas a eventos ............................................................. ¡Error! Marcador no definido.
13.2 Aplicaciones orientadas a eventos en Visual Prolog .................................. ¡Error! Marcador no definido.
13.3 Tipos de ventanas en Visual Prolog............................................................ ¡Error! Marcador no definido.
13.4 Programa Cero ........................................................................................... ¡Error! Marcador no definido.
13.4.1 Pasos para realizar una Aplicación Experta ................................. ¡Error! Marcador no definido.
Editado y corregido por Eliécer Pineda Ballesteros Página 4
Programación Lógica Lenguaje Prolog y Visual Prolog
13.4.2 Realizar una aplicación “Hello World” ........................................... ¡Error! Marcador no definido.
13.4.3 Añadir un cuadro de mensaje en la aplicación Experta. ............... ¡Error! Marcador no definido.
13.4.4 Crear "Cross Window" ................................................................ ¡Error! Marcador no definido.
13.4.5 Cómo crear una nueva ventana .................................................... ¡Error! Marcador no definido.
13.4.6 Generando código para la venta ................................................... ¡Error! Marcador no definido.
13.4.7 Comprobando que eventos inician en la ventana ......................... ¡Error! Marcador no definido.
13.4.8 Más operaciones con dibujos ....................................................... ¡Error! Marcador no definido.
13.4.9 Creando curvas en una ventana ................................................... ¡Error! Marcador no definido.
13.4.10 Creando un Bitmap .................................................................. ¡Error! Marcador no definido.
13.4.11 Creando una Toolbar ............................................................... ¡Error! Marcador no definido.
13.4.12 Creando una ventana .............................................................. ¡Error! Marcador no definido.
13.4.13 La Toolbar Expert ................................................................... ¡Error! Marcador no definido.
13.4.14 Dibujando con un Mouse Sweep ............................................ ¡Error! Marcador no definido.
13.4.15 El evento Mouse Down ............................................................ ¡Error! Marcador no definido.
13.4.16 El evento e_MouseUp ............................................................. ¡Error! Marcador no definido.
13.4.17 El evento e_Update ................................................................. ¡Error! Marcador no definido.
13.4.18 Manejando la Toolbar ............................................................. ¡Error! Marcador no definido.
13.4.19 Cleaning Up ............................................................................. ¡Error! Marcador no definido.
13.4.20 Cambiando el cursor del Mouse .............................................. ¡Error! Marcador no definido.
13.4.21 Ajustando el cursor .................................................................. ¡Error! Marcador no definido.
13.4.22 Creando un menu Pop-Up ....................................................... ¡Error! Marcador no definido.
13.4.23 Cambiando el color del dibujo.................................................. ¡Error! Marcador no definido.
13.4.24 Usando un Timer - El reloj de Window ................................... ¡Error! Marcador no definido.
13.4.25 Using Timers............................................................................ ¡Error! Marcador no definido.
13.4.26 The e_Size Event for the Clock Window .................................. ¡Error! Marcador no definido.
13.4.27 La ventana pintada ................................................................. ¡Error! Marcador no definido.
13.4.28 Creando una ventana Árbol ..................................................... ¡Error! Marcador no definido.
13.5 Primer Programa en Prolog ........................................................................ ¡Error! Marcador no definido.
13.6 El entorno VPI ............................................................................................. ¡Error! Marcador no definido.
13.7 El segundo programa VPI ........................................................................... ¡Error! Marcador no definido.
13.7.1 CREAR UNA APLICACIÓN DESDE CERO ................................. ¡Error! Marcador no definido.
13.7.2 Pestaña General ........................................................................... ¡Error! Marcador no definido.
13.7.3 Pestaña Target ............................................................................. ¡Error! Marcador no definido.
13.7.4 Pestaña VPI Options .................................................................... ¡Error! Marcador no definido.
13.7.5 Pestaña User Info ......................................................................... ¡Error! Marcador no definido.
13.7.6 Diseñar La Ventana Principal ....................................................... ¡Error! Marcador no definido.
13.7.7 Insertar Código En El Programa ................................................... ¡Error! Marcador no definido.
Editado y corregido por Eliécer Pineda Ballesteros Página 5
Programación Lógica Lenguaje Prolog y Visual Prolog
13.7.8 Ejecutar La Aplicación Y Eliminar Componentes Adicionales....... ¡Error! Marcador no definido.
13.7.9 Eliminación de menú emergente .................................................. ¡Error! Marcador no definido.
El tercer programa VPI ........................................................................................ ¡Error! Marcador no definido.
13.7.10 Crear Una Aplicación Desde Cero ........................................... ¡Error! Marcador no definido.
13.7.11 Diseñar La Ventana Principal .................................................. ¡Error! Marcador no definido.
13.7.12 Diseñar Ventanas De Tipo Dialog ............................................ ¡Error! Marcador no definido.
13.7.13 Insertar Código De Los Dialog Al Programa Principal ........... ¡Error! Marcador no definido.
13.7.14 Insertar Codigo En El Programa Principal ............................... ¡Error! Marcador no definido.
13.7.15 Ejecutar La Aplicación Y Eliminar Componentes Adicionales . ¡Error! Marcador no definido.
13.7.16 Eliminación de menú emergente ............................................. ¡Error! Marcador no definido.
Editado y corregido por Eliécer Pineda Ballesteros Página 6
Programación Lógica Lenguaje Prolog y Visual Prolog
CAPÍTULO 1
1 Lenguaje PROLOG: Conceptos
PROLOG constituye la primera realización práctica de un concepto de programación orientado más a
modelar la forma de entender un tipo de problemas que a la forma concreta de calcular las soluciones de
esos problemas. Esto quiere decir que se debe realizar un esfuerzo para modelar formalmente los
enunciados que definen los problemas en lugar de aportar los pasos concretos que resuelven dicho
problema. Por ejemplo, si se nos plantea el problema de resolver el factorial de un número, podemos
modelar el enunciado como: factorial(1)=1 y factorial(N)=N*factorial(N-1), en lugar de especificar de forma
imperativa los pasos individuales que resuelven el factorial a través de asignaciones y operaciones.
Por tanto, para entender la programación lógica, lo que necesitamos es adaptar nuestro lenguaje a un
lenguaje matemático más formal que nos permita expresar nuestros enunciados de manera que puedan ser
resueltos de modo general, automáticamente.
La máquina PROLOG, como se verá más adelante, no es más que un demostrador automático de
teoremas. Por tanto, nosotros debemos expresar nuestro problema en forma de premisas y teoremas para
que la máquina PROLOG pueda demostrarlos y, por tanto, aportarnos las soluciones que buscamos.
Evidentemente, para comprender las bases de la programación lógica es necesario tener unos
conocimientos mínimos de la lógica matemática que se aplica y se utiliza en estos casos. Por lo tanto, en el
anexo proporcionado al final de la documentación se describe brevemente el significado de "Cálculo
Proposicional", "Cálculo de Predicados" y "Método de Resolución".
2 Bases del lenguaje PROLOG.
Centrémonos ahora en comentar las diferencias existentes entre metodología declarativa e imperativa,
observando las ventajas e inconvenientes que supone usar este nuevo paradigma frente al método
tradicional imperativo al que estamos acostumbrados.
2.1 Metodología declarativa frente a metodología imperativa.
Como se ha comentado, la programación declarativa supone especificar formalmente los enunciados
utilizando la lógica de predicados de manera que la máquina PROLOG sea capaz de interpretar e inferir
soluciones a partir de esos enunciados. En un lenguaje imperativo, sin embargo, no sólo hemos de
preocuparnos de entender el significado del enunciado del problema sino que debemos escribir nosotros
Editado y corregido por Eliécer Pineda Ballesteros Página 7
Programación Lógica Lenguaje Prolog y Visual Prolog
mismos cada uno de los pasos e instrucciones que la máquina debe ejecutar para resolverlo. Esta es la
diferencia más notable entre ambas metodologías. Podemos especificar más las diferencias, pero al final,
todas se resumen en la que acabamos de enunciar:
Los lenguajes declarativos no se basan en la máquina Von Newman sino en modelos matemáticos.
Los lenguajes declarativos, en contra de lo que hacen los imperativos, intentan ser
referencialmente transparentes, es decir, la misma expresión siempre da los mismos resultados.
En un lenguaje declarativo el control lo lleva la máquina, sin embargo en un lenguaje imperativo el
control depende exclusivamente del programador.
Los lenguajes declarativos son independientes de la máquina, sin embargo los imperativos se basan
en el lenguaje máquina en el que se apoyan, teniendo como instrucción principal la asignación.
El concepto de variable en un lenguaje imperativo es un objeto cuyo valor puede cambiar en el
tiempo, en cambio, en los lenguajes declarativos las variables son objetos cuyo valor no se conoce,
y que, una vez que se le asocia un valor, conserva dicho valor hasta el final.
2.2 Ventajas e inconvenientes.
La principal ventaja de los lenguajes declarativos es que son independientes de la máquina y, como
se ha comentado, referencialmente transparentes.
Además la cantidad de código que debemos escribir es menor, aunque la representación formal de
estos problemas puede resultar, en ocasiones, poco evidente.
Podemos desentendernos del control. Aunque aquí existe una limitación: no podemos hacerlo
totalmente. Por ello, PROLOG nos proporciona formas, un tanto artificiales, de manejo de este
control.
Los datos pueden ser tanto de entrada como de salida y se pueden utilizar datos parcialmente
construidos, es decir, podemos empezar a ejecutar sin contar con todos los datos.
Es difícil representar la negación.
3 Definición de Hechos, Metas y Predicados en PROLOG
Para construir programas en Prolog es necesario convertir los conceptos expresados en lenguaje
natural en un lenguaje basado en la lógica de primer orden, con el fin de obtener las cláusulas de Horn tras
el proceso de conversión adecuado, ya que Prolog trabaja, precisamente, con este tipo de cláusulas.
Básicamente, nuestro trabajo va a consistir en especificar adecuadamente los enunciados y reglas básicas
Editado y corregido por Eliécer Pineda Ballesteros Página 8
Programación Lógica Lenguaje Prolog y Visual Prolog
para resolver un determinado problema de forma general. Después le plantearemos a Prolog el conjunto de
objetivos (problemas específicos para un problema general dado), que queremos que resuelva.
En definitiva, nuestros programas estarán formados por:
La base de conocimientos: Hechos + Reglas de Inferencia.
El conjunto de objetivos o metas.
Para comprender adecuadamente los conceptos expresados hasta ahora, veamos una serie de
definiciones básicas: predicado, hecho, regla de inferencia y meta.
Un predicado especifica la relación existente entre los argumentos del mismo. El número de
argumentos a los que se aplica dicho predicado se denomina aridad. Con un predicado podemos
representar algo que sucede en el mundo real (hecho), o una regla (regla de inferencia), que nos permite
deducir hechos que suceden en ese dominio mediante la aplicación de la misma. La sintaxis de Prolog para
especificar un predicado es la siguiente:
nombre_predicado(arg1, arg2, ... , argN). (En el caso de que el predicado represente un hecho).
nombre_p1[([arg1], [arg2],..., [argN])]:-otro_p1[([arg1], [arg2],..., [argN])],...,
otro_pN[([arg1], [arg2], ... , [argN])].
(En el caso de que el predicado represente una regla de inferencia).
Las reglas de inferencia se pueden definir como la especificación de una relación entre predicados y
argumentos que permiten plasmar el hecho de que si la parte derecha del predicado se cumple, se cumple
la parte izquierda. El eje lo proporciona el símbolo ":-" que representa para nosotros la implicación lógica
(en lógica ""). Las comas (","), representan el símbolo de conjunción (en lógica ""), y el punto y coma
(";"), representa el símbolo de disyunción (en lógica ""). En la Tabla 1 se representan estas
correspondencias.
Lógica de Primer Orden Prolog
:-
,
;
Tabla 1
Ejemplos:
Editado y corregido por Eliécer Pineda Ballesteros Página 9
Programación Lógica Lenguaje Prolog y Visual Prolog
Ejemplos de hechos:
madre(pepe, juan).
factorial(0,1).
Ejemplos de reglas de inferencia:
abuela(X,Y):-madre(X,Z), madre(Z,Y).
factorial(N, R):- N1 is N-1, factorial(N1, Y), R is N*Y.
Ejemplo de regla de inferencia utilizando la disyunción:
mcd(A,B,R):-A==B, R is A; A>B, Aux is A-B, mcd(Aux,B,R); A<B, Aux is B-A, mcd(A,Aux,R);
mcd(B,A,R).
Como se observa, las reglas de inferencia permiten llevar a cabo la deducción de metas. Para que las
reglas de inferencia sean aplicables, en general, deberá existir un conjunto de hechos sobre los que
apoyarse para que las demostraciones se puedan realizar. Las metas representan los problemas específicos,
basados en los problemas generales expresados en la base de conocimientos que deseamos que el
demostrador automático de teoremas resuelva. Si nos fijamos, para escribir programas en Prolog, siempre
debemos tener en cuenta que el demostrador resuelve las metas comenzando por los predicados situados
en la zona superior (de arriba a abajo), y para cada predicado el proceso de unificación se lleva a cabo de
izquierda a derecha, ver Figura 1.
Figura 1, Esquema del flujo de ejecución de un programa Prolog
Una vez que hemos comprobado el funcionamiento general del demostrador, pasemos a estudiar
como llevar a cabo la correcta especificación de las bases de conocimientos.
Editado y corregido por Eliécer Pineda Ballesteros Página 10
Programación Lógica Lenguaje Prolog y Visual Prolog
3.1 Construcción de Bases de Conocimientos en PROLOG
En el campo de la Inteligencia Artificial es muy habitual implantar agentes que se pueden considerar
como entidades que poseen un conocimiento de su mundo capaces de razonar sobre las posibles acciones
que pueden emprender. Este tipo de agentes adoptan tareas nuevas en forma de metas perfectamente
definidas. Pueden inferir y razonar conocimientos en función de los hechos que conocen de su mundo y de
las reglas de inferencia que permiten deducir propiedades de éste que no resultan completamente
evidentes [Russel, 1996]. La construcción de agentes o programas que desempeñan labores de este tipo se
puede realizar mediante el uso de lenguajes lógicos adaptados a la resolución de esta clase de cuestiones.
Como hemos visto, la forma de llevar a cabo la implantación de un agente consiste en estudiar el mundo o
ámbito donde va a tener que trabajar y definir ese dominio mediante una sintaxis adecuada al lenguaje
utilizado. El componente medular de un agente basado en el conocimiento es su base de conocimientos,
junto con el mecanismo de inferencia que se utilice para realizar las deducciones. Para nosotros, el
mecanismo o motor de inferencia que vamos a usar va a ser la máquina Prolog.
La construcción, por tanto, de la base de conocimientos es el punto crucial que nos debe ocupar en
este curso, por ello, en este punto y en los siguientes, comentaremos las reglas básicas que se deben tener
en cuenta para implementar adecuadamente nuestro conocimiento acerca de los problemas que queremos
resolver y veremos cómo plantear las metas al demostrador de teoremas (motor de inferencia), de Prolog.
La máquina virtual Prolog toma como entrada nuestra base de conocimientos expresada en forma
clausal, nuestro objetivo, también expresado en forma clausal, y genera una respuesta afirmativa en caso de
que el objetivo se pueda demostrar aplicando el conocimiento almacenado en la base. La Figura 2 muestra
un esquema gráfico de lo que acabamos de comentar.
Figura 2, Esquema del funcionamiento de la máquina Prolog.
Resolver un problema, por tanto, es construir adecuadamente la base de conocimientos, y esta base
expresada en lenguaje Prolog junto con el conjunto de metas especificadas constituirán nuestro programa.
Editado y corregido por Eliécer Pineda Ballesteros Página 11
Programación Lógica Lenguaje Prolog y Visual Prolog
Los programas que se pueden resolver utilizando esta metodología son muchos y muy variados. Desde
la manipulación de bases de datos hasta la construcción de sistemas expertos, sin olvidar la compresión del
lenguaje natural, resolución de juegos, diseño de compiladores, etc.
Un programa Prolog probablemente utilizará predicados recursivos, es decir, nuestro problema se
expresa en términos de sí mismo aplicado sobre un conjunto de datos distintos que tiende a convertirse en
el conjunto de datos que satisface el caso o casos triviales del proceso de recursión. Por ejemplo, en el caso
del problema del factorial, vamos calculando sucesivamente el factorial de un número decrementado del
nivel anterior. Este número se aproxima cada vez más a 0, que es justamente el caso trivial de este proceso
recursivo. Una vez que se alcanza este caso, las llamadas recursivas retornan los datos de salida y se
produce lo que todos conocemos como vuelta atrás.
Cuando sea necesario construir un programa usando técnicas recursivas en Prolog, hemos de recordar
que los objetivos intentarán satisfacerse mediante una búsqueda que comienza por los predicados situados
en la zona superior, y para cada uno de ellos el proceso de unificación se realizará de izquierda a derecha.
Evidentemente, para conseguir un funcionamiento adecuado en el procedimiento de resolución hemos de
construir la base de conocimientos adecuadamente, situando primero los casos triviales o específicos y a
continuación los casos más generales.
Ejemplo:
factorial(0,1).
factorial(N, R):- N1 is N-1, factorial(N1, Y), R is N*Y.
Igualmente, si ciertas realidades del mundo que se desea representar, se pueden expresar mediante
una regla de inferencia en lugar de hacerlo con un conjunto de hechos, elegiremos la primera opción, de
modo que en nuestra base de conocimientos, tendremos solamente los hechos que son necesarios para
deducir otros que se pueden razonar a través de reglas. Por ejemplo, si deseamos construir parte de
nuestro árbol genealógico y establecemos como dominio en el que vamos a trabajar el de las madres y
abuelas, solamente será necesario definir el predicado madre para representar hechos del tipo "Ana es
madre de Pepa", "Pepa es madre de Luisa", etc. Sin embargo el predicado abuela no se implementará como
un hecho, aunque podría hacerse, sino como una regla de inferencia ya que ese suceso ocurrido en el
mundo que estamos representando se puede deducir en función del hecho "ser madre".
Editado y corregido por Eliécer Pineda Ballesteros Página 12
Programación Lógica Lenguaje Prolog y Visual Prolog
Ejemplo:
A continuación proponemos un ejemplo de cómo debe modificarse una base de conocimientos incorrectamente implementada.
madre(pepa, juana).
madre(juana, ana).
madre(ana, beatriz).
abuela(pepa, ana).
abuela(juana, beatriz).
La base de conocimientos está mal construida porque su actualización es más complicada y, por tanto, también su manejo.
La forma correcta de realizar ese programa sería del modo que se propone:
madre(pepa, juana).
madre(juana, ana).
madre(ana, beatriz).
abuela(X,Y):-madre(X,Z), madre(Z,Y).
Como se observa la cantidad de código se reduce ya que para establecer nuevos hechos del mundo real: "ser madre" o "ser abuela" basta con introducir nuevos predicados del tipo madre ya que el hecho de "ser abuela" se deduce en función de la regla de inferencia especificada con el predicado abuela.
3.2 Consultas sobre la Base de Conocimientos
Evidentemente, las bases de conocimientos se construyen con el fin de que preguntemos al agente
sobre nuevos hechos del mundo deducidos de dicha base. El agente debe poseer un motor de inferencia
para llevar a cabo el proceso de deducción de forma automática. Para nosotros, Prolog va a constituir
nuestro "motor de inferencia". Por tanto, nos queda saber como hemos de plantear los objetivos y como
funciona la inferencia en Prolog (máquina virtual Prolog).
En este apartado vamos a centrarnos en estudiar las respuestas proporcionadas por Prolog a los
objetivos que le podemos plantear.
El objetivo se plantea como un predicado nuevo basado en el conocimiento que tenemos. La máquina
virtual o intérprete intentará unificar dicho predicado con los existentes en la base de conocimientos. Si
puede unificarlo con alguno, nos dará una respuesta afirmativa. En caso contrario, proporcionará una
respuesta negativa.
Prolog comienza a buscar de arriba a abajo en la secuencia de predicados y para cada predicado de
izquierda a derecha. Pues bien, vamos a examinar ahora el método de ejecución para cada caso, es decir, si
Editado y corregido por Eliécer Pineda Ballesteros Página 13
Programación Lógica Lenguaje Prolog y Visual Prolog
el predicado es un hecho, una regla de inferencia, etc. Además, será necesario concretar como se realiza el
proceso de recursión y backtracking a través de algunos ejemplos sencillos.
Cuando en la base de conocimientos sólo hay hechos
En este caso sólo tenemos un conjunto de predicados que expresan los hechos o afirmaciones que se
producen en el mundo real.
La forma de proceder de la máquina Prolog, será por tanto, el intento de unificación con alguno de
ellos.
predicado1(arg1, ..., argN).
predicado2(arg1, ..., argN).
...
predicadoM(arg1, ..., argN).
Supongamos que nuestro objetivo es:
predicado2(arg1, ..., argN).
El árbol de búsqueda generado sería el que se muestra en la Figura 3.
Cuando en la base de conocimientos hay hechos y reglas de inferencia no recursivas
Las reglas de inferencia permiten relacionar hechos o situaciones del mundo real para deducir otros
hechos que, en principio, no son evidentes sin la utilización de dicha reglas.
predicado2(arg1, ... ,argN).
OBJETIVO
predicado1(arg1, ... ,argN). predicado2(arg1, ... ,argN). predicadoM(arg1, ... ,argN).
FAIL ÉXITO EN LAUNIFICACIÓN
SALIDA = YES
Figura 3, Árbol de búsqueda para satisfacer un predicado en una base de hechos
Editado y corregido por Eliécer Pineda Ballesteros Página 14
Programación Lógica Lenguaje Prolog y Visual Prolog
Cuando en Prolog tenemos una sentencia de la forma “predicado(argumentos):-
predicado2(argumentos).”, la máquina intenta unificar la parte izquierda de la regla mediante la
demostración de la parte derecha. Dicha parte derecha se convierte en un subobjetivo a resolver. Las
entradas y salidas se proporcionan a través de los argumentos, y se pueden utilizar variables locales o
auxiliares para realizar cálculos que sólo afectan a esa parte derecha. De esta forma, en cada nivel de
llamadas dichas variables locales funcionan del mismo modo que en cualquier lenguaje imperativo, ya que
se consideran direcciones independientes unas de otras que sólo sobreviven en su nivel de llamada.
Supongamos una base de conocimientos como la siguiente:
pred1(arg1).
pred2(arg2).
pred3(arg1, arg2, arg3):- pred1(arg1), aux is “operación sobre arg1”, pred2(aux), arg3 is
“operación entre arg1 y aux”.
Para satisfacer el objetivo “pred3(arg1, arg2, arg3).” se genera el árbol de búsqueda de la Figura 4.
pred3(arg1, arg2, arg3).
OBJETIVO
pred1(arg1). pred2(arg2). pred3 (arg1, arg2, arg3)
FAIL FAIL
SALIDA = YES
pred1(arg1). pred2(aux).Operaciónsobre aux
Operaciónsobre arg3
ÉXITO ÉXITO ÉXITO ÉXITO
AND
Figura 4, Árbol de búsqueda para satisfacer un objetivo en función de una sencilla regla de inferencia
Cuando en la base de conocimientos hay hechos y reglas de inferencia recursivas
Para estudiar este caso, vamos a utilizar el ejemplo del cálculo del máximo común divisor. Hemos de
apuntar, que el proceso se realizará de la misma forma que en el caso anterior. Lo único que hay que tener
en cuenta es que es necesario controlar el orden en que se colocan los predicados para evitar una ejecución
no deseada, ya que toda solución recursiva debe evolucionar hacia el caso trivial.
Editado y corregido por Eliécer Pineda Ballesteros Página 15
Programación Lógica Lenguaje Prolog y Visual Prolog
En cada nivel de recursión, las variables locales son independientes y se localizan en direcciones de
memoria distintas.
mcd(A,B,R):-A==B, R is A.
mcd(A,B,R):-A>B, Aux is A-B, mcd(Aux,B,R).
mcd(A,B,R):-A<B, Aux is B-A, mcd(A,Aux,R).
mcd(A,Aux,R):-mcd(B,A,R).
El árbol de búsqueda generado para encontrar la solución “mcd(7, 5, R).” se muestra en la Figura 5.
mcd(7,5,R)
OBJETIVO
Predicado1 Predicado2
SALIDA = YESR = 1
7=5
FAIL
7>5
ÉXITO
Aux is 2
ÉXITO
mcd(2, 5, R)
Predicado1 Predicado2
2=5
FAIL
2>5
FAIL
Predicado3
2<5
ÉXITO
Aux is 3
ÉXITO
mcd(2, 3, R)2º Nivel de
Recursión
Figura 5, Árbol parcial de búsqueda para resolver un caso del problema del máximo común divisor de dos números
3.3 Ejemplos
En el punto anterior, hemos observado como funciona la máquina Prolog a la hora de resolver
objetivos planteados sobre distintos tipos de bases de conocimientos. Es conveniente ilustrar todos los
conocimientos adquiridos hasta ahora observando como se resuelven distintos problemas mediante un
lenguaje lógico. Por ello, veamos un resumen de algunos ejemplos comentados hasta ahora.
Cálculo del factorial.
Editado y corregido por Eliécer Pineda Ballesteros Página 16
Programación Lógica Lenguaje Prolog y Visual Prolog
factorial(0,1).
factorial(N, R):- N1 is N-1, factorial(N1, Y), R is N*Y.
Cálculo del máximo común divisor.
mcd(A,B,R):-A==B, R is A.
mcd(A,B,R):-A>B, Aux is A-B, mcd(Aux,B,R).
mcd(A,B,R):-A<B, Aux is B-A, mcd(A,Aux,R).
mcd(A,Aux,R):-mcd(B,A,R).
Cálculo del máximo común divisor usando disyunciones.
mcd(A,B,R):-A==B, R is A; A>B, Aux is A-B, mcd(Aux,B,R); A<B, Aux is B-A, mcd(A,Aux,R);
mcd(B,A,R).
Árbol genealógico.
madre(pepa, juana).
madre(juana, ana).
madre(ana, beatriz).
abuela(X,Y):-madre(X,Z), madre(Z,Y).
Editado y corregido por Eliécer Pineda Ballesteros Página 17
Programación Lógica Lenguaje Prolog y Visual Prolog
Tras la exposición de estos pequeños ejemplos, pasemos a realizar un programa un poco más grande.
Vamos a construir una base de conocimientos que nos permita resolver objetivos o preguntas relacionadas
con el código de la circulación de vehículos.
La aplicación va a permitir especificar un tipo de vehículo y las características de la vía por la que circula
y nos informará sobre la velocidad máxima genérica que dicho vehículo puede alcanzar. Hablaremos
exclusivamente de velocidad genérica de vía y vehículos.
A continuación, en la Tabla 2, se muestran los tipos de vía que existen tanto fuera como dentro de
poblado.
Características de la vía Nombre de la vía
Vía interurbana señalizada con la señal S-1 (Figura 6) Autopista
Vía interurbana señalizada con la señal S-1a (Figura 7) Autovía
Vía interurbana señalizada con la señal S-1b (Figura 8) Vía Rápida
Vía interurbana con dos o más carriles para cada sentido ó carril para facilitar el adelantamiento ó arcén pavimentado de, al menos, 1,5 metros de longitud
Carretera Convencional Buena
Vía interurbana que no cumple los requisitos de una carretera convencional buena.
Carretera Convencional Mala
Vía urbana Vía Urbana
Vía interurbana que discurre por suelo urbano Travesía
Tabla 2
Figura 6 Señal S-1
AUTOVÍA
Figura 7 Señal S-1a
VÍA RÁPIDA
Figura 8 Señal S-1b
En la Tabla 3, se expresan las relaciones de velocidad según la vía y el vehículo que se conduce.
Editado y corregido por Eliécer Pineda Ballesteros Página 18
Programación Lógica Lenguaje Prolog y Visual Prolog
Vía
Vehículo
Autopistas y Autovías Vías Rápidas y Carreteras
Convencionales Buenas
Carreteras Convencionales Malas
Vías Urbanas y Travesías
Turismos y Motocicletas
120 100 90 50
Autobuses y Vehículos Mixtos
100 90 80 50
Camiones y Vehículos Articulados
90 80 70 50
Automóviles con Remolque
80 80 70 50
Noveles 80 80 80 50
Tabla 3
Una vez que tenemos todos los datos, sólo nos queda expresar los acontecimientos de la realidad de
forma sintácticamente correcta.
Los hechos y reglas de inferencia para resolver este problema se muestran a continuación.
Experto de Autoescuela
predicates
maximo(string, string, integer)
via(integer, integer, string, string)
velocidad(string, integer, integer, string, integer)
nondeterm repeat
nondeterm pedirdatos
clauses
/* Definición de las velocidades genéricas de vehículos según la vía */
maximo("novel", "autopista", 80):-!.
maximo("novel", "autovia", 80):-!.
maximo("novel", "via_rapida", 80):-!.
maximo("novel", "ccb", 80):-!.
maximo("novel", "ccm", 80):-!.
maximo("turismo", "autopista", 120):-!.
maximo("motocicleta", "autopista", 120):-!.
maximo("vehiculomixto", "autopista", 100):-!.
maximo("autobus", "autopista", 100):-!.
maximo("camion", "autopista", 90):-!.
maximo("vehiculoarticulado", "autopista", 90):-!.
maximo("conjuntovehiculos", "autopista", 80):-!.
maximo(Veh, "autovia", R):-maximo(Veh, "autopista", R), !.
maximo("turismo", "ccb", 100):-!.
maximo("motocicleta", "ccb", 100):-!.
Editado y corregido por Eliécer Pineda Ballesteros Página 19
Programación Lógica Lenguaje Prolog y Visual Prolog
maximo("vehiculomixto", "ccb", 90):-!.
maximo("autobus", "ccb", 90):-!.
maximo("camion", "ccb", 80):-!.
maximo("vehiculoarticulado", "ccb", 80):-!.
maximo("conjuntovehiculos", "ccb", 80):-!.
maximo(Veh, "via_rapida", R):-maximo(Veh, "ccb", R),!.
maximo(Veh, "ccm", R):-maximo(Veh, "ccb", Auxi), R=Auxi-10, !.
maximo(Veh, "via_urbana", _):-
Veh<>"turismo",
Veh<>"motocicleta",
Veh<>"vehiculomixto",
Veh<>"autobus",
Veh<>"camion",
Veh<>"vehiculoarticulado",
Veh<>"conjuntovehiculos",
Veh<>"novel",
fail, !.
maximo(_, "via_urbana", 50):-!.
maximo(Veh, "travesia", R):-maximo(Veh, "via_urbana", R).
/* Definición de vía en función de sus características */
via(_, _, "autopista", "autopista"):-!.
via(_, _, Senal, Tipo):-Senal="autovia", Tipo="autovia", !.
via(_, _, Senal, Tipo):-Senal="viarapida", Tipo="via_rapida", !.
via(_, _, Senal, Tipo):-Senal="de_via_urbana", Tipo="via_urbana", !.
via(_, _, Senal, Tipo):-Senal="de_travesia", Tipo="travesia", !.
via(Arcen, _, "nohay", "ccb"):-Arcen >=150, !.
via(_, Carriles, "nohay", "ccb"):-Carriles>=2, !.
via(_, -1, "nohay", "ccb"):-!.
via(_, _, "nohay", "ccm").
/* Predicado de cálculo de velocidad en función del vehículo y las características
de la vía */
velocidad(Vehiculo, A, C, S , V):-via(A, C, S, Carretera),
maximo(Vehiculo, Carretera, V).
repeat.
repeat:-repeat.
pedirdatos:-repeat,
write("PETICIÓN DE DATOS (nohay=no hay dato concreto)"), nl, nl, nl,
write("Especifica el tipo de vehículo, (turismo, motocicleta,
vehiculomixto, autobus, camion)"), nl,
write("(vehiculoarticulado, conjuntovehiculos, novel): "),
readln(V),
nl,
write("Especifica el tamaño del arcen: "), readint(A),
nl,
write("Especifica el número de carriles (-1 para adelantamiento): "), readint(C),
nl,
write("Especifica señal (autopista, autovia, via_rapida): "), readln(S),
velocidad(V, A, C, S , Velocidad), nl,
write("La velocidad máxima es: "), write(Velocidad), nl,
write("Continuar=Cualquier tecla, Salir=1"), nl,
readint(Tecla), nl, nl, nl,
Tecla=1.
goal
pedirdatos.
Editado y corregido por Eliécer Pineda Ballesteros Página 20
Programación Lógica Lenguaje Prolog y Visual Prolog
4 Definición y funcionamiento de la Máquina PROLOG
Hasta ahora, conocemos como se pueden modelar problemas reales utilizando la metodología
declarativa lógica. Pero además, es necesario, definir formalmente qué es la máquina o intérprete Prolog.
En este apartado nos centraremos en la definición y muestra del funcionamiento interno de este intérprete,
examinando como se realiza el proceso de resolución, a través del método de unificación, y como se llevan a
cabo las tareas de recursión y backtracking.
Un intérprete Prolog es un demostrador de teoremas sobre Cláusulas de Horn que trabaja Top-Down, y
que emplea Resolución Lineal con Función de Selección. La entrada al intérprete es un conjunto de cláusulas
definidas C, junto con la especificación de la meta G0, como ya se vio en apartados anteriores. El proceso
del intérprete consiste en una búsqueda incremental por backtracking en el espacio (organización en forma
de árbol), de refutaciones posibles a G0 [Adarraga, 1994].
4.1 Unificación
La unificación se realiza, para cada predicado, de izquierda a derecha, y para cada conjunto de
predicados, de arriba a abajo. Se pueden unificar variables con constantes, siempre que la variable no esté
instanciada. Si la variable está instanciada, el hecho de hacer unificación entre ambas se corresponde con la
situación de unificación de dos constantes. Para que dos constantes se puedan unificar ambas han de ser
iguales.
Veamos en la Tabla 4 algunos casos que muestran el funcionamiento de la unificación.
Variable no instanciada se intenta unificar con cualquier átomo ÉXITO
X=5
Variable instanciada se intenta unificar con cualquier átomo distinto al valor que contiene
FAIL X que contiene 5, X=6
Constante se intenta unificar con otra constante distinta FAIL 5=6
Expresiones se intentan comparar mediante símbolos de comparación que no "evalúan" y no coinciden totalmente, incluido el orden
FAIL 5+3=3+5
Variable se intenta instanciar dos veces en la misma ejecución del programa. En el segundo intento de instanciación
FAIL X=6, X=7
Tabla 4
Vemos que las instanciación es un caso de unificación en la que a una variable no instanciada se le
asigna un valor.
Editado y corregido por Eliécer Pineda Ballesteros Página 21
Programación Lógica Lenguaje Prolog y Visual Prolog
También podemos observar que no es necesario definir los tipos de las variables locales usadas dentro
de cada regla de inferencia. Cuando las variables se instancian a un valor, entonces todas las operaciones
que se realicen con dicho valor deberán tener en cuenta el tipo especificado. Por ejemplo, si una variable se
instancia al valor 5, todas las comparaciones posteriores se harán con números y no con átomos del tipo
pepe, blas ó similar.
El proceso de unificación intenta casar un predicado con otro para comprobar si son absolutamente
iguales, cuando es posible hacer sustituciones, éstas se realizan de manera que los predicados que se están
unificando se tornen completamente iguales y proporcionen un resultado de ÉXITO.
4.2 Backtracking
Ya se ha comentado en puntos anteriores: Prolog utiliza un sistema de backtracking para resolver una
meta propuesta. El procedimiento de backtracking consiste en generar un árbol de búsqueda de todas las
posibles resoluciones que puede tener la meta en función de la base de conocimientos. Esto significa, que el
algoritmo itera hasta que encuentra una solución. Cada vez que los predicados fallan y no son unificables se
va generando una nueva rama hasta encontrar la solución deseada, de esta forma se va construyendo el
árbol de búsqueda.
Puede ser que un problema se pueda resolver de varias formas. Es, por tanto, posible especificar que
deseamos una nueva solución. El intérprete Prolog ignora la solución encontrada hasta ahora y construye el
árbol de búsqueda hasta generar una nueva solución o encontrar que ésta no existe.
Cuando un predicado se demuestra en función de una llamada a sí mismo, la llamada se convierte en
un subobjetivo casi idéntico al objetivo a cumplir, salvo por el conjunto de datos sobre el que se aplica.
Cuando se consigue la demostración de los subobjetivos generados en el proceso de recursión, se produce
lo que se denomina vuelta atrás de la recursión, que funciona igual que en cualquier lenguaje.
No hemos de confundir recursividad con backtracking. Los predicados recursivos los diseñamos
nosotros mientras que el procedimiento de backtracking es intrínseco al método de refutación que se usa
para demostrar las metas.
Para comprender mejor lo expuesto hasta ahora, vamos a examinar un par de ejemplos de uso forzado
de backtracking para obtener nuevas soluciones y de uso de predicados recursivos.
Uso forzado de backtracking
Editado y corregido por Eliécer Pineda Ballesteros Página 22
Programación Lógica Lenguaje Prolog y Visual Prolog
La traza del programa siguiente se muestra en la Figura 9.
hermano(juan, beatriz).
hermano(pepe, beatriz).
Objetivos planteados
?.-hermano(X, beatriz).
X->juan;
X->pepe;
no.
hermano(X, beatriz).
hermano(pepe, beatriz)
ÉXITO
X=pepe
hermano(juan, beatriz)
ÉXITO
X=juan
1ª SOLUCIÓN 2ª SOLUCIÓN
Figura 9, Árbol de búsqueda generado para la solución del predicado "hermano(X, beatriz)"
Uso de predicados recursivos
La traza del programa siguiente se muestra en la Figura 10.
numero(0):-write(0).
numero(N):-N1 is N-1, numero(N1), write(N).
Objetivo planteado.
?.-numero(2).
210
yes.
Editado y corregido por Eliécer Pineda Ballesteros Página 23
Programación Lógica Lenguaje Prolog y Visual Prolog
numero(2).
numero(0):-write(0).
FAIL
Predicado Siguiente
N1 is N-1
ÉXITO
write(2)
ÉXITO
numero(1)
Predicado Siguiente
N1 is N-1
ÉXITO
write(1)
ÉXITO
numero(0)
numero(0):-write(0).
ÉXITO
numero(0):-write(0).
FAIL
Figura 10, Árbol de búsqueda generado para la solución del predicado "numero(2)"
Editado y corregido por Eliécer Pineda Ballesteros Página 24
Programación Lógica Lenguaje Prolog y Visual Prolog
CAPITULO 2
Aritmética, datos y estructuras en Visual Prolog
5 Sintaxis Básica de VISUAL PROLOG
Hemos visto ya un buen número de convenciones que debemos utilizar para escribir programas en
Prolog. La última parte de este tema la dedicaremos a conocer detalladamente las reglas sintácticas que
hemos de seguir para que nuestras bases de conocimientos sean reconocidas por Visual Prolog.
Como ya hemos estudiado, un programa Prolog no es más que la especificación de una base de
conocimientos lógica con las características siguientes:
Consta de una secuencia de oraciones, todas ellas verdaderas, que expresan un conjunto de realidades
sobre los objetos del mundo representado, así como sobre sus relaciones. Todas las variables tienen
cuantificación universal implícita y cuando las variables aparecen en oraciones distintas se consideran
también distintas.
Se aceptan únicamente oraciones en forma de Cláusula de Horn, es decir, las oraciones son atómicas, o
bien una implicación con un antecedente no negado y un consecuente generalmente “expresiones”
separados por comas o por puntos y comas. Las comas significan conjunción y los puntos y comas
significan disyunción.
En vez de utilizar antecedentes negados en sus implicaciones, en Prolog se emplea un operador de
negación basado en el fallo: una meta no P se considera demostrada si el sistema no logra demostrar P.
5.1 Aritmética de VISUAL PROLOG
Las expresiones aritméticas en Visual Prolog se componen de operandos (números y variables),
operadores (+, -, *, /, div, y mod) y paréntesis: A = 1 + 6 / (11 + 3) * Z. Ver Tabla 5.
Los números "0x" o "0o" significan hexadecimal y octal respectivamente: 0xFFF = 4095; 86 = 0o112 +
12.
Editado y corregido por Eliécer Pineda Ballesteros Página 25
Programación Lógica Lenguaje Prolog y Visual Prolog
El valor de una expresión se puede calcular si todas las variables están unificadas en el momento de la
evaluación. El cálculo ocurre entonces en un orden determinado por la prioridad de los operadores
aritméticos. Los operadores de mayor prioridad son evaluados primero. Ver Tabla 6.
Operaciones
Operando 1 Operador Operando 2 Resultado
entero +, -, * Entero entero
real +, -, * Entero real
entero +, -, * Real real
real +, -, * Real real
entero ó real / entero ó real real
entero div Entero entero
entero mod Entero entero
Tabla 5
Orden de evaluación
Si la expresión contiene subexpresiones entre paréntesis, las subexpresiones se evalúan primero.
Si la expresión contiene multiplicación o división, estas operaciones son realizadas trabajando de
izquierda a derecha a través de la expresión.
Las operaciones de suma y resta son llevadas a cabo de izquierda a derecha también.
En el orden de evaluación se tiene en cuenta, lógicamente, la precedencia de los operadores.
Operador Prioridad
+ - 1
* / mod div 2
- + (unario 3
Tabla 6
Funciones y predicados
Visual Prolog posee una gran cantidad de funciones y predicados matemáticos para realizar las más
variadas operaciones. La lista completa se ofrece en la Tabla 7.
Nombre Descripción
X mod Y Resto de X dividido entre Y.
X div Y Cociente de X dividido entre Y.
abs(X) Valor absoluto de X.
cos(X) Coseno de X.
sin(X) Seno de X.
Editado y corregido por Eliécer Pineda Ballesteros Página 26
Programación Lógica Lenguaje Prolog y Visual Prolog
tan(X) Tangente de X.
arctan(X) Arcotangente de X.
exp(X) e elevado al valor almacenado en X. (Exponencial).
ln(X) Logaritmo neperiano de X.
log(X) Logaritmo en base 10 de X.
sqrt(X) Raíz cuadrada de X.
random(X) Almacena en X un número aleatorio real entre 0 y 1.
random(X, Y) Almacena en Y un número aleatorio en el intervalo 0 <= Y < X.
round(X) Valor redondeado de X. El resultado es un número real.
trunc(X) Valor truncado de X. El resultado es un número real.
val(domain,X) Conversión explícita entre dominios numéricos.
Tabla 7
Comparaciones
En Visual Prolog podemos comparar expresiones aritméticas, caracteres, cadenas de caracteres y
símbolos.
Las comparaciones de este tipo se realizan a través de operadores relacionales. Ver Tabla 8.
Símbolo Relación
< menor que
<= menor o igual que
= igual que
> mayor que
>= mayor o igual que
<> o >< Distinto
Tabla 8, Comparación de caracteres, cadenas de caracteres y símbolos
Además de las expresiones numéricas, podemos comparar caracteres, cadenas y símbolos: 'a' < 'b';
"antony" > "antonia" y P1 = peter, P2 = sally, P1 > P2.
- Caracteres: Visual Prolog convierta la comparación 'a' < 'b' a su expresión aritmética
correspondiente 97 < 98, usando el código ASCII correspondiente a cada carácter.
- Cadenas de caracteres: Cuando se comparan dos cadenas o símbolos, la comparación se realiza
carácter a carácter en sus correspondientes posiciones. El resultado es el mismo que se consigue
Editado y corregido por Eliécer Pineda Ballesteros Página 27
Programación Lógica Lenguaje Prolog y Visual Prolog
comparando el carácter inicial a menos que los dos sean iguales en cuyo caso se pasa al siguiente.
Cuando se encuentran dos caracteres iguales, el proceso de comparación termina y se produce el
resultado.
- Símbolos: No pueden ser comparados directamente debido a la sintaxis. Primero deben ser
unificados a variables o escritos como cadenas de caracteres.
6 Datos simples y Estructuras de Datos: DOMINIOS
En cualquier lenguaje de programación necesitamos representar datos complejos. Podemos definir
dato complejo como la agrupación homogénea o heterogénea de otros datos que a su vez pueden ser
también complejos o simples. Así pues, a partir de esta definición, los datos se pueden organizar de
múltiples formas que ya conocemos: vectores, registros, listas, árboles, grafos, etc.
Un programa en Visual Prolog utiliza distintas secciones para las declaraciones de tipos o dominios con
el fin de crear estructuras complejas de datos (DOMAINS), predicados (PREDICATES), reglas y hechos que
forman los predicados (CLAUSES) y metas (GOAL).
En la sección de predicados se definen las cabeceras de los predicados que vamos a utilizar en nuestros
programas, es decir el nombre del predicado y el dominio o tipo de los argumentos del mismo.
En la sección de cláusulas se define la implementación de cada predicado declarado en PREDICATES.
En la sección GOAL se establece la meta principal del programa.
Centrémonos ahora en la sección DOMAINS y en cómo crear estructuras complejas: objetos
compuestos, árboles, listas y matrices.
6.1 OBJETOS COMPUESTOS
Los objetos compuestos están formados por un functor y un conjunto de argumentos. Por ejemplo,
cuadro(NS, Autor, Estilo, Dimensiones) representa una estructura que almacena los datos más relevantes
para describir este tipo de obra de arte. El nombre cuadro es el functor y los elementos entre paréntesis son
los argumentos del objeto compuesto. Los argumentos (campos), de un objeto compuesto pueden ser datos
simples o datos complejos.
Editado y corregido por Eliécer Pineda Ballesteros Página 28
Programación Lógica Lenguaje Prolog y Visual Prolog
Para definir objetos compuestos es necesario introducirnos en el concepto de DOMINIO o DOMAINS.
Como veremos en la sección de prácticas, la sección DOMAINS de un programa en Visual Prolog agrupa los
dominios (tipos), no estándares en el sistema.
Definir un dominio no es más que establecer qué forma tendrán los objetos que pertenecen a dicho
dominio o tipo, por ejemplo, para el caso del cuadro, el dominio sería así:
un_cuadro= cuadro(INTEGER, STRING, STRING, STRING)
Como hemos dicho, los argumentos de un objeto compuesto pueden ser complejos:
un_comprador= comprador(STRING, un_cuadro)
El dominio o tipo del ejemplo define a un comprador de un cuadro. Los objetos compuestos de este
tipo almacenan una cadena que puede representar el DNI y el cuadro que posee.
Veamos varios objetos de tipo un_comprador:
comprador("111111111", cuadro(1239, "Martín Jiménez", "óleo", "39x23")).
comprador("122111111", cuadro(1449, "Suárez Jiménez", "acuarela", "130x50")).
comprador("111133331", cuadro(2232, "Martín Pérez", "carboncillo", "100x100")).
6.2 ÁRBOLES
Un árbol es una estructura con una definición puramente recursiva, ya que se puede considerar como
el elemento raíz cuyos hijos son, a su vez, árboles. Si el árbol tiene únicamente dos hijos se denomina árbol
binario. Este modelo específico de árbol se utiliza mucho para resolver gran cantidad de problemas en
aspectos de programación.
Un árbol se puede considerar, a su vez, un caso particular de grafo, donde todos los caminos son
acíclicos.
La Figura 11 muestra un ejemplo de árbol.
Nivel 0
Nivel 2
Nivel 1
Hoja
Raíz
Figura 11, Ejemplo de árbol
Editado y corregido por Eliécer Pineda Ballesteros Página 29
Programación Lógica Lenguaje Prolog y Visual Prolog
Muchos problemas de Inteligencia Artificial donde interviene el concepto de búsqueda se resuelven
mediante la implementación de árboles. Los árboles de juego o los utilizados en la resolución de problemas
relacionados con el procesamiento de lenguaje natural son casos muy concretos y descriptivos. Por lo tanto,
podemos notar que el manejo eficiente de estas estructuras es sumamente importante para conseguir
programas de calidad en este ámbito de la Ciencia.
Ya vimos que Prolog es un lenguaje que se adapta adecuadamente a este tipo de problemas. De hecho
la técnica de resolución que utiliza Prolog se basa en la construcción de un árbol de búsqueda de soluciones,
luego podemos concluir que el conocimiento de esta estructura es clave para este tipo de metodología
declarativa.
Como en cualquier lenguaje, lo que necesitamos saber es la forma de declarar el árbol, ya que su
implementación se puede realizar de muchas formas, por ejemplo, aunque una lista es un caso particular de
árbol, un árbol se puede representar a través de listas, aunque en el caso de Visual Prolog, estudiaremos la
construcción de árboles utilizando objetos compuestos recursivos.
Dado que un árbol está formado por la raíz y un conjunto de hijos, podemos representarlo utilizando la
siguiente notación:
oración (sujeto (artículo (el), sustantivo (hombre)), predicado (verbo (come), CD (pan)))
El árbol generado se muestra en la Figura 12.
Nivel 0
Nivel 2
Nivel 1
El
ORACIÓN
SUJETO PREDICADO
hombre come pan
ARTÍCULO SUSTANTIVO VERBO CD
Figura 12, Árbol de análisis de una frase en español
Como se observa, el uso de un predicado con dos argumentos en el caso de árbol binario o N
argumentos en el caso de árbol N-ario es una forma sencilla de representar un árbol.
Mediante objetos compuestos recursivos del tipo arbol(nodo, hijoizq, hijoder), donde hijoizq e hijoder
son también árboles, podemos representar un árbol binario. El árbol vacío se representa a través del hecho
vacio:
arbol(1,arbol(2,arbol(4,vacio,vacio),arbol(5,vacio,vacio)),arbol(3,vacio,vacio))
En la sección DOMAINS podemos crear un tipo árbol de enteros del modo siguiente:
Editado y corregido por Eliécer Pineda Ballesteros Página 30
Programación Lógica Lenguaje Prolog y Visual Prolog
mi_arbol= arbol(INTEGER, mi_arbol, mi_arbol); vacio
Operaciones con árboles representados mediante objetos compuestos recursivos
Domains
arbol= nodo(integer, arbol, arbol); vacio
lista= integer*
predicates
concatenar(lista, lista, lista)
preorden(arbol, lista)
inorden(arbol, lista)
postorden(arbol, lista)
clauses
concatenar([],[],[]):-!.
concatenar([],L2,L2):-!.
concatenar(L1,[],L1):-!.
concatenar([X|Y],L2,[X|Aux]):-concatenar(Y,L2,Aux).
preorden(vacio,[]):-!.
preorden(nodo(X,Izq,Der),[X|L]):-preorden(Izq,L1),
preorden(Der,L2),
concatenar(L1,L2,L).
inorden(vacio,[]):-!.
inorden(nodo(X,Izq,Der),L):-inorden(Izq,L1),
inorden(Der,L2),
concatenar(L1,[X|L2],L).
postorden(vacio,[]):-!.
postorden(nodo(X,Izq,Der),L):-postorden(Izq,L1),
postorden(Der,L2),
concatenar(L1,L2,L3),
concatenar(L3,[X],L).
Goal
inorden(nodo(1,nodo(2,nodo(4,vacio,vacio),nodo(5,vacio,vacio)),nodo(3,vacio,vacio)),
L1),
preorden(nodo(1,nodo(2,nodo(4,vacio,vacio),nodo(5,vacio,vacio)),nodo(3,vacio,vacio)),
L2),
postorden(nodo(1,nodo(2,nodo(4,vacio,vacio),nodo(5,vacio,vacio)),nodo(3,vacio,vacio)),
L3).
6.3 LISTAS
Una lista se puede considerar como un caso particular de árbol del modo que se muestra en la Figura
13.
Editado y corregido por Eliécer Pineda Ballesteros Página 31
Programación Lógica Lenguaje Prolog y Visual Prolog
Nivel 0
Nivel 2
Nivel 1
‘·’
1 ‘·’
2 3
Figura 13, Lista implementada en forma de árbol
A su vez, una lista se puede considerar de forma recursiva. Es decir, siempre está formada por un
elemento seguido de otra lista (ver Figura 14). Cuando la lista tienen un sólo elemento podemos considerar
que está formada por dicho elemento y la lista vacía. Esta definición es muy interesante, ya que su
conocimiento nos permitirá llevar a cabo todos las operaciones que se pueden realizar sobre las listas con
poco esfuerzo.
Figura 14, Definición recursiva de una lista
Hemos de recordar que en Prolog no existen estructuras para realizar bucles luego todo los algoritmos
que representemos se definirán de forma recursiva. El hecho de que la implementación de la lista sea
también recursiva facilita la construcción de operaciones sobre la misma.
Es necesario comprender este tipo de estructura para construir algoritmos eficientes. La mayor parte
de las operaciones que se realizan sobre una lista implica un recorrido de la misma, luego hemos de
centrarnos en conocer cómo se lleva a cabo este algoritmo utilizando técnicas de recursividad.
Una lista se puede especificar en un predicado o en un objetivo a través de:
una constante: [a, b, c, 1, pepe]
una variable: L
Editado y corregido por Eliécer Pineda Ballesteros Página 32
Programación Lógica Lenguaje Prolog y Visual Prolog
la estructura [Cabeza|Cola] que almacenará el primer elemento en la variable Cabeza y el resto
en la variable Cola.
Las listas pueden ser homogéneas o heterogéneas, es decir, almacenar elementos del mismo tipo, o
elementos de distinto tipo.
Para definir un tipo de lista en particular es necesario declararla en la sección DOMAINS.
lista= elementos* (lista de una dimensión)
lista2= elementos** (lista de dos dimensiones)
lista3= elementos*** (lista de tres dimensiones)...
Es interesante observar la sintaxis de definición de una lista: elementos representa el dominio o tipo de
los elementos que componen la lista.
El tipo elementos puede representar un dominio simple, es decir, sólo un tipo de elementos se
corresponde con dicho dominio o un dominio complejo, donde varios tipos de elementos se corresponden
con dicho dominio.
Por ejemplo, una lista homogénea de elementos simples estaría definida como:
lista= integer*
Una lista heterogénea de elementos estaría definida como:
listaenteros=integer*
elementos= i(integer); s(symbol); c(char); le(listaenteros)
lista= elementos*
Ejemplo:
Editado y corregido por Eliécer Pineda Ballesteros Página 33
Programación Lógica Lenguaje Prolog y Visual Prolog
Domains
listaenteros= integer*
elementos= i(integer); c(char); s(symbol); le(listaenteros)
lista= elementos*
predicates
recorrer(lista)
clauses
recorrer([]):-!.
recorrer([X|Y]):-write(X), nl, recorrer(Y).
Goal
recorrer([i(1),c('a'),s(pepe),i(5),c('b'),le([1,2,3])]).
Se observa que la lista puede contener cuatro tipo de elementos distintos: enteros, caracteres,
símbolos y listas de enteros. En la sección de declaración del dominio o tipo elementos no podemos escribir:
elementos= integer; char; symbol; listaenteros
para expresar que dicho dominio agrupa a cuatro tipos de elementos distintos sino que la sintaxis a
utilizar es aquella que representa que elementos agrupa a cuatro tipos de objetos compuestos distintos.
El resultado de la ejecución de la meta es el siguiente:
i(1)
c('a')
s("pepe")
i(5)
c('b')
le([1,2,3])
yes
Las operaciones típicas que se pueden realizar sobre listas son: la inserción de elementos al principio, al
final, en orden; borrado, búsqueda de elementos, recorrido, eliminación de duplicados y, en general, todas
las de las que se pueden realizar sobre conjuntos de elementos tales como: intersección, unión, diferencia,
pertenencia, comprobación de lista vacía, concatenación, etc.
Las listas se pueden utilizar para implementar otras estructuras tales como listas circulares, vectores,
pilas, colas, árboles, grafos y matrices.
De cada estructura nos interesa saber cuáles son los algoritmos para acceder a ellas. Una vez que
conocemos, perfectamente, el tipo de operaciones que las definen, cualquier tipo de implementación es
válida. Por ejemplo, es frecuente usar una implementación mediante listas para plasmar matrices.
Editado y corregido por Eliécer Pineda Ballesteros Página 34
Programación Lógica Lenguaje Prolog y Visual Prolog
Por otro lado, es fundamental aplicar técnicas de diseño descendente para resolver todos nuestros
problemas e implementar las estructuras necesarias en nuestras aplicaciones.
6.4 MATRICES
Podemos definir matrices a partir de listas, primero de 2 dimensiones y, más tarde, generalizar
matrices de dimensión N.
En un lenguaje imperativo, recorrer una matriz de dos dimensiones implica el uso de un par de bucles
anidados, que proporcionan una complejidad computacional O(n2). Sin embargo, en Prolog, no disponemos
de este tipo de estructuras de control, por tanto, cualquier operación debe ser resuelta de forma recursiva
mediante la declaración formal de su enunciado.
Un tratamiento elemento a elemento de las matrices tal y como se realiza en un lenguaje imperativo
no es adecuado en Prolog, por tanto, conviene entender la estructura matriz como una lista de listas, y
aplicar los algoritmos diseñados sobre listas para resolver problemas matriciales.
Una matriz de cuatro dimensiones se puede ver como la secuencia de un conjunto de matrices de tres
dimensiones, una matriz de tres dimensiones como un conjunto de matrices de dos dimensiones, una
matriz de dos dimensiones como un conjunto o lista de matrices de una dimensión (vector o lista), por
último, un vector o lista no es más que una secuencia de elementos simples.
Las definiciones dadas son recursivas, luego los algoritmos que debemos construir para realizar
operaciones sobre este tipo de estructuras, así definidas, también serán recursivos.
Operaciones con matrices bidimensionales
Domains
fila=integer*
matriz= fila*
predicates
sumafila(fila, fila, fila)
sumar(matriz, matriz, matriz)
clauses
/*Predicado para calcular la suma de los elementos de una fila */
sumafila([],[],[]):-!.
sumafila([], L2, L2):-!.
sumafila(L1, [], L1):-!.
sumafila([C1|Cola1], [C2|Cola2], Res):- S=C1+C2,
sumafila(Cola1, Cola2, ColaRes),
Res=[S|ColaRes].
/*Predicado de recorrido de las filas para sumar los elementos mediante el uso del
predicado anterior */
Editado y corregido por Eliécer Pineda Ballesteros Página 35
Programación Lógica Lenguaje Prolog y Visual Prolog
sumar([],[],[]):-!.
sumar([], L2, L2):-!.
sumar(L1,[], L1):-!.
sumar([C1|Cola1], [C2|Cola2], LR):-sumafila(C1, C2, Res),
sumar(Cola1, Cola2, ColaRes),
LR=[Res|ColaRes].
Goal
sumar([[1,2,3],[2,2,2],[4,4,4]],[[1,1,1],[2,1,2],[1,2,3]],R).
Editado y corregido por Eliécer Pineda Ballesteros Página 36
Programación Lógica Lenguaje Prolog y Visual Prolog
CAPITULO 3.
7 Manipulación del Control en Prolog
En el capítulo anterior, hemos aprendido cómo es el esquema básico de trabajo en Prolog.
Sabemos que un programa lógico consta de una base de conocimientos donde expresamos los hechos
y reglas de deducción que aportan la información completa acerca del mundo o dominio que deseamos
representar.
Por otro lado, disponemos de un motor de inferencia que aplica un algoritmo, concretamente el
algoritmo de resolución, que permite inferir nuevos datos relativos al mundo que estamos representando.
Para ello, toma como entrada la base de conocimientos desarrollada y el objetivo planteado y ofrece como
salida un resultado de verdadero o falso en función de si ha podido o no demostrar el objetivo según la base
de conocimientos. Además proporciona también el conjunto de sustituciones o unificaciones para los
parámetros de salida especificados en el objetivo.
El algoritmo de demostración del objetivo se basa en el uso de la técnica de backtracking, de forma que
la inferencia de dicho objetivo se realiza a base de prueba y error. Debido a este tipo de funcionamiento,
podemos notar que el control de la ejecución lo lleva la máquina Prolog y, aparentemente, nosotros no
podemos interferir en dicho control.
El hecho de que exista este tipo de control automático supone una extraordinaria ventaja a la hora de
programar aunque, en ocasiones, también limita el funcionamiento o la eficiencia del programa diseñado.
Para solventar esta limitación, se introduce en Prolog la posibilidad de incluir en nuestras bases de
conocimientos unos predicados especiales que tienen como misión proporcionar una herramienta, un tanto
artificial, para "controlar el control".
8 Corte (!) y fail
En este apartado describiremos el significado de los predicados "!" (Corte), y fail. Veremos
gráficamente como actúan, y propondremos algunos ejemplos de cómo y cuándo deben utilizarse.
8.1 El Corte "!"
Podemos definir el Corte como un predicado que siempre se cumple, es decir, que genera un resultado
verdadero en la primera ejecución, y falla en el proceso de backtracking, impidiendo dicho retroceso. Su
Editado y corregido por Eliécer Pineda Ballesteros Página 37
Programación Lógica Lenguaje Prolog y Visual Prolog
aplicación principal es generar código más eficiente por el efecto que causa en la reducción o poda del árbol
de búsqueda generado durante el procedimiento de resolución.
Para comprender el funcionamiento de este predicado nada mejor que considerar un par de ejemplos,
cuyos árboles de búsqueda se muestran en la Figura 15 y Figura 16.
Ejemplo:
Base de conocimientos sin utilizar el Corte.
padre(juan, pepe).
padre(juan, luis).
padre(juan, alberto).
hermanodepadre(X,Y):-padre(Z,X), padre(Z,Y).
Objetivo
?.- hermanodepadre(pepe, ana).
No
El proceso de ejecución se observa en la Figura 15.
hermanodepadre(pepe, ana)
padre(Z, pepe) padre(juan, ana)
ÉXITO
padre(juan, pepe)
Z=
juan
padre(juan, pepe)
FALLO
padre(juan, luis) padre(juan, alberto)
FALLO FALLO
padre(juan, luis)
FALLO
Z=
juan
Z=
juan
padre(juan, alberto)
FALLO
FALLO
Figura 15, Árbol de ejecución para la base de conocimientos y objetivo del ejemplo que no usa corte
Como se observa en el árbol de ejecución, cuando falla el segundo predicado del consecuente, al hacer
backtracking, ignoramos la solución obtenida para el primer predicado en la rama anterior, y buscamos una
Editado y corregido por Eliécer Pineda Ballesteros Página 38
Programación Lógica Lenguaje Prolog y Visual Prolog
nueva solución, con la esperanza de hallar aquella que, posteriormente, satisfaga al segundo predicado. Sin
embargo, nosotros sabemos, a priori, que dicha solución no va a ser posible, porque ya hemos demostrado
que juan es el padre de pepe y no lo es de ana, luego ambos no son hermanos de padre, luego, en este caso,
no interesa seguir buscando nuevos padres para pepe (esto sería absurdo e ineficiente). Por tanto, no es
necesario desarrollar la rama de retroceso representada por la línea discontinua en la Figura 15.
En la Figura 16 se muestra como queda el árbol al introducir en el código, el predicado corte. La rama
que no se procesa se representa en color gris, para que sea posible la comparación con el ejemplo anterior.
Ejemplo:
Base de conocimientos utilizando el Corte.
padre(juan, pepe).
padre(juan, luis).
padre(juan, alberto).
hermanodepadre(X,Y):-padre(Z,X), !, padre(Z,Y).
Objetivo
?.- hermanodepadre(pepe, ana).
no
El proceso de ejecución se observa en la Figura 16.
hermanodepadre(pepe, ana)
padre(Z, pepe) padre(juan, ana)
ÉXITO
padre(juan, pepe)
Z=
juan
padre(juan, pepe)
FALLO
padre(juan, luis) padre(juan, alberto)
FALLO FALLO
FALLO
Corte(!)
Figura 16, Árbol de ejecución utilizando el corte
Editado y corregido por Eliécer Pineda Ballesteros Página 39
Programación Lógica Lenguaje Prolog y Visual Prolog
Utilidad del predicado Corte
Las principales utilidades del Corte se exponen en los puntos siguientes:
Confirmación de la regla elegida. Por ejemplo, cuando calculamos el factorial, sólo hay una posible
solución para el mismo, sin embargo, desde el entorno de programación, en la ventana de objetivos,
podemos pedir una nueva solución. En lugar de buscarla, un programa correcto debe indicar que no
hay más soluciones, aunque exista la posibilidad de realizar el procedimiento de retroceso. La forma
de construir dicho programa es mediante el uso del Corte, es decir manejando desde la base de
conocimientos el control de la máquina Prolog.
Ahorrar comprobaciones innecesarias, como en el caso de los ejemplos vistos en el punto anterior.
Parar al obtener una solución y no permitir que se generen nuevas soluciones, aunque se lo
indiquemos de modo forzado.
Para construir la negación conjuntamente con el predicado fail, como se verá en la sección
"Implementación de la negación y predicado repeat".
8.2 El predicado fail
Se trata de un predicado que siempre falla, por tanto, implica la realización del proceso de retroceso
para que se generen nuevas soluciones.
Una aplicación de este predicado, entre otras que ya se han comentado en el punto anterior, es la
generación de todas las posibles soluciones para un problema.
Recordemos que cuando la máquina Prolog encuentra una solución para y devuelve el resultado de la
ejecución. Con fail podemos forzar a que no pare y siga construyendo el árbol de búsqueda hasta que no
queden más soluciones que mostrar. A continuación se ilustra el funcionamiento de este predicado con un
ejemplo sencillo.
Editado y corregido por Eliécer Pineda Ballesteros Página 40
Programación Lógica Lenguaje Prolog y Visual Prolog
Ejemplo:
Base de conocimientos.
padre(juan, pepe).
padre(juan, luis).
padre(juan, alberto).
listado:-padre(juan,X), write(X), nl, fail.
Objetivo
?.- listado.
pepe
luis
alberto
no.
El proceso de ejecución se observa en la Figura 17 .
listado
padre(juan, X)
ÉXITO
padre(juan, pepe)
X=
pep
e
FALLO
failwrite(X) nl
ÉXITO
padre(juan, luis)
ÉXITO
padre(juan, alberto)
X=
luis
X=
alb
ert
o
Figura 17, Ilustración del funcionamiento del predicado fail
8.3 Implementación de la negación y predicado repeat
Veamos cómo se implementan dos predicados interesantes: not y repeat
Predicado not (negación).
Como se comentó en el punto anterior, la negación se implementa como fallo, de modo que para negar
algo, debemos demostrar que el objeto de la negación falla, es decir, para negar P, hemos de demostrar que
P es falso y por tanto, la negación de P es verdadera.
Editado y corregido por Eliécer Pineda Ballesteros Página 41
Programación Lógica Lenguaje Prolog y Visual Prolog
El predicado not ya está implementado en Prolog pero conviene conocer dicha implementación.
not(P):-call(P), !, fail.
not(P).
Para comprender la implementación de la negación nos vamos a fijar en la Figura 18, que muestra el
funcionamiento del predicado cuando P es cierto y en la Figura 19, que muestra el funcionamiento cuando P
es falso.
not(P)
call(P)
ÉXITO
FALLO
! fail
FALLO
Figura 18, Funcionamiento de not cuando P es cierto
not(P)
call(P)
FALLO
ÉXITO
not(P)
ÉXITO
Figura 19, Funcionamiento de not cuando P es falso
Como ya se ha comentado la interpretación dada de not se basa en una hipótesis de modelización que
habitualmente se conoce con el nombre de "supuesto de mundo cerrado", y que se puede formular como la
afirmación de que si no podemos demostrar que una cláusula es cierta, entonces podemos afirmar de
forma coherente que la negación de la cláusula es verdadera. Sin embargo, esta no es la negación que se
utiliza en la lógica clásica y, por tanto, introduce problemas en la actividad de modelización lógica [Adarraga,
1994].
Consideremos por ejemplo, la aserción "soltero(X) si no casado(X)". Dicha aserción parece equivalente
a "casado(X) si no soltero(X)". Pero si utilizamos la primera aserción bajo el supuesto de mundo cerrado, con
un individuo X de cuyo estado nada sabemos, podemos concluir que es soltero, mientras que si utilizamos la
segunda aserción, podemos inferir que está casado.
casado(pepe).
soltero(X):-not(casado(X)).
Editado y corregido por Eliécer Pineda Ballesteros Página 42
Programación Lógica Lenguaje Prolog y Visual Prolog
Supongamos que no sabemos el estado de X=juan. Esto implica que casado(juan) falla y, por tanto,
not(casado(juan)) es cierto, luego soltero(juan) es cierto.
soltero(pepe).
casado(X):-not(soltero(X)).
Supongamos que no sabemos el estado de X=juan. Esto implica que soltero(juan) falla y, por tanto,
not(soltero(juan)) es cierto, luego casado(juan) es cierto.
Como vemos, el resultado del estado de un individuo del que no sabemos nada depende de cómo
implementemos la base de conocimientos. Una situación, por tanto, ilógica y contradictoria.
Predicado repeat
Se implementa como:
repeat.
repeat:-repeat.
Esto implica que siempre que hacemos backtracking repeat es verdadero.
Ejemplo:
predicates
nondeterm repeat
opcion(integer)
nondeterm menu
clauses
repeat.
repeat:-repeat.
/* Cómo hacer un menú de opciones */
opcion(X):-X=0, write("Has elegido salir"), nl, !.
opcion(X):-write("No has elegido salir"), nl.
menu:-repeat,
write("Elige opción (0 para salir, Otro para continuar): "),
readint(X),
opcion(X),
X=0.
goal
menu.
La ejecución de la meta proporciona el siguiente resultado:
Elige opción (0 para salir, Otro para continuar): 1
No has elegido salir
Elige opción (0 para salir, Otro para continuar): 2
No has elegido salir
Editado y corregido por Eliécer Pineda Ballesteros Página 43
Programación Lógica Lenguaje Prolog y Visual Prolog
Elige opción (0 para salir, Otro para continuar): 3
No has elegido salir
Elige opción (0 para salir, Otro para continuar): 0
Has elegido salir
yes
CAPITULO 4.
Aplicaciones del Lenguaje PROLOG
9 Aplicaciones actuales del Lenguaje PROLOG
Como hemos visto, programar en Prolog abre nuestras mentes a un nuevo modo de ver la
computación. Puede que nos resulte difícil comprender esta técnica, pero nos preocupa, finalmente, más
que su dificultad, su utilidad, ya que muchas veces nos preguntamos para qué aprender conceptos que
puede que en el futuro no sirvan.
Este capítulo trata de mostrar de forma general la importancia actual que este tipo de paradigmas
tiene. En concreto, el paradigma declarativo lógico y, por supuesto, el lenguaje Prolog.
Prolog se puede utilizar para resolver, básicamente, cualquier tipo de problema. Principalmente es útil
en la gestión de Juegos, en Inteligencia Artificial y Sistemas Expertos, como lenguaje especialmente pensado
para construir bases de conocimientos basados en la lógica que forman parte importante de cualquier
agente inteligente, en la construcción de Compiladores e Intérpretes, en el Reconocimiento del Lenguaje
Natural, etc.
9.1 Inteligencia Artificial
La resolución de juegos y la planificación así como la construcción de agentes inteligentes constituyen
amplios campos que abarca la rama de la Inteligencia Artificial. A continuación, veremos algunos ejemplos
de resolución de juegos y problemas típicos de planificación implementados en Prolog. Podremos observar
la facilidad con la que podemos plasmar las especificaciones de los problemas directamente, utilizando una
sintaxis que nos proporciona un alto grado de abstracción. Esto nos aporta una gran ventaja a la hora de
realizar el desarrollo de la aplicación una vez analizado el problema y diseñada su solución.
Editado y corregido por Eliécer Pineda Ballesteros Página 44
Programación Lógica Lenguaje Prolog y Visual Prolog
PROBLEMA DE LAS OCHO REINAS
El problema de las ocho reinas y en general de las N reinas, se basa en colocar 8 reinas en un tablero de
88 (o N en un tablero de NN, si el problema se generaliza), de forma que en no puede haber dos piezas
en la misma línea horizontal, vertical o diagonal, ver Figura 20.
Figura 20, Posible solución para el problema de las ocho reinas
Este programa ha sido muy estudiado por los matemáticos. Se trata de un problema NP-Completo que
no tiene solución para N=2 y N=3. Para N=4 tiene una única solución. Para N=8 hay más de 80 soluciones
dependiendo de las restricciones que se impongan.
Una forma de abordar el problema se lleva a cabo mediante la construcción de un predicado en Prolog
del tipo siguiente: reinas(N, Solucion), donde N representa las dimensiones del tablero y el número de
reinas y Solucion es una lista que contiene la permutación de la lista de números que resuelven el problema.
Los índices de dicha lista representan la columna en la que se encuentra una reina y el número que
almacena la posición o índice representa la fila donde la reina está colocada. Así, para el ejemplo mostrado
en la Figura 20, tenemos que R=[2,4,1,3].
Este problema es resuelto, de modo clásico, por el método de prueba y error, luego se adapta
perfectamente a un algoritmo de backtracking. Básicamente, el problema se reduce a colocar una reina, e
intentar repetir el proceso teniendo en cuenta la reina colocada. Si logramos poner todas las reinas el
problema se ha resuelto, en caso contrario, deshacemos lo que llevamos hasta ahora y probamos con otra
combinación. Por tanto, hemos de generar un conjunto de permutaciones y seleccionar aquella que cumpla
los requisitos impuestos por el juego.
Veamos el código que resuelve el problema:
domains
lista=integer*
predicates
rango(integer, integer, lista)
Editado y corregido por Eliécer Pineda Ballesteros Página 45
Programación Lógica Lenguaje Prolog y Visual Prolog
nondeterm dame(integer, lista, lista)
nondeterm permuta(lista, lista)
atacada(integer, integer, lista)
correcta(lista)
nondeterm reina(integer, lista)
clauses
rango(N, N, [N]):-!.
rango(N, M, [N|Cola]):-N<M, Aux=N+1, rango(Aux, M, Cola).
dame(X,[X|Xs],Xs).
dame(X,[Y|Ys],[Y|Zs]):-dame(X,Ys,Zs).
permuta([],[]).
permuta(L,[Z|Zs]):-dame(Z,L,Ys), permuta(Ys,Zs).
atacada(X,N,[Y|Ys]):-X=Y+N, !; X=Y-N, !.
atacada(X,N,[_|Ys]):-N1=N+1, atacada(X,N1,Ys).
correcta([]):-!.
correcta([X|Y]):-correcta(Y), not (atacada(X, 1, Y)).
reina(N, Solucion):-rango(1,N,L1), permuta(L1,Solucion), correcta(Solucion).
goal
write("Tamaño tablero = "), readint(N),
nl,
write("Soluciones: "), nl,
reina(N, Solucion),
write(Solucion),nl, fail.
Es muy importante comprender como funciona cada uno de los predicados para entender el
funcionamiento del algoritmo general.
Prolog permite implementar los programas casi directamente a partir de las especificaciones realizadas
a partir de un análisis y diseño de la solución desde un alto nivel de abstracción. Además el procedimiento
de backtracking está implícito en el propio motor de inferencia, luego este paradigma se adapta
perfectamente a nuestro problema.
Si analizamos y diseñamos nuestro problema tenemos que la forma de resolverlo se resume en los
pasos siguientes:
1. Para N, obtenemos una lista de números comprendidos entre 1 y N: [1,2,3,4,...,N].
2. Obtenemos una permutación del conjunto de números de la lista.
3. Comprobamos que la permutación es correcta.
4. Si la permutación no es correcta, lo que debemos hacer es volver al paso 2 para generar una
permutación nueva.
Editado y corregido por Eliécer Pineda Ballesteros Página 46
Programación Lógica Lenguaje Prolog y Visual Prolog
Comencemos a analizar la solución implementada. El problema se resuelve con el predicado reina(N,
Solucion):-rango(1,N,L1), permuta(L1,Solucion), correcta(Solucion). Como vemos es, sencillamente,
una copia de las especificaciones realizadas más arriba. Se genera el rango entre 1 y N, se obtiene una
permutación y se comprueba si la permutación es, o no, correcta. En el caso de que cualquier predicado del
consecuente falle, la propia máquina Prolog se encarga de realizar el proceso de backtracking. Con lo cual ya
tenemos cubiertos los cuatro pasos fundamentales del algoritmo.
Para tener más claras las ideas, observemos el árbol de ejecución general del objetivo
reina(4,Solucion) en la Figura 21.
reina(4,Solucion)
rango(1,4,L1) permuta(L1,Solucion) corrrecta(Solucion)
L1=[1,2,3,4] Solucion=[1,2,3,4] Solucion=[1,2,3,4]
FAIL
Solucion=[1,2,4,3]
Solucion=[2,4,1,3]
Solucion=[1,2,4,3]
FAIL
Solucion=[2,4,1,3]
ÉXITO
Solucion=[2,4,1,3]
Figura 21, Árbol de ejecución para el objetivo reina(4,Solucion)
Para N=4, existe una única solución, aunque si ejecutamos el programa, veremos que se obtienen dos
soluciones. La segunda solución es la primera girada, ver Figura 22.
Figura 22, Soluciones al problema de las 4 reinas
ANALOGÍA
Analogía es un problema clásico de Inteligencia Artificial diseñado por Evans para resolver cuestiones
de analogía geométrica en tests de Inteligencia.
Editado y corregido por Eliécer Pineda Ballesteros Página 47
Programación Lógica Lenguaje Prolog y Visual Prolog
En este tipo de tests de Inteligencia se presentan varias figuras geométricas complejas. Cada figura
compleja está formada por figuras más pequeñas unas dentro de otras, a este conjunto lo denominamos
Origen. Por otro lado, tenemos otro conjunto de figuras complejas que forman parte del conjunto
Respuesta. Se trata, pues, de encontrar una similitud entre las figuras de Origen y las figuras del conjunto
Respuesta. La relación entre las figuras de Origen es del tipo A es a B como C es a X, siendo X la solución que
puede encontrarse, o no, en el conjunto Respuesta. Si existe en dicho conjunto una figura que satisfaga la
anterior afirmación, X se empareja con dicha figura, en caso contrario, hemos de responder que no existe
analogía entre el conjunto Origen y el conjunto Respuesta.
Veamos un ejemplo que ilustre todos estos conceptos. Dada la situación de la Figura 23, la respuesta
correcta sería 2.
Figura 23, Problema de Analogía
La solución como vemos consiste en aplicar la operación invertir a la figura C. Teniendo en cuenta esto,
podemos escribir un programa que resuelva, de forma general, este tipo de analogías. Los pasos
fundamentales se exponen a continuación.
1. A debe ser el inverso de B.
2. Eso implica que debemos calcular el inverso de C.
3. Si el inverso de C está en la lista de respuestas, hemos encontrado la respuesta.
4. En caso contrario, volvemos al paso 2 para encontrar otra solución.
Editado y corregido por Eliécer Pineda Ballesteros Página 48
Programación Lógica Lenguaje Prolog y Visual Prolog
La implementación de las figuras complejas es sumamente importante. Por tanto, vamos a definirlas.
Las figuras complejas están formadas por dos figuras más simples una dentro de otra. Así la figura A se
puede representar mediante el predicado: dentro(cuadro,triangulo).
Una vez que sabemos plasmar dichas figuras, veamos el código fuente del programa Prolog que
resuelve este tipo de analogías.
domains
disposicion= dentro(symbol, symbol);
fuera(symbol, symbol)
lista=disposicion*
test=determ (integer, disposicion) - (i, o)
predicates
figuras(integer, disposicion, disposicion, disposicion)
respuestas(integer, lista)
esta(disposicion, lista)
casar(disposicion, disposicion)
analogia(disposicion, disposicion, disposicion, disposicion, lista)
test_analogia: test
clauses
figuras(1, dentro(cuadro, triangulo), dentro(triangulo, cuadro), dentro(circulo, cuadro)):-
!.
figuras(2, dentro(cuadro, triangulo), dentro(triangulo, cuadro), dentro(circulo, cuadro)).
respuestas(1, [dentro(circulo, triangulo), dentro(cuadro, circulo), dentro(triangulo,
cuadro)]):-!.
respuestas(2, [dentro(circulo, triangulo), dentro(circulo, cuadro), dentro(triangulo,
cuadro)]).
esta(X, [X|_]):-!.
esta(X, [_|Y]):-esta(X,Y).
casar(dentro(F1, F2), dentro(F2, F1)):-!.
casar(fuera(F1, F2), fuera(F2, F1)).
analogia(A, B, C, X, Respuestas):-casar(A, B),
casar(C, X),
esta(X, Respuestas).
test_analogia(Numero, X):-figuras(Numero, A, B, C),
respuestas(Numero, Respuestas),
analogia(A, B, C, X, Respuestas).
goal
write("Dame número de test: [1,2]: "),
readint(N),
test_analogia(N, X),
write(X).
Si nos centramos en el predicado analogia vemos que se ajusta, perfectamente, a los pasos generales
de resolución del problema expuestos en la fase de análisis-diseño:
analogia(es_a(A, B), como_es_a(C, X), Respuestas):-casar(A, B),
Editado y corregido por Eliécer Pineda Ballesteros Página 49
Programación Lógica Lenguaje Prolog y Visual Prolog
casar(C, X),
esta(X, Respuestas).
Por un lado intentamos casar A y B, esto implica que A debe ser el inverso de B. Si este predicado se
cumple, continuamos con la siguiente cláusula del consecuente. Como X no está aún instanciada, X se
instancia al valor inverso de C. A continuación, se comprueba si X está en la lista de respuestas. En caso de
que esté, analogia termina, si no, analogia mediante backtracking busca una nueva solución, hasta que la
encuentre o demuestre que no existe.
test_analogia(Numero, X) es un predicado que permite probar el funcionamiento de analogia para un
conjunto de figuras dado. Para testear el predicado diseñado se han seleccionado los tests de la Figura 24.
(a)
(b)
Figura 24, Tests del ejemplo codificado en Prolog
9.2 Sistemas Expertos
Los agentes y sistemas expertos se pueden considerar entes capaces de actuar como lo haría un
experto humano en la resolución de un determinado problema. Pueden percibir el ambiente mediante
sensores y actúan sobre ese ambiente por medio de efectores. En los agentes hardware, los sensores son
sustituidos por cámaras y telémetros y los efectores son reemplazados mediante motores. En los agentes
software, las percepciones y acciones vienen a ser las cadenas de bits codificados. La Figura 25 muestra un
agente genérico.
Editado y corregido por Eliécer Pineda Ballesteros Página 50
Programación Lógica Lenguaje Prolog y Visual Prolog
AMBIENTE
percepciones
acciones
sensores
efectores
AGENTE
Figura 25, Estructura general de un agente inteligente
Pero, tanto si un agente es hardware o software, necesita un programa que permita transformar los
datos provenientes del entorno de usuario en acciones adecuadas para la resolución del problema para el
que han sido diseñados.
Estos programas se pueden construir siguiendo multitud de paradigmas, y uno de ellos es la
programación lógica, que, como hemos visto, se adapta perfectamente a la representación del
conocimiento.
Existen muchos tipos de sistemas expertos: de diagnóstico médico, para el análisis de imágenes de
satélite, clasificadores, controladores, asesores, agentes económicos, etc.
Como ejemplo de sistema experto tenemos el programa Prolog que permite conocer la velocidad de un
vehículo dadas sus características y las de la vía por la que circula.
Dado que hemos hablado repetidas veces de estos sistemas a lo largo del curso, no vamos a
profundizar más en esta cuestión.
9.3 Compiladores
La comprensión del lenguaje natural y la construcción de compiladores e intérpretes son campos de
desarrollo muy adecuados para Prolog.
En esta sección vamos a ver una aplicación de la programación lógica a la teoría de autómatas y
lenguajes formales.
En Prolog se puede especificar un autómata finito mediante tres hechos, simplemente. El predicado
inicial, inicial(Q), es true si Q es el estado inicial. El predicado final(Q) es true si Q es el estado final. Y el
predicado delta(Q, X, Q1) que funciona del siguiente modo: es true si el autómata cambia del estado Q al
estado Q1 al recibir el símbolo X. El autómata recibe una cadena de símbolos del alfabeto *. El autómata
Editado y corregido por Eliécer Pineda Ballesteros Página 51
Programación Lógica Lenguaje Prolog y Visual Prolog
reconoce el lenguaje si comenzó en el estado inicial y acabó en el estado final tras seguir las transiciones
especificadas por .
Veamos un ejemplo concreto utilizando el lenguaje (ab)*. La Figura 26 representa el autómata que
reconoce el lenguaje.
q0 q1
a
b
Figura 26, Reconocedor del lenguaje (ab)*
El código del programa Prolog para implementar el reconocedor se expone a continuación.
domains
lista=char*
predicates
inicial(symbol)
final(symbol)
delta(symbol, char, symbol)
aceptar(lista, symbol)
acepto(lista)
clauses
inicial(q0).
final(q0).
delta(q0, 'a', q1).
delta(q1, 'b', q0).
acepto(L):-inicial(Q), aceptar(L,Q).
aceptar([X|Y], Q):-delta(Q, X, Q1), aceptar(Y, Q1).
aceptar([],Q):-final(Q).
goal
write("Dame lista de símbolos: "), readterm(lista, L),
acepto(L),
nl,
write("Pertenece al lenguaje").
Las trazas de los programas para los casos ab y aa se muestran en la Figura 27.
Editado y corregido por Eliécer Pineda Ballesteros Página 52
Programación Lógica Lenguaje Prolog y Visual Prolog
aceptar([a,b])
inicial(Q)
inicial(q0)
aceptar([a,b], q0)
aceptar([a|[b]], q0)
delta(q0, a, q1) aceptar([b], q1)
aceptar([], q1)
final(q0)
delta(q1, b, q0)
ÉXITO
ÉXITO
ÉXITO
ÉXITO
(a)
aceptar([a,a])
inicial(Q)
inicial(q0)
aceptar([a,a], q0)
aceptar([a|[a]], q0)
delta(q0, a, q1) aceptar([a], q1)
delta(q1, a, q0)
ÉXITO
FAIL
FAIL
(b)
Figura 27, Árboles de ejecución del predicado reconocedor del lenguaje (ab)*
9.4 Miscelánea
Como ya hemos comentado, Prolog se puede adaptar a la resolución de casi cualquier tipo de
problema con gran facilidad. Aunque, en mi opinión, es ideal como lenguaje de implementación de
aplicaciones provenientes del campo de la Inteligencia Artificial.
En este punto, vamos a proponer y resolver algunos problemas típicos que se pueden resolver en
Prolog de un modo sumamente sencillo.
TORRES DE HANOI
El problema de las torres de Hanoi consiste en mover un conjunto de discos de un palo a otro palo
utilizando un palo auxiliar situado en medio. Las reglas para mover los discos son las siguientes:
No se puede mover más de un disco en cada ocasión.
No puede quedar un disco de menor radio debajo de un disco de mayor radio.
Mover el conjunto de discos se puede ver como: mover N-1 discos del palo izquierdo al palo del
medio, mover el disco sobrante del palo izquierdo al palo derecho y mover N-1 discos del palo del
medio al palo derecho.
El pseudocódigo del algoritmo queda como sigue:
hanoi(N)mover(N,izquierda,medio,derecha).
mover(1,A,_,C)Pasar disco de A a C.
mover(N,A,B,C)mover(N-1,A,C,B), mover(1,A,C), mover(N-1,B,A,C).
Editado y corregido por Eliécer Pineda Ballesteros Página 53
Programación Lógica Lenguaje Prolog y Visual Prolog
La solución del problema de las torres de Hanoi para tres discos y tres palos se muestra en la Figura 28.
A B C A B C A B C A B C
A B C A B C CBA CA B
Figura 28, Solución al problema de las Torres de Hanoi, con tres palos y tres discos
10 Líneas Futuras
Los agentes inteligentes, quienes funcionan como sistemas de razonamiento, son necesarios para
obtener resultados eficaces. La principal ventaja que ofrecen es su alto grado de modularidad. Además, es
posible independizar la estructura de control del conocimiento, con lo que cada porción del mismo
mantiene total independencia entre sí. Actualmente se trabaja en la construcción de agentes inteligentes
verdaderamente eficientes tanto hardware como software. Para comprender cuales son las líneas futuras
que se pretenden trazar, conviene saber qué se está haciendo en la actualidad, por tanto, vamos a describir
brevemente los cuatro grupos principales que componen la clasificicación de los sistemas de razonamiento
automático, cada uno diseñado específicamente para resolver distintos tipos de problemas:
- Demostradores de teoremas y lenguajes de programación lógicos. En los demostradoress de
teoremas se utiliza la resolución o algún otro procedimiento de inferencia completa para
demostrar oraciones expresadas en lógica de primer orden total, frecuentemente en trabajos de
razonamiento matemático y de tipo científico. También son empleados para responder preguntas:
la demostración de una oración que contiene variables sirve como respuesta a una pregunta
debido a que concretiza las variables. Los lenguajes de programación lógicos se caracterizan por
restringir la lógica, lo que impide el manejo completo de la negación, la disyunción y/o la igualdad.
Por lo general utilizan el encadenamiento hacia atrás, y a veces pueden incluir características no
lógicas de los lenguajes de programación (por ejemplo, entrada y salida). Tenemos como ejemplos
de demostradores de teoremas a SAM, AURA, OTTER, y como ejemplo de lenguajes lógicos,
tenemos PROLOG, MRS, LIFE.
Editado y corregido por Eliécer Pineda Ballesteros Página 54
Programación Lógica Lenguaje Prolog y Visual Prolog
- Sistemas de producción. Estos sistemas, al igual que los lenguajes de programación, utilizan la
implicación como elemento primario de representación. El consecuente de cada implicación se
interpreta como recomendación de la acción, y no como mera conclusión lógica. Funcionan con
una estructura de control de encadenamiento hacia delante. Algunos de ellos cuentan con un
mecanismo de resolución de conflictos para decidir qué acción emprender cuando son varias las
que se recomienda realizar. Citemos algunos ejemplos: OPS-5, CLIPS, SOAR.
- Sistemas de cuadro y redes semánticas. En estos sistemas se aplica la metáfora de que los objetos
son nodos de una gráfica, de que estos nodos se organizan de acuerdo a una estructura
taxonómica y de que los vínculos que existen entre los nodos representan relaciones binarias. En
los sistemas de cuadro estas relaciones se consideran como ranuras de un cuadro que se llenan
mediante otra. En las redes semánticas, en cambio, se consideran como flechas entre un nodo y
otro. Tenemos ejemplos de sistemas de cuadro como OWL, FRAIL, KODIAK, y ejemplos de redes
semánticas: SNEPS, NETL, Gráficas Conceptuales.
- Sistemas lógicos por descripción: Son la consecuencia de la evolución de las redes semánticas, al ser
presionadas para formalizar el significado de las redes, sin dejar de poner énfasis en la estructura
taxonómica como principio rector. La idea consiste en emplear como medio de expresión y de
razonamiento las definiciones complejas de objetos y clases, así como sus relaciones entre ellos.
Los trabajos más recientes se han enfocado al compromiso entra expresividad del lenguaje y
complejidad para el cómputo de ciertas operaciones. Tenemos como ejemplos KL-ONE, CLASSIC,
LOOM.
Durante el curso, nos hemos centrado en el estudio del primer grupo de la clasificación citada. Los
lenguajes lógicos, como ya se ha comentado, ofrecen muchas ventajas y, evidentemente, plantean
inconvenientes que deben ser subsanados.
En concreto, si utilizamos un entorno de programación interpretado de Prolog notaremos que la
eficiencia, en cuanto a velocidad de ejecución se refiere, disminuye, al igual que en cualquier lenguaje
interpretado, frente a un lenguaje compilado.
El conjunto de instrucciones de las computadoras actuales resulta muy pobre en relación con la
semántica de Prolog, por lo que la mayoría de los compiladores de Prolog, que también existen, realizan una
compilación a un lenguaje intermedio en vez de hacerlo directamente a lenguaje máquina. El lenguaje más
popular es el Warren Abstract Machine (WAM), que es un conjunto de instrucciones abstractas utilizable en
Prolog y que se puede interpretar o traducir a lenguaje máquina. Existen otros compiladores que traducen
Prolog a un lenguaje de alto nivel como Lisp o C, y utilizan dicho compilador para traducir a lenguaje
máquina.
Editado y corregido por Eliécer Pineda Ballesteros Página 55
Programación Lógica Lenguaje Prolog y Visual Prolog
Antes del trabajo de Warren sobre la compilación de la inferencia en Prolog, la programación lógica
resultaba excesivamente lenta para su uso generalizado. Los compiladores diseñados por Warren y otros
permitieron a Prolog alcanzar velocidades adecuadas en estaciones de trabajo promedio modelo 1990. En
fechas más recientes, la aplicación de la moderna tecnología de compilación, incluidos inferencia de tipo,
codificación abierta y análisis de flujo de datos entre procedimientos ha permitido a Prolog alcanzar
velocidades tan óptimas que lo hace competir con C en cuanto a diversos aspectos estándar (Van Roy,
1990). Por supuesto, el hecho de poder escribir un planificador o un analizador de lenguaje natural en unas
cuantas decenas de líneas de Prolog, hacen que éste sea más preferible que C en la realización de los
prototipos de gran parte de los proyectos de investigación de Inteligencia Artificial a escala reducida.
Aparte de las mejoras que se están realizando en cuanto a velocidad de ejecución también se han
desarrollado y se están desarrollando ampliaciones de Prolog que permiten su adaptación a muchos
problemas que han surgido recientemente: programación lógica y orientación a objetos, programación
concurrente, programación visual y construcción de razonadores completos de lógica de primer orden.
Editado y corregido por Eliécer Pineda Ballesteros Página 56
Programación Lógica Lenguaje Prolog y Visual Prolog
CAPITULO 5.
LÓGICA MATEMÁTICA
11 Introducción.
Dado que el Lenguaje Natural, aunque es potente, resulta muy ambiguo, nos interesa encontrar un
lenguaje más sencillo, sin ambigüedades que nos permita realizar razonamientos y generalizaciones. Por
ello, es necesario introducirnos en la formalización del Cálculo Proposicional, que, aunque no cuenta con
toda la potencia necesaria para describir el mundo, es válido como primera aproximación. También
veremos algunos conceptos del Cálculo de Predicados y, por supuesto, nos centraremos en definir y ver
cómo funciona el Método de Resolución.
11.1 Conceptos básicos.
Para comprender los principios de la lógica matemática en el campo del Cálculo Proposicional,
necesitamos conocer una serie de conceptos básicos que se describen a continuación:
Átomo: También llamado Fórmula Atómica o Enunciado Simple. Permite la formalización de una
frase declarativa que no se puede descomponer en frases más simples. Para denotar átomos se
utilizan las letras p, q, r, etc.
Conectiva: Operador que permite construir sentencias compuestas a partir de átomos. Las
principales conectivas lógicas son: , , , .
Enunciado: También llamado Fórmula. Es una expresión realizada con átomos y conectivas lógicas,
siguiendo unas determinadas normas. Para denotar enunciados se utilizan las letras A, B, C, etc.
Deducción: Consiste en una lista de enunciados que, o bien son dados previamente, en este caso se
llaman Premisas, o bien se han obtenido de enunciados anteriores mediante la utilización de un
conjunto finito de reglas denominadas Reglas de Inferencia.
Dada una serie de premisas, a través de las reglas de inferencia, podemos llegar a un enunciado que
podemos denominar enunciado Conclusión. El conjunto de pasos para llegar a este enunciado a partir de las
premisas usando dichas reglas de inferencia, compone un algoritmo general que permite automatizar el
Editado y corregido por Eliécer Pineda Ballesteros Página 57
Programación Lógica Lenguaje Prolog y Visual Prolog
proceso de demostración. De esta forma, obtenemos un demostrador automático de teoremas que es,
justamente, en lo que consiste la máquina PROLOG.
Aunque mediante la Lógica Proposicional podemos describir muchas situaciones, existen otras
imposibles de representar. Necesitamos introducirnos, además, en la Lógica de Predicados. Podemos
considerar la Lógica Proposicional como un subconjunto de la Lógica de Predicados o de Primer Orden. Por
tanto, a las definiciones anteriores, hemos de añadir otras nuevas que nos permitan comprender los
métodos que se explicarán en apartados posteriores.
Símbolos: Existen varios tipos:
Individuales o Constantes: Representan valores concretos. C={a, b, c, d, e}.
Variables: Se pueden sustituir por constantes. V={x, y, z, v, w}.
Funciones: Aplicación que asocia una serie de constantes con otra constante. F={f, g, h}.
Predicados: Función de resultado Verdadero o Falso. Pred={P, Q, R}.
Relaciones: Representan relaciones o cuantificaciones. Rel={, , , , , , }
Signos de puntuación: Permiten agrupar o separar otros símbolos. Pun={(, ), ,, [, ]}
Términos: Se pueden definir de varias maneras. A continuación se exponen las distintas formas de
definición de términos:
Una constante: a, c.
Una variable: x, z.
Si f es un símbolo de función y t1, t2,..., tn son términos, entonces f (t1, t2,,..., tn) es un término, por
ejemplo g(a, f(x)).
Fórmulas: Se definen como:
Si R es un símbolo de relación y t1, t2,..., tn son términos, entonces R (t1, t2,,..., tn) es una fórmula.
Ejemplo:
f(a, x) g(x), x (g(x) a) [f(a, v) P(b c)]
Si A y B son dos fórmulas y R es un símbolo de relación, entonces R(A, B) también es una fórmula.
Editado y corregido por Eliécer Pineda Ballesteros Página 58
Programación Lógica Lenguaje Prolog y Visual Prolog
Ejemplo:
[x (g(x) a) (f(a, v) P(b c))] (f(a, x) g(z))
Sentencias: Se definen como fórmulas en las que ninguna de las variables que la componen tiene
una o más ocurrencias libres, o sea, todas las variables de la fórmula son ligadas. Es necesario que
definamos, por tanto, lo que son variables libres y ligadas.
Una ocurrencia de una variable x es ligada en una fórmula si y sólo si se da una de las siguientes
condiciones:
1) La variable x está inmediatamente después de un símbolo ó .
2) La variable x está en el radio de acción de un cuantificador x ó x.
El radio de acción de un cuantificador en una fórmula abarca al término inmediatamente
siguiente, haciéndose imprescindible el uso de paréntesis para aumentar su radio de acción.
Ejemplos:
x (f(x) g(z)). El cuantificador abarca a f(x) y g(z).
x h(x) f(a, v, x). El cuantificador abarca sólo a h(x).
Una variable es libre en una fórmula si no tiene ninguna ocurrencia ligada en la misma. En el
siguiente ejemplo, la variables v es libre, puesto que no tiene ninguna ocurrencia ligada. Sin
embargo, la x presenta una ocurrencia ligada, ya que g(x) cae dentro del radio de acción del
cuantificador x.
Ejemplo:
x [P(g(x)) R(a)] [f(a, v) Q(b c)]
Editado y corregido por Eliécer Pineda Ballesteros Página 59
Programación Lógica Lenguaje Prolog y Visual Prolog
Sustituciones: Dado el conjunto de variables V y el conjunto de términos Term, una sustitución se
define como la aplicación que se muestra en la Ec 1 y se suele denotar como s={x1/t1,...,xn/tn}. De
dicha definición podemos concluir dos cosas:
Sólo son válidas aquellas sustituciones que transforman una variable en una constante, en otra
variable o en una función, es decir, en términos.
La sustitución de una variable afecta a todas las ocurrencias de la misma.
nn tx
tx
TermV
......
11
Ec 1
11.2 Resolución y unificación. Métodos.
La Deducción Natural consiste en un sistema de reglas de inferencia que permite construir
deducciones, es decir, a partir de "algo" podemos deducir o "llegar a" "otra cosa", hasta que encontramos
una conclusión. Se trata de un método puramente sintáctico donde sólo nos ocupamos de la manipulación
de símbolos. Es un método interesante para construir demostraciones, sin embargo es difícilmente
mecanizable.
Por otro lado, como hemos visto, es fácil representar hechos del mundo real mediante la lógica
proposicional y mediante la lógica de predicados. Además mediante la lógica de predicados podemos
representar el conocimiento que tenemos sobre un cierto mundo finito poniéndolo en forma de sentencias
y disponemos de un mecanismo para razonar con ese conocimiento. Sin embargo, lo que para el ser
humano resulta trivial, deducir una sentencia a partir de otra, para la máquina puede llegar a ser
computacionalmente muy costoso e, incluso, inviable. Los estudios, por tanto, se han centrado en conseguir
un método de demostración que se puede ejecutar en un tiempo finito, y que en dicho tiempo, de forma
eficiente, nos proporcione una solución acertada.
El Método de Resolución [Robinson, 1965], es un intento de mecanizar el proceso de deducción natural
de esa forma eficiente. Las demostraciones se consiguen utilizando el método refutativo (reducción al
absurdo), es decir lo que intentamos es encontrar contradicciones. Para probar una sentencia nos basta con
demostrar que su negación nos lleva a una contradicción con las sentencias conocidas (es insatisfactible). Si
la negación de una sentencia entra en contradicción con los hechos de nuestra base de conocimiento es
porque lo contrario, es decir, la sentencia original era verdadera y se puede deducir lógicamente de las
sentencias que componen dicha base de conocimientos.
Editado y corregido por Eliécer Pineda Ballesteros Página 60
Programación Lógica Lenguaje Prolog y Visual Prolog
Existen distintas Estrategias de Resolución: sistemática, con conjunto soporte, unitaria, primaria y
lineal.
En este apartado formularemos detalladamente el método de Resolución por Refutación Lineal. Para
ello, es necesario conocer el proceso de conversión a forma clausal, ya que las cláusulas con las que se
trabaja en esta técnica deben tener una forma específica. Por otro lado, hemos de definir también el
proceso o algoritmo de Unificación, paso imprescindible en este método de Resolución.
Conversión a forma clausal.
El proceso de conversión a forma clausal consiste en transformar las sentencias y fórmulas en
cláusulas, cuya principal característica, al nivel de representación, es la ausencia casi total de símbolos de
relación. En una cláusula sólo aparecerán disyunciones "".
De esta manera, el primer paso será transformar todas las sentencias a una forma canónica llamada
forma normal conjuntiva [Davis y Putnam, 1960], a partir de la cual obtendremos el conjunto de cláusulas.
Así, podemos definir una cláusula, más formalmente, como una fórmula en forma normalizada conjuntiva
que no tiene ninguna conectiva. Esta transformación la vamos a realizar en varios pasos:
1) Primero pasaremos las sentencias a Forma Normal Prenexa.
2) En el siguiente paso las transformaremos a Funciones de Skolem.
3) Finalmente llegaremos a una representación en Forma de Cláusulas.
Forma Prenexa
Una fórmula está en Forma Normal Prenexa si es de la forma: Q1x1...QnxnY donde Y es una fórmula
desprovista de cuantificadores y escrita como conjunción de disyunciones, Q1,...,Qn {, } y x1,..., xn son
variables.
Ejemplos:
x y z v [(R(x) T(y)) Q(v, z)]
x y (R(x, y) Q(b, z))
x P(x, y)
Editado y corregido por Eliécer Pineda Ballesteros Página 61
Programación Lógica Lenguaje Prolog y Visual Prolog
Tenemos nuestro conocimiento en forma de sentencias, formadas por símbolos de relación, variables,
constantes, cuantificadores, todos mezclados. Para transformar una fórmula a Forma Normal Prenexa (o
inferencia por resolución) seguiremos el siguiente algoritmo:
Eliminar todos los símbolos de equivalencia (), sustituyéndolos por una implicación a la derecha y
una implicación a la izquierda: P Q = (PQ) (QP)
Eliminar todas las implicaciones (), sabiendo que (a b) es equivalente a (a b).
Reducir el ámbito de las negaciones (), a un único término, usando las siguientes propiedades:
- (p)=p
- Leyes de Morgan: (a b)= a b y (a b)= a b
- x P(x) = x P(x)
- x P(x) = x P(x)
Normalizar las variables de los cuantificadores, de forma que cada uno esté ligado con una única
variable. Para ello podemos, incluso, renombrar las variables.
Ejemplos:
x P(x) x Q(x) y P(y) x Q(x)
x [P(x) Q(x)] y R(y) Q(x) z [P(z) Q(z)] y R(y) Q(x)
Mover todos los cuantificadores a la izquierda de la fórmula sin cambiar su orden relativo.
Ejemplos:
x P(x) x Q(x)
y x [P(y) Q(x)]
(x R(x) y T(y)) z v Q(v z)
x y zv [(R(x) T(y)) Q(v z)]
Editado y corregido por Eliécer Pineda Ballesteros Página 62
Programación Lógica Lenguaje Prolog y Visual Prolog
Funciones de Skolem
El siguiente paso es convertir las fórmulas de Forma Normal Prenexa a Fórmulas de Skolem, que se
caracterizan por no estar cuantificadas existencialmente. Por tanto, el algoritmo de transformación a forma
de Skolem elimina los cuantificadores existenciales.
Partimos de una fórmula: Q1x1...QnxnY. Se recorre la fórmula en forma prenexa de izquierda a derecha y
se eliminan los cuantificadores existenciales según los dos casos siguientes:
Sea Qr un cuantificador existencial:
Si no hay ningún cuantificador universal antes de Qrxr, elegir una nueva constante c distinta de
todas las que aparecen en Y, y reemplazar cada ocurrencia de xr en Y por c. Borrar Qrxr del prefijo
de la fórmula.
Si Qs1, Qs2,…, Qsk son los cuantificadores universales que aparecen antes de Qrxr, tomar un nuevo
símbolo de función f distinto a todos los que aparecen en Y y reemplazar cada ocurrencia de xr
por f(xs1,xs2,...,xsk). Borrar Qrxr del prefijo de la fórmula.
Ejemplos:
1. Supongamos que tenemos:
x y z [(R(x) P(y)) Q(b, z)]
nos queda como
x y [(R(x) P(y)) Q(b, f(x, y))]
2. Supongamos la siguiente sentencia:
x y w [R(a, w) P(y) P(f(x))]
sustituimos x por c (caso 1): y w [R(a, w) P(y) P(f(c))]
sustituimos w por g(y) (caso 2): y [R(a, g(y)) P(y) P(f(c))]
Representación en forma de cláusulas: El último paso será convertir las funciones de Skolem a
cláusulas. Tenemos las fórmulas cuantificadas universalmente, entonces podemos eliminar todos
los prefijos, de tal manera que la fórmula resultante está en forma de conjunción de disyunciones
(forma normal conjuntiva): (a b c) (d e) (j l m). Finalmente, por cada conjunción
obtenemos una cláusula: (a b c), (d e) y (j l m).
Editado y corregido por Eliécer Pineda Ballesteros Página 63
Programación Lógica Lenguaje Prolog y Visual Prolog
Todos los pasos que hemos visto podemos resumirlos en el siguiente algoritmo, que es justamente el
algoritmo general de conversión a forma clausal:
1. Convertir la fórmula a Forma Normal Prenexa.
2. Transformarla a Forma de Skolem.
3. Pasar a Forma Normal Conjuntiva.
4. Separar cada conjunción en una cláusula.
Ejemplo:
Vamos a partir de la sentencia:
x [(R(x) C(x, a)) [O(x, b) (y(z O(y, z) L(x,y)))]]
Paso 1: Eliminamos los símbolos de implicación:
x [(R(x) C(x, a)) [O(x, b) (y(z O(y, z) L(x,y)))]]
Paso 2: Reducimos el ámbito de las negaciones:
x [(R(x) C(x, a)) [O(x, b) (y(z O(y, z) L(x,y)))]]
Paso 3: En este caso no es necesario normalizar las variables de los cuantificadores por lo tanto pasamos al paso siguiente
Paso 4: Movemos los cuantificadores a la izquierda:
x y z [(R(x) C(x, a)) (O(x, b) (O(y, z) L(x,y)))]
Paso 5: Eliminamos los cuantificadores existenciales:
x z [(R(x) C(x, a)) (O(x, b) (O(s(x), z) L(x, s(x))))]
Paso 6: Eliminamos todos los cuantificadores: [(R(x) C(x, a)) (O(x, b) (O(s(x), z) L(x, s(x))))]
Paso 7: Separar una cláusula por cada conjunción:
(R(x) C(x, a))
(O(x, b) (O(s(x), z) L(x, s(x))))
Algoritmo de Unificación.
Podemos definir la Unificación como un procedimiento de emparejamiento que compara dos literales y
descubre si existe un conjunto de sustituciones que los haga idénticos. La idea básica de la unificación es
muy sencilla. Para unificar dos literales vamos recorriéndolos de izquierda a derecha. En primer lugar se
comprueba si los predicados coinciden. Si es así, seguimos adelante; si no es que no son unificables. Si el
Editado y corregido por Eliécer Pineda Ballesteros Página 64
Programación Lógica Lenguaje Prolog y Visual Prolog
predicado concuerda, comenzamos a comparar los argumentos. Si el primero de ellos coincide en ambos
literales, continuamos con el siguiente... y así hasta completar todos los argumentos. Como resulta obvio,
ambos literales deben tener el mismo número de argumentos.
Para conseguir que cada argumento de un literal sea coincidente con su homólogo en el otro literal,
debemos buscar una sustitución que nos permita emparejarlos. La única condición que debe reunir esta
sustitución es que ha de aplicarse a todo el literal, es decir, que la sustitución afecta a todo el literal, y no
sólo al argumento en cuestión. Por decirlo de una manera sencilla, las sustituciones se van arrastrando a lo
largo del proceso de unificación.
Ejemplo:
Vamos a unificar P(x, x) con P(y, z):
Primera sustitución: (y/x)
Resultado: P(y, y) P(y, z)
Segunda sustitución: (z/y)
Resultado: P(z, z) P (z, z)
La sustitución resultante es la composición de las sustituciones: s = { z/y , y/x}
Describamos a continuación los pasos básicos del algoritmo de unificación:
Tomamos como entrada dos cláusulas, R y S.
1 Si R = S entonces R y S son unificables.
2 Si no, localizar el símbolo más a la izquierda de R que se diferencia de su homólogo en S
2.1 Si es el primero (predicado), entonces R y S no son unificables.
2.2 Si es uno de los argumentos, entonces sean t1, t2 los términos en los que difieren.
2.2.1 Si ninguno de los dos (t1, t2) es una variable, entonces las cláusulas no son unificables. Tampoco lo
serán si siendo uno de ellos una variable, está presente en las variables del otro.
2.2.2 Si t1 es una variable x y no está entre las variables del otro t2, entonces haremos la sustitución: s =
{x/t2}
3 Volver al paso 1.
A partir del algoritmo de unificación podemos extraer las siguientes conclusiones:
Editado y corregido por Eliécer Pineda Ballesteros Página 65
Programación Lógica Lenguaje Prolog y Visual Prolog
a) Podemos señalar como unificables todas aquellas cláusulas que no coincidan en su predicado y número
de argumentos.
b) Antes de intentar la unificación debemos asegurarnos que no existen variables comunes en ambas
cláusulas.
c) Debemos recordar siempre las condiciones que debe reunir una sustitución y que ésta debe ser única.
Ejemplo:
Unificación de las sentencias R (x, f(g(x)), a) y R (b, y, z)
Términos desiguales Sustitución Resultado
t1 = x t2 = b x/b - R(b, f(g(b)), a) , R(b, y, z)
t1 = f(g(b)) t2 = y y/f(g(b)) - R(b, f(g(b)), a), R(b, f(g(b)), z)
t1 = a t2 = z z/a - R(b, f(g(b)), a) , R(b, f(g(b)), a)
Las dos cláusulas son unificables y la sustitución resultante es: s = { z/a , y/f(g(b)) , x/b }
Una vez que hemos comprendido como funciona el algoritmo de unificación y cómo debemos
especificar adecuadamente las sentencias para llevar a cabo el algoritmo de resolución por refutación,
vamos a describir los pasos del mismo detenidamente.
Algoritmo de Resolución
El procedimiento de resolución consiste en un proceso iterativo en el cual comparamos (resolvemos),
dos cláusulas llamadas cláusulas padres y producimos una nueva cláusula que se ha inferido (deducido), de
ellas. Por tanto, lo que hacemos es combinar las cláusulas padres para dar lugar a una nueva cláusula, en la
que podemos simplificar alguno de sus términos.
Por ejemplo, supongamos que tenemos las cláusulas siguientes (ambas verdaderas):
invierno verano (es invierno o es verano).
invierno frío (hace frío o no es invierno).
Aplicando resolución, podemos combinar ambas cláusulas y obtener:
Editado y corregido por Eliécer Pineda Ballesteros Página 66
Programación Lógica Lenguaje Prolog y Visual Prolog
invierno verano invierno frío.
Ahora podemos hacer una simplificación, ya que (invierno invierno) es una tautología, con lo que
nos queda:
verano frío (es verano o hace frío).
Que también deberá ser verdadera, pues hemos seguido puntualmente todas las propiedades de la
lógica de primer orden.
La resolución opera tomando dos cláusulas tales que cada una contenga un mismo literal, en una
cláusula en forma positiva y en la otra en forma negativa. El resolvente se obtiene combinando todos los
literales de las cláusulas padres y eliminando aquellos que se cancelan.
Si la cláusula resultante es la cláusula vacía (€), entonces es que hemos llegado a una contradicción.
Como observamos el proceso de resolución parece sencillo. Podemos resumirlo formalmente en los
pasos siguientes, basados en el algoritmo de resolución lineal:
Vamos a partir de un conjunto de cláusulas. Nuestro objetivo es probar una sentencia mediante la
demostración de que su negación nos lleva a una contradicción con las sentencias conocidas (es
insatisfacible):
1 Convertimos todas las proposiciones a forma clausal.
2 Negamos la proposición que queremos demostrar y convertimos el resultado a forma clausal añadiendo
la cláusula resultante al conjunto obtenido en el paso anterior.
3 Hasta que se encuentre una contradicción o no se pueda seguir avanzando, repetimos lo siguiente:
3.1 Seleccionamos dos cláusulas (cláusulas padres) que contengan un literal común pero con signos
contrarios y unificamos esos dos literales.
3.2 Las resolvemos juntas. La cláusula resultante llamada resolvente, será la disyunción de los literales de
las dos cláusulas padres, una vez realizadas las sustituciones apropiadas. El par de literales L y L, que
provienen de cada una de las cláusulas padres, se pueden eliminar de la resolvente.
3.3 Si la resolvente es la cláusula vacía, es que se ha encontrado una contradicción. Si no, añadimos la
resolvente al conjunto de cláusulas disponibles.
El algoritmo que acabamos de ver está definido de una forma muy general. Sin embargo, para su uso
cotidiano se pueden hacer una serie de sugerencias que, si bien en la mayoría de los casos no están basadas
en aserciones infalibles, pueden facilitar el proceso general de resolución:
Editado y corregido por Eliécer Pineda Ballesteros Página 67
Programación Lógica Lenguaje Prolog y Visual Prolog
Aunque no sea un criterio estricto, suele dar buenos resultados comenzar a resolver por las cláusulas de
mayor tamaño, es decir, las que poseen mayor número de literales.
La cláusula resolvente se añade al conjunto de cláusulas disponible y, en teoría, se puede continuar el
proceso tomando dos cláusulas padre cualesquiera. Sin embargo, al igual que en el caso anterior, suele
dar buen resultado continuar el proceso de resolución a partir de la nueva cláusula resultante.
De igual forma, aunque no existe ninguna limitación en cuanto al número de veces que se puede usar
una cláusula para resolver, se recomienda probar primero a no usar dos veces la misma cláusula antes
de usar todas las cláusulas disponibles.
Si es posible llegar a la cláusula vacía resolviendo únicamente con las cláusulas del conjunto inicial sin
usar en ningún momento la o las cláusulas provenientes de la hipótesis, es porque existe una
inconsistencia dentro del conjunto inicial de cláusulas. Ésta puede ser una forma de detectar errores en
el diseño de la base de conocimiento.
Ejemplo:
Partir de la base de conocimiento siguiente, compuesta por 5 cláusulas, aplicar resolución para demostrar que la hipótesis V(z) es cierta:
P(x) Q(c, x) S(y, x) y P(a) R(z) S(b, a) y Q(z, a) V(a) y R(x) V(y) y
P(y) Q(x, y)
Ya tenemos las proposiciones en forma de cláusulas, luego sólo nos falta agregar la hipótesis, transformarla en cláusula y añadirla al conjunto de sentencias anterior:
V(z) negada nos queda V(z). (Como vemos está en forma de cláusula).
Dado que las sustituciones afectan a todas las ocurrencias de la variable que se pretende sustituir en toda la base de conocimientos, si queremos que dicha sustitución afecte a muchas ocurrencias de una variable podemos intentar renombrarlas. Pero para evitar tener todas las variables renombradas y, por tanto, evitar la complicación del procedimiento, estableceremos un uso especial de las sustituciones. Sólo afectarán a las cláusulas padres en el momento de la resolución, y a la cláusula resolvente, quedando el resto inalteradas.
Comenzamos el proceso por las cláusulas de mayor tamaño:
P(x) Q(c, x) S(y, x) y P(a) R(z) S(b, a) con la sustitución = {y/b, x/a} nos queda:
P(x) Q(c, x) S(y, x) P(a) R(z) S(b, a) = P(a) Q(c, a) R(z).
Combinamos la resolvente con P(y) Q(x, y) con la sustitución = {y/a} nos queda:
P(a) Q(c, a) R(z) P(y) Q(x, y) = Q(c, a) R(z) Q(x, a).
Aplicamos a la resolvente la sustitución = {x/c} y nos queda:
Editado y corregido por Eliécer Pineda Ballesteros Página 68
Programación Lógica Lenguaje Prolog y Visual Prolog
Q(c, a) R(z).
Combinamos la resolvente con Q(z, a) V(a) con la sustitución = {z/c} nos queda:
Q(c, a) R(z) Q(z, a) V(a) = R(c) V(a).
Combinamos la resolvente con R(x) V(y) con la sustitución = {x/c} nos queda:
R(c) V(a) R(x) V(y) = V(a) V(y).
Aplicamos la sustitución = {y/a} y nos queda V(a) que podemos combinar con V(z) obteniendo la cláusula
vacía {}.
Si en la cláusula resolvente existen dos literales iguales, ésta se puede simplificar eliminando uno de los
dos literales. Puede ser necesaria una sustitución previa a fin de que esos literales sean unificables y,
por tanto, completamente iguales.
No es necesario usar todas las cláusulas en el proceso de resolución. En la mayoría de los casos basta
con usar algunas de las cláusulas de la base de conocimiento y alguna o algunas de las cláusulas
provenientes de la hipótesis.