<div class="notebook"> <div class="nb-cell html" name="htm1"> </div> <div class="nb-cell html" name="htm2"> <h2 align="center"> Universidad Nacional de Colombia </h2> <h2 align="center"> Lenguajes de programacion 2021 - I </h2> <h2 align="center"> Tutorial Prolog </h2> <p align="center"> <img src="https://avatars2.githubusercontent.com/u/6884283?v=3&s=200"> </p> <h4> Realizado por: <br> Jonathan López Castellanos <br> Víctor Alfredo Barragán Páez <br> Wilson Nicolás Arévalo Rodríguez </h4> <hr> </div> <div class="nb-cell html" name="htm3"> <h3></h3> </div> <div class="nb-cell html" name="htm15"> <h3> Hechos </h3> <ol> <p> Un hecho es un predicado que sirve para representar propiedades o relaciones entre objetos. Estos hechos son tomados siempre como verdaderos para toda la base de conocimiento (Programa). </p> </ol> </div> <div class="nb-cell html" name="htm13"> </div> <div class="nb-cell program" name="p9"> avenger(capAmerica). % Capitan america es un vengador avenger(thor). % Thor es un vengador avenger(ironMan). % Iron man es un vengador % Consultar si Thor es un vengador % Obtenemos TRUE porque el hecho esta en nuestra base de conocimiento </div> <div class="nb-cell query" name="q20"> avenger(thor). </div> <div class="nb-cell html" name="htm16"> <ol> <h4> Propiedades: </h4> <p> Las propiedades llevan solo un argumento para expresar una propiedad de los objetos. </p> </ol> </div> <div class="nb-cell html" name="htm14"> </div> <div class="nb-cell program" name="p10"> avenger(hulk). % Hulk es un vengador - Denota la propiedad de Hulk de ser un vengador color(verde). % verde es un color - Denota la propiedad de verde de ser un Color vehiculo(carro). % carro es un vehiculo - Denota la propiedad de carro de ser un vehiculo </div> <div class="nb-cell query" name="q21"> color(verde). </div> <div class="nb-cell html" name="htm17"> <ol> <h4> Relaciones: </h4> <p> Llevan mas de un argumento para caracterizar la relacion entre objetos. </p> </ol> </div> <div class="nb-cell program" name="p11"> amigo_de(felipe,pedro). % felipe es amigo de pedro amigo_de(nicolas,jonathan). % nicolas es amigo de jonathan amigo_de(victor,mario). % victor es amigo de mario </div> <div class="nb-cell html" name="htm18"> <h3> Reglas </h3> <ol> <p> Las reglas son la representacion de la implicaciones logicas del tipo " P implica Q ". Estas se utilizan para representar que un hecho depende de uno o mas hechos. </p> </ol> </div> <div class="nb-cell program" name="p12"> es_impar(X) :- 1 is X mod 2. menor_que(X) :- X < 20. verificar_numero(X):- es_impar(X) , menor_que(X). % Se busca verificar 2 hechos sobre un numero X. </div> <div class="nb-cell query" name="q23"> verificar_numero(3). </div> <div class="nb-cell html" name="htm29"> </div> <div class="nb-cell program" name="p1"> </div> <div class="nb-cell query" name="q1"> </div> <div class="nb-cell html" name="htm19"> <h3> Consultas </h3> <ol> <p> Es el mecanismo para preguntar sobre las relaciones entre los objetos y las propiedades de los objetos que estan en la base de conocimiento ( programa ). </p> </ol> </div> <div class="nb-cell program" name="p13"> driver(carlos). % establecemos en la base de conocimiento que carlos es un conductor % Cuando realizamos la consulta de " ¿ Carlos es un conductor ? " % obtendremos como resultado True </div> <div class="nb-cell query" name="q24"> driver(carlos). </div> <div class="nb-cell html" name="htm9"> <h3>Operaciones</h3> <ul> <h4>Expresiones aritméticas</h4> </ul> </div> <div class="nb-cell program" name="p6"> suma(X, Y, Z):-Z is X+Y. resta(X, Y, Z):-Z is X-Y. multiplicacion(X, Y, Z):-Z is X*Y. divisionEntera(X, Y, Z):-Z is X//Y. divisionReal(X, Y, Z):-Z is X/Y. modulo(X, Y, Z):-Z is X mod Y. </div> <div class="nb-cell query" name="q15"> suma(4, 2, X); suma(3, 0.2, X) </div> <div class="nb-cell query" name="q11"> resta(3.5, 3.0, X); resta(3, 3, X) </div> <div class="nb-cell query" name="q13"> multiplicacion(2.4, 2, X); multiplicacion(2, 5, X) </div> <div class="nb-cell query" name="q12"> divisionEntera(5, 2, X). </div> <div class="nb-cell query" name="q14"> divisionReal(1, 4, X); divisionReal(3, 2, X) </div> <div class="nb-cell query" name="q16"> modulo(3, 2, X); modulo(1, 4, X) </div> <div class="nb-cell html" name="htm11"> <ul> <h4>Comparación de expresiones</h4> </ul> </div> <div class="nb-cell program" name="p7"> igualValor(X, Y):-X =:= Y. diferenteValor(X, Y):-X =\= Y. menorValorQue(X, Y):-X < Y. mayorValorQue(X, Y):-X > Y. menorIgualValorQue(X, Y):-X =< Y. mayorIgualValorQue(X, Y):-X >= Y. </div> <div class="nb-cell html" name="htm10"> <ul> <h4></h4> </ul> </div> <div class="nb-cell query" name="q17"> igualValor(3+5, 8); diferenteValor(3+5, 7) </div> <div class="nb-cell html" name="htm12"> <ul> <h4>Comparación de términos</h4> </ul> </div> <div class="nb-cell program" name="p8"> terminosIguales(X, Y):-X == Y. terminosDiferentes(X, Y):-X \== Y. terminoMenorQue(X, Y):-X @< Y. terminoMayorQue(X, Y):-X @> Y. terminoMenorIgualQue(X, Y):-X @=< Y. terminoMayorIgualQue(X, Y):-X @>= Y. </div> <div class="nb-cell query" name="q18"> terminosIguales(1+2, 1+2); terminosDiferentes(1+2, 2+1) </div> <div class="nb-cell query" name="q19"> terminoMenorQue(abstract, abstracto); terminoMayorIgualQue(oso, osario) </div> <div class="nb-cell html" name="htm21"> <h3>Proposiciones lógicas</h3> <p>A continuación se muestra cómo emplear Prolog para la declaración de proposiciones lógicas</p> </div> <div class="nb-cell program" name="p15"> t. f:-fail. % ! le dice a Prolog, que no haga Backtracking, algo que veremos más adelante and(P, Q):-P , Q, !. or(P, Q):-(P ; Q), !. xor(P, Q):-or(and(P, not(Q)), and(Q , not(P))), !. if(P, Q):-or(Q, not(P)), !. %Implicación iif(P, Q):-and(or(P, not(Q)), or(Q , not(P))), !. %Doble implicación o equivalencia %Con Backtracking xorbt(P, Q):-(P , not(Q)) ; (Q , not(P)). </div> <div class="nb-cell query" name="q38"> not(t) </div> <div class="nb-cell query" name="q33"> xor(f, f) </div> <div class="nb-cell query" name="q32"> xor(f, t) </div> <div class="nb-cell html" name="htm26"> </div> <div class="nb-cell query" name="q30"> xor(t, f) </div> <div class="nb-cell query" name="q31"> xor(t, t) </div> <div class="nb-cell query" name="q34"> xorbt(t, f) </div> <div class="nb-cell html" name="htm4"> <h3> Funciones predefinidas </h3> <ol> <h4> Matematicas: </h4> <p>Prolog otorga multiples funciones matematicas, incluidas funciones trigonometricas, operaciones sobre números como el logaritmo, la exponencial o el valor absoluto, y otros tipos de funciones sumamente utiles como la generación de enteros aleatorios entre un rango de numeros o la <b> obtención de todos los valores enteros entre un rango </b>. Por ejemplo, para obtener los numeros de 0 a 10 de manera incremental se puede usar la funcion succ(A,X) en un proceso recursivo o la funcion between.</p></ol> </div> <div class="nb-cell program" name="p4"> count_up(Low, High):- between(Low, High, Y), Z is Y, write(Z), nl. count_to_10(10):- write(10), nl. count_to_10(X):- write(X), nl, succ(X,Y), count_to_10(Y). </div> <div class="nb-cell query" name="q2"> count_up(0,10). </div> <div class="nb-cell query" name="q3"> count_to_10(0). </div> <div class="nb-cell html" name="htm5"> <ol><h4> Entrada/Salida: </h4> <p>Prolog permite la entrada de datos a partir de las funciones read(X), que lee el siguiente termino en consola y get(X) que recibe un caracter y lo guarda como valor ASCII. <br> La escritura se realiza a partir de funciones como write(X) y format(), donde la primera escribe un termino X en la salida y la segunda permite escribir mas terminos de acuerdo a los argumentos recibidos.</p></ol> </div> <div class="nb-cell program" name="p2"> hola:- write('Cual es tu nombre? '), read(X), write('Hola, '), write(X). caracter:- write('Digita un caracter '), get(Char), format('~s ~w es ', ["El valor ASCII ", Char]), put(Char), nl. </div> <div class="nb-cell query" name="q4"> hola. </div> <div class="nb-cell query" name="q5"> caracter. </div> <div class="nb-cell html" name="htm6"> <ol><h4> Cambios dinamicos a la base de conocimiento: </h4> <p>Prolog permite hacer cambios a la base de conocimiento desde el nivel superior. Cualquier hecho que se planee cambiar debe marcarse como dinámico antes de su uso.<br> </p></ol> </div> <div class="nb-cell program" name="p3"> :- dynamic(padre/2). :- dynamic(leagrada/2). :- dynamic(amigo/2). padre(lord_montague,romeo). padre(lord_capulet,juliet). leagrada(mercutio,bailar). leagrada(benvolio,bailar). leagrada(romeo,bailar). leagrada(romeo,juliet). leagrada(juliet,romeo). amigo(romeo,mercutio). amigo(romeo,benvolio). </div> <div class="nb-cell query" name="q6"> %Assertz agrega un hechio al final de la lista para ese predicado assertz(padre(lord_montague,juliet)), padre(lord_montague,juliet). </div> <div class="nb-cell query" name="q7"> %Retract remueve un hecho H retract(leagrada(romeo, juliet)), leagrada(romeo,juliet). </div> <div class="nb-cell query" name="q8"> %Remueve todos los hechos que coinciden con H (todos los amigos) retractall(amigo(_,_)), amigo(romeo,mercutio), amigo(romeo,benvolio). </div> <div class="nb-cell html" name="htm7"> <h3> Reglas recursivas </h3> <p> La recursividad es comunmente utilizada en Prolog para realizar repetidamente alguna operación hasta que se alcance cierto punto. En Prolog, la recursividad comienza por un primer hecho que actúa como una condición de detención seguida por alguna regla que realiza alguna operación antes de volver a invocarse.</p> </div> <div class="nb-cell program" name="p5"> %lectura de archivo mediante recursion read_file(File):- open(File, read, Stream), get_char(Stream, Char1), process_stream(Char1, Stream), close(Stream). process_stream(end_of_file, _):- !. %!. = detiene ejecucion process_stream(Char, Stream):- write(Char), get_char(Stream, Char2), process_stream(Char2, Stream). %X esta digestiendo a Y si X se comio a Y o X comio un Z y Z come a Y o alguien que comio a Y comio(mosquito,sangre(felipe)). comio(rana,mosquito). comio(serpiente,rana). comio(aguila,serpiente). digestiendo(X,Y) :- comio(X,Y). digestiendo(X,Y) :- comio(X,Z), digestiendo(Z,Y). </div> <div class="nb-cell query" name="q10"> read_file('test1.txt'). </div> <div class="nb-cell query" name="q9"> digestiendo(serpiente, sangre(felipe)). </div> <div class="nb-cell html" name="htm22"> <h3> Backtracking </h3> ¿Cómo funciona el backtracking en Prolog? <br> <ol> <li>Comienza intentando resolver cada objetivo en una consulta, de izquierda a derecha (objetivos separados por el operador Y).</li> <li>Para cada objetivo, intenta hacer coincidir un hecho o el encabezado de una regla correspondiente. </li> <li>Si un hecho o un predicado coincide, continúa para coincidir con los objetivos restantes. </li> <li>Cuando se llega a un punto en el que un objetivo no se puede igualar, <b> Prolog retrocede al punto más reciente donde se tomó la decisión de igualar un hecho o una regla en particular </b>.</li> <li>Se intenta hacer coincidir un hecho o una regla diferente. Si esto falla, se vuelve al siguiente punto anterior donde se hizo una elección para probar una coincidencia diferente allí. </li> <li>Se intentan alternativas hasta que sea capaz de resolver todos los objetivos de la consulta o hasta que se hayan probado todas las opciones posibles y se haya comprobado que fallan. </li> </ol> <p> El seguimiento de la ejecución de una consulta de Prolog permite ver todos los objetivos que se ejecutan como parte de la consulta, en secuencia, junto con su éxito o no. Ademas permite ver qué pasos ocurren cuando Prolog "retrocede". El modo que permite hacer el seguimiento a la ejecucion se inicia con la consulta "trace."</p> </div> <div class="nb-cell program" name="p16"> %ej1 de_sangre_caliente(pinguino). de_sangre_caliente(humano). de_sangre_caliente(vaca). produce_leche(humano). produce_leche(vaca). tiene_plumas(pinguino). tiene_pelo(humano). tiene_pelo(vaca). mamifero(X) :- de_sangre_caliente(X), produce_leche(X), tiene_pelo(X). %ej2 miembro(X, [X | Rest]). % X es miembro si es el primer elemento miembro(X, [Y | Rest]) :- miembro(X, Rest). % mira si X esta en el resto %ej3 abuelaDe(X,GM) :- madreDe(X,M), madreDe(M,GM). abuelaDe(X,GM) :- padreDe(X,F), madreDe(F,GM). padreDe(carlos,salastanio). padreDe(salastanio,olivio). padreDe(lucas,olivio). madreDe(carlos,antonia). madreDe(salastanio,maria). madreDe(lucas,maria). </div> <div class="nb-cell query" name="q22"> trace, mamifero(X). </div> <div class="nb-cell query" name="q26"> trace, miembro(X, [b,c,d,a]). </div> <div class="nb-cell query" name="q27"> trace, miembro(d, [d,c,d,d]). </div> <div class="nb-cell query" name="q28"> trace, abuelaDe(carlos, X). </div> <div class="nb-cell html" name="htm27"> <h3>Listas</h3> <p>La lista es una estructura de datos simple que almacena secuencialmente elementos de cualquier tipo (incluso listas). Es flexible, por lo que no tiene un tamaño fijo. Cada lista tiene una cabeza (el primer elemento) y una cola (la lista conformada por todos los elementos de la lista excluído el primero).</p> <ul> <h4>Obtener el elemento en una determinada posición:</h4> </ul> </div> <div class="nb-cell program" name="p21"> kesimoElemento(Cabeza, [Cabeza | _], 1). kesimoElemento(Elemento, [_ | Resto], Posicion):- Posicion > 1, Posicion1 is Posicion - 1, kesimoElemento(Elemento, Resto, Posicion1). </div> <div class="nb-cell query" name="q36"> kesimoElemento(E, [1, 4, 5, 2, 3, 1], 2) </div> <div class="nb-cell html" name="htm25"> <h3>Resolución SLD</h3> <p>Selección-Resolución Lineal-Cláusula definida, el método de resolución básico que emplea Prolog para resolver casos de no-determinismo.</p> </div> <div class="nb-cell program" name="p20"> longitud([], 0). longitud([_ | T], N):- longitud(T, N1), N is N1 + 1. </div> <div class="nb-cell query" name="q35"> longitud([1, 2], L) </div> <div class="nb-cell html" name="htm28"> <ul> <h4>Bubble Sort</h4> <p>En Prolog, para el algoritmo de Bubble Sort es necesario comparar los dos elementos de la lista restante en cada evaluación recursiva y hacer el intercambio de estos en una lista auxiliar, hasta obtener la lista ordenada.</p> </ul> </div> <div class="nb-cell program" name="p22"> swap([X, Y | Resto], [Y, X | Resto]):- X > Y, !. swap([Z | Resto], [Z | RestoAux]):-swap(Resto, RestoAux). bubbleSort(Lista, ListaOrdenada):- swap(Lista, ListaAux), !, bubbleSort(ListaAux, ListaOrdenada). bubbleSort(Lista, Lista). </div> <div class="nb-cell query" name="q37"> bubbleSort([13, 2, 5, 6, 1, 2, 7, 21], B) </div> <div class="nb-cell html" name="htm20"> <ul> <h4> Merge Sort </h4> <p> En Prolog, para el algoritmo de merge sort es necesario realizar dos pasadas, la primera para realizar el merge y otra para copiar del vector auxiliar al vector original. </p> </ul> </div> <div class="nb-cell program" name="p14"> mergesort([],[]). mergesort([A],[A]). mergesort([A,B|R],S):- partir([A,B|R],L1,L2), mergesort(L1,S1), mergesort(L2,S2), merge(S1,S2,S). partir([],[],[]). partir([A],[A],[]). partir([A,B|R],[A|Ra],[B|Rb]):-partir(R,Ra,Rb). merge(A,[],A). merge([],B,B). merge([A|Ra],[B|Rb],[A|M]):-A =< B,merge(Ra,[B|Rb],M). merge([A|Ra],[B|Rb],[B|M]):-A > B,merge([A|Ra],Rb,M). </div> <div class="nb-cell query" name="q25"> mergesort([2,5,3,7],R). </div> <div class="nb-cell html" name="htm8"> <h3> Grafos </h3> Los grafos pueden ser representados de multiples formas en Prolog.<br> Dependiendo del tipo de grafo (dirigido o no dirigido) la representacion varía: <ol> <li> Grafos no dirigidos: El grafo no dirigido presentado se puede representar de cuatro formas diferentes.</li> <p align="center"><br> <img src="https://www.ic.unicamp.br/~meidanis/courses/mc336/2009s2/prolog/problemas/graph1.gif"> </p> <li> Grafos dirigidos: Los cuatro tipos de representación varían para un grafo dirigido como el siguiente:</li> <p align="center"><br> <img src="https://www.ic.unicamp.br/~meidanis/courses/mc336/2009s2/prolog/problemas/graph2.gif"> </p></ol> </div> <div class="nb-cell program" name="p17"> %GRAFOS NO DIRIGIDOS %forma arista-hecho arista(b,c). arista(b,f). arista(c,f). arista(f,k). arista(g,h). %forma grafo-termino grafo([b,c,f,k,g,h,d],[e(b,c),e(b,f),e(c,f),e(f,k),e(g,h)]). %forma de lista de adyacencia % Grafo = [n(b,[c,f]),n(c,[b,f]),n(f,[b,c,k]),n(k,[f]),n(d,[]),n(g,[h]),n(h,[g])]. %forma aristas y nodos % Grafo = [b-c, f-c, g-h, d, f-b, k-f, h-g]. %GRAFO DIRIGIDOS %forma arco-hecho arco(u,r). arco(u,s). arco(s,u). arco(s,r). arco(v,u). %forma grafo-termino digrafo([r,s,t,u,v],[a(s,r),a(s,u),a(u,r),a(u,s),a(v,u)]). %forma de lista de adyacencia: no puede determinar si es un gráfo o un dígrafo. % Digrafo = [n(r,[]),n(s,[r,u]),n(t,[]),n(u,[r]),n(v,[u])] %forma aristas y nodos: Si existe un arco del nodo n1 a n2, este se representa como n1 > n2. % Digrafo = [s > r, s > u, u > r, u > s, v > u, t]. </div> <div class="nb-cell html" name="htm23"> <h4> Ejemplo de grafos: Encontrar todos los caminos de un nodo a otro.</h4> <p>Teniendo la representacion de un grafo G en Prolog como sus aristas, es decir, sea G1:</p> <center> <img src="https://i2.paste.pics/de2a83098194deece2946a4b5157cc74.png"> </center> Y su representación dada por: </div> <div class="nb-cell program" name="p18"> arista(e,d). arista(e,c). arista(c,b). arista(c,a). arista(a,b). arista(d,b). </div> <div class="nb-cell html" name="htm24"> Un nodo A esta conectado con B si existe <b>arista(A,B) o arista(B,A)</b>. <br> Los caminos están representados por la lista de nodos a través de los cuales se debe viajar para pasar del nodo A al nodo B, sin repetir nodos. <br> Luego, para encontrar los caminos de <b> e a d </b> se realiza: </div> <div class="nb-cell program" name="p19"> arista(e,d). arista(e,c). arista(c,b). arista(c,a). arista(a,b). arista(d,b). %ej caso base || camino(p,q,P). arista(p,q). %dos nodos estan conectados si hay una arista entre estos conectados(A,B):- arista(A,B); arista(B,A). camino(A,B,Camino) :- viajar(A,B,[A],Q), %revierte el arreglo Q de los elementos que componen el camino de B a A y lo pone en camino reverse(Q,Camino). %caso base...si A y B estan conectados, se agrega B al inicio del arreglo que contiene a A (P) viajar(A,B,P,[B|P]) :- conectados(A,B). %si A, B no estan conectados, se debe buscar un C conectado a A tal que C sea diferente de B %que no pertenezca a la parte visitada anteriormente del camino y se continua buscando un camino %desde C hasta B viajar(A,B,Visitados,Camino) :- conectados(A,C), C \== B, \+member(C,Visitados), viajar(C,B,[C|Visitados],Camino). </div> <div class="nb-cell query" name="q29"> camino(e,d,P). </div> </div>