11 /42/42

Mg. Samuel Oporto Díaz Lima, 9 de mayo 2005

Programación Lógica: Semántica

INTELIGENCIA ARTIFICIAL Y SISTEMAS EXPERTOS

22 /42/42

Tabla de Contenido

1. Semántica

2. Bibliografía

33 /42/42

SINTAXIS Y SEMÁNTICA

44 /42/42

Átomos

• Los átomos (o constantes simbólicas) pueden tomar los siguientes nombres:– Cadenas de letras, dígitos y guión bajo, comenzando

por una letra minúscula: juan, x, el_pais

– Cadenas de caracteres especiales: + - * / < > = : . & _ ~: <===>, --->, .:., ::=, ...

– Cadenas de caracteres entre comillas simples: 'El_Salvador', 'Nueva_Guinea', 'Juan'

55 /42/42

Números

• Enteros: 1, 34, -5, 0• Reales: 3.14, -0.0035, 100.2

– No son muy utilizados, pues Prolog es un lenguaje de programación simbólica.

66 /42/42

Variables• Cadenas de letras, dígitos y guión bajo, que comienzan

con letra mayúscula, o con el guión bajo:

X Result _ Lista_de_tareas _x23

• El nombre _ está reservado para variables "anónimas".

• El alcance de una variable es en la cláusula (excepto _):

abuelo(X,Y) :- padre(X,Z), padre(Z,Y).

padre(X,Y) :- hijo(Y,X).

padreEHijo(X) :- padre(X,_), padre(_,X).

77 /42/42

Variables y Constantes

Variables• Se inician con mayúscula.

constantes• Se inician con minúscula o con _• Si el objeto no interesa, entonces usa la variable anónima

(_)

88 /42/42

Estructuras

• Son objetos que tienen varios componentes.– La estructura ha de tener un nombre (functor)– El functor tiene atributos: los elementos de la

estructura.

• Por ejemplo:– date(1, mayo, 2001): puede usarse para

representar el 1 de mayo de 2001– date(Dia, mayo, 2001): para representar

cualquier día de mayo de 2001.

99 /42/42

Ejercicios• ¿Cuáles de los siguientes son objetos

morfológicamente correctos?1. Diana2. diana3. _diana4. 'Diana'5. 'Diana se va al sur'6. va(diana, sur)7. 458. 5(x,y)9. +(north, west)10.three(Black(Cats))

11. f12. vacio13. juan_perez14. ‘Juan Perez’15. A23216. 2meses17. Vacio18. juan-perez19. _juan20. 223b

1010 /42/42

Unificación (I)

• Dados dos términos, decimos que unifican si:– Son idénticos, o– Las variables de los dos términos se pueden

instanciar a objetos de manera que los dos términos lleguen a ser idénticos.

• Ejemplo: date(D,M,2001) date(D1, mayo, A1)D = D1

M = mayo

A1 = 2001

1111 /42/42

Unificación (II)

• Siempre se escoge la unificación más general:date(D,M,2001) date(D1, mayo, A1)

D = D1 D = 1 D = siete

M = mayo D1 = 1 D1 = siete

A1 = 2001 M = mayo M = mayo

A1 = 2001 A1 = 2001

1212 /42/42

Unificación (III)

• Las reglas generales de la unificación son:– Si S y T son constantes, han de ser el mismo objeto.

– Si S es una variable y T es cualquier cosa, unifican (S se instancia a T); y viceversa.

– Si S y T son estructuras, unifican siempre y cuando:• El nombre del functor sea el mismo• Todos sus atributos unifican

variable

constante

1313 /42/42

Ejemplo

date(D, mes(M), 2001)

date(D1, mes(mayo), A1)

date(15, mes(M), Y)

_________________

date(15,mes(mayo),2001)

D = D1 = 15

M = may

A1 = Y = 2001

1414 /42/42

Semántica declarativa

• Los programas en Prolog se pueden entender como teorías lógicas:

P :- Q, R

Si Q y R son ciertos, P es cierto

• Un objetivo G se cumple si:– Existe una cláusula C en el programa tal que:

• Existe una instancia I de C tal que1. La cabeza de I es idéntica a G

2. Todos los objetivos en el cuerpo de I son ciertos

1515 /42/42

Semántica declarativa: ejemplo

• Objetivo G: abuelo(juan, Nieto).• Cláusula C:

abuelo(X,Y) :- padre(X,Z), padre(Z,Y)

• Instancia I:abuelo(juan,marta) :- padre(juan,luis),

