Ejemplos Prolog 5x5y1e

FUNDACIÓN UNIVERSITARIA KONRAD LORENZ-PROGRAMA DE INGENIERÍA DE SISTEMAS CURSO DE SISTEMAS BASADOS EN EL CONOCIMIENTO 1 PROFESOR: PERVYS RENGIFO RENGIFO AUTOR: FELIPE FORERO INGENIERIA DE SISTEMAS VIII SEMESTRE 2007-I

1) Elabore un programa en prolog que permita resolver el problema de las Torres de Hanoi. Solución: Las torres de Hanoi se ha convertido en uno de los problemas clásicos dentro de las ciencias de la computación- El problema es fácil de comprender, y ite una solución recursiva simple. La historia puede ser embellecida de varias formas. Hay tres varillas, una de las cuales tiene un número de discos insertados, formando una pirámide. La cuestión fundamental es los discos están insertados en orden de tamaño, con el más grande en el fondo. La figura siguiente ilustra la condición inicial del problema Varilla de la izquierda

Varilla central

Varilla de la derecha

Figura 1: Ilustración de la condición inicial del problema de la torre de Hanoi (Tomada de http://www.pbclibrary.org/raton/towers.htm) La tarea es transferir los discos desde la varilla de la izquierda hasta la varilla de la derecha, apoyándose, si se necesita, en la varilla central. Lo que hace no trivial este problema es que se deben cumplir tres restricciones: 1) Los discos pueden ser movidos uno a la vez. Si no estuviera esta restricción el problema se resolvería moviendo el bloque de la varilla actual a la varilla de la derecha. 2) Un disco sólo puede ser movido a otra varilla. Otra vez, esto previene una solución trivial – dejar los disco en el piso, y luego insertarlos en las varilla de la derecha. Esta restricción obliga a utilizar la varilla del centro para almacenar temporalmente los discos. 3) Un disco más grande nunca puede ser coloca encima de uno más pequeño.

FUNDACIÓN UNIVERSITARIA KONRAD LORENZ-PROGRAMA DE INGENIERÍA DE SISTEMAS Si esta restricción no existiera, el problema podría, otra vez ser fácilmente resuelto. Simplemente se pasarían todos discos en la varilla central y luego trasladarían a la varilla de la derecha. El problema computacional básico de las torres de Hanoi consiste en escribir un programa que incluya las operaciones necesarias para realizar la transferencia de un conjunto de N discos desde la varilla de la izquierda hasta la varilla de la derecha. La manera de pensar un problema recursivo es siempre concentrarse en dos preguntas: a) Cuál es el caso base El caso más simple de las torres de Hanoi podría ser para una pirámide de solo un disco. El caso más simple es a menudo directo el es fácil de olvidar pero es fundamental para el éxito de cualquier recursión. Aquí, la cuestión es esencialmente esta: Como transferir una pila de un disco desde el la varilla de la izquierda, utilizando la varilla de la mitad( si es necesario), a la verilla de la derecha?. La respuesta es directa: Sólo mueva el disco de la pila de la izquierda a la pila de la derecha. También podría tomarse como caso base, el caso de que no haya discos. En este caso la respuesta es muy simple: Si no hay discos, entonces, no haga nada. En este momento no se sabe precisamente como formalizar esta respuesta. Debido a que el caso base es el más simple, su definición podría no aclarar qué factores se deben tomar en cuenta para la solución general del problema, es decir que argumentos tendría la función o el predicado principal que aproxime la solución. Sin embargo, el planteamiento si hace una distinción entre dos operaciones y el tipo de entidades a las que se aplican: Transferencia de pilas(de discos) y movimiento de un disco individual. Recuerde que la tarea general es transferir una pirámide de n discos, desde una varilla a otra, apoyándose en una tercera varilla como almacenamiento temporal, pero una de las restricciones establece que su solución debe involucrar el movimiento de discos individuales de una varilla a otra. b) Cual es el caso recursivo Pensar acerca de este problema recursivamente es pensar cómo puede usar la transferencia de una pila de discos para ayudar en su propia definición, es decir pensar cómo el problema de la transferencia de N discos puede ser reducido a un caso más simple de transferencia. Una aproximación inicial para este problema se logra haciendo la siguiente reflexión: Se deben pasar todos los discos desde la varilla de la izquierda hasta la varilla de la derecha pero no puede colocarse un disco más grande sobre uno más pequeño, moviendo solo un disco a la vez. Si pudiera pasar el disco más grande desde la varilla de la izquierda a la varilla de la derecha, tendría un comienzo excelente para transferir la pila de discos hasta la varilla de la derecha, ya que para que esta transferencia sea exitosa los discos se deben transferir aquí desde el mayor hasta el menor (recuerde que así están ordenados en la pila de la izquierda). Sin embargo, para hacer esto se requieren dos condiciones:

FUNDACIÓN UNIVERSITARIA KONRAD LORENZ-PROGRAMA DE INGENIERÍA DE SISTEMAS  

Que el disco más grande quede solo en la varilla de la izquierda(sin ningún disco encima de él) y que la varilla de la derecha no tenga, en este momento, ningún disco. De estas condiciones resulta como consecuencia que los N-1 discos que se encuentran inicialmente encima del disco más grande deben ser transferidos a la varilla central(utilizando, si se requiere, a la varilla de la derecha como varilla de almacenamiento temporal). La siguiente gráfica ilustra estas condiciones:

Figura 2: Se deben pasar n-1 discos desde la varilla izquierda hasta la varilla central

Figura 3: Luego se puede pasar el disco más grande desde la varilla izquierda hasta la varilla de la derecha.

Figura4: Estado final luego de las acciones anteriores.

Esto sugiere la primera fase de la recursión: Con el fin de transferir N discos desde la varilla de la izquierda a la varilla de la derecha, se debe transferir N1 discos desde la varilla de la izquierda a la varilla central. El problema de transferir una pila de N discos se ha reducido al problema de transferir una pila de N-1 discos. Observe que durante la transferencia de los N-1 discos de la varilla de la izquierda hasta la varilla del centro, la varilla de la derecha actuará como varilla de almacenamiento temporal. Sin embargo, a pesar de que en el proceso de este paso, la varilla de la derecha almacenará temporalmente discos, al final de este paso, la varilla de la derecha no contendrá ningún disco, ya que todos estarán en la varilla del centro(N-1 disco) y en la varilla de la izquierda (el disco más grande)(ver figura 3). El paso siguiente de la recursión es el paso pivotal: mover el disco más grande desde la varilla de la izquierda hasta la varilla de la derecha(ver Figuras 3 y 4). La tercera fase de la recursión requiere que se transfiera los N-1 discos desde la varilla central hasta la varilla de la derecha, durante lo cual, la varilla de la izquierda actuará como varilla de almacenamiento temporal. Esta solución requiere que se distinga entre cada varilla particular y el papel que juega en cualquier fase de la operación. Cuando se inicia con N discos, la varilla de la izquierda es la fuente y la varilla de la derecha es el destino y la varilla central es la de almacenamiento temporal. Cuando esto se reduce al problema de transferir N-1 discos, la varilla de la mitad es la fuente, la de la derecha es el destino y la de la izquierda es la de almacenamiento temporal. Implementación en Prolog Para la implementación se requiere un predicado que permita transferir una pila de N discos desde una fuente X, apoyándose como almacenamiento temporal en Y, a un destino Z, que se podría declarar como: transfiera(N,X,Y,Z).

FUNDACIÓN UNIVERSITARIA KONRAD LORENZ-PROGRAMA DE INGENIERÍA DE SISTEMAS Caso Base: El caso base del algoritmo recursivo, como se mencionó más arriba podría ser el caso en que la pila de la izquierda tenga solamente un disco, para lo cual se requiere solamente, mover el disco desde el origen hasta el destino. En prolog, esto podría escribirse como: transfiera(1,Izquierda,Centro,Derecha):- mueva_disco(Izquierda,Derecha). También podría considerarse como caso base el caso más trivial, en el cual no hay disco, en este caso simplemente, no hay que hacer nada. En prolog se escribiría así: transfiera(0,Izquierda,Centro,Derecha). Usted puede elegir uno de estos dos casos bases. Para este ejemplo se elegirá el caso de 0 discos como el caso base, y se exigirá que N>=0.

Caso Recursivo Aquí simplemente se debe expresar en la sintaxis de prolog el algoritmo discutido anteriormente: Para transferir N discos desde la varilla Izquierda hasta la varilla Derecha haga lo siguiente: Transfiera N-1 discos desde la varilla de la izquierda hasta la varilla central, utilizando la varilla de la derecha como varilla de almacenamiento temporal. Luego, mueva el disco más grande (que quedó solo en la varilla de la izquierda), desde la varilla Izquierda hasta la varilla Derecha. A continuación, transfiera los N-1 discos desde la varilla Centro, hasta la varilla Derecha, utilizando la varilla izquierda como varilla de almacenamiento temporal. En prolog, esto se expresaría de la siguiente forma transfiera(N,Izquierda,Centro,Derecha):-

