PDF de programación - Introducción a la programación lógica con Prolog

Introducción a la programación lógica con

Prolog

José A. Alonso Jiménez

Grupo de Lógica Computacional
Dpto. de Ciencias de la Computación e Inteligencia Artificial
Universidad de Sevilla
Sevilla, 17 de Junio de 2006 (versión de 25 de septiembre de 2006)

2

José A. Alonso

Esta obra está bajo una licencia Reconocimiento–NoComercial–CompartirIgual 2.5 Spain de Crea-
tive Commons.

Se permite:

copiar, distribuir y comunicar públicamente la obra

hacer obras derivadas

Bajo las condiciones siguientes:

Reconocimiento. Debe reconocer los créditos de la obra de la manera especificada
por el autor.

No comercial. No puede utilizar esta obra para fines comerciales.

Compartir bajo la misma licencia. Si altera o transforma esta obra, o genera una
obra derivada, sólo puede distribuir la obra generada bajo una licencia idéntica a
ésta.

Al reutilizar o distribuir la obra, tiene que dejar bien claro los términos de la licencia de
esta obra.

Alguna de estas condiciones puede no aplicarse si se obtiene el permiso del titular de los
derechos de autor.

Esto es un resumen del texto legal (la licencia completa). Para ver una copia de esta licencia,

visite

http://creativecommons.org/licenses/by-nc-sa/2.5/es/

o envie una carta a

Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.

Introducción a la programación lógica con Prolog

Índice

1. Introducción

2. El sistema deductivo de Prolog

2.1. Deducción Prolog en lógica proposicional . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . .
2.2. Deducción Prolog en lógica relacional
2.3. Deducción Prolog en lógica funcional
. . . . . . . . . . . . . . . . . . . . . . . . .

.
.
.

3. Listas

.
3.1. Representación de listas .
3.2. Concatenación de listas .
.
.
3.3. La relación de pertenencia .

.
.
.

.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4. Disyunciones

5. Operadores

6. Aritmética

7. Control mediante corte

8. Negación

9. El condicional

10. Predicados sobre tipos de término

11. Comparación y ordenación de términos

12. Procesamiento de términos

13. Procedimientos aplicativos

14. Todas las soluciones

Bibliografía

3

4

4
4
8
10

13
13
15
16

17

18

19

20

23

26

27

28

30

31

32

33

4

José A. Alonso

1.

Introducción

En este trabajo presentamos el lenguaje de programación lógica Prolog con un doble objetivo:
como una aplicación de la deducción automática estudiada en la asignatura de “Lógica informá-
tica” y como soporte de la asignatura de “Programación declarativa”.

Los textos fundamentales de Prolog son

1. I. Bratko. Prolog Programming for Artificial Intelligence. Addison–Wesley, 3 edition, 2001.

2. W. F. Clocksin y C. S. Mellish. Programming in Prolog. Springer–Verlag, 4 edition, 1994.

3. L. Sterling y E. Shapiro. The Art of Prolog. MIT Press, second edition, 1994.

4. T. Van Le. Techniques of Prolog Programming (with implementation of logical negation and quan-

tified goals). John Wiley, 1993.

Algunas introducciones a Prolog publicadas en la Red son

1. P. Blackburn, J. Bos y K. Striegnitz. Learn Prolog Now!, 2001.

2. T. Cornell. Introduction to Prolog, 1998.

3. U. Endriss. An Introduction to Prolog Programming. Universiteit van Amsterdam, 2005.

4. J. E. Labra. Programación práctica en Prolog. Cuaderno Didáctico Num. 13. Ed. Servitec, 1998.

5. F. Llorens y M. J. Castel. Prácticas de Lógica: Prolog. Universidad de Alicante, 2001.

6. H. Pain y R. Dale. An Introduction to Prolog, 2002.

7. G. Ritchie. Prolog Step–by–Step. University of Edinburgh, 2002.

8. D. Robertson. Prolog. University od Edinburgh, 2003.

9. T. Smith. Artificial Intelligence Programming in Prolog. University of Edinburgh, 2004.

2. El sistema deductivo de Prolog

En esta sección vamos a presentar el procedimiento básico de deducción de Prolog: la re-
solución SLD. La presentación la haremos ampliando sucesivamente la potencia expresiva del
lenguaje considerado.

2.1. Deducción Prolog en lógica proposicional

En esta sección vamos a estudiar el sistema deductivo de Prolog en el caso de la lógica pro-

posicional. Vamos a desarrollar el estudio mediante el siguiente ejemplo.

Ejemplo 2.1 [Problema de clasificación de animales] Disponemos de una base de conocimiento com-
puesta de reglas sobre clasificación de animales y hechos sobre características de un animal.

Regla 1: Si un animal es ungulado y tiene rayas negras, entonces es una cebra.

Introducción a la programación lógica con Prolog

5

Regla 2: Si un animal rumia y es mamífero, entonces es ungulado.

Regla 3: Si un animal es mamífero y tiene pezuñas, entonces es ungulado.

Hecho 1: El animal es mamífero.

Hecho 2: El animal tiene pezuñas.

Hecho 3: El animal tiene rayas negras.

Demostrar a partir de la base de conocimientos que el animal es una cebra.

