PDF de programación - Tema 1. Programación en Prolog

. PROGRAMACION en PROLOG


1



Tema 1. PROGRAMACION en PROLOG

1.1. Sintaxis: Hechos, Preguntas y Reglas.

1.2. Sintaxis: Objetos estructurados. Listas.

1.3. Computación: Unificación y Regla de Resolución.

1.4. Estrategia de Resolución usada en PROLOG.

1.5. Recorrido en el Espacio de Búsqueda.

1.6. Aspectos Declarativos y Procedurales.

Apuntes: Curso de PROGRAMACION LOGICA

Marisa Navarro 2008-09



2


1. PROGRAMACION en PROLOG

Apuntes: Curso de PROGRAMACION LOGICA Marisa Navarro 2008-09



1. PROGRAMACION en PROLOG


3

TEMA 1. PROGRAMACION en PROLOG



La programación lógica está basada en la lógica de primer orden LPO (o lógica de predicados). Un programa PROLOG consiste en un
conjunto de sentencias (o fórmulas), de la forma: A :- B1 , ... , Bn . con n ‡

0.

• Cuando n>0, la sentencia se escribe A :- B1 , ... , Bn . y se denomina regla.
• Si n=0, la sentencia se escribe A . y se denomina hecho.

Informalmente, un programa PROLOG consiste en un conjunto de hechos (afirmaciones simples) y de reglas que afirman “El hecho A es

cierto si son ciertos los hechos B1 y … y Bn”. Esto es, las reglas servirán para deducir nuevos hechos a partir de otros.


A un programa PROLOG se le hacen preguntas. Una pregunta se escribe como: ?A1, A2, …, Am. siendo m>0. Informalmente, dicha

pregunta se leerá: “¿Son ciertos los hechos A1 y A2 y … y Am?”.



1.1. Sintaxis: Hechos, Preguntas y Reglas



Los hechos son las sentencias más sencillas. Un hecho es una fórmula atómica o átomo: p(t1, ..., tn) e indica que se verifica la relación
(predicado) p sobre los objetos (términos) t1, ..., tn.



Ejemplos:



es_padre(abraham, isaac) es un hecho que indica “Abraham es padre de Isaac”

es_hombre(abraham)

es un hecho que indica “Abraham es un hombre”

suma(3,2,5) es un hecho que indica “la suma de 3 y 2 es 5”



Un conjunto de hechos constituye un programa (la forma más simple de programa lógico) que puede ser visto como una base de datos que
describe una situación. Por ejemplo, el Programa 1 refleja la base de datos de las relaciones familiares que se muestran en el siguiente

gráfico.

Apuntes: Curso de PROGRAMACION LOGICA Marisa Navarro 2008-09



4



Terach

Abraham

Nachor

Haran

Sarah

Isaac

Lot Milcah Yiscah



1. PROGRAMACION en PROLOG

Programa 1:


1. es_padre(terach, abraham).
2. es_padre(terach, nachor).
3. es_padre(terach, haran).
4. es_padre(abraham, isaac).
5. es_padre(haran, lot).
6. es_padre(haran, milcah).
7. es_padre(haran, yiscah).
8. es_madre(sarah, isaac).


9. es_hombre(terach).
10. es_hombre(abraham).
11. es_hombre(nachor).
12. es_hombre(haran).
13. es_hombre(isaac).
14. es_hombre(lot).
15. es_mujer(sarah).
16. es_mujer(milcah).
17. es_mujer(yiscah).

Todos los hechos de este programa son hechos de base (sin variables), pero también se pueden introducir hechos con variables como axiomas,
por ejemplo: suma(0, X, X). En ellos, las variables se consideran cuantificadas universalmente. Es decir, "
Al igual que el hecho es_mujer(sarah) establece la verdad de la sentencia "Sarah es mujer", el hecho suma(0, X, X) establece la verdad para

" x suma(0, x, x).

cualquier valor que pueda tomar la variable, es decir, nos dice que "para todo término x, la suma de 0 con x es x" . Equivale a un conjunto de
hechos de base como serían: suma(0, 1, 1), suma(0, 2, 2), etc.

Una vez que se tiene el programa describiendo una situación, se pueden hacer preguntas para obtener información acerca de él. Por ejemplo,
podemos hacer preguntas al Programa 1 del tipo siguiente:

PREGUNTA


?es_padre(abraham,isaac).
? es_padre(abraham,lot).
? es_padre(abraham,X).


? es_padre(haran,X).

SIGNIFICADO

¿es padre Abraham de Isaac?

¿es padre Abraham de Lot?

¿existe un X tal que es padre Abraham de X?



¿existe un X tal que es padre Haran de X?



RESPUESTA

Sí, pues encuentra un hecho que lo afirma.
No, pues no hay ningún hecho que lo afirme.
Sí. El programa contestará dando para X los
valores que verifican dicha relación: X=isaac.
Sí, dando todas las soluciones posibles:
X=lot ; X=milcah ; X=yiscah.

Apuntes: Curso de PROGRAMACION LOGICA Marisa Navarro 2008-09

"
"
1. PROGRAMACION en PROLOG


5

Estas preguntas sencillas se llaman fines. Como puede verse en la lectura de las preguntas, en éstas se consideran las variables cuantificadas

