PDF de programación - Programación Lógica - Introducción

PROGRAMACIÓN
LÓGICA

INTRODUCCIÓN

Juan Juárez Fuentes

1

Introducción
Trabajo propuesto en 1970
¿Cómo programar un sistema como el siguiente?

Usuario> Los gatos matan ratones.
Usuario> Tom es un gato al que no le gustan los ratones que comen queso.
Usuario> Jerry es un raton que come queso.
Usuario> Max no es un gato.
Usuario> ¿Qué hace Tom?
Sistema> A Tom no le gustan los ratones que comen queso.
Sistema> Tom mata ratones.
Usuario> ¿Qien es un gato?
Sistema> Tom.
Usuario> ¿Qué como Jerry?
Sistema> Queso

2

Introducción
Elementos de una lógica

¿Cómo programar un sistema como el siguiente?



Observe que este lenguaje define símbolos (sintaxis) para:
Designar elementos (Tom, Jerry, etc.).
Designar conjuntos (Gatos, Ratones, etc.).
Relaciones binarias (Comer, Matar, Gustar, etc.).
Funciones (The, Subset, True)

El razonamiento automático (semántica) se hacía mediante
resolución - SL.

3

Introducción
Historia
1965. Alan Robinson [3] formula el principio de resolución. Reglas de

inferencias menos humanas, pero más eficientes.

1970. Alain Colmerauer, Philippe Roussel y Robert Pasero [1]
trabajan en traducción automática y procesamiento de lenguaje
natural.

1971. Robert Kowalski[2] define la resolución - SL.

1974. El lenguaje Prolog.

4

Introducción
Mas generalmente

Siglo XIX. En su segunda mitad, Gottlob Frege introduce la lógica de primer
orden. Modificada a su forma actual por Giuseppe Peano y Bertrand Russell.

1930’s. Kurt Gôedel y Jacques Herbrand estudiaron la noción de

computabilidad basada en derivaciones.

1965. La resolución y unificación por Alain Robinson.

1974. La resolución – SL de Kowalski: fin del debate (en ese momento) sobre

representaciones declarativas y procedimentales. Prolog.

1983. La máquina abstracta de Warren [1], Compilación independiente al

procesador usado.

5

Introducción
Resumiendo



La programación lógica es una herramienta y un sujeto de estudio de la
inteligencia artificial.

La lógica de primer orden es fundamental para entender este paradigma de
programación.

La programación lógica es un paradigma de programación, que difiere de
otros paradigmas como la programación imperativa (Algol, C, Pascal, etc.),
la orientada a objetos (Simula, Smalltalk, Eiffel, C++, Java, etc.), o la
funcional (ML, Haskell, Lisp, etc.).

Prolog no es igual a programación lógica, pero es su realización práctica
más usada en la actualidad.

6

Introducción
Objetos Relaciones y programas
Asumamos que queremos razonar sobre una genealogía [2]:

1. progenitor(pam, bob).
2. progenitor(tom, bob).
3. progenitor(tom, liz).
4. progenitor(bob, ann).
5. progenitor(bob, pat).
6. progenitor(pat, jim).

7

Introducción
Cargando Prolog (1)
Prolog se puede ejecutar desde una terminal:

8

Introducción
Cargando Prolog (2)
El sistema está en un ciclo Read – Eval – Print (REPL).

1. progenitor(pam, bob).
2. progenitor(tom, bob).
3. progenitor(tom, liz).
4. progenitor(bob, ann).
5. progenitor(bob, pat).
6. progenitor(pat, jim).

9

Introducción
Variables
Se pueden hacer preguntas más interesantes usando variables:

?progenitor(X,liz).

X = tom

?progenitor(bob,X).

X = ann ;

X = pat ;

false.

1. progenitor(pam, bob).
2. progenitor(tom, bob).
3. progenitor(tom, liz).
4. progenitor(bob, ann).
5. progenitor(bob, pat).
6. progenitor(pat, jim).

10

Introducción
¿Quién es el abuelo de jim?

?progenitor(Y,jim), progenitor(X,Y).
Y = pat
X = bob
?progenitor(X,Y), progenitor(Y,jim).
X = bob
Y = pat
?progenitor(tom,X), progenitor(X,Y).
X = bob
Y = ann ;
X = bob
Y = pat ;
false.

11

Introducción
Resumiendo
Es sencillo definir en Prolog una relación especificando las n-tuplas de objetos

que la satisfacen. N es conocido como aridad.

Un programa Prolog consiste de cláusulas.

Los argumentos de una relación pueden ser: objetos concretos o constantes

como tom y ann; objetos generales o variables como X e Y.