Demostración: Una forma de demostrarlo es razonando hacia atrás. El problema inicial consiste
en demostrar que el animal es una cebra. Por la regla 1, el problema se reduce a demostrar que el
animal es ungulado y tiene rayas negras. Por la regla 3, el problema se reduce a demostrar que el
animal es mamífero, tiene pezuñas y tiene rayas negras. Por el hecho 1, el problema se reduce a
demostrar que el animal tiene pezuñas y tiene rayas negras. Por el hecho 2, el problema se reduce
ut
a demostrar que el animal tiene rayas negras. Que es cierto por el hecho 3.
Para resolver el problema anterior con Prolog vamos a considerar las siguientes cuestiones:

1. cómo se representan en Prolog las reglas,

2. cómo se representan en Prolog los hechos,

3. cómo se representan en Prolog las bases de conocimientos,

4. cómo se inicia una sesión Prolog,

5. cómo se carga en Prolog la base de conocimiento,

6. cómo se representa en Prolog el objetivo a demostrar,

7. cómo se interpreta la respuesta de Prolog,

8. cómo ha realizado Prolog la búsqueda de la demostración,

9. cuál es la demostración obtenida y

10. cómo se corresponde dicha demostración con la anteriormente presentada.

Para representar una regla, se empieza por elegir los símbolos para los átomos que aparecen
en la regla. Para la regla 1, podemos elegir los símbolos es_ungulado, tiene_rayas_negras y
es_cebra. La regla 1 puede representarse como

Si es_ungulado y tiene_rayas_negras entonces es_cebra
es_ungulado ∧ tiene_rayas_negras → es_cebra

Usando las conectivas lógicas la expresión anterior se escribe mediante la fórmula
donde ∧ representa la conjunción y →, el condicional. La fórmula anterior se representa en Prolog,
mediante la cláusula

es_cebra :- es_ungulado, tiene_rayas_negras.

Se puede observar que la transformación ha consistido en invertir el sentido de la escritura y
sustituir las conectivas por :- (condicional inversa) y , (conjunción). El átomo a la izquierda de
:- se llama la cabeza y los átomos a la derecha se llama el cuerpo de la regla.

6

José A. Alonso

Para representar los hechos basta elegir los símbolos de los átomos. Por ejemplo, el hecho 2

se representa en Prolog por

tiene_rayas_negras.

es decir, el símbolo del átomo terminado en un punto. Los hechos pueden verse como cláusulas
con el cuerpo vacío.

Para representar la base de conocimiento en Prolog, se escribe en un fichero (por ejemplo,

animales.pl) cada una de las reglas y los hechos 1.

:- es_ungulado, tiene_rayas_negras.

es_cebra
es_ungulado :- rumia, es_mamífero.
es_ungulado :- es_mamífero, tiene_pezuñas.
es_mamífero.
tiene_pezuñas.
tiene_rayas_negras.

% Regla 1
% Regla 2
% Regla 3
% Hecho 1
% Hecho 2
% Hecho 3

Al lado de cada regla y de cada hecho se ha escrito un comentario (desde % hasta el final de la
línea).

Para iniciar una sesión de Prolog (con SWI Prolog) se usa la orden pl. La base de conocimiento
se carga en la sesión Prolog escribiendo el nombre entre corchetes y terminado en un punto. La
pregunta se plantea escribiendo el átomo y un punto.

Welcome to SWI-Prolog (Multi-threaded, Version 5.6.18)
Copyright (c) 1990-2006 University of Amsterdam.

?- [animales].
Yes

?- es_cebra.
Yes

La respuesta Yes significa que ha demostrado que el animal es una cebra.

Podemos ver cómo Prolog ha obtenido la demostración mediante el árbol de deducción en la

Figura 1.

La búsqueda de la prueba es una búsqueda en profundidad en un espacio de estados, donde
cada estado es una pila de problemas por resolver. En nuestro ejemplo, el estado inicial consta de
un único problema (es_cebra). Buscamos en la base de hechos una cláusula cuya cabeza coinci-
da con el primer problema de la pila, encontrando sólo la regla 1. Sustituimos el problema por
el cuerpo de la regla. dando lugar a la pila es_ungulado, tiene_rayas_negras. Para el primer
problema tenemos dos reglas cuyas cabezas coinciden (las reglas 2 y 3). Consideramos en primer
lugar la regla 2, produciendo la pila de problemas rumia, es_mamífero, tiene_rayas_negras.
El primer problema no coincide con la cabeza de ninguna cláusula. Se produce un fallo y se recon-
sidera la elección anterior. Consideramos ahora la cláusula 3, produciendo la pila de problemas
es_mamífero, tiene_pezuñas, tiene_rayas_negras. Cada uno de los problemas restantes coin-
cide con uno de los hechos, con lo que obtenemos una solución del problema inicial.

1En SWI Prolog, para que no dé error en los predicados no definidos, hay que añadirle al fichero con la base de

conocimiento la línea
:- set_prolog_flag(unknown,fail).

Introducción a la programación lógica con Prolog

7

Figura 1: Árbol de deducción del problema de los animales

es_mamifero,:− rumia, tiene_rayas_negras.:− es_mamifero, tiene_pezuñas, tiene_rayas_negras. tiene_rayas_negras.:− es_ungulado,:− tiene_pezuñas, tiene_rayas_negras.:−.:− es_cebra.R1R3R2H1H2:− tiene_rayas_negras.H3FalloExito 8

José A. Alonso

Podemos observar que el árbol tiene dos ramas: una rama de fallo (su hoja es no vacía y su
primer átomo no coincide con la cabeza de ninguna