Ejercicios Tema 2 Programacion Lógica PDF

Preview

Summary

Ejercicios Tema 2 Programacion Lógica, Ejercicios de sintaxis y sem´antica de Prolog...

Description

´n Declarativa Programacio 3er Curso, Grado en Ingenier´ıa en Inform´atica Universidad Rey Juan Carlos

Programaci´on L´ogica TEMA PL-2: EL LENGUAJE PROLOG, ASPECTOS ´ BASICOS Ejercicios de sintaxis y sem´ antica de Prolog 1. Sintaxis: programas Dado el programa en Prolog relativo a amistades (Cuadro 2 del tema PL-2): a) Complete el programa a˜ nadiendo cl´ausulas que representen el siguiente conocimiento: Dolores es amiga de cualquiera que sea enemigo de Abilio o de Blas. Los que son enemigos de Ca´ın y de Abel tambi´en son enemigos de Abilio. b) Suponga que se a˜ nade al programa el siguiente hecho: amigo(abilio, X). Escriba la f´ormula correspondiente en L´ ogica de Primer Orden, y exprese el conocimiento que describe en lenguaje natural. c) Defina el predicado tiene_enemigos(?X), cierto si X tiene alg´ un enemigo. 2. Sintaxis: programas Suponga que la primera cl´ausula del programa l´ogico “puro” para la suma de n´ umeros naturales (Cuadro 4 del tema PL-2) fuese “suma(0,X,X).” en lugar de la dada. ¿C´omo ser´ıa el resto del programa? 3. Sintaxis: programas Escriba un programa l´ogico “puro” capaz de decidir si un n´ umero natural es par. Es decir, implemente el predicado par(?X), cierto si X es par, manejando los n´ umeros naturales mediante la constante cero y la funci´on sucesor s(X) como se ha hecho en los apuntes. 4. Sintaxis: programas Escriba un programa l´ogico “puro” capaz de multiplicar n´ umeros naturales. Puede utilizar para ello la siguiente definici´ on recursiva del producto:

Para cualquier n ∈ N,

n×0= 0

Para cualesquiera n, m ∈ N,

n × (m + 1) = (n × m) + n

El programa podr´ a usar el predicado suma definido en el Cuadro 4 para sumar n´ umeros naturales. 1

5. Sintaxis: consultas Dado el programa en Prolog del tema PL-2 relativo a amistades (Cuadro 2 del tema PL-2): a) Escriba en L´ogica de Primer Orden y en Prolog las siguientes preguntas: ¿Existen pares de personas tales que una es enemiga de la otra? En caso afirmativo, ¿qui´enes son? ¿Tiene Dolores alg´ un enemigo? ¿Qui´enes son los enemigos de Ca´ın, si los tiene? ¿Son Abel y Ca´ın enemigos de una misma persona? En caso afirmativo, ¿de qui´en o qui´enes? b) Para cada una de las siguientes consultas en Prolog, exprese su significado en lenguaje natural: ?????-

amigo(Uno,Dos). enemigo(X,X). enemigo(X,Y), enemigo(X,Z), enemigo(Y,Z). enemigo(_, abel). amigo(Amigo, dolores).

c) Estime cu´ales deber´ıan ser las respuestas a las consultas anteriores, sabiendo que se dispone del conocimiento plasmado en el programa relativo a amistades. Emplee para ello alg´ un m´etodo de demostraci´on para la L´ogica de Primer Orden de los estudiados en la asignatura de L´ ogica, o h´agalo informalmente usando su sentido com´ un. 6. Sem´ antica: Unificaci´on Dadas las sustituciones σ1 = {X/Z, Z/g (Y, Y ), V /Y, T /X }

y σ2 = {Y /V, Z/g (V, V ), T /a},

conteste de forma razonada a las siguientes cuestiones: a) ¿Existe alguna sustituci´on θ tal que σ1 θ = σ2 ? b) ¿Existe alguna sustituci´on θ tal que σ2 θ = σ1 ? 7. Sem´ antica: Unificaci´on Para cada uno de los siguientes pares de expresiones, aplique el algoritmo de Unificaci´on para averiguar si las expresiones son unificables. En caso afirmativo, facilite un unificador de m´axima generalidad. Compare los resultados obtenidos con las respuestas devueltas por Prolog utilizando el predicado de unificaci´ on =. a) {p(W, X, f (g(Y ))), p(Z, f (Z), f (U ))} b) {p(a, X, f (g (Y ))), p(Z, h(Z, U ), f (U ))} c) {p(a, W, X, f (f (X))), p(Z, g (Y ), g (Z), f (Y ))} d ) {q(X, g(Y ), a), q(c, Z, Z )} e) {q(h(X, a), X), q (Y, f (a, c))} 2

8. Sem´ antica: Regla de Resoluci´on Para cada uno de los siguientes pares de cl´ausulas, razone si es posible aplicar la Regla de Resoluci´on, y, en caso afirmativo, calcule la cl´ausula resolvente asociada: ?- r(Z,a), q(a,f(a)).

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

?- q(a,f(a)), r(Z,a).

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

?- q(X,a), p(X), q(b,Y).

q(X,X).

?- r(f(X),X), q(X,Z), r(f(Z),f(f(a))).

r(X,f(Z)) :- p(X,Z), q(Z,X).

´ de Resoluci´ on 9. Sem´ antica: Arbol Dado el programa Prolog p(X,X). p(X,Z) :p(Y,Z), q(X,Y). q(a,b). a) Exprese en lenguaje natural el significado de cada una de las cl´ausulas del programa. b) Dada la consulta “?- p(X,b).”, construya el a´rbol de Resoluci´on correspondiente y deduzca el comportamiento de Prolog ante esta consulta. ¿Qu´e se pretende averiguar con ella? Compare sus resultados con los facilitados por Prolog. ´ de Resoluci´ on 10. Sem´ antica: Arbol Dado el programa l´ogico “puro” para la suma de n´ umeros naturales (cuadro 4 del tema PL-2), construya los a´rboles de Resoluci´on para las consultas “?- suma(X,Y,s(s(0))).” y “?- suma(U,V,W).” ¿Qu´e respuestas dar´ıa Prolog, y en qu´e orden? Compare sus resultados con los facilitados por Prolog. ´ de Resoluci´ on 11. Sem´ antica: Arbol Dado el programa en Prolog del cuadro 2 del tema PL-2 relativo a amistades, construya los a´rboles de Resoluci´on necesarios para establecer qu´e respuestas dar´ıa Prolog, y en qu´e orden, ante las siguientes consultas. Compare sus resultados con los facilitados por Prolog. Explique adem´as en lenguaje natural qu´e se pretende averiguar con estas consultas. ?- amigo(X, Y). ?- amigo(abel, X), amigo(cain, Y), enemigo(X, Y).

3...