padre(luis,marta)

– La cabeza de I es idéntica a G.– Los objetivos en el cuerpo de I todos se cumplen.

1616 /42/42

Semántica procedimental

• Se refiere a la manera en que Prolog resuelve los objetivos.– Las cláusulas de la BD están en un cierto orden.– Se selecciona siempre la primera disponible. Si no se

llega a la solución, se da marcha atrás (backtracking) y se busca otra.

– El orden de las cláusulas puede afectar a la ejecución, especialmente a la eficiencia.

1717 /42/42

Peligro de bucle infinito

• Si tenemos una cláusula del tipo:padre(X,Y) :- padre(X,Y)

• Aunque lógicamente correcta, puede meter al intérprete en bucle cerrado.

1818 /42/42

• Definiendo predicados recursivos, hay que tener cuidado en poner la condición de finalización en primer lugar.

pred(X,Y) :- pred(Z,Y), parent(X,Z).pred(X,Y) :- parent(X,Y).

pred(X,Y) :- parent(X,Z), pred(Z,Y).pred(X,Y) :- parent(X,Y).

pred(X,Y) :- parent(X,Y).pred(X,Y) :- pred(Z,Y), parent(X,Z).

pred(X,Y) :- parent(X,Y).pred(X,Y) :- parent(X,Z), pred(Z,Y).

Peligro de bucle infinito

pred2(juan,marta)

1919 /42/42

LISTAS

2020 /42/42

Listas (I)

• Una lista es una secuencia de elementos (átomos, estructuras, o listas).

• Se representan entre corchetes:[juana, tenis, carlos, futbol]

• Una lista vacía se representa como:

[]

2121 /42/42

Listas (II)

• La representación interna es con una estructura llamada ".", con dos elementos: cabeza y cola:.(juana, .(tenis, .(carlos, .(futbol,[]))))

.(tenis, .(carlos, .(futbol,[])))

.(carlos, .(futbol,[]))

.(futbol,[])

[]

• La cola de toda lista puede ser:– Otra lista, usando el functor “.”– La lista vacía [].

2222 /42/42

Listas (III) - Ejemplo

?- List1 = [a,b,c],

List2 = .(a, .(b, .(c, []))),

List3 = [a,List1,List2].

List1 = [a,b,c]

List2 = [a,b,c]

List3 = [a,[a,b,c],[a,b,c]]

2323 /42/42

Separación de la cabeza y la cola• Se puede especificar explícitamente la

separación entre la cabeza y la cola, mediante una barra vertical:

?- L = [a,b,c], R = [cabeza|L]L = [a,b,c]R = [cabeza,a,b,c]

?- L=[a,b,c], R=[el1,el2|L], U=[a|[]]L = [a,b,c]R = [el1,el2,a,b,c]U = [a]

2424 /42/42

Operaciones con listas (I)• Miembro de una lista: miembro(X, [X|Tail]).

miembro(X, [Head|Tail]) :-

miembro(X, Tail).

?- miembro(a, [a,b,c]).

yes

?- miembro([b,c], [a,[b,c]]).

yes

?- miembro(b, [a,[b,c]]).

no

2525 /42/42

Ejercicio

• Diseña una regla para determinar si un elemento pertenece a una lista o no.

• Sugerencia, una carta esta en un mazo de cartas si es la primera carta o si está en el resto.

miembro(E,L) :- L=[X|Y],X=E.

miembro(E,L) :- L=[X|Y],miembro(E,Y).

2626 /42/42

Ejercicio

• Diseña una regla para determinar si una variable es una lista o no.es_lista([]).

es_lista([_|_]).

• Diseña una regla para determinar el tamaño de una lista.nel([],0).

nel([X|Y]):-nel(Y,M),N is M+1.

2727 /42/42

Operaciones con listas (II)

• Concatenación: conc([], L, L).

conc([X|L1], L2, [X|L3]) :-

conc(L1,L2,L3).

?- conc([a,b,c],[1,2,3],L).

L = [a,b,c,1,2,3]

?- conc([a,b],L2,[a,b,[],c]).

L2 = [[],c]

2828 /42/42

Operaciones con listas (II)?- conc(L1,L2,[a,b]).L1=[]L2=[a,b] ;

L1=[a]L2=[b] ;

L1=[a,b]L2=[] ;

no

2929 /42/42

Ejercicio

• Qué valores obtiene el Prolog para la siguiente consulta.

?- conc(Before,[3,X|After],[1,2,3,4,5]).

