PDF de programación - Introduccion Programacion Logica y Prolog

Introducción a la

Programación Lógica

o Revisión histórica, ideas centrales, Prolog.

o Aspectos centrales de un lenguaje de programación
lógica.
. Rasgos distintivos de Prolog respecto de otros lenguajes de

programación.

Introducción a la Programación Lógica

Luis Iraola

Orígenes históricos

. Comienzos de los años 70, R. Kowalski y A. Colmerauer
o Dos usos de la Lógica:

- representación rigurosa del conocimiento
- demostración como algoritmo: Algoritmo = Lógica + Control

o Resultados anteriores de Herbrand, Horn y Robinson (demostración

automática de teoremas)

Prografirá = Algoritmos + Datos

Programa = Reglas + Teoría

Instrucclón #1 1
Inetrueción #Z 7
1v

t

a

a

InstrueeLón

groP

#^ -l
,

1
I

Fó¡uula #1
Fó¡su1a #2

Fórnula #n

Teoreun

I
I

I
I

Introducción a la Programación Lógica

Luis Iraola

HtH,l'@ffih"

Teorema
Canüdato

Denogtración

o Desarrollo de implementaciones eficientes de Prolog a partir de la de Warren
. Normalización de Prolog: ISO 95
. Prolog como lenguaje de proposito general: Prolog puro e impuro.
. Constraint Logic Programming, PARLOG, Datalog, ...

Introducción a la Programación Lógica

Luis Iraola

Ete¡upto No. 1

Conocimiento a representar:

1. Todos los hombres son mortales.
2. Sócrates es un hombre.

A deducir:

Sócrates es mortal.

Representación PROLOG:

Representación LPl:

m o r t a l ( X ) : -

h o m b r e ( X )

h o m b r e ( s o c r a t . e s )

.

V x ( H x

H a

? - m o r t a f ( s o c r a t e s )

.

F M a

lntroducción a la Programación Lógica

Luis Iraola

Eteupto lvo. 2

Conocimiento a representar:

1. El Sol es una estrella.
2. Mercurio orbita en torno al Sol.
3. Venus orbita en torno al Sol.
4. La Luna orbita en torno a la Tierra.
5. La Tierra orbita en torno al Sol.
6. Marte orbita en torno al Sol.
7. Fobos orbita en torno a Marte.
8. Deimos orbita en torno a Marte.
9. Son planetas aquellos cuerpos que orbitan en torno a una estrella.
10. Todo cuerpo que orbita en torno a un planeta es un satélite.
11. Pertenecen a un sistema solar la estrella misma y todo cuerpo que
orbite en torno a otro que pertenezca.

Representación PROLOG:

Representación LPl:

1 . e s t r e l - 1 a ( s o l - )
2 . o r b i t a ( m e r c u r i o , s o l _ ) .
3 . o r b i t a ( v e n u s , s o l - )
4 . o r b i t a ( l u n a , t i e r r a )
5 . o r b i t a ( t i e r r a , s o l ) o
6 . o r b i t a ( m a r t e , s o I )
1 . o r b i t a ( f o b o s , m a r t e )
B . o r b i t a ( d e i m o s , m a r t e ) .
e Pranetiif::rgiíl

:
10 ' sar"::ilt!i",
r, ,
p l a n e t a ( Y ) .
1 1 . p e r t e n e c e ( X , X ) : -
e s t r e l - l a ( X )

p e r t e n e c e ( X , Y ) : -

o r b i t a ( X , Z ) ,
p e r t e n e c e ( Z , Y ) .

1 . E a
2 . O b a
3 . O c a
4 . O d e
5 . O e a
6 . O f a
1 . O g f
B . O h f

( a
( b
( c
( o
( e
( f
( s
( h

S o I )
Mercurio )
Venus )
Luna )
T i e r r a )
Marte )
fobos )
deimos )

9 . V * y ( O x y & E y

1 0 . V * y ( O x y s , P y - > S x )

1 1 . V x ( E x

Y x y z ( O x z & T z y

Introducción a la Programación Lógica

Luis Iraola

Ete¡upto No. 3

Conocimiento a representar:

L. '0' es el numeral que representa al numero cero.
2. La expresión 's(n)' es el numeral del numero sucesor al representado
por la expresión 'n'.
3. Cualquier numero sumado a cero es igual a ese mismo numero.
4. La suma de dos numeros 'n'
's(m)' es igual a 's(j)', siendo 'j' el
I
resultado de sumar '^' y 'm'. I n + s(m) = s(n+m) ]

Representación Prolog:

Representación LPl:

1 . n u m e r o ( O ) .
2 . n u m e r o ( s ( N ) ) : -

n u m e r o ( N )

3 . s u m a ( N / 0 , N ) : -

n u m e r o ( N ) .

4 . s u m a ( N , s ( M ) , s ( J ) ) : -

s u m a ( N , M , J )

Algunos usos de la teoría:

? - n u m e r o ( s ( s ( 0 ) ) ) .
y e s .

? - n u m e r o ( X )
X _ 0
X _ s ( 0 ) - >
s ( s ( o )
T . : -
? * n u m e r o ( 2 ) .
n o ,

1 . N a
2 . V x ( N x

( a : c e r o )

3 . V x ( N x

4 . V x y z ( S x y z

? - s u m a ( 0 , 0 , 0 )
y e s .

? - s u m a ( s ( 0 ) , s ( 0 ) , X )
X _ s ( s ( 0 ) )
y e s .

? - s u m a ( s ( 0 ) , X , s ( s ( 0 ) ) )
X _ s ( 0 )
y e s .

? - s u m a ( X , Y r s ( 0 ) )
X _ s ( 0 ) , Y _ 0
X _ 0 , Y _ s ( 0 ) - >
n o .

Introducción a la Programación Lógica

Luis Iraola

Eteupto No. 4

mortal (X) : - hombre (X) .

hombre(X) -> mortal(X)

?- mortal (socrates) .

-> I
mortal(socrates)

?- hombre (socrares) .

-> tr
hombre(socrates)

{)(/socrates}

hombre (socrates) .

I -> hombre(socrates)

?- hombre (socrates) .

-> I
hombre(socrates)

{ }

y e s .

I - > T

Dada la teoría (programa) T :

{ hombre(X)-> mortal(X), I -> hombre(socrates)

}

y el candidato a teorema (objetivo) C :

mortal(socrates)->

I

ha sido demostrado que T u { C } F I -> I
Luego T l- -C

-( mortal(socrates)->
tr )

mortal(socrates) n -¡
mortal(socrates) n t

moftal(socrates)

Introducción a la Programación Lógica

Luis Iraola

Términos

Consrn rrEs

Nombran individuos (objetos) de la teorfa:

L 2

m a r t e

' A l - e j a n d r o I g l e s i a s l

Venlnates

Toman como valor cualquier expresión:

X

Val-or

A1

Una sustitución 0 es un conjunto finito de pares:

{ v,/t, , vrlI2, ... , vn/L }

donde cada vi es una variable distinta del resto, y cada I es un
término en el que no aparece V.

Exp n e g o ¡t es F u u ct o¡t n¿Es

Nombran objetos mediante la composición de otros más simples

3 + 2 p a d r e ( ' A I e j a n d r o

I g l e s i a s | ) d e r i v a d a ( 2 * x ^ 2 + 3 * x )

En general, siendo'f'un símbolo funcional n-ádico y siendo t.,...q
términos, la expresión:

es un término.

f(t.| ,. ..,tn)

Introducción a la Progranación

Iógica

Luis Iraola

Cláusulas

Fórmulas compuestas a partir de fórmulas atómicas según el esquema:

VX,... xm ( (A.' A ... ^ An) -> B)

donde B, A., ... Anson fórmulas atómicas y xr... xmson todas las variables que
aparecen en ellas.

Reates

Hecnos

A r ^ . . . A A h - > B
B : - A ' , . . . , , \ .

h e r m a n o ( X , Y ) : - p a d r e ( Z , X ' ) , p a d r e ( Z r y ) .

I - > B

p l a n e t a ( t j - e r r a ) .

d i v i s i b l - e

( N , 1 ) .

c a s a d o s ( b i l l - , h i l a r y )

.

Oa¿envos

A r A . . . A A h - > t r

: - d i v i s i b l e

( 3 , 1 ) .

? - p l a n e t a ( X ) .

Introducción a la Programación I'ógca

Luis Iraola

Fórmulas atómicas

Reciben un valor de verdad

m a y o r ( 3 , 2 )

c a s a d o s ( b i l l , h i l a r y )

p l a n e t a ( m a r t e )

En general, siendo'p'un símbolo predicativo n-ádico y siendo t1...q
términos, la expresión:

es una fórmula atómica. Conviene incluir tambien como fórmulas
atómicas los signos f y !, que reciben siempre los valores verdadero
falso respectivamente.

P(tr,...'il)

Unificación

Dos fórmulas atómicas A y B unifican si y sólo si hay una sustitución
0 tal que (A)0 es idéntica a (B)0.

Ejemplos:

p(x) unifica con p(a) bajo 0 = { xla } : (p(X))O es idéntico a (p(a))O.
p(a) no unifica con p(b)

p(X,a) unifica con p(b,Y) bajo 0 = { )(/b, Ylal
p(X) unifica con p(Y) bajo 0 = { XAr }
b a j o 0 ' = t X f )
bajo 0" = { Xla, Y/a }
bajo 0"' = { X/c, Y/b }

Introducqión a la Programación LóStca

Luis Iraola

Regla de Resolución

Unica regla deductiva empleada en una demostración
forma general establece:

/ computación. En su

A r 4 . . . ' r A n - > B

B ' A . . . A B ¡ - . , A B ¡ A B ¡ * , A . . . B r - > t r

( B' ,l ... ,r B¡-r ^ Ar A ... n An A Bi*r A ... B,n )0-> n

(B)0 = (B¡)0

tal y como la aplica Prolog:

A r A . . . A A n - > B

B . , A B z A . . . A B r - > [

( A'' r., ... A An ^ Bz ,r ... B, )0 -> n

(B)0 = (81)0

casos pafticulares son:

I - > B

B , ^ B z ^ . . . A B , ' , ' , - > [

(B)0 = (B1)0

( B r A . . . B , n ) 0 - > t r

r - > B

8 1 - > t r

r - > n

(B)0 = (81)0

Introducción a la Programación Llrgea

Luis Iraola

E¿eupto No. 5

p l a n e t a ( X ) : - o r b i t a

( X , Y ) , e s t r e t l a

( y )

? - p l a n e t a ( P ) .

orbita(X,Y) n estrella(Y) -> planeta(X)
planeta(P) -> tr

OUP}

? - o r b i t a ( P , Y ) , € s t r e t t a

( Y )

orbita(P,Y) ^ estella(Y) -> E

o r b i t a ( t i e r r a , s o l ) .

I -> orbita(tierra,sol)

? - o r b i t a ( P , Y ) , € s t r e l l _ a

( y )

orbita(P,Y) nVstrella(Y) -> [

{P/tierra,Y/sol}

? - e s t r e l l a ( s o l )

I n estrella(sol) -> n

e s t r e l - 1 a ( s o 1 ) .

? - e s t r e l l a ( s o l )

y e s .
P :

t i e r r a

I -> estrella(sol)

estrella(sol) -> n
{ }

r - > n

I -> orbita(tierra,sol),

I -> estrella(sol) }

T = { orbita(X,Y) ^ estrella(Y) -> planeta(X),
T u { planeta(P) -> n } l- I -> tr
T l- - vP ( planeta(P) -> n )
T l- lP-( planeta(P) -> r )
T l- lP( planeta(P) ,.. -fi )
T l- 3P planeta(P)

Introd.ucción a la Programación Lógica

Luis Iraola

a -



.

.

.



-

i orbita(tierra,sol): :
1 . . ' .
i orbita(luna,tbrra).

a

t

. ' . t

. ' .

i p"'A#ii, li' : ;;iñr r l'm'
! pertenece(X,Y):- orbita(X,2),pertenece(Z,Y).
: " . . '

i
¿ o ¡ ¡ r r o r

I
I

? - p e r t , e n e c e { l u n a , s o 1 )

- -

- . . . . )

L . 2

? - o r b i E , a ( l u n d , Z t ) , p e r t , e n e c . e ( Z t , s o 1 )
sustltución

¿ (Xtl luna , Ytf sol)

L . 2

1 : ? - o r b i t a ( l u n d , Z t )
sustltución

'
: { Ztl Elarra } <-

" " t

l- orbit,a (1una, tierra )

,.

L . 2

2 z ? - p e r t , e n e c e ( t i e r r a , s o l

) - - r

2 . L : ? - E . i e r r a = s o l
f r a c a g o

! . 2 . 2 . L

d e

. . . . . ' . - . - " "

L . 2

t . 2

2 . 2 : ? - o r b i t ' a ( E i e r r a , Z z | , p e r t ' e n e c e ( Z z ,