PDF de programación - Tema 1: Introducción a Prolog

Imágen de pdf Tema 1: Introducción a Prolog

Tema 1: Introducción a Prologgráfica de visualizaciones

Publicado el 6 de Agosto del 2017
372 visualizaciones desde el 6 de Agosto del 2017
117,5 KB
22 paginas
Creado hace 18a (20/10/2002)
Programación Declarativa

Curso 2000–2001

Tema 1: Introducción a Prolog

José A. Alonso Jiménez
Miguel A. Gutiérrez Naranjo

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

Universidad de Sevilla

PD 2000–01

CcIa

Introducción a Prolog

1.1

gramación

Objetivos del curso
x Lógica como especificación y lenguaje de pro-
x Prolog = Programming in Logic
x Relaciones con otros campos:
u Bases de datos
u Sistemas basados en el conocimiento
u Procesamiento del lenguaje natural
u Inteligencia artificial
x Pensar declarativamente

PD 2000–01

CcIa

Introducción a 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

PD 2000–01

CcIa

Introducción a Prolog

1.3

Historia
x -350: Grecia clásica (Aristóteles,...)
x 1930: Edad de oro de la lógica (G¨odel)
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

PD 2000–01

CcIa

Introducción a Prolog

1.4

Un ejemplo simple: divisibilidad
x Problema: Escribir un programa para declarar

que 2 divide a 6 y utilizarlo para responder a
las siguientes cuestiones:

u ¿2 divide a 6?.
u ¿3 divide a 12?.
u ¿Cuáles son los múltiplos de 2?.
u ¿Cuáles son los divisores de 6?.
u ¿Cuáles son los elementos X e Y tales que X divide a
x Programa: divisibilidad-1.pl

Y?.

divide(2,6).

x Sesión

?- divide(2,6).
Yes
?- divide(3,12).
No
?- divide(2,X).
X = 6
Yes
?- divide(X,Y).
X=2
Y=6
Yes

PD 2000–01

CcIa

Introducción a Prolog

1.5

Un ejemplo simple: divisibilidad
x Conceptos
u Relación: divide/2
u Nombre de una relación: divide
u Argumentos de una relación
u Hecho
u Programa
u Constante: 2, 6
u Variable: X, Y
u Objetivo
u Objetivo satisfacible
u Respuesta

PD 2000–01

CcIa

Introducción a Prolog

1.6

Unificación
x Ejemplos de unificación

divide(2,6) divide(2,X)

{X/6}

divide(2,6)

divide(X,6) divide(2,Y}

{X/2, Y/6}

divide(2,6)

divide(X,6) divide(2,X)

divide(2,6) divide(X,X)

No unif.

No unif.

divide(X,6) divide(Y,Z)

{X/4, Y/4, Z/6} divide(4,6)

divide(X,6) divide(Y,Z)

{X/Y, Z/6}

x Unificador de máxima generalidad (u.m.g.)

divide(4,6)

PD 2000–01

CcIa

Introducción a Prolog

1.7

Ampliación del programa
x Problema: Ampliar el programa anterior,

añadiéndole que 2 divide a 12 y que 3 divide
a 6 y a 12 y utilizarlo para responder a las si-
guientes cuestiones:

u ¿Cuáles son los elementos X e Y tales que X divide a
u ¿Cuáles son los múltiplos de 2 y de 3?
x Programa: divisibilidad-2.pl

Y?

divide(2,6).
divide(2,12).
divide(3,6).
divide(3,12).

x Sesión

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

PD 2000–01

CcIa

Introducción a Prolog

1.8

Ampliación del programa
x Conceptos:
u Pregunta cerrada
u Pregunta abierta
u Pregunta compuesta
u Respuesta
u Respuestas múltiples
u Literal seleccionado

PD 2000–01

CcIa

Introducción a Prolog

1.9

Reglas
x Problema: Ampliar el programa anterior

añadiéndole que los números divisibles por 2
y por 3 son divisibles por 6 y utilizarlo para
responder a las siguientes cuestiones:

u ¿Cuáles son los múltiplos de 6?
u ¿Cuáles son los elementos X e Y tales que X divide a
x Programa: divisibilidad-3.pl

