<div class="notebook"> <div class="nb-cell markdown" name="md1"> </div> <div class="nb-cell markdown" name="md2"> # Hechos </div> <div class="nb-cell markdown" name="md3"> ## Ejemplo 1: #### Tomando como referencia el árbol genealógico se pueden determinar las siguientes reglas: </div> <div class="nb-cell program" name="p18"> </div> <div class="nb-cell program" data-background="true" name="p1"> %Relaciones progenitor(clara,jose). %Hecho 1 progenitor(tomas, jose). %Hecho 2 progenitor(tomas,isabel). %Hecho 3 progenitor(jose, ana). %Hecho 4 progenitor(jose, patricia). %Hecho 5 progenitor(patricia,jaime). %Hecho 6 </div> <div class="nb-cell markdown" name="md4"> #### a. ¿clara es bisabuela de jaime? </div> <div class="nb-cell html" name="htm1"> <style> mark { background-color: #F7FE2E; color: black; } </style> <p align="center"><mark>?-progenitor(clara,X)</mark>, progenitor(X,Y), progenitor(Y,jaime).</p> <p align="center">|</p> <p align="center">X=jose</p> </div> <div class="nb-cell markdown" name="md5"> Inicalmente analiza el primer objetivo ?-progenitor(clara,X) de la conjunción de objetivos, según el árbol la variable X será instanciada a *jose* </div> <div class="nb-cell html" name="htm2"> <p align="center">?-progenitor(clara,X), progenitor(X,Y), progenitor(Y,jaime).</p> <p align="center">|</p> <p align="center">X=jose</p> <p align="center">?-progenitor(clara,jose), <mark>progenitor(jose,Y), progenitor(Y,jaime).</mark></p> <p align="center">Y=ana *</p> </div> <div class="nb-cell markdown" name="md6"> Dentro de una misma pregunta (conjunción de objetivos), las variables con el mismo nombre se refieren al mismo objeto, por tanto prolog seguirá comprobando "progenitor(jose,Y), progenitor(Y,jaime)”. En la base de datos el primer hecho que coincide para progenitor(jose,Y) es *ana*, por tanto se instanciará Y= ana y prolog hará una marca de posición en este punto para ese objetivo. Ahora se debe comprobar el tercer objetivo con Y=ana. Como en los hechos no existe que progenitor(ana,jaime). Prolog señala el árbol (en este caso con * ). Y desintancia Y. Sigue buscando en la base de datos el siguiente hecho para progenitor(jose,Y) desde el punto donde dejó la marcam por tanto Y se instancia a *patricia*. Ahora debe demostrar que progenitor(jose,patricia). Como este hecho sí está en la base de datos, *X=jose* y *Y=patricia* es una solución a la conjunción de objetivos y realiza una marca en el árbol (para nosotros $). </div> <div class="nb-cell query" data-chunk="2" name="q1"> progenitor(clara,X), progenitor(X,Y), progenitor(Y,jaime). </div> <div class="nb-cell markdown" name="md7"> #### b. Qué representa la consulta: ?-progenitor(jaime,X). </div> <div class="nb-cell query" name="q2"> progenitor(jaime,X). </div> <div class="nb-cell markdown" name="md8"> La respuesta es *false* porque no existe ningún hecho para los hijos de jaime. </div> <div class="nb-cell markdown" name="md9"> #### c. Qué representa la consulta: ?-progenitor(X,jaime). </div> <div class="nb-cell query" name="q3"> progenitor(X,jaime). </div> <div class="nb-cell query" data-chunk="2" name="q4"> progenitor(tomas,X), progenitor(X,Y), progenitor(Y,Z). </div> <div class="nb-cell markdown" name="md10"> La consulta anterior pretende buscar los bisnietos de *tomas*. En este caso sólo tiene un bisnieto que es *jaime* </div> <div class="nb-cell markdown" name="md11"> # Reglas </div> <div class="nb-cell markdown" name="md12"> ## Ejemplo 2: #### a. Con el árbol genealógico del punto anterior, definir las reglas para determinar la madre y el padre. </div> <div class="nb-cell program" data-background="true" name="p2"> /* Equivale a: Para todo X e Y, si X es mujer y X es el progenitor de Y, entonces X es la madre de Y */ madre(X,Y):- mujer(X), progenitor(X,Y). /* Equivale a: Para todo X e Y, si X es hombre y X es el progenitor de Y, entonces X es el padre de Y */ padre(X,Y):- hombre(X), progenitor(X,Y). %Hechos. mujer(clara). mujer(isabel). mujer(ana). mujer(patricia). hombre(tomas). hombre(jose). hombre(jaime). </div> <div class="nb-cell query" data-chunk="5" data-tabled="true" name="q5"> madre(X,Y). </div> <div class="nb-cell markdown" name="md13"> Las filas de la tabla de resultados son las relaciones que se forman según el árbol. - clara es madre de jose - patricia es madre de jaime </div> <div class="nb-cell query" data-chunk="8" data-tabled="true" name="q6"> padre(X,Y). </div> <div class="nb-cell markdown" name="md14"> Como se puede observar en la tabla anterior, se obtie el resultado de todas las parejas que se pueden formar entre padres e hijos según el árbol genealógico. - tomas es padre de jose - tomás es padre de isabel - jose es padre de ana - jose es padre de patricia </div> <div class="nb-cell markdown" name="md15"> #### b. Defina las reglas para determinar los abuelos </div> <div class="nb-cell program" data-background="true" name="p3"> % El abuelo se define como el progenitor de mi progenitor abuelo(X,Y):- progenitor(X,Z), progenitor(Z,Y). </div> <div class="nb-cell markdown" name="md16"> Ahora podemos calcular todos los posibles abuelos que se generan a partir del árbol genealógico. </div> <div class="nb-cell query" data-chunk="10" data-tabled="true" name="q7"> abuelo(X,Y). </div> <div class="nb-cell markdown" name="md17"> También se pueden hacer validaciones para verificar si X es abuelo de Y. </div> <div class="nb-cell query" name="q8"> abuelo(clara,ana). </div> <div class="nb-cell query" name="q9"> abuelo(clara, tomas) </div> <div class="nb-cell markdown" name="md18"> Se puede consultar cuál o cuáles son los abuelos de Y </div> <div class="nb-cell query" data-chunk="5" name="q10"> abuelo(X,jaime) </div> <div class="nb-cell markdown" name="md19"> Se puede averiguar de quién es abuelo X. </div> <div class="nb-cell query" data-chunk="4" name="q11"> abuelo(clara,Y). </div> <div class="nb-cell markdown" name="md20"> ### Reglas recursivas Para hacer uso de reglas recursivas se debe considerar 2 casos: - *Caso básico:* Define cuándo se detiene el cálculo. - *Caso recursivo:* Suponiendo que ya se ha solucionado un caso más simple, cómo descomponer el caso actual hasta llegar al caso básico. </div> <div class="nb-cell markdown" name="md21"> Para ilustrar las reglas recursivas, se creará una regla que calcule los predecesores de una persona según el árbol genealógico usado en el ejemplo. </div> <div class="nb-cell program" data-background="true" name="p4"> %El caso base son los padres. antepasado(X,Y):- progenitor(X,Y). %Los progenitores de mis antepasados también son mis progenitores antepasado(X,Y):- progenitor(X,Z), antepasado(Z,Y). </div> <div class="nb-cell markdown" name="md22"> Calcularemos todas las posibles relaciones de antepasados que se encuentren en el árbol </div> <div class="nb-cell query" data-chunk="20" data-tabled="true" name="Relación de antepasados"> antepasado(X,Y). </div> <div class="nb-cell markdown" name="md23"> Ahora calcularemos todos los antepasados de jaime </div> <div class="nb-cell query" data-chunk="6" name="q12"> antepasado(X,jaime) </div> <div class="nb-cell markdown" name="md24"> # Backtracking Considerando el siguiente ejemplo: </div> <div class="nb-cell program" data-background="true" name="p5"> % Regla compra(X,Y):- sevende(Y), gusta(X,Y), bueno(Y). % Hechos sevende(vestido). sevende(sombrero). sevende(zapatos). % Relaciones gusta(jaime,zapatos). gusta(maria,vestido). gusta(maria,sombrero). bueno(sombrero). </div> <div class="nb-cell markdown" name="md25"> Prolog intenta satisfacer los objetivos de la consulta de izquierda a derecha y para cada uno va probando las cláusulas correspondientes. </div> <div class="nb-cell markdown" name="md26"> #### *Primer intento* - Intentará calcular el primer objetivo de la regla: </div> <div class="nb-cell html" name="htm3"> <style> mark2 { color: #08088A; } mark3 { color: #088A08; } </style> <p>compra(X,Y):- <mark>sevende(Y)</mark>,gusta(X,Y),bueno(Y).</p> </div> <div class="nb-cell markdown" name="md27"> - El primer hecho en la base de datos para el objetivo sevende(Y), es sevende(vestido). Instanciando a Y con vestido y obteniendo: </div> <div class="nb-cell html" name="htm4"> <p>compra(X,<mark2>vestido</mark2>):- sevende(<mark2>vestido</mark2>),gusta(X,<mark2>vestido</mark2>),bueno(<mark2>vestido</mark2>).</p> </div> <div class="nb-cell markdown" name="md28"> - Seguido de esto, buscará la cláusula para sustituir *X* teniendo a vestido como segundo argumento. Primero buscará para el objetivo gusta(X,vestido). Encuentra en la base de datos gusta(maria,vestido). Por tanto se tiene: </div> <div class="nb-cell html" name="htm5"> <p>compra(<mark3>maria</mark3>,<mark2>vestido</mark2>):- sevende(<mark2>vestido</mark2>),gusta(<mark3>maria</mark3>,<mark2>vestido</mark2>),bueno(<mark2>vestido</mark2>).</p> </div> <div class="nb-cell markdown" name="md29"> - La regla fracasa porque el hecho bueno(vestido). no se cumple, por tanto debe devolverse y hacer los cálculos para el hecho siguiente. </div> <div class="nb-cell markdown" name="md30"> #### *Segundo intento* Intentará calcular con el segundo hecho: sevende(sombrero). Ahora la Y queda instanciada con *sombrero*. </div> <div class="nb-cell html" name="htm6"> <p>compra(X,<mark2>sombrero</mark2>):- sevende(<mark2>sombrero</mark2>),gusta(X,<mark2>sombrero</mark2>),bueno(<mark2>sombrero</mark2>).</p> </div> <div class="nb-cell markdown" name="md31"> - Buscar la cláusula para sustituir *X* teniendo a sombrero como segundo argumento. Encuentra en la base de datos gusta(maria,sombrero). Por tanto se tiene: </div> <div class="nb-cell html" name="htm7"> <p>compra(<mark3>maria</mark3>,<mark2>sombrero</mark2>):- sevende(<mark2>sombrero</mark2>),gusta(<mark3>maria</mark3>,<mark2>sombrero</mark2>),bueno(<mark2>sombrero</mark2>).</p> </div> <div class="nb-cell markdown" name="md32"> La regla tiene éxito porque se cumple el hecho bueno(sombrero). </div> <div class="nb-cell markdown" name="md33"> # Listas Existe un conjunto de predicados ya definidos que permiten manipular listas en prolog. Vamos a ver algunos ejemplos </div> <div class="nb-cell markdown" name="md34"> - member(+Term,+List). Verifica si un elemento pertenece a una lista </div> <div class="nb-cell query" name="q13"> member(a,[b, a, t, s]). </div> <div class="nb-cell markdown" name="md35"> - subset(+List1,+List2). Verifica si una sublista pertenece a una lista </div> <div class="nb-cell query" name="q14"> subset([bill, joe, ted],[joe, bill, sally, ted]). </div> <div class="nb-cell markdown" name="md36"> #### Ejemplos a). Encontrar el último elemento de la lista </div> <div class="nb-cell program" data-background="true" name="p6"> % (element,list) ultimo(X,[X]). ultimo(X,[_|L]) :- ultimo(X,L). </div> <div class="nb-cell query" name="q15"> ultimo(X,[a,b,c,d]). </div> <div class="nb-cell markdown" name="md37"> b). Encontrar el k-ésimo elemento de una lista </div> <div class="nb-cell program" data-background="true" name="p7"> % (elemento,lista,entero) elemento_k(X,[X|_],1). elemento_k(X,[_|L],K) :- K > 1, K1 is K - 1, elemento_k(X,L,K1). </div> <div class="nb-cell query" name="q16"> elemento_k(X,[a,b,c,d,e],3). </div> <div class="nb-cell markdown" name="md38"> c). Verifica si el número dado corresponde a la longitud de una lista </div> <div class="nb-cell program" data-background="true" name="p8"> % (lista,entero) % Note: length(?List, ?Int) is predefined longitud([],0). longitud([_|Cola],N) :- longitud(Cola,N1), N is N1 + 1. </div> <div class="nb-cell query" name="q17"> longitud([a,b,c,d],4). </div> <div class="nb-cell markdown" name="md39"> d). Verifica si una lista es palindroma o no. </div> <div class="nb-cell markdown" name="md40"> </div> <div class="nb-cell program" data-background="true" name="p9"> es_palindromo(L) :- reverse(L,L). </div> <div class="nb-cell query" name="q18"> es_palindromo([a,b,b,a]). </div> <div class="nb-cell markdown" name="md41"> e). Crear una lista que contenga los enteros de un rango dado. </div> <div class="nb-cell program" data-background="true" name="p10"> % (entero,entero,lista) rango(I,I,[I]). rango(I,K,[I|L]) :- I < K, I1 is I + 1, rango(I1,K,L). </div> <div class="nb-cell query" name="q19"> rango(4,9,L). </div> <div class="nb-cell markdown" name="md42"> f). Sumar los elementos de una lista </div> <div class="nb-cell program" data-background="true" name="p11"> suma([],0). suma([X|L],N) :- suma(L,C), N is C + X. </div> <div class="nb-cell query" name="q20"> suma([1,2,2,3],R) </div> <div class="nb-cell markdown" name="md43"> # Ejercicio 1 </div> <div class="nb-cell program" data-background="true" name="p12"> ciudad(bogota). ciudad(cali). ciudad(bucaramanga). ciudad(medellín). ciudad(cartagena). ciudad(villavicencio). </div> <div class="nb-cell query" name="q21"> ciudad(bogota). </div> <div class="nb-cell query" data-chunk="10" name="q22"> ciudad( X ). </div> <div class="nb-cell markdown" name="md44"> # Ejercicio 2 </div> <div class="nb-cell program" data-background="true" name="p13"> fact(0,1). fact(N,F) :- N>0, Nmenos1 is N-1, fact(Nmenos1,F1), F is N*F1. </div> <div class="nb-cell query" data-chunk="100" name="q23"> fact(4, Y). </div> <div class="nb-cell markdown" name="md45"> # Ejercicio 3 </div> <div class="nb-cell program" data-background="true" name="p14"> sumar([],R):- R=0. sumar([X|Y],R) :- sumar(Y, R1), R = R1+X. tamaño([],0). tamaño([X|Y], N):-tamaño(Y, N1), N is N1+1. </div> <div class="nb-cell query" name="q24"> sumar([1,2,3]). </div> <div class="nb-cell markdown" name="md46"> # Ejercicio grafos </div> <div class="nb-cell markdown" name="md47"> Construir el grafo presentado en clase y responder las siguientes preguntas: - Existe una conexión entre A e I?. - ¿Con qué nodos está conectado F y cuál es el costo de cada conexión? - Construir una regla para determinar si un nodo tiene aristas de salida. - Construir una regla que de el costo de ir de un nodo X a Y pasando por un nodo Z </div> <div class="nb-cell program" data-background="true" name="p15"> edge(a,b). edge(b,e). edge(a,c). edge(c,d). edge(e,d). edge(d,f). edge(d,g). path(X,Y) :- edge(X,Y). path(X,Y) :- edge(X,Z), path(Z,Y). </div> <div class="nb-cell query" name="q25"> findall(X, path(a,X), List). </div> <div class="nb-cell markdown" name="md48"> # Ejercicio AFD Construir el autómata presentado en clase y verificar para las cadenas: - bbaabab - bba </div> <div class="nb-cell program" data-background="true" name="p16"> parse(L) :- inicio(S), %estado inicial del automata transicion(S,L). transicion(X,[A|B]) :- delta(X,A,Y), % Transicion X ---a---> Y write(X), write(' '), write([A|B]), nl, %Genera una nueva linea transicion(Y,B). transicion(X,[]) :- %Caso base final(X), % estado final del autómata write(X), write(' '), write([]), nl. </div> <div class="nb-cell program" data-background="true" name="p17"> delta(0,a,1). delta(0,b,0). delta(1,a,1). delta(1,b,2). delta(2,a,2). delta(2,b,2). inicio(0). %Estado inicial final(2). %Estado final </div> <div class="nb-cell query" name="q26"> parse([b,b,a,a,b,a,b]). </div> <div class="nb-cell query" name="q27"> parse([b,b,a]). </div> </div>