%Para transferir N discos de Izquierda a Derecha, utilizando Centro

como apoyo

N>0,M is N-1, % se asegura que N>0 y almacena N-1 en M transfiera(M,Izquierda,Derecha,Centro), %transfiera N-1 discos de Izquierda a Centro, utilizando Derecha como apoyo

mueva_disco(Izquierda, Derecha), %mueva el disco mayor de Izquierda a Derecha transfiera(M,Centro,Izquierda,Derecha). %transfiera N-1 discos de Centro a Derecha, utilizando a Derecha como apoyo

Ahora se define el predicado mueva_disco(Izquierda, Derecha). Este predicado solo debe indicar de donde a donde se realizará el movimiento del disco mueva_disco(Izquierda,Derecha):- write('Mueva el disco de arriba desde '), write(Izquierda), write(' hasta '), write(Derecha),nl. Finalmente el programa quedaría de la siguiente manera: transfiera(0,Izquierda,Centro,Derecha). transfiera(N,Izquierda,Centro,Derecha):- N>0,M is N-1,

FUNDACIÓN UNIVERSITARIA KONRAD LORENZ-PROGRAMA DE INGENIERÍA DE SISTEMAS transfiera(M,Izquierda,Derecha,Centro), mueva_disco(Izquierda, Derecha), transfiera(M,Centro,Izquierda,Derecha). mueva_disco(Izquierda,Derecha):- write('Mueva el disco de arriba desde '), write(Izquierda), write(' hasta '), write(Derecha),nl. mueva_disco(Izquierda,Derecha):- write('Mueva el disco de arriba desde '), write(Izquierda), write(' hasta '), write(Derecha),nl. Al compilar este programa y correrlo con 3 discos en la varilla izquierda, mediante transfiera(3,izquierda,centro,derecho), se obtiene:

2) Un sistema de producción consiste en un conjunto de pares “situaciónacción”, indicando que si esta situación surge, tome esta acción. Un ejemplo de un sistema de producción es el programa “numerales romanos” dado abajo:

% Numerales Romanos para 1 <= X <= 39 romano(X) :X > 39, write('Numero debe estar entre 1 y 39'), nl. romano(X) :X < 0, write(' Numero debe estar entre 1 y 39'), nl. romano(X) :X >= 10, X =< 39, write('X'), Y is X - 10, romano(Y). romano(X) :X == 9, write('IX'). romano(X) :X >= 5, X =< 8, write('V'),

FUNDACIÓN UNIVERSITARIA KONRAD LORENZ-PROGRAMA DE INGENIERÍA DE SISTEMAS Y is X - 5, romano(Y). romano(X) :X == 4, write('IV'). romano(X) :X >= 1, X =< 3, write('I'), Y is X - 1, romano(Y). romano(0) :- nl.

Estudie como trabaja este algoritmo, y extiéndalo para manejar todos los números desde 1 a 399. Muestre que su programa funciona para 49, 51, 99, 101,299, y 399. Escriba un ciclo que despliegue los números romanos de todos los números entre 1 y 399 inclusive. SOLUCION: Se puede notar que la manera de procesar el número es de los mayores valores hacia los menores, ya que es la manera de escribir un número romano, encontramos primero los símbolos de mayor peso, o que representan mayor valor. Para expender el código para que maneje los número del 1 al 399, empezamos de manera similar, procesando primero los números de mayor valor, descomponiéndolo hasta llegar a un mínimo valor. Antes de comenzar se valida que el número este en el rango que el algoritmo puede manejar:

romano(X) :X > 399, write('Numero debe estar entre 1 y 399'), nl. romano(X) :X < 0, write(' Numero debe estar entre 1 y 399'), nl. Empezamos entonces con los números que sean mayores o iguales que 100 y menores a 400, si esto sucede, se imprime una C como parte del resultado, y le restamos al numero de entrada estos 100 que ya se representaron, y volvemos a llamar la función, de manera recursiva, de tal manera que vuelva a hacer esta evaluación, y así poner tantas C como sea necesario o seguir con uno de los predicados siguientes: romano(X) :X >= 100, X =< 399, write('C'), Y is X - 100, romano(Y).

FUNDACIÓN UNIVERSITARIA KONRAD LORENZ-PROGRAMA DE INGENIERÍA DE SISTEMAS Una vez el numero sea menor que 100, se evalúa de nuevo, y si esta entre 90 y 99, agregamos a la salida „XC‟, que es la manera de representar al 90, al hacer esto, tenemos que restarle al numero 90, ya que ya fueron representados, y se vuelve a llamar la función con este nuevo numero como argumento romano(X) :X >= 90, X < 100, write('XC'), Y is X-90, romano(Y). Si el número esta entre 50 y 89, se le agrega a la salida una „L‟, que representa el numero 50 en romano, y estos 50 son restados del numero a representar, y se vuelve a llamar la función romano con este nuevo valor romano(X) :X >= 50, X < 90, write('L'), Y is X - 50, romano(Y). En el caso en que el número al que se le aplica la función romano es mayor o igual a 40 y menor que 50, se agrega a la salida „XL‟, que representa 40 en romano. Como se ha venido haciendo, se le resta al numero procesado 40, que ya fueron representados, y con este valor se llama de nuevo la función romano, para seguir procesando el valor restante. Hasta este punto es la modificación que se le tuvo que hace al algoritmo para que procesara números del 1 a 399. romano(X) :X >= 40, X < 50, Y is X-40, write('XL'), romano(Y). En otro caso, si el numero a procesar es mayor o igual a 10 y menor que 40, se agrega a la salida una X que representa un 10, estos se le restan a el numero y se vuelve a llamar la función con este nuevo valor romano(X) :X >= 10, X =< 39, write('X'), Y is X - 10, romano(Y). Cuando el número es igual a 9, se agrega a la salida „IX‟, que representa al número 9 en romano, y no se vuelve a llamar la función. Cuando el número esta entre 5 y 8, se agrega a la salida „V‟, se le resta 5 al número y se vuelve a llamar la función con este nuevo valor.

FUNDACIÓN UNIVERSITARIA KONRAD LORENZ-PROGRAMA DE INGENIERÍA DE SISTEMAS romano(X) :X == 9, write('IX'). romano(X) :X >= 5, X =< 8, write('V'), Y is X - 5, romano(Y). En otra entrada a la función, si el número es igual a 4, se agrega a la salida „IV‟, y no se vuelve a llamar la función, ya que el número estaría totalmente representado en romano. Cuando el numero es menor que 4 y mayor o igual a 1, se agrega a la salida „I‟, se resta 1, y se vuelve a llamar la función con el nuevo valor. El algoritmo quedaría de la siguiente manera:

% Numerales Romanos para 1 <= X <= 39 romano(X) :X > 399, write('Numero debe estar entre 1 y 399'), nl. romano(X) :X < 0, write(' Numero debe estar entre 1 y 399'), nl.

romano(X) :X >= 100, X =< 399, write('C'), Y is X - 100, romano(Y). romano(X) :X >= 90, X < 100, write('XC'), Y is X-90, romano(Y). romano(X) :X >= 50, X < 90, write('L'), Y is X - 50, romano(Y). romano(X) :X >= 40, X < 50, Y is X-40, write('XL'), romano(Y). romano(X) :X >= 10, X =< 39,

FUNDACIÓN UNIVERSITARIA KONRAD LORENZ-PROGRAMA DE INGENIERÍA DE SISTEMAS write('X'), Y is X - 10, romano(Y). romano(X) :X == 9, write('IX'). romano(X) :X >= 5, X =< 8, write('V'), Y is X - 5, romano(Y). romano(X) :X == 4, write('IV'). romano(X) :X >= 1, X =< 3, write('I'), Y is X - 1, romano(Y). romano(0) :- nl. Finalmente, para imprimir todos los números del 1 al 399 en romano, usamos la función forall, acompañada de la función integer_bound: romanos:- forall(integer_bound(1,A,399), romano(A)), nl. De esta manera, al llamar la función romanos, se imprimirán todos los números. El programa final sería el siguiente: % Numerales Romanos para 1 <= X <= 39 romano(X) :X > 399, write('Numero debe estar entre 1 y 399'), nl. romano(X) :X < 0, write(' Numero debe estar entre 1 y 399'), nl.

romano(X) :X >= 100, X =< 399, write('C'), Y is X - 100, romano(Y). romano(X) :X >= 90, X < 100, write('XC'), Y is X-90, romano(Y). romano(X) :-

FUNDACIÓN UNIVERSITARIA KONRAD LORENZ-PROGRAMA DE INGENIERÍA DE SISTEMAS X >= 50, X < 90, write('L'), Y is X - 50, romano(Y). romano(X) :X >= 40, X < 50, Y is X-40, write('XL'), romano(Y). romano(X) :X >= 10, X =< 39, write('X'), Y is X - 10, romano(Y). romano(X) :X == 9, write('IX'). romano(X) :X >= 5, X =< 8, write('V'), Y is X - 5, romano(Y). romano(X) :X == 4, write('IV'). romano(X) :X >= 1, X =< 3, write('I'), Y is X - 1, romano(Y). romano(0) :- nl. romanos:- forall(integer_bound(1,A,399), romano(A)), nl. Al correr el predicado “romanos”, se obtiene el siguiente resultado:

FUNDACIÓN UNIVERSITARIA KONRAD LORENZ-PROGRAMA DE INGENIERÍA DE SISTEMAS Si quisiera saber cómo se escribe un número cualquiera en el intervalo [1,399], puede utilizar el predicado “romano”, de la siguiente forma:

3) Definir los siguientes predicados

a. Definir en prolog la siguiente función: F(x)=2, si x>10 F(x)= raíz(x), si 0 F(x)=-x, si x <0

x

10

SOLUCION Se definen los predicados de la misma manera que están enunciados, usando la función de prolog ,„sqrt(X)‟, que sirve para hallar la raíz cuadrada de X. funcion(X,2):-X>10, !. funcion(X,Y):-X>=0, X=<10, Y is sqrt(X), !. funcion(X,Y):-X<0, Y is -X, !. Al correr el programa, se obtiene:

FUNDACIÓN UNIVERSITARIA KONRAD LORENZ-PROGRAMA DE INGENIERÍA DE SISTEMAS b. suma(Liminferior, LimSup, Suma), donde suma es igual a la suma de los enteros desde límite inferior hasta límite superior. Por ejemplo: Suma(2, 10, Suma), debería retornar suma= 2+3+4+5+6+7+8+9+10= 54 SOLUCION Se definen los predicados de manera recursiva: Caso base: Cuando el valor del límite inferior, Liminferior, es igual al limite superior, LimSup. En este caso la Suma es igual a Liminferior. ∑ Esto se podría indicar de la siguiente manera: suma(Liminferior, Liminferior, Liminferior):- !. Caso recursivo: Cuando Liminferior < LimSup, en este caso, la Suma es igual a Liminferior más la suma desde Liminferior+1 hasta LimSup. ∑

∑

Esto se escribe de la siguiente manera: suma(Liminferior, LimSup, Suma):- Liminferior
FUNDACIÓN UNIVERSITARIA KONRAD LORENZ-PROGRAMA DE INGENIERÍA DE SISTEMAS

c. Construya el predicado: Productoria(Liminferior, LimSup, Prod), donde Prod sea el producto de los enteros entre liminferior y LimSup. Por ejemplo Productoria(2,5,Prod), debe retornar, Prod= 2*3*4*5=120 SOLUCION La manera de implementar el predicado que realice este producto, es similar a la manera en que se desarrollo el punto 4 de este taller, la única diferencia es que en lugar de hacer la suma, se hace el producto: productoria(X,Y,X):- X==Y,!. productoria(X,Y,Prod):- X
Aquí se incluye el caso en que 2) Cuando el discriminante, soluciones son conjugadas complejas.

, en el cual X1=X2 , en este caso las

√|

|

√|

|

FUNDACIÓN UNIVERSITARIA KONRAD LORENZ-PROGRAMA DE INGENIERÍA DE SISTEMAS Adicionalmente, con el fin de garantizar que la ecuación sea cuadrática, se verificará que el primer coeficiente sea diferente de cero. El programa quedaría de la siguiente forma: raicesecuacion(A,_,_,_,_):-A=:=0, write('Para que la ecuación sea cuadrática,el primer coeficiente debe ser diferente de cero'),abort,!. raicesecuacion(A,B,C,X1,X2):-B*B-4*A*C>=0, X1 is (-B+sqrt(B*B-4*A*C))/(2*A), X2 is (-B-sqrt(B*B-4*A*C))/(2*A),!. raicesecuacion(A,B,C,X1,X2):-B*B-4*A*C<0, Aux is abs(B*B-4*A*C), Xr is -B/(2*A), Xi is sqrt(Aux )/(2*A), X1=Xr+Xi*i, X2=Xr-Xi*i. A continuación se presentan varias corridas de este programa:

e. Construya el predicado: potencia(X,N, Pot), donde Pot= X^N, pero sin utilizar la función ^ definida en prolog. SOLUCION %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

La potenciación tiene una definición recursiva: Caso Base: X0=1, lo cual se indicaría en prolog de la siguiente manera: potencia(X,0, 1).

Caso recursivo: potencia(X,N,P):-Y is N-1, potencia(X,Y,Q), P is X*Q,!.

Aunque esto captura el contenido lógico de la potenciación, no es totalmente correcta como un programa, debido a la forma como prolog busca la solución a una consulta. En primera instancia este programa retornará el resultado correcto para un X>0, pero cuando se pregunte por soluciones adicionales, se hará una recursión infinita, ya que en ninguna parte del programa se ha establecido que existe una

FUNDACIÓN UNIVERSITARIA KONRAD LORENZ-PROGRAMA DE INGENIERÍA DE SISTEMAS única solución para X0,por lo tanto protentará encontrar otras soluciones para potencia(X,0, P), ahora utilizando la definición recursiva. En este caso se generará una recursión infinita, ya que no hay un caso base para detenerla y se produdirá un desbordamiento de pila.

Al escribir ―;‖ o presionar la barra espaciadora, se pregunta a prolog por soluciones alternativas, obteniéndose:

Para resolver este inconveniente, se debe indicar a prolog que X0=1 y no hay más soluciones; esto se puede hacer utilizando el corte,!, de la siguiente forma: potencia(X,0, 1):-!.

El corte evita que prolog, una vez halle una solución, siga buscando otras soluciones. Para evitar que se produzcan errores por el procesamiento de exponentes negativos: %caso recursivo N>0 potencia(X,N,P):-N>0, Y is N-1, potencia(X,Y,Q), P is X*Q,!.

El caso de exponentes negativos se puede incluir teniendo en cuenta que para N<0:

FUNDACIÓN UNIVERSITARIA KONRAD LORENZ-PROGRAMA DE INGENIERÍA DE SISTEMAS

| |

Con lo cual esta parte quedaría como: %caso recursivo N<0 potencia(X,N,P):-N<0, AN is abs(N), potencia(X,AN,Q), P is 1/Q,!.

El programa, finalmente sería: %%%Potencias(X,N,P) calcula el valor de X^N, y lo almacena en P %caso base X^0=1 potencia(X,0,1):-!. %caso recursivo N>0 potencia(X,N,P):-N>0, Y is N-1, potencia(X,Y,Q), P is X*Q,!. %caso recursivo N<0 potencia(X,N,P):-N<0, AN is abs(N), potencia(X,AN,Q), P is 1/Q,!.

A continuación se presentan algunas ejecuciones de este programa:

f. Construya el predicado: Fibonacci(N,M), donde M es N-ésimo término de la serie de fibonacci SOLUCION La serie fibonacci también la definimos en términos recursivos, ya que el n-esimo término de la serie es igual a la suma de los dos términos anteriores. Los casos base de la serie son el primer y segundo termino

FUNDACIÓN UNIVERSITARIA KONRAD LORENZ-PROGRAMA DE INGENIERÍA DE SISTEMAS de la serie, que son el 0 y el 1. Los otros los podemos hallar de la suma de los dos anteriores términos de la serie: fibonacci(0,0):-!. fibonacci(1,1):-!. fibonacci(N,M):-N>0, A is N-2, B is N-1, fibonacci(A,X), fibonacci(B,Y), M is X+Y.

g. Construya el predicado:Tabla_de_multiplicar(X, LimSup) imprima la tabla de multiplicar de X, desde 1 hasta LimSup. Ejemplos: Tabla_multiplicar(2, 5), debe imprimir: 2*1=2 2*2=4 2*3=6 2*4=8 2*5=10

SOLUCION Para este predicado podemos usar la función de Prolog llamada integer_bound, la cual, si se llama con los parámetros (1,M,L), en M asignará un numero entero desde 1 hasta L, incrementándose de 1 en 1, cada vez que se llame la función. Para obligar a que prolog vuelva a entrar en el predicado, usamos la instrucción fail, que hace que prolog vuelva a buscar una solución, y así incrementar a M en la siguiente entrada. Cada vez que entre se va a imprimir la multiplicación con M del numero del que se quiere la tabla de multiplicar, que en este caso es X. esto sucederá hasta que M llegue a L.

FUNDACIÓN UNIVERSITARIA KONRAD LORENZ-PROGRAMA DE INGENIERÍA DE SISTEMAS tabla_de_multiplicar(X,L):- integer_bound(1,M,L), R is X*M, write(X * M = R), nl, fail. Al ejecutar este predicado para generar la tabla de multiplicación del 9, desde 1 hasta 10, se obtiene lo siguiente:

Utilizando un esquema recursivo también es posible obtener el mismo resultado. Se define un predicado que escribe las multiplicaciones: escribir_mult(X,N,R):-write(X*N=R), nl. Se define un predicado que imprime las tabla de multiplicar para X, desde LimInf hasta LimSup: Caso Base: Si LimInf =LimSup, entonces escriba X*N=R, donde R es la variable en donde se almacena el resultado numérico de X*N. multiplicar(X,LimSup,LimSup):-Resultado is X*LimSup, escribir_mult(X,LimSup,Resultado),!. Caso Recursivo: Si LimInf
FUNDACIÓN UNIVERSITARIA KONRAD LORENZ-PROGRAMA DE INGENIERÍA DE SISTEMAS multiplicar(X,LimInf,LimSup):-LimInf
h. Elabore un programa que simule una instrucción “while”, imprimiendo en pantalla una palabra, un número determinado de veces. SOLUCIÓN: Se puede plantear una solución recursiva, basados en un predicado imprima_palabra(Veces, palabra), se la siguiente forma: Caso Base: Si Veces es igual a cero, no haga nada. Esto se escribiría como: imprima_palabra(0, Palabra). Caso Recursivo: Si Veces es diferente a 0, entonces escriba Palabra , decremente Veces en 1 y vuelva a llamar el predicado imprima_palabra. Esto se indica en prolog de la siguiente forma imprima_palabra(Veces, Palabra):write(Palabra),nl, % esto corresponde al predicado que desea repetir Veces1 is Veces-1, imprima_palabra(Veces1,Palabra). Al ejecutar este predicado con Veces=5, y Palabra = Pervys, se obtiene

FUNDACIÓN UNIVERSITARIA KONRAD LORENZ-PROGRAMA DE INGENIERÍA DE SISTEMAS

4) Construya predicados convenientes para calcular las siguientes series:

a)

( )

∑

b)

( )

∑

c)

( )

∑

d)

( )

∑

e) f)

( ) ( )

∑ ∑

(

(

)

(

(

) (

)

)

(

)

)

SOLUCION Para desarrollar estos ejemplos se requiere desarrollar los siguientes predicados básicos: %%%Potencias(X,N,P) calcula el valor de X^N, y lo almacena en P %caso base X^0=1 potencia(X,0,1):-!. %caso recursivo N>0 potencia(X,N,P):-N>0, Y is N-1, potencia(X,Y,Q), P is X*Q,!. %caso recursivo N<0 potencia(X,N,P):-N<0, AN is abs(N), potencia(X,AN,Q), P is 1/Q,!.

FUNDACIÓN UNIVERSITARIA KONRAD LORENZ-PROGRAMA DE INGENIERÍA DE SISTEMAS %%factorial(N,Factorial) calcula el valor de N!, y lo almacena en NFactorial %caso base 0!=1 factorial(0,1):-!. %caso recursivo factorial(N,NFactorial):-N>0,X is N-1, factorial(X,Y), NFactorial is N*Y,!. %%%Factorial version iterativa factorial_iter(N,F) :- fact_iter(N,1,F). %El valor en Aux, cuando I sea 0 es el factorial fact_iter(0,F,F):-!. fact_iter(I,Aux,F) :- I1 is I-1, Aux1 is I*Aux, fact_iter(I1,Aux1,F). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% a)

( )

∑

%%versión 1 suma1(X,LimInf,LimInf, Suma1):-potencia(X,LimInf,Suma1),!. suma1(X,LimInf,N,Suma1):-N>0,K is LimInf+1, potencia(X,LimInf,R), suma1(X,K,N,T), Suma1 is R+T. f1(X,N,F1):- suma1(X,0,N, F1). Considérese el caso en el cual X=3 y N=7 ( )

∑

Al correr este programa se obtiene:

FUNDACIÓN UNIVERSITARIA KONRAD LORENZ-PROGRAMA DE INGENIERÍA DE SISTEMAS %%versión 2 suma11(X,0,1):-!. suma11(X,N,S):-N>0,K is N-1, potencia(X,N,R), suma11(X,K,T), S is R+T,!. f11(X,N,F1):- suma11(X,N, F1). Al correr esta nueva versión se obtiene:

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% a)

( )

∑

f2(X,0,X):-!. f2(X,N,S):-N>0,Q is N-1, P is 2*N+1, potencia(X,P,Z), f2(X,Q,T), S is Z/P+T. Al correr esta predicado con X=3 y N=4, se obtiene: ( )

( )

∑

( )

( )

( )

( )

( )

( )

( )

( )

( )

FUNDACIÓN UNIVERSITARIA KONRAD LORENZ-PROGRAMA DE INGENIERÍA DE SISTEMAS

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% a)

( )

∑

(

)

(

)

suma3(X,0,X):-!. suma3(X,N,S):-N>0,Q is N-1, P is 2*N+1, potencia(X,P,Z), potencia(-1,N,R), factorial(P,F),suma3(X,Q,T), S is R*Z/F+T. Ahora, con base en el predicado anterior se define la función seno, tomando N= 8 términos de la serie( N mayores producirán mayor exactitud) seno(X,Seno):-suma3(X,8,Seno). El programa completo quedaría así: suma3(X,0,X):-!. suma3(X,N,S):-N>0,Q is N-1, P is 2*N+1, potencia(X,P,Z), potencia(-1,N,R), factorial(P,F),suma3(X,Q,T), S is R*Z/F+T. seno(X,Seno):-suma3(X,8,Seno). Al correr este programa con X=0.5 se obtiene: Sen(0.5)= 0.47942554

FUNDACIÓN UNIVERSITARIA KONRAD LORENZ-PROGRAMA DE INGENIERÍA DE SISTEMAS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

b)

( )

∑

suma5(X,0,1):-!. suma5(X,N,S):-P is N-1, potencia(X,N,R), factorial(N,F), suma5(X,P,T), S is R/F+T. %Ahora se define la función exponencial con N=11 exp (X,Exp):-suma5(X,11,Exp). Al correr este programa con X=0.5, se obtiene: Exp(0.5)= 1.64872127

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% c)

( )

∑

(

suma6(X,1,S):-S is -1+X,!. suma6(X,N,S):-P is N-1, Q is -1+X, potencia(-1,P,R), potencia(Q,N,T), suma6(X,P,M), S is R*T/N+M.

)

(

)

FUNDACIÓN UNIVERSITARIA KONRAD LORENZ-PROGRAMA DE INGENIERÍA DE SISTEMAS %Con base en el predicado anterior se define el Logaritmo, tomando 30 términos de la serie ln(X,Ln):-suma6(X,30,Ln). Al correr este programa con X=0.5 se obtiene: ln(0.5)= -0.69314718

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% d)

( )

∑

(

)

(

)

%%version 1 suma7(X,0,1):-!. suma7(X,N,S):-Q is N-1, P is 2*N, potencia(X,P,Z), potencia(-1,N,R), factorial(P,F), suma7(X,Q,T), S is R*Z/F+T,!. coseno(X,Cos):-suma7(X,8,Cos). %%version 2 suma71(X,N,N,S):- P is 2*N,potencia(1,N,R),potencia(X,P,Z),factorial(P,F),S is R*Z/F,!. suma71(X,N,N1,S):-Q is N+1, P is 2*N, potencia(X,P,Z), potencia(-1,N,R), factorial(P,F), suma71(X,Q,N1,T), S is R*Z/F+T,!. coseno1(X,Cos):-suma71(X,0,7,Cos). Al correr estos programas con X=0.5, se obtiene:cos(0.5)= 0.87758256

FUNDACIÓN UNIVERSITARIA KONRAD LORENZ-PROGRAMA DE INGENIERÍA DE SISTEMAS

5) Elabore un programa que permita responder consultas acerca de las capitales de los departamentos de Colombia, siguiendo los siguientes lineamiento:  Que cargue al iniciar la base de conocimiento incompleta sobre departamentos y capitales del archivo “capital.pl”, lo cual se puede hacer almacenando en este archivo, hechos de la forma “capital(departamento, capital)”.  Cuando el digite un departamento que no se encuentre en la base de conocimiento actual, el programa debe solicitar al que ingrese la capital de ese departamento con el fin de aprenderla y poder responder adecuadamente en la siguiente ocasión.  Al finalizar el programa debe guardar en el archivo “capital.pl”, toda la base de conocimiento. SOLUCIÓN %Se define a capital como un predicado dinámico de dos argumentos. Esto permite agregar instancias de este predicado, en tiempo de corrida % durante el tiempo de corrida. :-dynamic(capital/2).

% encuentraCapital es el predicado principal. El acepta el nombre de un departamento % y llama a buscaCapital para que haga la búsqueda pregunta_cont:-write('desea continuar? '),read(T),continue(T). continue('s'):-encuentraCapital,!. continue('S'):-encuentraCapital,!. continue('n'):-continue('N'). continue('N'):-write('Ahora se procederá a salvar la base de conocimiento'),nl, tell('capital.pl'), listing(capital), told, write('Ya se ha guardado'),nl,write(' ADIOS!!!!!!'). continue(_):-pregunta_cont,!. inicio:-reconsult('capital.pl'), encuentraCapital.