Y?

divide(2,6).
divide(2,12).
divide(3,6).
divide(3,12).
divide(6,X) :-

divide(2,X),
divide(3,X).

divide(6,X) :- divide(2,X), divide(3,X).

x Interpretación de cláusulas
u Cláusula:
u Fórmula:
(∀X)[divide(2, X) ∧ divide(3, X) → divide(6, X)]
u Interpretación declarativa
u Interpretación procedimental

PD 2000–01

CcIa

Introducción a Prolog

1.10

Reglas
x Sesión

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

Y = 6 ;
Y = 12 ;
Y = 6 ;
Y = 12 ;
Y = 6 ;
Y = 12 ;

x Conceptos:
u Cláusulas: hechos, reglas y preguntas
u Reglas: cabeza y cuerpo

PD 2000–01

CcIa

Introducción a Prolog

1.11

Resolución
x Modus ponens
A → B
A
B

x Resolución (I)
A ∨ B
¬A ∨ C
B ∨ C
x Resolución (II)
A ← B1, . . . , Bn
← A, C1, . . . , Cm
← B1, . . . , Bn, C1, . . . , Cm
x Resolución (III): Si A1θ = A2θ con θ u.m.g.
A1 ← B1, . . . , Bn
← A2, C1, . . . , Cm
← (B1, . . . , Bn, C1, . . . , Cm)θ

PD 2000–01

CcIa

Introducción a Prolog

1.12

Resolución en lógica proposicional
x Programa: leche.pl

es_leche :-

parece_leche,
lo_da_la_vaca.

parece_leche :-

es_blanco,
hay_una_vaca_en_la_etiqueta.

lo_da_la_vaca.
es_blanco.
hay_una_vaca_en_la_etiqueta.

x Sesión

?- es_leche.
yes

x Traza

(1) 0 CALL es_leche?
(2) 1 CALL parece_leche?
(3) 2 CALL es_blanco?
(3) 2 EXIT es_blanco
(4) 2 CALL hay_una_vaca_en_la_etiqueta?
(4) 2 EXIT hay_una_vaca_en_la_etiqueta
(2) 1 EXIT parece_leche
(5) 1 CALL lo_da_la_vaca?
(5) 1 EXIT lo_da_la_vaca
(1) 0 EXIT es_leche

PD 2000–01

CcIa

Introducción a Prolog

1.13

Demostración SLD

:- es leche.

es leche :- parece leche, lo da la vaca.

:- parece leche, lo da la vaca.

parece leche :-

es blanco,
hay una vaca en la etiqueta.

?

)
9

?

?

9
9
)?

?

:- es blanco,
hay una vaca en la etiqueta.
lo da la vaca.

es blanco.

:- hay una vaca en la etiqueta,
lo da la vaca.

:- hay una vaca en la etiqueta.

:- lo da la vaca.

lo da la vaca.



x SLD:
u S: regla de Selección
u L: resolución Lineal
u D: cláusulas Definidas

PD 2000–01

CcIa

Introducción a Prolog

1.14

Traza
x Problema: Utilizar el programa anterior para

calcular los divisores de 6 con el dispositivo
trace y construir el árbol de deducción.

[1] divide(2,6).
[2] divide(2,12).
[3] divide(3,6).
[4] divide(3,12).

x Arbol de resolución SLD

[5] divide(6,X) :-
divide(2,X),
divide(3,X).

PD 2000–01

CcIa

Introducción a Prolog

1.15

?-divide_a(6,X).?- divide_a(2,X), divide_a(3,X).?-divide_a(3,6).?-divide_a(3,12).[5][1][2][3][4]{X/6}{X/12} Traza
x Programa

[1] divide(2,6).
[2] divide(2,12).
[3] divide(3,6).
[4] divide(3,12).

x Traza:

?- trace(divide).

[5] divide(6,X) :-
divide(2,X),
divide(3,X).

divide/2: call redo exit fail