existencialmente. También se pueden hacer preguntas más complejas, como conjunción de fines, de la forma:

PREGUNTA
? es_padre(haran,lot), es_hombre(lot).
? es_padre(abraham,lot), es_hombre(lot). ¿es padre Abraham de Lot y es hombre Lot? La respuesta es no pues algún fin no es cierto.
? es_padre(abraham,X), es_hombre(X).

¿existe un X tal que es padre Abraham de

¿es padre Haran de Lot y es hombre Lot?

Sí, pues ambos fines son ciertos.

SIGNIFICADO

RESPUESTA


? es_padre(haran,X), es_mujer(X).

X y es hombre X?

¿existe un X tal que es padre Haran de



X y es mujer X?

La respuesta es sí pues ambos fines son ciertos para
algún valor de X. El programa contestará X=isaac.
El programa contestará que sí, dando todas las
soluciones posibles: X=milcah ; X=yiscah.


Las reglas son sentencias de la forma: A :- B1 , ... , Bn . donde A y cada Bi son átomos. A es la cabeza de la regla y los Bi's componen el cuerpo
de la regla.


Ejemplo: Una regla que define la relación “ser hijo” a partir de las relaciones dadas podría ser: es_hijo(X,Y) :- es_padre(Y,X),
es_hombre(X).

que se leería de la forma: “para cualesquiera X e Y, X es hijo de Y si Y es padre de X y X es hombre" ya que se corresponde con la fórmula
lógica: "
De igual forma se definirían otras relaciones mediante reglas:

" y ((es_padre(y,x)

es_hombre(x)) fi

es_hijo(x,y)).

" x "



es_hija(X,Y) :- es_padre(Y,X), es_mujer(X).
es_abuelo(X,Z) :- es_padre(X,U), es_padre(U,Z).



La última regla podría leerse "para cualesquiera X, Z y U, X es abuelo de Z si X es padre de U y U es padre de Z", que se corresponde con la
fórmula "
es_abuelo(x,z)) , o bien como "para cualesquiera X y Z, X es abuelo de Z si existe un U
tal que X es padre de U y U es padre de Z" que se corresponde con la fórmula "
es_abuelo(x,z)).

" u (es_padre(x,u)

$ u (es_padre(x,u)

es_padre(u,z) ) fi

es_padre(u,z) fi

" z ($

" x "

" x "

" z "

Apuntes: Curso de PROGRAMACION LOGICA Marisa Navarro 2008-09



"
"
"
"



fi
fi
fi
"
"
"
"
"
"



fi
fi
fi
"
"
"
"
$
$



fi
fi
fi
6


1. PROGRAMACION en PROLOG

Esto es debido a que ambas fórmulas son lógicamente equivalentes.
Con estas tres nuevas relaciones entre objetos y los hechos de base anteriores podemos crear el siguiente Programa 2.



Programa 2 = Programa 1 +

18. es_hijo(X,Y):- es_padre(Y,X), es_hombre(X).
19. es_hija(X,Y):- es_padre(Y,X), es_mujer(X).
20. es_abuelo(X,Z):- es_padre(X,Y), es_padre(Y,Z).


Ahora podemos hacer preguntas al Programa 2 sobre las nuevas relaciones introducidas:


PREGUNTA
? es_hijo(lot,haran).


? es_hija(X,haran).



SIGNIFICADO

RESPUESTA

¿es hijo lot de Haran?



¿existe un X tal que es hija X de Haran?



Sí, pues este hecho puede deducirse, ya que según la regla 18
es equivalente a preguntar: ?es_padre(haran,lot), es_hombre(lot).

Según la regla 19 es equivalente a preguntar
? es_padre(haran,X), es_mujer(X).
por lo que el programa contestará que sí, dando las soluciones:
X=milcah ; X=yiscah.

Otras preguntas y respuestas a este programa serían:



PREGUNTA

RESPUESTA

? es_abuelo(terach,isaac).

sí

? es_abuelo(terach,X), es_mujer(X).

X=milcah ; X=yiscah

? es_madre(X,Y).

X=sarah Y=isaac

? es_abuelo(X,Y), es_hombre(Y).

X=terach Y=isaac ; X=terach Y=lot

Apuntes: Curso de PROGRAMACION LOGICA Marisa Navarro 2008-09



1. PROGRAMACION en PROLOG


7


1.2. Sintaxis: Objetos estructurados. Listas.

Los objetos estructurados (o estructuras) en PROLOG son términos de la forma f(t1, ..., tn) donde f es un símbolo de función n-ario, o funtor,
y t1, ..., tn son a su vez términos (que pueden ser constantes, variables o a su vez estructuras).



Ejemplos de estructuras son las siguientes:

Los ejemplos anteriores se representarían de la forma:



libro(moby-dick, autor(herman, melville))
a+(b*c) ó +(a, *(b, c))



Las estructuras se suelen representar por árboles donde el

funtor es un nodo y los componentes son los subárboles que

libro

moby-dick

autor

+

a

*

herman melville

b

c

cuelgan de dicho nodo.



Introduciendo variables en una estructura se puede obtener información. Por ejemplo, supongamos que se tiene el siguiente program