FUNDACIÓN UNIVERSITARIA KONRAD LORENZ-PROGRAMA DE INGENIERÍA DE SISTEMAS encuentraCapital :- write('ingrese el departamento: '),nl, read(Departamento), buscaCapital(Departamento), pregunta_cont. % buscaCapital usa la busqueda de encadenamiento hacia atrás para encontrar una matching % capital(Departamento, Capital). Si él tiene éxito, entonces imprime la ciudad y se detiene buscaCapital(Departamento) :- capital(Departamento, Capital), write('La capital del departamento: '),write(Departamento), write(' es: '), write(Capital), nl. % El control pasará aquí solamente si el primer intento de búsqueda falla % En ese caso se pregunta al para que proporcione la información. % Observe el uso de assertz, que adiciona la nueva información al final de la base de conocimiento buscaCapital(Departamento) :-write('Yo no conozco ese departamento.'),nl, write('Usted me podría decir cuál es su capital?'),nl, write('Yo lo recordaré la próxima vez.'), read(Capital), assertz(capital(Departamento, Capital)), write('Gracias!'), nl.

inicio:-captchreconsult('capital.pl'), encuentraCapital. inicio:-catch(Error,reconsult('capital.pl')),Error=:=31>fcreate(cap,'capital.pl',0,0,0),fclose(cap),reconsult('capital.pl'), encuentraCapital;encuentraCapital. %reconsult('capital.pl'), encuentraCapital. 1. Construya un programa que implemente los siguientes métodos para hallar raíces de ecuaciones no lineales: Método de Bisección Método de Regla falsa

FUNDACIÓN UNIVERSITARIA KONRAD LORENZ-PROGRAMA DE INGENIERÍA DE SISTEMAS Método de la Secante.

CONTROL CON EL CORTE Por una variedad de razones, una definición puede ser lógicamente correcta pero ser ineficiente como un programa. Una forma en la que un programa es ineficiente es por permitir a Prolog que busque más soluciones cuando no hay más soluciones. Esto hace que Porlog gaste un poco de tiempo hasta darse cuenta que ya no hay más soluciónes y en el pero de los casos lo enviará a un ciclo infinito. Prolog tiene una característica especial que restringe la búsqueda para soluciones alternativas, el corte. En la sintaxis de Edimburgo ella se escribe como una signo de exclamación. A pesar de su nombre el corte es un buen instumento de corte para controlar a un programa restringiendo el backtracking. La idea básica es que cuando prolog pasa por una ocurrencia de ¡!, al intentar resolver alguna consulta, el corte previene el re-paso de ese punto cuando hace el backtracking.Una vez prolog alcanza el ¡! En algún punto dentro de una cláusula, else vuelve comprometido para la solución de cualquier meta que lo obtenga en la búsqueda de ese punto , y puede backtarck solamente a la derecha del corte. Suponga que diversas cláusulas en la definición de algún predicado p, y que una de ellas contiene una ocurrencia de ¡!,imagine que en el curso de resolver alguna consulta , Prolog necesita encontrar una solución ap(x) y obtener la cláusula con el corte. Una analogía sería, si pensamos a prolog como un vehículo que viaja una ruta hacia adelante y hacía atrás a traves de un progrmam, buscano soluciones, ese corte es un tipo especial de traluz de tráfico. Inicialmente, las luces estan en verde. Cuando Prolog pasa a través de la luz , búsqueda de una solución, ellas automáticamente cambian a rojo,. Prolog puede seguir hacia delante y hacia atrás la parte de la carretera que está después de las luces, en la búsqueda de soluciones , pero no puede pasar hacia atrás de las luces para intentar re-resolver las metas que las preceden. Tv(t) Tv(f) Pair(X,Y):-tv(X),tv(Y). Sintácticamente, el corte puede ser adicionado como una condición atómica en cualquier parte en el cuerpo de una regla. Por ejemplo podemos colocarlo así. Pair(X,Y):-tv(X),!!,tv(Y). Hay tres lugares en donde podría ser colocado en esta regla, la cual marcaría como sigue: Pair(X,Y):- (iii), tv(X), (ii) tv(Y) (i). Ninguna de las tres posiciones corresponde a un usos realísticos del corte, pero ilustran su efecto sobre el backtracking. Si nosotros colocamos el cote al final de la cláusula n la posición (i), Prolog es reducido a las soluciones que él obtiene para tv(X) y tv(Y) que obtiene allí; el no puede baktrack de ninguna forma. Si nosotros lo clocamos en la posición ii) esto libera para backtrack sobre la soluciónes de tv(Y), pero no sobre tv(X). Poniéndolo en la posición iii, significa que prolog cruza el corte tan pronto como intenta resolver pair, y es reducido a esa cláusula. El puede backtrack por todas las metas a la derecha, justo como el programa original sin corte. Pero si hubieran clausulas adicionales a la definición de pair, un! En la posición (iii) podría resultar redundante

FUNDACIÓN UNIVERSITARIA KONRAD LORENZ-PROGRAMA DE INGENIERÍA DE SISTEMAS Y=t X=t

pair(X,Y)

iii

ii

i

pair(t,t)

tv(Y) Y=f

pait(t,f)

Y=t

pair(f,t)

tv(X)

X=f

tv(Y)

Y=f

pair(f,f)

Posición (i) permite a este programa solo una solución, (i) le permite dos, y (iii) permite todas las cuatro. Factorial: La función factorial es uno de los ejemplos más simples de recursión numérica. Para construir la función vamos a analizar el procedimiento de cálculo para un ejemplo en particular: 5!=5*4*3*2*1=5*4! Generalizando: n!=n(n-1)! En palabras: el factorial de un número es ese número multiplicado por el factorial de su predecesor. Adicionando a esto el caso base de que 1!=1, se tiene una definición recursiva del factorial. En notación matemática: 1!. N!=N(N-1)! Para calcular el factorial de un número n, primero encontramos el número X que es uno menos que n, luego halle el factorial Y de X, luego multiplique Y por N. En prolog Fac.(1,1). Fac.(N,M):-X is N-1, fact(X,Y), M is N*Y. Aunque esto es esencialmente correcto, aquí surge el mismo problema que ocurre durante el retroceso para el caso de la potenciación. Si se requieren soluciones adicionales, fact generará una regresión infinita.

FUNDACIÓN UNIVERSITARIA KONRAD LORENZ-PROGRAMA DE INGENIERÍA DE SISTEMAS Ruta invertida durante el retroceso

Ruta de la solución

M=6

fact(3,M)

X is 3-1

fact(2,Y)

M is 3*2

Y=2

X=2

6 is 3*2 2 is 3-1 A is 2-1 A=1

Y is 2*1

fact(1,B) B=1

1 is 2-1

fact(1,1)

6 is 3*2

C is 1-1

fact(0,D)

C=0 ! E=0-1 E=-1

fact(-1,F)

Nosotros podemos prevenir esto conla estrategia adoptada para exp: insertando un N>1 como la primera condición en el antecedente de la cláusula general, nosotros hacemos explícita la condición que fact aplica solamente para número mayores que 1. Hay sin embargo, una manera completamente diferente de asegurar este efecto. Más que construir en la definición la condición que fact solo aplica a números positivos, nosotros tenemos como meta hacerlo a partir del hecho de que fact es una función. En este sentido aunque sabemos que el factorial es una relación funcional que para la cualquier N solo puede existir uno y solo un M tal que fact(N,M), no hay nada en el programa que lo explicite. Nosotros sabemos por ejemplo que la única solución para fact(1,M) es M=1. Pero si Prolog está buscando soluciones para esta meta, nada en le programa hasta ahora le dice que esta es la única instancia de esa relación. El corte nos habilita para asegurar este efecto-decirle a Prolog que no intente buscar soluciones alternativas para fact(1,M). Ya que ¡ es sintácticamente solo una condición atómica, si nosotros deseamos adicionar un corte a una sentencia incondicional, la haremos condicional: fact(1,1):-!. En general, es mejor pensar el corte como no teniendo ningún efecto sobre la lectura declarativa de un sentencia, es decir para leer esto como: El fatorial e 1 es 1, incondicionalmente( es decir si nada) Esto es esencialmente lo mismo que antes. Debido a que el corte esta relacionado con el

FUNDACIÓN UNIVERSITARIA KONRAD LORENZ-PROGRAMA DE INGENIERÍA DE SISTEMAS control, es decir con la restricción del backtracking, el corte no se muestra realmente en el contenido lógico de un programa. Donde el hace una diferencia significativa es en la lectura procedimental. Para probar que el factorial de 1 es 1, no haga nada(esto es lo mismo que sin ¡)-pero falle totalmente en cualquier intento por re-resolver esta meta. Sin embargo, en este caso la presencia del corte es ligeramente especial, en que nosotros podemos pensarlo como una afectación al contenido descriptivo de la definición. , viz El factorial de 1 es, únicamente 1. Esto es, pensarlo como decirle a prolo que fact es una función que para el caso del número 1 , el único M para el cual fact(1,M) es 1(y el único N para el cual fac(N,1) es 1) Debido a que esto es la base para una recursión, la unicidad tiene aquí el efecto de asegurar la unicidad para todos los números. Para ver la forma que tiene el corte para prevenir que fact entre en una regresión infinita en el retroceso, ayuda seguie la manera como el factorial es calculado en un caso particular, por ejemplo hallar el factorial de 3 es 6. Nosotros ilustramos el camino para la solución como siguies. Cada vez el fact se llama recursivamente , mostramos el valor obtenido en los cálculos como instanciaciones sucesivas de la regla general hasta que se verifique la condición base. El siguiente predicado chequea si un elemento pertenece a una lista

pertenece(X,[X|_]). pertenece(X,[_|Ys]):-pertenece(X,Ys).

Tamaño de una lista longitud([],0).

longitud([H|T],N) :- size(T,N1), N is N1+1.  

The length of the empty list is 0. The length of the list whose head is H and whose tail is the list T is: 1 + (the length of T).

La longitud de la lista vacia es cero: La longitud de la lista cuya cabeza es H y cuya cola es T es 1+(la longitud de T) Suma de los elementos de una lista sumlist([],0).

sumlist([H|T],N) :- sumlist(T,N1), N is N1+H. La suma de los elementos de la lista vacía es 0. La suma de los elementos de la lista cuya cabeza es H y cuya cola es T, es H+ ( la suma de los elementos de T). Menbresía member(X,[X|_]).

FUNDACIÓN UNIVERSITARIA KONRAD LORENZ-PROGRAMA DE INGENIERÍA DE SISTEMAS member(X,[_|T]) :- member(X,T). x es un miembro si la lista cuyo elemento de la cabeza es X( y cuya cola es cualquiera. X es miembro de la lista cuya cabeza es cualquiera y cuya cola es T, si X es un miembro de T Predicado append append([a,b,c],[one,two,three],Result).

Suponga uque se desea escribir un predicado de un argumento, e imprima todos los nùmero entre èl y 0. Imprima_hasta(0) :- write(0). Imprima_hasta(N) :- N>0, write(N), nl, N1 is N-1, imprima_hasta(N1) Si N=0, imprima 0 Si N>0, escriba N, haga N-1 y luego imprima N-1, hasta que N=0. Ahora suponga que deseamos tomar estos números y procesarlos en una cierta otra parte del programa; para hacer esto tendríamos que almacenarlos en alguna parte - la opción natural es utilizar una lista. Así desearíamos un predicado de la forma collect_to(N, L) donde estaba el número N de la entrada, y L era la lista que contenía la respuesta. collect_to(0,L) :- L=[].

This will be slightly different to the other list predicates, since now we want to build a list as we iterate, rather than take one apart. However, the process will still use the standard "[H|T]" notation that we have been using. We should work it out int he usual recursive manner: Esto será levemente diferente a los otros predicados de lista, ya que ahora nosotros deseamos construir una lista conforme se itera, y no tomar cada uno por separado. Sin embargo, el proceso usarà la notacion estándar [ H|T ] . Caso Base: Si el numero que se ingresa es igual a 0, entonces la respuesta es sera [ 0 ], asì se puede escribir  collect_to(0,L) :- L=[].  Caso Recursivo: Si se està tratando con un numero, por decir N, entonces asumimos que sabemos como recolectar todos los nùmero hasta N-1(gracias a la recursiòn) de tal forma que solo necesitamos conocer como asicionarun bit de información extra acerca del elemento actual; el codigo seria 

collect_to(N,L) :- N>0, N1 is N-1, collect_to(N1,T), L=[N|T].

Aunque esto esta bien la manera mas normal de escribir esto es: new_collect_to(0,[]). new_collect_to(N,[N|T]) :- N>0, N1 is N-1, new_collect_to(N1,T). JUNTANDO LISTAS

FUNDACIÓN UNIVERSITARIA KONRAD LORENZ-PROGRAMA DE INGENIERÍA DE SISTEMAS Nosotros podemos escribir un predicado que junte dos listas; el predicado append(L1,L2,L3) significa Si juntamos L1 y L2 se obtine L3

Si se consideran las posibilidades para L1 1) L1 es vacìa, caso en el cual L3 es L2 2) L1 es de la forma [H1 | T1]. 1. L1 is the empty list, in which case L3 is just L2 2. L1 is of the form [H1 | T1]., se obtendría una lista cuya cabeza es H1 y cuya cola es el resultado de juntar T1 y L2 Asì un intento inicial sería append(L1,L2,L3) :- L1=[], L3=L2. append(L1,L2,L3) :- L1=[H1|T1], append(T1,L2,T3), L3=[H1|T3].

Ya que se sabe que prolog harà unificación cuando el empareje(matches) parámetro contra argumentos, una soluciòn mas simple( pero equivalente) serìa append([], L2, L2). append([H1|T1], L2, [H1|L3]) :- append(T1,L2,L3). Haga las siguientes consultas   

append([1,2],[6,7],X) append(X, [5,6], [3,5,6]). append([3,4], Y, [3,4,5,6]). append(X,Y,[1,2]).

El operador "corte". El operador corte, representado por el símbolo "!" nos da un cierto control sobre el mecanismo de deducción del PROLOG. Su función es la de controlar el proceso de reevaluación, limit ndolo a los hechos que nos interesen. Supongamos la siguiente regla: regla :- hecho1, hecho2, !, hecho3, hecho4, hecho5.

PROLOG efectuará reevaluaciones entre los hechos 1, 2 sin ningún problema, hasta que se satisface el hecho2. En ese momento se alcanza el hecho3, pudiendo haber a continuación reevaluaciones de los hechos 3, 4 y 5. Sin embargo, si el hecho3 fracasa, no se intentara de ninguna forma reevaluar el hecho2. Una interpretación práctica del significado del corte en una regla puede er que "si has llegado hasta aquí es que has encontrado la única solución a este problema y no hay razón para seguir buscando alternativas".

FUNDACIÓN UNIVERSITARIA KONRAD LORENZ-PROGRAMA DE INGENIERÍA DE SISTEMAS Aunque se suele emplear como una herramienta para la optimización de programas, en muchos casos marca la diferencia entre un programa que funciona y otro que no lo hace.

% From the book % PROLOG PROGRAMMING IN DEPTH % by Michael A. Covington, Donald Nute, and Andre Vellino % (Prentice Hall, 1997). % Copyright 1997 Prentice-Hall, Inc. % For educational use only % File CAR.PL % Simple automotive expert system :- reconsult('getyesno.pl'). % Use ensure_loaded if available. % % Main control procedures % start :write('This program diagnoses why a car won''t start.'),nl, write('Answer all questions with Y for yes or N for no.'),nl, clear_stored_answers, try_all_possibilities. try_all_possibilities :defect_may_be(D), explain(D), fail.

% Backtrack through all possibilities...

try_all_possibilities.

% ...then succeed with no further action.

% % Diagnostic knowledge base % (conditions under which to give each diagnosis) % defect_may_be(drained_battery) :_says(starter_was_ok,yes), _says(starter_is_ok,no). defect_may_be(wrong_gear) :_says(starter_was_ok,no). defect_may_be(starting_system) :_says(starter_was_ok,no).

FUNDACIÓN UNIVERSITARIA KONRAD LORENZ-PROGRAMA DE INGENIERÍA DE SISTEMAS defect_may_be(fuel_system) :_says(starter_was_ok,yes), _says(fuel_is_ok,no). defect_may_be(ignition_system) :_says(starter_was_ok,yes), _says(fuel_is_ok,yes).

% % Case knowledge base % (information supplied by the during the consultation) % :- dynamic(stored_answer/2). % (Clauses get added as answers questions.)

% % Procedure to get rid of the stored answers % without abolishing the dynamic declaration % clear_stored_answers :- retract(stored_answer(_,_)),fail. clear_stored_answers.

% % Procedure to retrieve the 's answer to each question when needed, % or ask the question if it has not already been asked % _says(Q,A) :- stored_answer(Q,A). _says(Q,A) :- \+ stored_answer(Q,_), nl,nl, ask_question(Q), get_yes_or_no(Response), asserta(stored_answer(Q,Response)), Response = A.

% % Texts of the questions % ask_question(starter_was_ok) :write('When you first started trying to start the car,'),nl,

FUNDACIÓN UNIVERSITARIA KONRAD LORENZ-PROGRAMA DE INGENIERÍA DE SISTEMAS write('did the starter crank the engine normally? '),nl. ask_question(starter_is_ok) :write('Does the starter crank the engine normally now? '),nl. ask_question(fuel_is_ok) :write('Look in the carburetor. Can you see or smell gasoline?'),nl.

% % Explanations for the various diagnoses % explain(wrong_gear) :nl, write('Check that the gearshift is set to Park or Neutral.'),nl, write('Try jiggling the gearshift lever.'),nl. explain(starting_system) :nl, write('Check for a defective battery, voltage'),nl, write('regulator, or alternator; if any of these is'),nl, write('the problem, charging the battery or jump-'),nl, write('starting may get the car going temporarily.'),nl, write('Or the starter itself may be defective.'),nl. explain(drained_battery) :nl, write('Your attempts to start the car have run down the battery.'),nl, write('Recharging or jump-starting will be necessary.'),nl, write('But there is probably nothing wrong with the battery itself.'),nl. explain(fuel_system) :nl, write('Check whether there is fuel in the tank.'),nl, write('If so, check for a clogged fuel line or filter'),nl, write('or a defective fuel pump.'),nl. explain(ignition_system) :nl, write('Check the spark plugs, cables, distributor,'),nl, write('coil, and other parts of the ignition system.'),nl, write('If any of these are visibly defective or long'),nl, write('overdue for replacement, replace them; if this'),nl, write('does not solve the problem, consult a mechanic.'),nl.