Las preguntas planteadas a Prolog consisten en una o más metas. Una

secuencia de metas significa conjunción.

La respuesta a una pregunta puede ser positiva o negativa, dependiendo de si

la meta se puede satisfacer o no.

Si varias respuestas satisfacen una pregunta, Prolog encontrará tantas como el

usuario quiera.

12

Introducción
Reglas



Las reglas tienen dos partes:



Una parte condicional (el lado derecho de la regla o cuerpo de la regla).
Una conclusión (el lado izquierdo de la regla o cabeza de la regla).

13

Introducción
Extendiendo nuestro conocimiento

14

Introducción
Probando el nuevo conocimiento
La relación hermana/2 presenta una anomalía:

?hermana(ann,pat).
true.
?hermana(X,pat).
X = ann ;
X = pat ;
false.

15

Introducción
Resumiendo

Los programas Prolog pueden extenderse fácilmente agregando nuevas

cláusulas.

Las cláusulas en Prolog son de tres tipos: hechos, reglas y metas.

Los hechos declaran cosas que son verdaderas siempre, incondicionalmente.

Las reglas declaran cosas que son verdaderas dependiendo de ciertas

condiciones.

Por medio de las metas el usuario puede computar qué cosas son verdaderas.

16

Introducción
Resumiendo (2)

Las reglas de Prolog tienen cabeza y cuerpo. El cuerpo es una lista de metas

separadas por comas. Las comas implican conjunción.

Los hechos son cláusulas con el cuerpo vacío; las preguntas tienen la cabeza

vacía; y las reglas tienen cabeza y cuerpo.

En el curso de una computación, las variables pueden ser substituidas por

otros objetos.

Las variables se asumen cuantificadas universalmente. La cuantificación

existencial solo es posible en las variables que aparecen en el cuerpo de una
cláusula.

17

Introducción
Extensional contra Intensional

18

Introducción
Definición recursiva
Ancestro definido en términos de ancestro.

?ancestro(pam,X).
X = bob ;
X = ann ;
X = pat ;
X = jim ;
false.
?ancestro(X,jim).
X = pat ;
X = bob ;
X = pam ;
X = tom ;
false.

19

Introducción
Resumiendo



Las reglas recursivas definen conceptos en términos de ellos mismos.

Están definidas por lo menos dos casos: uno terminal (no recursivo) y la
llamada recursiva.

Una relación recursiva define intenSionalmente un concepto.

intensional no es igual a intencional.

20

Introducción
Demostración como Computo



Satisfacer una meta implica que la meta es verdadera, asumiendo que las
relaciones en el programa lógico son verdaderas.

Satisfacer una meta significa entonces demostrar que la meta es una
consecuencia lógica de los hechos y reglas definidas en un programa.

Si la pregunta contiene variables, Prolog necesita también computar cuales
son los objetos particulares (que remplazaran a las variables) para los
cuales la meta se satisface.

21

Introducción
Programas lógicos como matemáticas



Prolog acepta hechos y reglas como un conjunto de axiomas.

El usuario plantea preguntas teoremas

Prolog trata de probar este teorema, es decir, demostrar que el teorema se
sigue lógicamente de los axiomas.

22

Introducción
Ejemplos



Axioma1: Todos los hombres son
falibles.

Axioma2: Sócrates es un hombre.

Conclusión: Sócrates es falible.

23

Introducción
?- ancestro(tom, pat)



El proceso en un paso:

24

Introducción
?- ancestro(tom, pat)



El proceso en dos pasos:

25

Introducción
?- ancestro(tom, pat). Recursión

26

Introducción
Traza de un programa

27

Introducción
Ejercicio: Coloreando mapas

28

Introducción
Enunciado
Escriba un programa que describa el siguiente mapa. Añada una que
verifique si el esquema de color empleado es consistente. ¿Cuántos
cómputos son necesarios para verificar un mapa de N regiones?

29

Bibliografía

1.

2.

3.

A. Colmerauer and P. Roussel. The birth of Prolog. ACM SIGPLAN
Notices, 28(3):1–31, 1993.

R. Kowalski and D. Kuehner. Linear resolution with selection
function. Artificial Intelligence, 2(3):227–260, 1971.

J. A. Robinson. Amachine – oriented logic based on the resolution
principle. Journal of the ACM, 12(1):23–41, 1965.

30

Bibliografía (2)

4.

5.

6.

D. H. D. Warren. An abstract Prolog instruction set.
TechnicalReport309,SRI,1983.

I. Bratko. Prolog programming for Artificial Intelligence. Addison-Wesley,
1986. .

Notas del DR Alejandro Guerra Hernandez.

31