1/42 mg. samuel oporto díaz lima, 16 de julio 2005 inferencia en lógica de predicados inteligencia...
Post on 16-Feb-2015
14 Views
Preview:
TRANSCRIPT
11 /42/42
Mg. Samuel Oporto Díaz Lima, 16 de Julio 2005
Inferencia en Lógica de Predicados
INTELIGENCIA ARTIFICIAL
22 /42/42
Tabla de Contenido
1. Sustitución.
2. Unificación
3. Reglas de Inferencia con Cuantificadores
4. Formas Canónicas para Resolución
5. Bibliografía
33 /42/42
Objetivos• Exponer los mecanismos de inferencia en lógica
de Predicados.• Presentar los conceptos de Sustitución y
Unificación.• Ampliar la técnica de Resolución a la Lógica de
Predicados• Exponer las reglas de inferencia con
cuantificadores.• Exponer las formas canónicas de la resolución.• Exponer los conceptos del probador de
teoremas (refutación)
44 /42/42
SUSTITUCION
55 /42/42
Término Base (Ground term)
• El término base es:– Una constante
• Taki• Piedra• Pedro
– El resultado de una función donde todas sus entradas son términos base.
• loriana(Lunes)
• policia(Asiri)
66 /42/42
Sustitución
• Se utilizará la notación SUST(, ) para representar el resultado de aplicar la sustitución (o lista de enlace) a la oración , por ejemplo:
= ConcurreA(x, y) GustaDe(x, y) = {x/Juan, y/CursoIA}
• subst( {x/Juan, y/CursoIA}, ConcurreA(x, y) GustaDe(x, y) )
• ConcurreA(Juan, CursoIA) GustaDe(Juan, CursoIA)
• Juan concurre a curso de IA y Juan gusta de curso de IA.
77 /42/42
Sustitución• Dadas las variables x1, x2, ..., xn y los términos t1, t2, .., tn (sin
variables), la sustitución θ es un conjunto de pares ordenados:
θ = {x1/t1, x2/t2,..,xn/tn} (x/t se lee sustituir x por t)
• La operación consiste en, dado un literal α que contiene x1, x2, .., xn, y una sustitución θ, reemplazar en todos los lugares de α donde aparezca xi por ti.
Ejemplo:subst({X/george, Y/tony}, likes(X,Y)) = likes(george, tony)
Los términos de θ no pueden contener símbolos de constantes ni de función que ya estén en α
88 /42/42
Sustitución• Sustitución vacía {}, cuando no modifica la expresión.
• Composición de la sustitución. Es una sustitución tal que αθ1 θ2=(αθ1) θ2.– La composición de sustituciones es asociativa
(θ1 θ2)θ3 = θ1(θ2 θ3)– Pero no conmutativa
θ1θ2≠θ2θ1
• No se puede calcular la composición resultante uniendo simplemente los conjuntos θ1 y θ2, hemos de aplicar primero θ2 a los términos de θ1 y después añadir los pares de θ2 cuyas variables no están entre los de θ1.
99 /42/42
Ejercicios
Sean:
α = F1(x,y), F2(y,w), F3(x,y,z,r)
θ1 = (x/a, y/b, z/w), θ2 = (w/c), θ3 = (r/b)
Calcular: αθ1θ2θ3
αθ1 = F1(a, b), F2(b,w), F3(a, b, w, r)
αθ1θ2 = F1(a, b), F2(b,c), F3(a, b, c, r)
αθ1θ2θ3 = F1(a, b), F2(b,c), F3(a, b, c, c)
1010 /42/42
Ejercicios• Calcular: θ4 = (θ1θ2)θ3 y luego αθ4
θ1 = (x/a, y/b, z/w), θ2 = (w/c), θ3 = (r/b)• θ12= (x/a, y/b, z/c)• θ4 = (x/a, y/b, z/c, r/b)• αθ4 = F1(a,b), F2(b,w), F3(a,b,c,b)
• Calcular: θ4 = θ1(θ2θ3) y luego αθ4
θ1 = (x/a, y/b, z/w), θ2 = (w/c), θ3 = (r/b)• θ23= (w/c, r/b)• θ4 = (x/a, y/b, z/c, r/b)• αθ4 = F1(a,b), F2(b,w), F3(a,b,c,b)
1111 /42/42
EjerciciosEjercicios = monopolio(M) penalizado(M) = {M/LosGarcia}
subst( {M/LosGarcia}, monopolio(M) penalizado(M) )monopolio(LosGarcia) penalizados(LosGarcia)
= realiza(M,W) feo(W) odiado(M) = {M/Hormel, W/Spam}
subst( {M/Hormel,W/Spam} realiza(M,W)feo(W)odiado(M)) realiza(Hormel, Spam) feo(Spam) odiado(Hormel)
1212 /42/42
UNIFICACION
1313 /42/42
Unificación• Lo que hace la rutina de unificación UNIFICAR es
convertir dos oraciones α y β en una sustitución mediante la cual α y β resultan idénticas. De no existir tal unificación, UNIFICAR produce una falla.
• Formalmente:– UNIFICAR(α, β) = , donde SUST(, α) = SUST(, β)
se conoce como el unificador de las dos oraciones.
1414 /42/42
Unificación• Supongamos que tenemos la regla conoce(juan,X) odia(juan,X) “Juan odia a todos los que conoce”
• Y la queremos utilizar como regla de inferencia de Modus Ponens y poder saber a quién odia Juan. Es decir, tenemos que saber a qué oraciones de la base de conocimiento se unifican a conoce(juan,X).
• Supongamos que nuestra base de conocimiento contiene:– conoce(juan,jane)– conoce(Y,leónidas)– conoce(Y,madre(Y))– conoce(X, isabel)
1515 /42/42
Unificación
Al unificar el antecedente de la regla con cada una de las oraciones de la BC obtenemos:conoce(juan,X) odia(juan,X)
UNIFICAR(conoce(juan,X),conoce(juan,jane)) = {X/jane}
UNIFICAR(conoce(juan,X),conoce(Y,leónidas)) = {X/leónidas, Y/Juan}
UNIFICAR(conoce(juan,X),conoce(Y,madre(Y))) = {Y/juan, X/madre(juan)}
UNIFICAR(conoce(juan,X),conoce(X,isabel))= falla
– conoce(juan,jane)– conoce(Y,leónidas)– conoce(Y,madre(Y))– conoce(X, isabel)
1616 /42/42
Unificación• La última unificación falla, porque X no puede tomar el
valor de juan e isabel al mismo tiempo.• De manera intuitiva, sabemos que Juan odia a todos los
que conoce, y que todos conocen a Isabel, por lo que podríamos inferir que Juan odia a Isabel.
• Para resolver este problema, se pueden normalizar por separado las dos oraciones que se van a unificar, lo que significa renombrar las variables de una de ellas (o de ambas) para evitar que haya repetición de nombres:
UNIFICAR(conoce(juan,x1),conoce(x2,isabel))={x1/isabel, x2/juan}
1717 /42/42
Ejercicio: Unificar y Resolver.
1. femenino(ana)2. femenino(X) Λ padre (Y, X) hija(X, Y)3. padre (juan, ana)
1818 /42/42
Ejercicio: Unificar y Resolver.
femenino(ana) femenino(X) Λ padre (Y, X) hija(X, Y)
padre(Y,ana) hija(ana,Y)
hija(ana, juan)
padre (juan, ana)
θ1 = (X/ana)
θ2 = (Y/juan)
1. femenino(ana)2. femenino(X) Λ padre (Y, X) hija(X, Y)3. padre (juan, ana)
1919 /42/42
Tarea• Para cada uno de los siguientes pares de oraciones,
indique el unificador más general, o diga que no existe y explique por qué.
• El unificador más general es el que permite que pocas variables o funciones no sean cambiadas a constantes como sea posible.
1. P(x, y, y) y P(A, f(B), f(z))
2. P(x, F(x), A) y P(y, y, z)
3. P(x, y, z) y Q(A, B, B)
4. Q(x, F(y, A), z) y Q(A, F(A, A), x)
5. Q(x, G(y, y), w, F(z, z)) y Q(H(u, v), v, A, F(x, y))
2020 /42/42
Reglas de Inferencia con cuantificadores
2121 /42/42
Reglas de Inferencia con cuantificadores• Reglas de inferencia utilizadas en lógica proposicional:
• También son válidas en la lógica de primer orden, pero se requieren reglas de inferencias adicionales para manejar las oraciones de lógica de primer orden con cuantificadores:– Eliminación Universal– Eliminación Existencial– Introducción Existencial.
Modus ponensY-eliminaciónY-introducciónO-introducción
Doble negación eliminaciónResolución unitariaResolución
2222 /42/42
Eliminación Universal
• Para toda oración , variable v y término de base g :
Por ejemplo, en x le_gusta(x, helado), podemos utilizar la sustitución {x/ben} e inferir que:
le_gusta(ben, helado).
v SUST({v/g},)
Término de Base: Es aquél término en el que no hay variables; es decir, un símbolo constante o un símbolo de función aplicados a algunos términos de base.
2323 /42/42
Eliminación Existencial
• Para toda oración , variable v y símbolo constante k que no aparezca en ninguna parte de la base de conocimientos:
Por ejemplo, en x matar(x, víctima), podemos inferir que matar(asesino, víctima) en tanto que asesino no aparezca en ninguna parte de la base de conocimientos.
v SUST({v/k},)
Es importante que la constante k usada para la sustituir la variable sea una variable nueva
2424 /42/42
Introducción Existencial
• Para toda oración , variable v que no esté en y término de base g que no esté presente en :
Por ejemplo, en le_gusta(jerry,helado) podemos inferir que X le_gusta(X, helado).
v SUST({g/v},)
2525 /42/42
EjemploAxiomas:Es ilegal que un turista venda huacos en Rusia x,y Turista(x) Λ huacos(y) Λ Vender(x,y)=>Infractor(x)
Diego es un turista en RusiaTurista(Diego)
Cada uno de los turistas en Rusia venden algunos huacosx,y Turista(x) Λ Huacos(y) Λ Vende(x,y)
¿Es Diego un infractor?Infractor(Diego)
2626 /42/42
EjemploEliminación Universal: SUST({x/Diego}, )x,y Turista(x) Λ Huacos(y) Λ Vender(x,y)=>Infractor(x) Turista(Diego) Λ Huacos(y) Λ Vender(Diego,y)=>Infractor(Diego)
Eliminación Universal: SUST({x/Diego}, )
x,y Turista(x) Λ Huacos(y) Λ Vende(x,y)Turista(Diego) Λ Huacos(y) Λ Vende(Diego,y)
2727 /42/42
EjemploEliminación Universal: SUST({x/Diego}, )x,y Turista(x) Λ Huacos(y) Λ Vender(x,y)=>Infractor(x) Turista(Diego) Λ Huacos(y) Λ Vender(Diego,y)=>Infractor(Diego)
Eliminación Universal: SUST({x/Diego}, )
x,y Turista(x) Λ Huacos(y) Λ Vende(x,y)Turista(Diego) Λ Huacos(y) Λ Vende(Diego,y)
Turista(Diego) Λ Huacos(y) Λ Vender(Diego,y)=>Infractor(Diego)
Turista(Diego) Λ Huacos(y) Λ Vende(Diego,y)
Infractor(Diego)
2828 /42/42
Formas Canónicas para Resolución
Formas Canónicas: Regla de Resolución
1. Forma normal conjuntiva (CNF). Disyunción de literales.2. Forma normal implicativa (INF). Conjunciones en la
izquierda que implica las disyunciones en el derecho.
• La CNF es más común, pero la INF es más "natural" para el análisis humano.
Original KB CNF INF
x P(x) Q(x) P(w) Q(w) P(w) Q(w)
x P(x) R(x) P(x) R(x) True P(x) R(x)
x Q(x) S(x) Q(y)S(y) Q(y) S(y)
x R(x) S(x) R(z)S(z) R(z) S(z)
A, A B True A, A B
B True B
Ejercicio: Unificar y resolver por Resolución.
1. P(w) Q(w)2. Q(y) S(y)3. True P(x) V R(x)4. R(z) s(z)
Ejercicio: Unificar y resolver por Resolución.
1. P(w) Q(w)2. Q(y) S(y)3. True P(x) V R(x)4. R(z) s(z)
3232 /42/42
Probador de Teoremas• Conocido como:
– Refutación.– Demostración por contradicción– Reducción al absurdo
• Consiste en que para demostrar P(x), suponemos que P(x) es falsa (se añade –P(x) a la BD) y se demuestra la contradicción
[BD [BD ΛΛ ¬¬P(x) P(x) Falso] Falso] [BD [BD P(x)] P(x)]
Probador de TeoremasPrueba por refutación: (1). P P (2). (P Q) R P Q R (3). (S T) Q S Q (4). T QProbar R: (5). T T
Probador de TeoremasPrueba por refutación: (1). P P (2). (P Q) R P Q R (3). (S T) Q S Q (4). T QProbar R: (5). T T
P Q R R
P Q
T Q
P
Q
T T
nil
3535 /42/42
Ejercicio: Unificar y resolver por Resolución.
1. -PhD(x) V HQ(x)2. -HQ(x) V Rich(x)3. PhD(x) V ES(x)4. -ES(x) V Rich(x)
Probar Rich(Me)
3636 /42/42
Ejercicio: Unificar y resolver por Resolución.
1. -PhD(x) V HQ(x)2. -HQ(x) V Rich(x)3. PhD(x) V ES(x)4. -ES(x) V Rich(x)5. Probar Rich(Me)
3737 /42/42
Ejemplo
1. x [y animal (y) ama(x,y)] [y ama(y,x)]
2. x [y animal (y) Λ mata(x,y)] [z ¬ama(z,x)]
3. x animal (x) ama(Bush,y)
4. mata(Bush,Fido) V mata(Wolfowitz,Fido)
5. perro(Fido)
6. x perro(x) animal (x)
Probar: mata(Wolfowitz, gato)
7. ¬mata(Wolfowitz, Fido)
3838 /42/42
Ejemplo
Convirtiendo a lógica de predicados:1. [animal (y) ama(x,y)] ama(G, x)
2. [animal (H) Λ mata(x, H)] ¬ama(z,x)
3. animal (x) ama(Bush,y)
4. mata(Bush,Fido) V mata(Wolfowitz,Fido)
5. perro(Fido)
6. perro(x) animal (x)
7. ¬mata(Wolfowitz, Fido)
3939 /42/42
Ejemplo
Convirtiendo a CNF:1. animal (y) V ama(G, x)
2. - ama(x, y) V ama(G, x)
3. -animal (H) V -mata(x, H) V ¬ama(z, x)
4. -animal (x) V ama(Bush, y)
5. mata(Bush, Fido) V mata(Wolfowitz, Fido)
6. perro(Fido)
7. - perro(x) V animal (x)
8. ¬mata(Wolfowitz, Fido)
4040 /42/42
Ejemplo
animal (y) V ama(G, x)
- ama(x, y) V ama(G, x)
-animal (H) V -mata(x, H) V ¬ama(z, x)
-animal (x) V ama(Bush, y)
mata(Bush, Fido) V mata(Wolfowitz, Fido)
perro(Fido) - perro(x) V animal (x)
¬mata(Wolfowitz, Fido)
4141 /42/42
Tarea(1) man(Marcus)
(2) Pompeian(Marcus)
(3) x Pompeian(x) Roman(x)
(4) ruler(Caesar)
(5) x Roman(x) loyalto(x, Caesar) hate(x, Caesar)
(6) x y loyalto(x, y)
(7) x y person(x) ruler(y) tryassassinate(x, y) loyalto(x, y)
(8) tryassassinate(Marcus, Caesar)
¿Marcus era fiel a César?
4242 /42/42
Bibliografía• AIMA. Capítulo 8, primera edición.• AIMA. Chapter 9, second edition.
top related