Yes
?- divide(6,X).
T Call: ( 7) divide(6, _G260)
T Call: ( 8) divide(2, _G260)
T Exit: ( 8) divide(2, 6)
T Call: ( 8) divide(3, 6)
T Exit: ( 8) divide(3, 6)
T Exit: ( 7) divide(6, 6)
X = 6 ;
T Redo: ( 8) divide(3, 6)
T Fail: ( 8) divide(3, 6)
T Redo: ( 8) divide(2, _G260)
T Exit: ( 8) divide(2, 12)
T Call: ( 8) divide(3, 12)
T Exit: ( 8) divide(3, 12)
T Exit: ( 7) divide(6, 12)
X = 12 ;
No

PD 2000–01

CcIa

Introducción a Prolog

1.16

Reglas recursivas: naturales.pl
x Problema: Los números naturales se forman a

partir del cero y la función sucesor. De forma
más precisa:
* El 0 es un número natural
* Si n es un número natural, s(n) también lo es
Escribir un programa para decidir si una ex-
presión es un número natural y utilizarlo para
responder a las siguientes cuestiones:

u ¿Es s(s(0)) un número natural?
u ¿Es 2 un número natural?
u ¿Cuáles son los números naturales?
x Programa: naturales.pl

nat(0).
nat(s(X)) :-

nat(X).

PD 2000–01

CcIa

Introducción a Prolog

1.17

Reglas recursivas: naturales.pl
x Sesión

?- nat(s(s(0))).
Yes
?- nat(dos).
No
?- nat(X).
X = 0 ;
X = s(0) ;
X = s(s(0)) ;
X = s(s(s(0))) ;
X = s(s(s(s(0))))
Yes

x Conceptos:
u Regla recursiva
u Símbolos de función
u Términos
u Infinitas respuestas

PD 2000–01

CcIa

Introducción a Prolog

1.18

Reglas recursivas: naturales.pl
x Arbol de resolución SLD

(I) nat(0).
(II) nat(s(X)):-nat(X).

:-nat(N ).



Z





Z

Z





Z

Z

(II)

θ2 = {N → s(X1)}

Z

Z

Z

ZZ~

:-nat(X1).

(I)

θ1 = {N → 0}







=


RC1 = {N → 0}

(I)

θ21 = {X1 → 0}







=


RC2 = {N → s(0)}



Z



Z

Z

Z

Z







(II)

θ22 = {X1 → s(X2)}

Z

Z

Z

ZZ~

:-nat(X2).



Z



Z







Z

Z

Z

(I)

θ221 = {X2 → 0}







=


RC3 = {N → s(s(0))}

θ222 = {X2 → s(X3)}

(II)

Z

Z

Z

ZZ~
. . .

PD 2000–01

CcIa

Introducción a Prolog

1.19

Reglas recursivas: suma.pl
x Problema: Definir el predicado suma(X,Y,Z)

de forma que si X e Y son dos números
naturales con la representación del programa
naturales.pl, entonces Z es el resultado de
sumar X e Y. Por ejemplo,

suma(s(0),s(s(0)),X) => X=s(s(s(0)))

Utilizarlo para responder a las siguientes cues-
tiones:

u ¿Cuál es la suma de s(0) y s(s(0))?
u ¿Cuál es la resta de s(s(s(0))) y s(0)
u ¿Cuáles son las soluciones de la ecuación X + Y =
x Programa: suma.pl

s(s(0))?

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

PD 2000–01

CcIa

Introducción a Prolog

1.20

Reglas recursivas: suma.pl
x Sesión

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

PD 2000–01

CcIa

Introducción a Prolog

1.21

Intelligence (2nd ed.) (Addison–Wesley, 1990)

Bibliografía
x Bratko, I. Prolog Programming for Artificial
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

ligence (John Wiley, 1990)

in Prolog (Fourth Edition) (Springer Verlag,
1994)

u Cap. 1: “Tutorial introduction”
u Cap. 2: “A closer look”
x Shapiro, S.C. Encyclopedia of Artificial Intel-
u “Logic programming” (por R.A. Kowalski y C.J. Hog-
x Van Le, T. Technique
  • Links de descarga
http://lwp-l.com/pdf6143

Comentarios de: Tema 1: Introducción a Prolog (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad