CIENCIA DE LA COMPUTACION

Lógica para Cs. de la Computación

Material Adicional

Repaso
• En el paradigma de la programación en lógica sólo se
debe describir el problema considerado.
• La solución será encontrada al interpretar el programa
lógico asociado.
• Un programa lógico describe un conjunto de relaciones
entre objetos.
• Se compone de hechos y reglas.
• Las consultas permiten explorar las relacionesdefinidas
por un programa lógico.

PROLOG
PROgramación en LÓGica
Lógica para Ciencias de la Computación
Primer Cuatrimestre de 2013
– Material Adicional –

2

Sintaxis Formal

Estructuras y Listas

programa ::= cláusula . | cláusula . programa
cláusula ::= predicado | predicado :- predicados
predicados ::= predicado | predicado , predicados
predicado ::= nombre | nombre ( términos )términos ::= término | término , términos
termino ::= nombre | variable | lista | estructura
estructura ::= nombre ( términos )
lista ::= [ términos ] | [ términos | lista ] | [ ]

• Las estructuras se asemejan a los predicados en su
forma, pero no en su rol: son objetos, y por lo tanto
aparecen como argumentos a predicados.
• Las estructuras pueden contener estructuras.
• Las listasson un tipo especial de estructura.

padre_de(homero, bart).

Programa

hermanos(X,Y):- padre_de(P, X), padre_de(P, Y).

3

4

Sustitución

Estructuras

1. padre_de(homero, bart).

cliente (homero, simpson, av_s_viva, 742).

2. padre_de(homero, lisa).
3. hermanos(X,Y):- padre_de(P, X), padre_de(P, Y).

cliente (nom(homero, simpson),
calle(av_s_viva), nro(742) ).
cliente(nom(homero, simpson),
dir(calle(av_s_viva), nro(742) )).
5

-

?- hermanos(bart, lisa).
yes
¿Como lo prueba prolog?
Mediante la regla 3, sustituyendo X por bart, Y por
6
lisa y P por homero, y empleando los hechos 1 y 2.

1

Lógica para Cs. de la Computación

Material Adicional

Ejemplos

Sustitución

De acuerdo a la definición formal, ¿cuáles de los
siguientes conjuntosconstituyen sustituciones?

Def.: Una sustitución es un conjunto finito de
pares ordenados [Xn, Tn] donde Xn es una
variable y Tn es un término, tales que:

θ1 = { [X/bart], [Y/lisa]}
θ2 = { [X/bart], [X/moe]}

– para cada i ≠ j, se verifica que Xi ≠ Xj, y
– para todo valor posible de i, j, se debe cumplir que
Xi no aparezca en Tj.

θ3 = { [X/Q], [Y/lisa]}
θ4 = { [bart/lisa]}
θ5 = {[X/bart], [Y/X]}

Terminología: Aplicar una sustitución consiste en
efectuar los reemplazos correspondientes.
7

¡Sólo θ1y θ3 respetan la
definición anterior!

Instanciación

θ = {[X/a]}
s(a) = s(X)θ

t(X)

= hermanos(bart, lisa)
hermanos(X, X) θ1
= hermanos(bart, bart)
hermanos(X, Y) θ3
= hermanos(Q, lisa)
8

Instanciación

Def.: Sean A y B sendos términos. Diremos que A
esuna instancia de B si, y sólo si, existe una
sustitución θ tal que A = Bθ.

s(X)

hermanos(X, Y) θ1

t(Y)

• Resumiendo, sean A y B sendos términos:
– A puede ser instancia de B, pero B no ser
instancia de A.
– A puede ser instancia de B y B instancia de
A.
– B puede ser instancia de A, pero A no ser
instancia de B.
– A puede no ser instancia de B, ni B de A.

A

B

s(a)s(X)
s(U) s(V)
Idem al
primero

s(a) s(b)
f(X,b) f(a, Y)

s(a)

t(Y)

• Notemos que si A es una instancia de B, B es
más general que A.

t(X)
9

10

¿Qué respondería PROLOG?

Intérprete Abstracto
1.
2.
3.
4.

• La ejecución de cualquier programa Prolog
puede ser simulada mediante un intérprete
abstracto, donde:
– ENTRADA: Un programa lógico P y una consulta
fija G.
–SALIDA: YES si G es satisfecha por P; NO en caso
contrario.

• Terminología: Una consulta fija es una consulta
sin variables.
11

-

p(X) :- q(X), r(b).
r(b):- s(b).
q(a).
s(b).

?- p(a).
yes
¿Como nos damos cuenta que p(a) es satisfecha por
el programa?
Para el siguiente algoritmo tener presente que un
hecho puede verse como una regla con cuerpo vacío.
12

2

Lógica...