% suma de vectores sumavectores( [],[],[] ).

FUNDACIÓN UNIVERSITARIA KONRAD LORENZ-PROGRAMA DE INGENIERÍA DE SISTEMAS

sumavectores( [C1|R1],[C2|R2],[C3|R3] ):-C3 is C1+C2, sumavectores( R1,R2,R3 ). ?-sumavectores( [1,2,3], [4,5,6], X ). X=[5,7,9] %suma de matrices bidimensionales sumamatrices( [],[],[] ). sumamatrices( [C1|R1],[C2|R2],[C3|R3] ):sumavectores(C1,C2,C3),sumamatrices(R1,R2,R3). ?-sumamatrices([[1,2],[3,4]],[[5,6],[7,8]],X). X=[[6,8],[10,12]]. %suma generalizada suma([],[],[]). suma(X,Y,Z):- var(Z),number(X),number(Y),Z is X+Y. suma( [C1|R1],[C2|R2],[C3|R3] ):suma(C1,C2,C3),suma(R1,R2,R3). ?-suma( [1,2,3], [4,5,6], X ). X=[5,7,9] ?-suma([[1,2],[3,4]],[[5,6],[7,8]],X). X=[[6,8],[10,12]]. ?-suma([[[1,2],[1,1]],[[2,2],[3,4]]],[[[5,6],[0,0]],[[8,8],[7,8]]],X). X=[[[6,8],[1,1]],[[10,10],[10,12]]].

Definición de operadores - Contenido de la base de conocimiento :- op(800,xfx,estudian). :- op(400,xfx,y). juan y ana estudian logica. - Consultas: ?- Quienes estudian logica. Quienes = juan y ana ?- juan y Otro estudian Algo. Otro = ana Algo = logica 2.6 Tree data and relations Consider the following tree diagram.

FUNDACIÓN UNIVERSITARIA KONRAD LORENZ-PROGRAMA DE INGENIERÍA DE SISTEMAS

Fig. 2.6 The file 2_6.pl has a representation for this tree and predicate definitions to do some processing of the tree. Note the use of Prolog operators in some of the definitions. /* The tree database */ :- op(500,xfx,'is_parent'). a a a b b

is_parent is_parent is_parent is_parent is_parent

b. c. d. e. f.

c c c d e

is_parent is_parent is_parent is_parent is_parent

g. h. i. j. k.

f f h i i

is_parent is_parent is_parent is_parent is_parent

l. m. n. o. p.

j j j m

is_parent is_parent is_parent is_parent

/* X and Y are siblings */ :- op(500,xfx,'is_sibling_of'). X is_sibling_of Y :- Z is_parent X, Z is_parent Y, X \== Y. /* X and Y are on the same level in the tree. */ :-op(500,xfx,'is_same_level_as'). X is_same_level_as X is_same_level_as

X . Y :- W is_parent X, Z is_parent Y, W is_same_level_as Z.

/* Depth of node in the tree. */ :- op(500,xfx,'has_depth'). a has_depth 0 :- !. Node has_depth D :- Mother is_parent Node, Mother has_depth D1, D is D1 + 1. /* Locate node by finding a path from root down to the node. */ locate(Node) :- path(Node), write(Node), nl. path(a). /* Can start at a. */

q. r. s. t.

FUNDACIÓN UNIVERSITARIA KONRAD LORENZ-PROGRAMA DE INGENIERÍA DE SISTEMAS path(Node) :- Mother is_parent Node, path(Mother), write(Mother), write(' --> '). /*

/* Choose parent, /* find path and then

Calculate the height of a node, length of longest a leaf under the node. */

height(N,H) :- setof(Z,ht(N,Z),Set), */ max(Set,0,H).

*/ */

path to

