PDF de programación - Tema 1: El sistema deductivo de Prolog

Programación lógica

Curso 2002–03

Tema 1: El sistema deductivo

de Prolog

José A. Alonso Jiménez

[email protected]
http://www.cs.us.es/∼jalonso

Dpto. de Ciencias de la Computación e Inteligencia Artificial

Universidad de Sevilla

PL 2002–03

CcIa

El sistema deductivo de Prolog

1.1

Objetivos del curso
x Lógica como:
u sistema de especificación y
u lenguaje de programación
x Principios:
u Programas = Teorías
u Ejecución = Búsqueda de pruebas
u Programación = Modelización
x Prolog = Programming in Logic
x Relaciones con otros campos:
u Inteligencia artificial
u Sistemas basados en el conocimiento
u Procesamiento del lenguaje natural

PL 2002–03

CcIa

El sistema deductivo de Prolog

1.2

Declarativo vs. imperativo
x Paradigmas
u Imperativo: Se describe cómo resolver el problema
u Declarativo: Se describe qué es el problema
x Programas
u Imperativo: Una sucesión de instrucciones
u Declarativo: Un conjunto de sentencias
x Lenguajes
u Imperativo: Pascal, C, Fortran
u Declarativo: Prolog, Lisp puro, ML, Haskell
x Ventajas
u Imperativo: Programas rápidos y especializados
u Declarativo: Programas generales, cortos y legibles

PL 2002–03

CcIa

El sistema deductivo de Prolog

1.3

Historia de la programación lógica
x 1960: Demostración automática de teoremas
x 1965: Resolución y unificación (Robinson)
x 1969: QA3, obtención de respuesta (Green)
x 1972: Implementación de Prolog (Colmerauer)
x 1974: Programación lógica (Kowalski)
x 1977: Prolog de Edimburgo (Warren)
x 1981: Proyecto japonés de Quinta Generación
x 1986: Programación lógica con restricciones
x 1995: Estándar ISO de Prolog

PL 2002–03

CcIa

El sistema deductivo de Prolog

1.4

Deducción Prolog en lógica proposicional
x Base de conocimiento y objetivo:
u 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.

u Objetivo: Demostrar a partir de la base de conocimientos que el animal es una

cebra.

PL 2002–03

CcIa

El sistema deductivo de Prolog

1.5

Deducción Prolog en lógica proposicional
x Programa

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.

:- es_ungulado, tiene_rayas_negras. % R1
% R2
% R3
% H1
% H2
% H3

x Sesión

> pl
Welcome to SWI-Prolog (Version 5.0.3)
Copyright (c) 1990-2002 University of Amsterdam.

?- [animales].
Yes

?- es_cebra.
Yes

PL 2002–03

CcIa

El sistema deductivo de Prolog

1.6

Deducción Prolog en lógica proposicional
x Árbol de deducción

PL 2002–03

CcIa

El sistema deductivo de Prolog

1.7

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Deducción Prolog en lógica proposicional
x Demostración por resolución SLD

PL 2002–03

CcIa

El sistema deductivo de Prolog

1.8

es_ungulado :− es_mamifero, tiene_pezuñas.es_cebra :− es_ungulado, tiene_rayas_negras.:− tiene_pezuñas, tiene_rayas_negras.:− es_mamifero, tiene_pezuñas, tiene_rayas_negras.:− es_ungulado, tiene_rayas_negras.:− tiene_rayas_negras.:−.:− es_cebra.tiene_rayas_negras.tiene_pezuñas.es_mamifero.Deducción Prolog en lógica relacional
x Base de conocimiento:
u Hechos 1-4: 6 y 12 son divisibles por 2 y por 3.
u Hecho 5: 4 es divisible por 2.
u Regla 1: Los números divisibles por 2 y por 3 son divisibles por 6.
x 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).

% Hecho 1
% Hecho 2
% Hecho 3
% Hecho 4
% Hecho 5
% Regla 1

PL 2002–03

CcIa

El sistema deductivo de Prolog

1.9

Deducción Prolog en lógica relacional
x Símbolos:
u Constantes: 2, 3, 4, 6, 12
u Relación binaria: divide
u Variable: X
x Interpretaciones de la Regla 1:
u divide(6,X) :- divide(2,X), divide(3,X).
u Interpretación declarativa:
(∀X)[divide(2, X) ∧ divide(3, X) → divide(6, X)]
u Interpretación procedimental
x Consulta:
u ¿Cuáles son los múltiplos de 6?

?- divide(6,X).
X = 6 ;
X = 12 ;
No

PL 2002–03

CcIa

El sistema deductivo de Prolog

1.10

Deducción Prolog en lógica relacional
x Árbol de deducción

x Comentarios:
u Unificación
u Cálculo de respuestas
u Respuestas múltiples

PL 2002–03

CcIa

El sistema deductivo de Prolog

1.11

:− divide(6,X).:− divide(2,X), divide(3,X).:−.:−.:− divide(3,12).:− divide(3,4).:− divide(3,6).Respuesta X=6FalloRespuesta X=12R1H2{X/4}H1 {X/6}H3 {X/12}H4H5Deducción Prolog en lógica funcional
x Representación de los números naturales:
u 0, s(0), s(s(0)), . . .
x Definición de la suma

