Tema 1: El sistema deductivo de Prolog
Introducción
Objetivos del seminario
Declarativo vs. imperativo
- Paradigmas
- Imperativo: Se describe cómo resolver el problema
- Declarativo: Se describe qué es el problema
- Programas
- Imperativo: Una sucesión de instrucciones
- Declarativo: Un conjunto de sentencias
- Lenguajes
- Imperativo: Pascal, C, Fortran, Java, Python
- Declarativo: Prolog, Lisp puro, ML, Haskell
- Ventajas
- Imperativo: Programas rápidos y especializados
- Declarativo: Programas generales, cortos y legibles
Historia de la programación lógica
- 1960: Demostración automática de teoremas
- 1965: Resolución y unificación (Robinson)
- 1969: QA3, obtención de respuesta (Green)
- 1972: Implementación de Prolog (Colmerauer)
- 1974: Programación lógica (Kowalski)
- 1977: Prolog de Edimburgo (Warren)
- 1981: Proyecto japonés de Quinta Generación
- 1986: Programación lógica con restricciones
- 1995: Estándar ISO de Prolog
Deducción Prolog
Deducción Prolog en lógica proposicional
- Base de conocimiento y objetivo:
- Base de conocimiento:
- Regla 1: Si un animal es ungulado y tiene rayas negras, entonces es una cebra.
- 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.
- Objetivo: Demostrar a partir de la base de conocimientos que el animal es una cebra.
- Programa:
es_cebra :- es_ungulado, tiene_rayas_negras.
es_ungulado :- rumia, es_mamífero.
es_ungulado :- es_mamífero, tiene_pezuñas.
es_mamífero.
tiene_pezuñas.
tiene_rayas_negras.
/home/SLC2015/tema-1> prolog
Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 6.6.4)
Copyright (c) 1990-2013 University of Amsterdam, VU Amsterdam
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit http://www.swi-prolog.org for details.
For help, use ?- help(Topic). or ?- apropos(Word).
?- [animales].
% animales compiled 0.00 sec, 7 clauses
true.
?- es_cebra.
true.
?- trace.
true.
[trace] ?- es_cebra.
Call: (6) es_cebra ?
Call: (7) es_ungulado ?
Call: (8) rumia ?
Fail: (8) rumia ?
Redo: (7) es_ungulado ?
Call: (8) es_mamifero ?
Exit: (8) es_mamifero ?
Call: (8) tiene_pezuñas ?
Exit: (8) tiene_pezuñas ?
Exit: (7) es_ungulado ?
Call: (7) tiene_rayas_negras ?
Exit: (7) tiene_rayas_negras ?
Exit: (6) es_cebra ?
true.
[trace] ?- nodebug.
true.
- Demostración por resolución SLD:
Deducción Prolog en lógica relacional
- Base de conocimiento:
- Hechos 1-4: 6 y 12 son divisibles por 2 y por 3.
- Hecho 5: 4 es divisible por 2.
- Regla 1: Los números divisibles por 2 y por 3 son divisibles por 6.
- Programa:
divide(2,6).
divide(2,4).
divide(2,12).
divide(3,6).
divide(3,12).
divide(6,X) :- divide(2,X), divide(3,X).
- Símbolos:
- Constantes:
2
, 3
, 4
, 6
, 12
- Relación binaria:
divide
- Variable:
X
- Interpretaciones de la Regla 1:
- Interpretación procedimental.
divide(6,X) :- divide(2,X), divide(3,X).
- Interpretación declarativa: (∀X)[divide(2,X) ∧ divide(3, X) → divide(6, X)]
- Consulta: ¿Cuáles son los múltiplos de 6?
?- divide(6,X).
X = 6 ;
X = 12 ;
No
- Comentarios:
- Unificación.
- Cálculo de respuestas.
- Respuestas múltiples.
Deducción Prolog en lógica funcional
Suma de números naturales
- Representación de los números naturales:
0, s(0), s(s(0)), ...
0 + Y = Y
s(X) + Y = s(X+Y)
suma(0,Y,Y).
suma(s(X),Y,s(Z)) :- suma(X,Y,Z).
Cálculo de sumas
?- suma(s(0),s(s(0)),X).
X = s(s(s(0)))
Cálculo de restas
?- suma(X,s(s(0)),s(s(s(0)))).
X = s(0) ;
false.
Descomposiciones en dos sumandos
?- suma(X,Y,s(s(0))).
X = 0 Y = s(s(0)) ;
X = s(0) Y = s(0) ;
X = s(s(0)) Y = 0 ;
false.
Soluciones de sistemas de ecuaciones
- Consulta: ¿Cuáles son las soluciones del sistema de ecuaciones
1 + X = Y
X + Y = 1
?- suma(s(0),X,Y), suma(X,Y,s(0)).
X = 0 Y = s(0) ;
false.
Bibliografía
- J.A. Alonso (2006) Introducción a la programación lógica con Prolog.
- I. Bratko (1990) Prolog Programming for Artificial Intelligence (2nd ed.)
- Cap. 1: “An overview of Prolog”.
- Cap. 2: “Syntax and meaning of Prolog programs”.
- W.F. Clocksin y C.S. Mellish (1994) Programming in Prolog (Fourth Edition).
- Cap. 1: “Tutorial introduction”.
- Cap. 2: “A closer look”.
R.A. Kowalski (2006) La lógica computacional y el pensamiento humano: cómo ser artificialmente inteligente.
SWISH: SWI-Prolog for SHaring (a SWI-Prolog web IDE).