/* See section 2.8 for 'setof'.

ht(Node,0) :- leaf(Node), !. ht(Node,H) :- Node is_parent Child, ht(Child,H1), H is H1 +1. leaf(Node) :- not(is_parent(Node,Child)). max([],M,M). max([X|R],M,A) :- (X > M -> max(R,X,A) ; max(R,M,A)).

The 'is_sibling_of' relationship tests whether two nodes have a common parent in the tree. For example, ?- h is_sibling_of S=g ; S=i ; no

S.

Note the use of the literal X \==Y, which succeeds just in case X and Y are not cobound (bound to the same value). The 'is_same_level_as' relationship tests whether two nodes are on the same level in the tree. The 'depth' predicate computes the depth of a node in the tree (how many edges from the root). For example, ?- t has_depth D. D=4

Here is an alternate definition of 'depth' using Prolog implication: N has_depth D :- N == 'a' -> D=0 ; Mother is_parent N, Mother has_depth D1, D is D1 + 1.

The 'locate' predicate computes and prints a path from the root to a node. For example, ?- locate(n). a --> c --> h --> n

FUNDACIÓN UNIVERSITARIA KONRAD LORENZ-PROGRAMA DE INGENIERÍA DE SISTEMAS The 'leaf' predicate defines a leaf to be a node which is not a parent. Note the free variable inside the negation. This is correct, since if the node has any child then the node is not a leaf. The 'height' predicate computes the height of a node -- defined as the length of the longest path to a leaf under the node. This definition uses lists and the second-order Prolog predicate 'setof'. We will continue discussion of 'height' and 'setof' in section 2.8. Load the program into the Prolog environment and test the program by issuing various goals. Exercise 2.6.1 Write a Prolog definition for 'ancestor(X,Y)' with the intended meaning that "X is an ancestor of Y in the tree". Pay attention: recursion from the top of the tree or from the bottom of the tree? Exercise 2.6.2 Formulate definitions for a human family tree using relations 'male', 'female', 'parent', 'father', 'mother', 'sibling', 'grandparent', 'grandmother', 'grandfather', 'cousin', 'aunt', and 'uncle'. Let 'male', 'female', 'parent' be the fundamental relations and define the others in of these.

Prolog Code for this section. Prolog Tutorial Contents

The program is mainly interesting with regard to how it tries to certain properties that it uses to draw conclusions, and how it asks questions and records the answers for further reference. If a question q is asked and the answer is 'yes', then that answer is recorded by asserting 'yes(q)' and succeeding, otherwise the answer is recorded by asserting 'no(q)' and failing. Even 'yes' answers need to be recorded since a subsequent 'no' answer to a different question while trying to the same hypothesis may cause the entire hypothesis to fail, but that same 'yes' answer could lead to a successful verification of a different hypothesis later. This is how the program avoids asking the same question twice. The general method of ing a condition q is then to check whether 'yes(q)' has been stored in memory, and succeed, or 'no(q)' has been stored, and fail, otherwise ask(q).

Factorial (N) Si N = 0 entonces Factorial = 1 Si N > 0 entonces Factorial = N * Factorial (N-1)

Suponga que desea crear un programa que halle todas las soluciones para un objetivo dado. Si se pretende crear un predicado que recursivamente muestre las soluciones, entonces puede ocurrir un desbordamiento de pila. Una opción es utilizar los siguientes predicados: Findall(T,C,L) father(michael,cathy). father(charles_gordon,michael). father(jim,melody).

FUNDACIÓN UNIVERSITARIA KONRAD LORENZ-PROGRAMA DE INGENIERÍA DE SISTEMAS We can ask Prolog to display the names of all the fathers by issuing a query such as: ?- father(X,_), write(X), nl, fail. That is: Find an X for which father(X,_) succeeds, print it, and backtrack to find another one. But what if, instead of displaying the names, we want to process them further as a list? We are in a dilemma. In order to get all the names, the program must backtrack. But in order to construct the list, it must use recursion, ing the partially constructed list as an argument from one iteration to the next — which a backtracking program cannot do. One possibility would be to use assert and retract to implement roughly the following algorithm: 1. Backtrack through all solutions of father(X,_), storing each value of X in a separate fact in the knowledge base; 2. After all solutions have been tried, execute a recursive loop that retracts all the stored clauses and gathers the information into a list. Fortunately, we don’t have to go through all this. The built–in predicate findall will gather the solutions to a query into a list without needing to perform asserts and retracts.5 Here’s an example: ?- findall(X,father(X,_),L). L = [michael,charles_gordon,jim] More generally, a query of the form ?- findall(Variable,Goal,List). will instantiate List to the list of all instantiations of Variable that correspond to solutions of Goal. You can then process this list any way you want to. The first argument of findall need not be a variable; it can be any term with variables in it. The third argument will then be a list of instantiations of the first argument, each one corresponding to a solution of the goal. For example: ?- findall(Parent+Child,father(Parent,Child),L). L = [michael+cathy,charles_gordon+michael,jim+melody] Here the plus sign (+) is, of course, simply a functor written between its arguments. Exercise 5.14.1 Given the knowledge base 5If your Prolog lacks findall, define it: findall(V,Goal,L) :- bagof(V,Goal^Goal,L).

5.15. USING bagof AND setof A BAG is a mathematical object like a set except that the same element can occur in it more than once. Obviously, findall creates a bag, not a set, because the same solution can appear in it more than once. Likewise, bagof creates a bag in the form of a list containing all the solutions to a query; setof does the same thing except that the list is sorted into alphabetical order and duplicates are removed. The sorting operation takes extra time, but it can be worthwhile if it saves duplication of subsequent work. The big difference between bagof and setof on the one hand, and findall on the other, concerns the way they handle uninstantiated variables in Goal that do not occur in X. As you might expect, findall treats them as uninstantiated on every . Thus, ?- findall(X,parent(X,Y),L). means ―Find everyone who is the parent of anybody‖ – Y need not have the same value for each parent. But ?- bagof(X,parent(X,Y),L).

findall/3

FUNDACIÓN UNIVERSITARIA KONRAD LORENZ-PROGRAMA DE INGENIERÍA DE SISTEMAS

Retorna una lista no ordenada de términos en las soluciones de una meta u objetivo dado. findall( Termino, Objetivo, Lista ) ?Termino +Objetivo ?Lista o <lista> Comentarios Este predicado retorna una lista no ordenada de soluciones que normalmente se pueden obtener sólo por falla y backtracking a través de una consulta. Este predicado es exitoso si Lista puede ser unificada a una lista de todas las instancias de Término tales que el Objetivo sea cierto. El Término puede ser cualquier termino de Prolog, y el Objetivo puede ser cualquier objetivo Prolog, con o sin llamadas al predicado “cuantificador existencial”, ^ / 2, que es ignorado en el presente predicado Examples Consider the database relation: foo( 1, c ). foo( 2, a ). foo( 1, b ). foo( 2, a ). La siguiente llamada devuelve una lista de todas las soluciones de "X" en el Objetivo "foo(Y,X)", sin hacer partición en los diferentes valores de "Y": ?- findall( X, foo(Y,X), Z ). <enter> X=_, Y=_, Z = [c,a,b,a] Notes A diferencia de los predicados bagof/3 y setof/3, findall/3 no realiza ninguna partición de resultados. Por lo tanto, no tiene el concepto de "cuantificación existential ", y como tal trata cualquier llamada a ^/2 sólo como si el objetivo apropiado se llamara directamente.

bagof/3 Retorna una lista no ordenada de términos en las soluciones de un objetivo dado bagof( Termino, Objetivo, Lista ) ?Term +Goal ?List or <list> Comments Este predicado retorna una lista no ordenada de soluciones que normalmente se pueden obtener sólo por falla y backtracking a través de una consulta. Este predicado es exitoso Lista puede ser unificada a una lista de todos las instancias de Término tales que el Objetivo sea cierto. El Término puede ser cualquier termino de Prolog, y el Objetivo puede ser cualquier objetivo Prolog, con o sin llamadas al predicado “cuantificador existencial”, ^ / 2, que es usado para alterar la partición e las soluciones

Examples Consider the database relation: padre( felipe, jose ). foo( Felipe, maria ). foo( 1, b ). foo( 2, a ).

FUNDACIÓN UNIVERSITARIA KONRAD LORENZ-PROGRAMA DE INGENIERÍA DE SISTEMAS La siguiente llamada retorna los conjuntos de soluciones de "X" en el objetivo "foo(Y,X)", particionado de acuerdo a los diferentes valroes de "Y": ?- bagof( X, foo(Y,X), Z ). <enter> X=_, Y=1, Z = [c,b] ; <space> X=_, Y=2, Z = [a,a] ; <space> no If it is desired to get all solutions irrespective of the bindings of "Y", then "existential quantification" can be used: Si se desea obtener todas las soluciones independientemente de los valores de "Y", entonces se puede usar "la cuantificación existencial": ?- bagof( X, Y^foo(Y,X), Z ). <enter> X=_, Y=_, Z = [c,a,b,a] Notes El predicado bagof/3 está muy relacionado con setof/3. La única diferencia en el comportamiento es que el último ordena los conjuntos retornados, removiendo las solcuiones duplicadas en el proceso. La característica de "existential quantification" de bagof/3 y setof/3 a menudo causan confusión. En general, las solcuiones para ambos predicados se particionan simplmente de acuerdo con los valores de las variables que aparecen en el Objetivo pero no en el Término Considere el comando: ?- bagof( (X,Y), foo(X,Y,A,B), Z ). Esto podría retornar una serie de listas de (X,Y) para el predicado hipotético, foo/4, con cada lista correspondiente a una combinación diferente de (A,B). Supóngase que lo que se desea es obtener una partición de acuerdo a los valores de B, pero no de A, todo lo que se requiere es mencionar a A en el Objetivo como el operando izquierdo de una llamada a ^/2: ?- bagof( (X,Y), A^foo(X,Y,A,B), Z ). Esta vez, las series de listas de las soluciones (X,Y) serán divididas de acuerdo cin los diferentes valores de B: efectivamente, A será ignorado durante la partición. El átomo "^" se define como un operador infijo y asociativo por la izquierda, de tal forma que se puede mencionar una serie de variables, extendiendo(profundizando) simplmente la secuencia de llamadas de a ^/2: ?- bagof( (X,Y), A^B^foo(X,Y,A,B), Z ). Note que aparte de la interpretación especial en los predicados bagof/3 y setof/3, ^/2 no tiene ningún significado diferente al de la meta que constituye su segundo argumento; Es por esto que el comando: ?- A ^ foo(A,B). Es en todo los aspectos idéntico al comando ?- call( foo(A,B) ). One remaining solution set predicate, findall/3, returns all solutions to a goal, without partitioning or sorting: in this case, use of existential quantification is meaningless.

setof/3 Retorna conjuntos ordenados de términos en las soluciones de un objetivo dado

FUNDACIÓN UNIVERSITARIA KONRAD LORENZ-PROGRAMA DE INGENIERÍA DE SISTEMAS setof( Termino, Objetivo, Lista ) ?Termino +Objetivo ?Lista o <lista> Este predicado retorna conjuntos ordenados de soluciones que normalmente se pueden obtener sólo por falla y backtracking a través de una consulta. Este predicado es exitoso Lista puede ser unificada a una lista de todos las instancias de Término tales que el Objetivo sea cierto. El Término puede ser cualquier termino de Prolog, y el Objetivo puede ser cualquier objetivo Prolog, con o sin llamadas al predicado “cuantificador existencial”, ^ / 2, que es usado para alterar la partición e las soluciones Examples Consider the database relation: foo( 1, c ). foo( 2, a ). foo( 1, b ). foo( 2, a ). La siguiente llamada retorna conjuntos de soluciones de "X" en el Objetivo "foo(Y,X)", particionado de acuerdo a los diferentes valores de "Y": ?- setof( X, foo(Y,X), Z ). <enter> X=_, Y=1, Z = [b,c] ; <space> X=_, Y=2, Z = [a] ; <space> no If it is desired to get all solutions irrespective of the bindings of "Y", then "existential quantification" can be used: ?- setof( X, Y^foo(Y,X), Z ). <enter> X=_, Y=_, Z = [a,b,c]

integer_bound/3 genera o prueba enteros entre una cota superior y una cota inferior integer_bound( Cota_Inferior, Numero, Cota_Superior ) +Cota_Inferior <entero> ?Numero <entero> o +Cota_Superior Comments When called with three integers, this predicate succeeds if the given Number is greater than or equal to the given Lower bound, and less than or equal to the given Upper bound. If both the Lower and Upper bounds are specified, but Number is an unbound variable, successive integers in the range [Lower..Upper] are bound to Number on backtracking. Cuando se llama con tres enteros, este predicado tiene éxito si el Número es mayor o igual a Cota_Inferior, y menor o igual que la Cota_Superior. Si se especifican tanto Cota_Inferior como Cota_Superior, pero Número es una variable no acotada, entonces, enteros sucesivos en el rango [Cota_Inferior… Cota_Superior], se unifican con el Número.

FUNDACIÓN UNIVERSITARIA KONRAD LORENZ-PROGRAMA DE INGENIERÍA DE SISTEMAS Examples La siguiente llamada verifica simplemente que "2" es un entero en el rango [1..3]: ?- integer_bound( 1, 2, 3 ). <enter> yes La siguiente llamada muestra que este predicado puede generar soluciones sucesivas en el backtracking: ?- integer_bound( 1, X, 3 ). <enter> X = 1 ; <space> X = 2 ; <space> X=3 Notes Aunque conveniente en su modo de "prueba", integer_bound/3 es en realidad como un generador de números. Debido a que Prolog no proporciona la asignación destructiva, es difícil escribir programas que se comporten como ciclos "for", incrementando un contador y deteniéndolo cuando se alcanza el límite. Una combinación de integer_bound / 3 y backtracking permite una solución simple a esta necesidad particular. La siguiente es una forma de escribir "para los valores de X de 0 a 9, escribir X" ?- integer_bound( 0, X, 9 ), write( X ), fail ; nl. <enter> 0123456789 X=_