0 + Y = Y
s(X) + Y = s(X+Y)

x Programa

suma(0,Y,Y).
suma(s(X),Y,s(Z)) :- suma(X,Y,Z).

% R1
% R2

x Consulta:
u Pregunta: ¿Cuál es la suma de s(0) y s(s(0))?
u Sesión:

?- suma(s(0),s(s(0)),X).
X = s(s(s(0)))
Yes

PL 2002–03

CcIa

El sistema deductivo de Prolog

1.12

Deducción Prolog en lógica funcional
u Árbol de deducción:

PL 2002–03

CcIa

El sistema deductivo de Prolog

1.13

:− suma(s(0),s(s(0)),X0).:− suma(0,s(s(0)),Z1).:−.suma(0,Y2,Y2).{Y2/s(s(0)), Z1/s(s(0))}Resp.: X = X0 = s(Z1) = s(s(s(0)))suma(X1,Y1,Z1).{X1/0,Y1/s(s(0)),X0/s(Z1)}suma(s(X1),Y1,s(Z1)) :−Deducción Prolog en lógica funcional
x Consulta:
u ¿Cuál es la resta de s(s(s(0))) y s(0)?
u Sesión:

?- suma(X,s(s(0)),s(s(s(0)))).
X = s(0) ;
No

PL 2002–03

CcIa

El sistema deductivo de Prolog

1.14

Deducción Prolog en lógica funcional
u Árbol de deducción:

PL 2002–03

CcIa

El sistema deductivo de Prolog

1.15

:− suma(X0,s(s(0)),s(s(s(0))).:− suma(X1,s(s(0)),s(s(0))).:−.:− suma(X2,s(s(0)),s(0)).suma(s(X3),Y3,s(Z3)) :−suma(X3,Y3,Z3).{X2/s(X3),Y3/s(s(0)),Z3/0}{X1/0, Y2/s(s(0))}suma(0,Y2,Y2).Resp: X=X0=s(X1)=s(0):− suma(X3,s(s(0)),0).Fallosuma(s(X1),Y1,s(Z1)) :−suma(X1,Y1,Z1).{X0/s(X1),Y1/s(s(0)),Z1/s(s(0))}suma(s(X2),Y2,s(Z2)) :−suma(X2,Y2,Z2).{X1/s(X2),Y2/s(s(0)),Z2/s(0)}Deducción Prolog en lógica funcional
x Consulta:
u Pregunta: ¿Cuáles son las soluciones de la ecuación
u Sesión:

X + Y = s(s(0))?

?- suma(X,Y,s(s(0))).
X = 0
X = s(0)
X = s(s(0))
No

Y = s(s(0)) ;
Y = s(0) ;
Y = 0 ;

PL 2002–03

CcIa

El sistema deductivo de Prolog

1.16

Deducción Prolog en lógica funcional
u Árbol de deducción:

PL 2002–03

CcIa

El sistema deductivo de Prolog

1.17

:− suma(X0,Y0,s(s(0))).:−.R2 {X0/s(X1), Y1/Y0, Z1/s(0)}:− suma(X1,Y0,s(0)).R1 {X1/0, Y2/s(0), Y0/s(0)}X=s(0)Y=s(0)R2 {X1/s(X2), Y2/Y0, Z2/0}R1 {X2/0, Y3/0, Y2/0}R1 {X0/0, Y1/s(s(0)), Y0/s(s(0)).:−.X=0Y=s(s(0)):− suma(X2,Y0,0).:−.X=s(s(0))Y=0Deducción Prolog en lógica funcional
x Consulta:
u Pregunta: resolver el sistema de ecuaciones

1 + X = Y
X + Y = 1

u Sesión:

?- suma(s(0),X,Y), suma(X,Y,s(0)).
X = 0
Y = s(0) ;
No

PL 2002–03

CcIa

El sistema deductivo de Prolog

1.18

Deducción Prolog en lógica funcional
u Árbol de deducción

PL 2002–03

CcIa

El sistema deductivo de Prolog

1.19

:− suma(s(0),X0,Y0) suma(X0,Y0,s(0)).:− suma(0,X0,Z1), suma(X0,s(Z1),s(0)).:− suma(X0,s(X0),s(0)).:−.X=0Y=s(0):− suma(X3,s(X0),0).R2 {X1/0, Y1/X0, Y0/s(Z1)}R1 {Z1/X0}R1 {X0/0}FalloR2 {X0/s(X3),Y3/s(X0),Z3/0}Bibliografía
x Alonso, J.A. y Borrego, J. Deducción automática (Vol. 1: Cons-

trucción lógica de sistemas lógicos) (Ed. Kronos, 2002)
www.cs.us.es/~jalonso/libros/da1-02.pdf

(Addison–Wesley, 1990)

u Cap. 2: Introducción a la programación lógica con Prolog.
x Bratko, I. Prolog Programming for Artificial Intelligence (2nd ed.)
u Cap. 1: “An overview of Prolog”
u Cap. 2: “Syntax and meaning of Prolog programs”
x Clocksin, W.F. y Mellish, C.S. Programming in Prolog (Fourth Edi-
u Cap. 1: “Tutorial introduction”
u Cap. 2: “A closer look”

tion) (Springer Verlag, 1994)

PL 2002–03

CcIa

El sistema deductivo de Prolog

1.20