Before=[1,2]

X=4

After=[5];

3030 /42/42

Ejercicios

• Escribe un predicado para añadir un elemento a una lista.

insertar(E,L1,L2)

• Añadir E en la lista L1 para obtener L2insertar(E,L,[E|L]).

3131 /42/42

Ejercicios

• Escribe un predicado para eliminar un elemento de una lista.

borrar(X,[X|Y],Y).

borrar(X,[Z|L],[Z|M]):-borrar(X,L,M).

L

MZ

Z

LX

M

3232 /42/42

Ejercicio para la casa

• Define el predicado "last" que devuelva el último elemento de una lista, de dos maneras:– Basándose en el predicado "conc"– Sin utilizarlo.

3333 /42/42

OPERADORES

3434 /42/42

Operadores (I)

• Aunque las listas son estructuras .(Head,Tail), se pueden escribir entre corchetes por claridad.

• Otros predicados, también por claridad, se pueden escribir como operadores (p.ej., con notación infija).

• Ejemplo:– +(3, 5)– 3 + 5

3535 /42/42

Operadores (II) - Aritméticos• Existen operadores predefinidos para

operaciones aritméticas+ Suma- Resta* Multiplicación/ División// División entera** Elevación a potenciamod Módulo (resto de división)

3636 /42/42

Operadores (III) - Evaluación

• Los operadores son como cualquier otro predicado de prolog. Por omisión, no se evalúan.?- X = 1 + 2.

X = 1 + 2

• Se puede forzar la evaluación utilizando el operador "is".

?- X is 1 + 2.

X = 3

3737 /42/42

Operadores (IV) – Operador "is"

• El argumento izquierdo ha de ser una variable.• El argumento derecho será una expresión.

Todas las variables en esa expresión han de estar asociadas a valores.

• Los operadores en prolog tienen todos asociado un número de precedencia. Los de menor número se ejecutan antes (ej: ** antes que *, antes que +, antes que is)

3838 /42/42

Operadores (V) - Ejemplo

• Máximo común divisor de dos números:

gcd(X,X,X).

gcd(X,Y,D) :- X < Y,

Y1 is Y – X,

gcd(X, Y1, D).

gcd(X,Y,D) :- Y < X,

gcd(Y,X,D).

3939 /42/42

Ejercicios

• Define un predicado que calcule la longitud de una lista.

• Define un predicado que calcule el menor número dentro de una lista de números.

• Define un predicado con un único argumento, que devuelva "true" si los elementos en esa lista están ordenados.

4040 /42/42

BACKTRACKING

4141 /42/42

Previniendo el backtracking (I)

• Cuando prolog tiene que satisfacer una consulta, prueba todas las posibilidades (realizando backtracking) hasta encontrar las asignaciones de valores que la satisfagan.

• En el intérprete, si se piden más soluciones, se continúan buscando mediante backtracking.

4242 /42/42

Ejemplo (I)

f(x) =

f(X,0) :- X < 3.

f(X,2) :- 3 =< X, X < 6.

f(X,4) :- 6 =< X.

Ejemplo:

?- f(1,Y)

0 si x < 3

2 si x >= 3 y x < 6

4 si x >= 6

4343 /42/42

Ejemplo(II)f(X,0) :- X < 3, !.

f(X,2) :- 3 =< X, X < 6, !.

f(X,4) :- 6 =< X.

:- f(1,Y), 2 < Y.

no

:- f(7,Y).

Y = 4

4444 /42/42

Ejemplo(III)f(X,0) :- X < 3, !.

f(X,2) :- X < 6, !.

f(X,4).

:- f(1,Y).

Y = 0 ;

Y = 2 ;

Y = 4

4545 /42/42

Corte

• Sea G el objetivo a satisfacer.• Si entre los antecedentes de G se encuentra un

corte !,– El corte inmediatamente se da por satisfecho– Todas las alternativas a reglas para G dejan de

considerarse– Todas las alternativas a los antecedentes previos al

corte dejan de considerarse

4646 /42/42

Corte (II)c(X) :- p(X),q(X),r(X),!,s(X),t(X),u(X).c(X) :- v(X).a(X) :- b(X),c(X),d(X).a(maria).

?- a(X).• Suponemos que b(X) se cumple.• Suponemos que p,q,r se cumplen, y la X se instancia a un cierto valor.• ! también se cumple (automáticamente)• Suponemos que s(X) falla. Entonces:

– No se permite intentar otras posibilidades para p(X), q(X) o r(X)– No se permite intentar con la regla c(X) :- v(X).– Sí se permite probar otra posibilidad de a: X se instancia a “maria”

4747 /42/42

Ejemplos usando el corte (I)max(X, Y, X) :- X >= Y.

max(X, Y, Y) :- X < Y.

max(X, Y, X) :- X >= Y, !.

max(X, Y, Y).

Requisito: el tercer argumento no debe estar instanciado. En caso contrario, se pueden obtener resultados no deseados:

?- max(3,1,1).

yes

4848 /42/42

Ejemplos usando el corte (II)

• Añadir elementos a una listaadd(X,L,L) :- member(X,L), !.

add(X,L,[X|L]).

Igual que antes, el tercer argumento no debe estar instanciado al invocar este predicado en el intérprete.

4949 /42/42

Ejercicios (I)

• Sea el siguiente programa Prolog:p(1).

p(2) :- !.

p(3).

Escribir las respuestas a las siguientes consultas:

?- p(X).

?- p(X), p(Y).

?- p(X), !, p(Y).

5050 /42/42

Ejercicios (II)

• La siguiente relación clisifica números en positivos o negativos:

class(Number, positive) :- Number > 0.

class(0, zero).

class(Number, negative) :- Number < 0.

• Defínelo de manera más eficiente usando cortes.

5151 /42/42

Ejercicios (III)

• Escribe, con y sin cortes, el procedimiento “split”, que divide una lista en dos sublistas, la primera con los números positivos, y la segunda con los negativos.

?- split([3,-1,0,5,-2],[3,0,5],[-1,-2]).

yes

5252 /42/42

Negación como fallo

• Para evitar la aplicación de una regla, se puede forzar el fallo con una combinación del corte, y la constante “fail”.– “fail” es un objetivo que nunca se satisface.

• Por ejemplo, “Todos los pájaros, excepto el avestruz y el pingüino, vuelan”:

vuela(X) :- pinguino(X), !, fail.

vuela(X) :- avestruz(X), !, fail.

vuela(X) :- pajaro(X).

5353 /42/42

Comprobación de diferencia:different(X,X) :- !, fail.different(X,Y).

o bien:

different(X,Y) :-X = Y , !, fail

;true.

donde “true” es un objetivo que siempre se cumple.

5454 /42/42

Predicado de negación

not(P) :-

P, !, fail

;

true

Muchos intérpretes de prolog traen el predicado not predefinido, con un operador asociado \+

vuela(X) :- pajaro(X), \+ pinguino(X),

\+ avestruz(X).

5555 /42/42

Problemas con corte y negación

Corte:• Los programas ya no corresponden a la

definición declarativa: el orden de las cláusulas importa, y puede ser necesario forzar a que algún argumento sea una variable no instanciada.

Negación:• No corresponde a una negación lógica, sino al

hecho de que no hay evidencia para demostrar lo contrario.

5656 /42/42

Problema con negación – Ejemplo

• Ejemplo de restaurantes:buena_comida(el_meson).

caro(el_meson).

buena_comida(casa_paco).

razonable(Restaurante) :- \+ caro(restaurante).

?- buena_comida(X), razonable(X).

X = casa_paco

?- razonable(X), buena_comida(X).

no

5757 /42/42

Problema con negación – Causa• En Prolog, una consulta con una variable no instanciada

se satisface si hay al menos una asignación de valores a la variable que la cumpla:

buena_comida(X) -> X = casa_paco

• Al usar la negación, esa consulta pasa a ser cierta si el argumento de la negación fue falso, es decir, si ninguna asignación posible de valores cumplió la fórmula:

not(razonable(X)) = no(existe X tal que X razonable) =

para todo X, X no es razonable

5858 /42/42

Negación - Ejercicioshombre(juan). hombre(carlos).mujer(maria). mujer(laura).padre(juan,maria).padre(juan,carlos).madre(laura,maria).madre(laura,carlos).esposo(juan,laura).esposo(laura,juan).soltero(X) :- \+ esposo(X,Y).sinHijos(X) :- \+ padre(X,Y), \+ madre(X,Z).

?- soltero(juan).?- soltero(carlos).?- soltero(X).?- sinHijos(juan).?- sinHijos(carlos).?- sinHijos(X).?- soltero(X), sinHijos(X).?- hombre(X), soltero(X), sinHijos(X).

5959 /42/42

Bibliografía• AIMA. Capítulo 4, primera edición.• AIMA. Chapter 4, second edition.

6060 /42/42

PREGUNTAS