logic m.c. juan carlos olivares rojas [email protected] february, 2009
TRANSCRIPT
Outline
Sistemas de Deducción
Sistemas de Reacción
Encadenamiento Progresivo y Regresivo
Modelamiento Cognitivo
Modelos para la Resolución de Problemas
Sistemas de Deducción
• Los sistemas de deducción pueden variar dependiendo del problema pero en general se utiliza el método de resolución visto en la unidad pasada.
• Los lenguajes utilizados en IA como LISP y PROLOG tienen su propio motor de inferencia y están sujetos a reglas muy particulares.
Sistemas de Deducción
• ¿Cuál es la diferencia entre un hecho y una afirmación?
• Un hecho es algo que se considera verdadero, una afirmación es una proposición afirmativa que necesita ser demostrada.
• Ejemplos de reglas para identificar animales:
Sistemas de Deducción
• Z1 Si X tiene pelo entonces X es mamífero• Z2 Si X da leche entonces X es mamífero• Z3 Si X tiene plumas entonces X es ave
• Z4 Si X vuela y X come carne entonces es mamífero
• Z5 Si X es mamífero y X come carne entonces X es carnívoro
Sistemas de Reacción• Los sistemas de reacción permite inferir
conocimiento a través de una concatenación de reglas, las cuales pueden ser Progresivas o Regresivas.
• Los sistemas de reacción tratar de anclar consecuentes con antecedentes de las reglas teniendo así sistemas más inteligentes.
• Los sistemas de reacción implican la ejecución de acciones.
Sistemas Reacción
B1 Si el paso es la verificación de la orden
Papas fritas se van a empacar
No se va a empacar Pepsi
Entonces pregunte al cliente si no le gustarían llevar una botella de Pepsi.
• Otras reglas por definir son eliminar y añadir elementos.
Encadenamiento Progresivo y Regresivo
• El encadenamiento de reglas puede ser hacia adelante. En ésta, se inicia con cláusulas atómicas de la base de conocimiento. Luego se aplica el modus Ponens Generalizado hacia delante hasta que ya no se puedan obtener nuevas cláusulas atómicas.
• Las inferencias realizadas son de la forma:• Situación Respuesta⇒
Encadenamiento Progresivo o Regresivo
• Reglas:• R1: si A entonces B.• R2: si B entonces C.• R3: si C entonces Z
• Hechos:• H1: A (dato de partida)• H3: Z (objetivo a alcanzar)
Encadenamiento Progresivo y Regresivo
• En el encadenamiento regresivo se aplica todo lo contrario; es decir, dado un objetivo se pretende llegar al hecho para dar una solución a un problema.
• El encadenamiento regresivo o backtracking permite regresar a una opción anterior en caso de que existieran varios encadenamientos de regla que no llevan a la resolución
Modelamiento Cognitivo
• Los sistemas basados en reglas pueden verse como sustratos, de esta forma se puede tener una forma de introspección del como obtuvieron la deducción; es decir, muestran como se formaron las reglas.
• Los sistemas basados en reglas se les conoce como sabios idiotas, ya que sólo respondan a preguntas fáciles y carecen de muchas de las características del experto del dominio.
Modelos para la Resolución de Problemas
• Los sistemas basados en reglas pueden funcionar como sistemas de producción.
• Siendo sistemas de producción pueden utilizarse para generar nuevo conocimiento de las reglas ya existentes.
PROLOG
• Hechos:• las aves vuelan • los pingüinos no vuelan • "pichurri" es un ave • "sandokan" es un perro • "alegría" es un ave
PROLOG
• Reglas o Restricciones:
• una mascota vuela si es un ave y no es un pingüino
• Preguntas• ¿ "pichurri" vuela ? • ¿ qué mascotas vuelan ?
PROLOG
• Términos: constantes (a), variables (X), funciones (f(X, Y ))
pepe, juan, Cliente, cliente-de(X, Y )
• Fórmulas atómicas: predicados definidos sobre términos
tipo-cliente(X,bueno)
PROLOG• Fórmulas bien formadas (wff): fórmulas atómicas
unidas por conectivas (^, _,!, ¬) y cuantificadas (1A universal, 1B existencial)
• 1AX, 1BZ cliente(X) ^ compra(X, Z) ^ caro(Z) tipo-cliente(X, bueno)
• abuelo(X,Y) :- padre(X,Z), padre(Z,Y).• 1AX, Y 1BZ padre(X, Z) ^ padre(Z, Y) abuelo(X,
Y )
PROLOG
• abuelo(X,Y) :- padre(X,Z), madre(Z,Y).• abuelo(X,Y) :- padre(X,Z), padre(Z,Y).
• abuelo(X, Y) = {(pepe, juan), (pepe, ana), … , (luis, javier)}
• progenitor(X, Y ) :- padre(X, Y ).• progenitor(X, Y ) :- madre(X, Y ).
PROLOG
• abuelo(X,Y) :- padre(X,Z), madre(Z,Y).• abuelo(X,Y) :- padre(X,Z), padre(Z,Y).
• abuelo(X,Y) :- padre(X,Z), progenitor(Z,Y).
• hechos: A. (A átomo)• reglas: A :- A1, ..., An. (n>0, y A, A1, ..., An
átomos)
PROLOG
• Hechos:– padece(jon, gripe). – padece(jon, hepatitis). – padece(ana, gripe). – padece(carlos, alergia).– es-síntoma(fiebre, gripe).– es-síntoma(cansancio, gripe).– es-síntoma(estornudos, alergia).– suprime(paracetamol, fiebre).– suprime(antihistamínico, estornudos).
PROLOG
• Reglas:– debe-tomar(Per, Far) :- padece(Per, Enf),
alivia(Far, Enf).– alivia(Far, Enf) :- es-síntoma(Sin, Enf),
suprime(Far, Sin).
• Preguntas:– ? padece(carlos, gripe).– ? padece(jon, Z).– ? alivia(paracetamol, gripe).
PROLOG
– ? alivia(X, gripe).– ? debe-tomar(Y, antihistamínico).– ? alivia(X, Y).– ? suprime(X, fiebre), suprime(X, estornudos).
• ¿Qué devuelve cada pregunta como resultado?
PROLOG
• hija (*A, *B) <- mujer (*A), padre (*B, *A). • hija (*A, *B) <- mujer (*A), madre (*B, *A).
• A continuación se muestra un programa completo en PROLOG:
%% declaraciones
padrede('juan', 'maria').
padrede('pablo', 'juan').
PROLOG
padrede('pablo', 'marcela').
padrede('carlos', 'debora').
%%Reglas
% A es hijo de B si B es padre de A hijode(A,B) :- padrede(B,A).
abuelode(A,B) :- padrede(A,C), padrede(C,B).
hermanode(A,B) :- padrede(C,A) , padrede(C,B), A \== B.
familiarde(A,B) :- padrede(A,B).
PROLOG
familiarde(A,B) :- hijode(A,B).
familiarde(A,B) :- hermanode(A,B).
%% consultas
% juan es hermano de marcela?
?- hermanode('juan', 'marcela').
Yes
?- hermanode('carlos', 'juan'). No
?- abuelode('pablo', 'maria'). Yes
?- abuelode('maria', 'pablo'). no
PROLOG
%unificación con evaluación.
?- X is 3+5.
X = 8
%unificación simbólica
?- X = 3+5.
X = 3+5
PROLOG
%comparación con evaluación
?- 3+5 =:= 2+6.
yes
%comparación simbólica.
?- 3+5 == 2+6.
no
?- 3+5 == 3+5.
yes
PROLOG
• Los programas en PROLOG se definen a través de Algoritmos, Lógica y Control.
• En caso de que una consulta de más de un resultado, el prompt no aparece en la shell. Se puede utilizar el operador . Para terminar el resultado, o bien, el operador ; para continuar con los emparejamientos de resultados.
• Se pueden combinar preguntas para obtener respuestas más exactas.
PROLOG
• %Combinación de preguntas• legusta(pepe, pesca).• legusta(maria, bailar).• legusta(ana, pesca).• legusta(pepe, musica).• legusta(maria, musica).• legusta(ana, bailar).
• %preguntas
PROLOG• ¿Le gusta la música a Pepé y a María?• ?_ legusta(pepe,musica), legusta(maria, musica).
• ¿Le gusta bailar a Pepé o le gusta la música a maria?
• ?_ legusta(pepe,bailar); legusta(maria, musica).
• ¿Le gusta bailar a Pepé y a maria no le gusta la música?
• legusta(pepe,bailar), not(legusta(maria,musica)).
PROLOG
• El portal de redes sociales de la UVAQ desea diseñar un Sistema Experto para encontrar la pareja ideal de cada estudiante si es que existiere. Para lograr esto, se tienen en la base de conocimientos registrados los gustos de cada usuario (color de ojos, altura, complexión, carro, etc.). Se da un punto por cada coincidencia. Diseñar la regla o reglas que determinen la mejor pareja de cada usuario. (Se deben tener al menos 2 hombres y 2 mujeres con 5 gustos c/u).
PROLOG
• Se puede aplicar recursividad en PROLOG además de que algunos programas en programación estructurada pueden ser implementados.
• %Sucesiones• sucesor(1,2).• sucesor(2,3).• sucesor(3,4).• sucesor(4,5).• sucesor(5,6).
PROLOG
• sucesor(6,7).• suma(1,X,R):-sucesor(X,R).• suma(N,X,R):-sucesor(M,N), suma(M,X, R1),
sucesor(R1, R).
• %Como se crearía una consulta?• %¿Qué es lo que el programa haría?
PROLOG
• Una lista es una secuencia lineal de objetos en donde todas las manipulaciones se hacen del lado izquierdo de la lista.
• La lista vacía se representa []. Una lista que no es vacía debe contener al menos dos elementos, uno del lado izquierdo y otro del lado derecho. Ejemplo: [X | Y], [X, Y | Z].
PROLOG
• agregar([], L, L).• agregar([A|R], L, [A|T]):-agregar(R, L, T).
• %Como se realiza la consulta?• ?- agregar([1,2,3 | [] ], [1, 5,7 | [] ], R).
• Dos predicados com el mismo nombre pero diferente aridad (numero de argumentos) son diferentes.
PROLOG
• %Programa aridad• ama(juan).• ama(pepe, maria).
• La unificación es el proceso en el cual uma variable toma un valor.
• Cuando una variable tiene un valor, este no cambia.
PROLOG• Dos términos se ejecutan cuando existe una
posible ligadura en sus variables y en sus valores. Ejemplo: a(X, 3) = a(2, Y).
• edad(luis,25).• edad(hugo,32).• edad(paco,29).• edad(jaime,67).• edad(laura,85).• es_viejo(Persona) :- edad(Persona,Valor), valor >
60.
Ejercicio
• padre(X,Y) – X es padre de Y• madre(X,Y) – X es madre de Y• es_padre(X) – X es un padre• es_madre(X) – X es una madre• es_hijo(X) – X es un hijo (hombre)• hermana(X,Y) – X es hermana de Y• abuelo(X,Y) – X es abuelo (hombre) de Y• tia(X,Y) – X es tía de Y• primo(X,Y) – X es primo (hombre) de Y
PROLOG
• Prolog tiene la característica de ser reversible; es decir, los argumentos pueden ser de entrada y salida. Si se tiene un predicado abuelo se puede saber quienes son los nietos de ese abuelo.
• Esto no sucede con los operadores aritméticos.
• Otro tipo de datos utilizado en Prolog es el registro. El cual es una combinación de elementos.
PROLOG
• Por ejemplo: persona(‘Eva’, ‘López’, ‘Cárdenas’, 25)
• Define a una persona teniendo como atributos su nombre, sus apellidos y su edad. Dado que los términos son anidados se pueden tener registros como:
• Persona(“Helena”, edad(22), dirección(‘Miguel Hidalgo 33’, ‘Centro’, ‘Morelia’))
PROLOG
• Se pueden utilizar estructuras de datos recurrentes como árboles, en donde el primer elemento podría ser un nodo, el segundo el hijo izquierdo y el tercer elemento, el hijo derecho.
• arbol(dato1, temp, temp)• arbol(dato1, arbol(dato2, temp, temp), temp)
• En donde temp indica un campo vacío.
PROLOG
• ¿Qué diferencia existe entre las siguientes listas?
• L= [1, 2, 3, 4, 5],• M = [0, L].
• L = [1, 2, 3, 4, 5],• M = [0 | L].
• Las listas pueden ser de elementos heterogéneos como: [1, p(a), [a, b], f(g(h))]
PROLOG
• El predicado member nos permite saber si un elemento existe en la lista
• ?- member(3, [1,2,3,4,5,6]). %regresa true
• El método append/3 sirve para concatenar listas
• ?- append([1,2,3], [a, b, c], X).
• Las cadenas pueden ser tratadas como listas cuando se escriben con comillas dobles.
PROLOG
• Por ejemplo la cadena X=“ABC” es equivalente a X=[65, 66, 67].
• Los predicados utilizados para listas, también nos sirven para cadenas.
• La función number_codes/2 convierte un número a cadena.
• ? number_codes(12, X). % X=[49, 50].
PROLOG
• La función atom_codes/2 proporciona el código equivalente de una cadena.
• ?- atom_codes(juan, X).• X = [106, 117, 97, 110].
• //Comprobación de tipos• es_lista([]).• es_lista([_|B]):-es_lista(B).
PROLOG
• ?- es_lista([a]).
• Existen ya predicados definidos para la comprobación de tipos de datos básicos como: integer/1, float/1, number/1, atom/1, var/1, novar/1, ground/1.
PROLOG
• % Ejemplo • entrada(paella). • entrada(gazpacho). • entrada(consome). • carne(filete_de_cerdo). • carne(pollo_asado). • pescado(trucha). • pescado(bacalao). • postre(flan).
PROLOG
• postre(nueces_con_miel). • postre(naranja). • calorias(paella, 200). • calorias(gazpacho, 150). • calorias(consome, 300). • calorias(filete_de_cerdo, 400). • calorias(pollo_asado, 280). • calorias(trucha, 160). • calorias(bacalao, 300).
PROLOG
• calorias(flan, 200). • calorias(nueces_con_miel, 500). • calorias(naranja, 50). • plato_principal(P):- carne(P); pescado(P). • comida(Entrada, Principal, Postre):-
entrada(Entrada), plato_principal(Principal), postre(Postre).
• valor(Entrada, Principal, Postre, Valor):- calorias(Entrada, X), calorias(Principal, Y), calorias(Postre, Z), sumar(X, Y, Z, Valor).
PROLOG
• comida_equilibrada(Entrada, Principal, Postre):- comida(Entrada, Principal, Postre), valor(Entrada, Principal, Postre, Valor), menor(Valor, 800).
• sumar(X, Y, Z, Res):- Res is X + Y + Z. • menor(X, Y):- X < Y. • dif(X, Y):- X \==Y. • • Encontrar: ¿Cuántas calorías tiene la combinación
paella, trucha, naranja? ¿Qué comida que tiene cónsome de entrada es la más balanceada?
PROLOG
• Se pueden definir funciones recursivas como el factorial:
• fac(0,1).• fac(N,F) :- N > 0, M is N - 1, fac(M,Fm), F is N
* Fm.
• ¿Cómo se expresa la serie de fibonnaci?
PROLOG
• Algo sumamente importante en cualquier lenguaje de programación son las interfaces de E/S y Prolog no es la excepcion.
• Se cuenta con los predicados read/1 para leer el valor de variables seguidas por un punto y get para leer carácter por carácter regresando el código ASCII correspondiente.
Prolog
• Para salida estándar se cuenta con las funciones write/1 para cualquier valor, put/1 para colocar un carácter. Adicionalmente se cuenta con las relaciones nl/0 para nueva línea y display/1 para mostrar mensajes en pantalla.
• A continuación se muestra el ejemplo de un programa que utiliza entrada y salida, así como un manejo estructurado de programa.
PROLOG
• sumar_lista([],Parcial,Parcial).
• sumar_lista([Num|Resto],Parcial,Result) :- NParcial is Num+Parcial, sumar_lista(Resto,NParcial,Result).
• leer_numero(Num) :- read(Num), number(Num).
PROLOG
• suma :- suma_aux([]).
• suma_aux(Lista) :- leer_numero(Num), suma_aux([Num|Lista]).
• suma_aux(Lista) :- sumar_lista(Lista,0,Result), nl, display('LA SUMA ES : '), display(Result), nl.
Questions?