Inteligencia Artificial
3.3 Inferencia en Lógica de Primer
Orden
Objetivo
 Definir mecanismos de inferencia que
permiten responder de manera eficiente a
preguntas formuladas en lógica de primer
orden.
Introducción
 Se ha definido el concepto de inferencia y
se ha mostrado que tan sólida y completa
es la inferencia que puede obtenerse para
el caso de la lógica proposicional.
 En este tema, los resultados anteriores se
hacen extensivos a la lógica de primer
orden.
Reglas de inferencia relacionadas
con cuantificadores
 Ya se han visto las reglas de inferencia que se utilizan
en lógica proposicional:





Modus ponens
Y-eliminación
Y-introducción
O-introducción
Resolución
 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
Reglas de inferencia relacionadas
con cuantificadores
 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:
 SUST({X/sam, Y/futbol}, le_gusta(X,Y)) =
le_gusta(sam,futbol)
Reglas de inferencia relacionadas
con cuantificadores
 Eliminación Universal:
 Para toda oración , variable v y término de
base g :
v 
SUST({v/g},)
Por ejemplo, en X le_gusta(X, helado),
podemos utilizar la sustitución {X/ben} e
inferir que le_gusta(ben, helado).
Reglas de inferencia relacionadas
con cuantificadores
 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:
v 
SUST({v/k},)
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.
Reglas de inferencia relacionadas
con cuantificadores
 Introducción Existencial:
 Para toda oración , variable v que no esté en  y
término de base g que no esté presente en :

v SUST({g/v},)
Por ejemplo, en le_gusta(jerry,helado) podemos
inferir que X le_gusta(X, helado).
Ejemplo de una demostración
 Descripción de la situación en lenguaje
natural:
 “La ley establece que se considera como
delito el que un estadounidense venda armas
a naciones enemigas. El país Nono, enemigo
de Estados Unidos, tiene algunos proyectiles,
todos los cuales le fueron vendidos por el
coronel West, un estadounidense.”
Ejemplo de una demostración
 Lo que se desea demostrar es que West
es un delincuente.
 Empezaremos por representar estos
hechos en la lógica de primer orden, y
luego se verá que la demostración
consiste en una secuencia de aplicación
de las reglas de inferencia.
Ejemplo de una demostración
 “…es delito que un estadounidense venda
armas a naciones enemigas”
X,Y,Z estadounidense(X)  arma(Y) 
nación(Z)  hostil(Z)  vende(X,Z,Y) 
delincuente(X)
(1)
Ejemplo de una demostración
 “Nono…tiene algunos proyectiles”
X posee(nono,X)  proyectiles(X)
(2)
Ejemplo de una demostración
 “Todos sus proyectiles (que posee Nono)
le fueron vendidos por el coronel West”
X posee(nono,X)  proyectiles(X) 
vende(west, nono, X)
(3)
Ejemplo de una demostración
 También es necesario saber que los
proyectiles son armas:
X proyectiles(X)  arma (X)
(4)
Ejemplo de una demostración
 Y que a los enemigos de Estados Unidos
se les considera como “hostiles”:
X enemigo(X,estados_unidos)  hostil(X)
(5)
Ejemplo de una demostración
 “…West, un estadounidense…”:
estadounidense(west)
(6)
 “El país Nono, …”:
nación(nono)
(7)
Ejemplo de una demostración
 “…Nono, enemigo de Estados Unidos…”:
enemigo(nono, estados_unidos)
(8)
nación(estados_unidos)
(9)
Ejemplo de una demostración
 La demostración consiste en una serie de
aplicaciones de las reglas de inferencia:
 De (2) y usando Eliminación Existencial
X posee(nono,X)  proyectiles(X)
(2)
posee(nono,m1)  proyectiles(m1)
(10)
Ejemplo de una demostración
 De (10) y usando Y-Eliminación
posee(nono,m1)  proyectiles(m1)
posee(nono,m1)
(11)
proyectiles(m1)
(12)
(10)
Ejemplo de una demostración
 De (4) y usando Eliminación Universal:
X proyectiles(X)  arma (X)
proyectiles(m1)  arma (m1)
(4)
(13)
Ejemplo de una demostración
 De (12) y (13), usando Modus Ponens:
proyectiles(m1)
(12)
proyectiles(m1)  arma (m1)
arma(m1)
(14)
(13)
Ejemplo de una demostración
 De (3), usando Eliminación Universal:
X posee(nono,X)  proyectiles(X) 
vende(west, nono, X)
(3)
posee(nono,m1)  proyectiles(m1) 
vende(west, nono, m1)
(15)
Ejemplo de una demostración
 De (15) y (10), usando Modus Ponens:
posee(nono,m1)  proyectiles(m1) 
vende(west, nono, m1)
(15)
posee(nono,m1)  proyectiles(m1)
vende(west, nono, m1)
(10)
(16)
Ejemplo de una demostración
 De (1) y usando Eliminación Universal tres
veces
X,Y,Z estadounidense(X)  arma(Y) 
nación(Z)  hostil(Z)  vende(X,Z,Y) 
delincuente(X) (1)
estadounidense(west)  arma(m1) 
nación(nono)  hostil(nono)  vende(west, nono,
m1)  delincuente(west)
(17)
Ejemplo de una demostración
 De (5) y usando Eliminación Universal
X enemigo(X,estados_unidos) 
hostil(X)
(5)
enemigo(nono, estados_unidos) 
hostil(nono)
(18)
Ejemplo de una demostración
 De (8) y (18), usando Modus Ponens
enemigo(nono, estados_unidos) (8)
enemigo(nono, estados_unidos) 
hostil(nono)
(18)
hostil(nono)
(19)
Ejemplo de una demostración
 De (6), (7), (14), (16) y (19), usando Y-Introducción
estadounidense(west)
nación(nono)
arma(m1)
vende(west, nono, m1)
hostil(nono)
(6)
(7)
(14)
(16)
(19)
estadounidense(west)  nación(nono)  arma(m1) 
vende(west, nono, m1)  hostil(nono)
(20)
Ejemplo de una demostración
 De (17) y (20), usando Modus Ponens
estadounidense(west)  arma(m1) 
nación(nono)  hostil(nono)  vende(west, nono,
m1)  delincuente(west)
(17)
estadounidense(west)  nación(nono) 
arma(m1)  vende(west, nono, m1) 
hostil(nono)
(20)
delincuente(west)
(21)
Modus Ponens Generalizado
 Aquí se presenta una generalización de la regla de
inferencia de Modus Ponens mediante la que en un solo
paso se logra lo que en la prueba anterior requería de la
Y-introducción, Eliminación Universal y el Modus
Ponens.
 La ida es ser capaz de tomar una base de
conocimientos que contenga, por ejemplo:
 proyectil(m1)
 posee(nono,m1)
 X proyectil(X)  posee(nono,X)  vende(west, nono, X)
 E inferir en un solo paso la nueva oración
 vende(west, nono, m1)
Modus Ponens Generalizado
 Aquí se presenta una generalización de la regla de
inferencia de Modus Ponens mediante la que en un solo
paso se logra lo que en la prueba anterior requería de la
Y-introducción, Eliminación Universal y el Modus
Ponens.
 La ida es ser capaz de tomar una base de
conocimientos que contenga, por ejemplo:
 proyectil(m1)
 posee(nono,m1)
 X proyectil(X)  posee(nono,X)  vende(west, nono, X)
 E inferir en un solo paso la nueva oración
 vende(west, nono, m1)
Modus Ponens Generalizado
 La clave consiste en determinar alguna X de la
base de conocimiento tal que X sea un proyectil
y que Nono sea el propietario de X, para luego
inferir que West vende este proyectil a Nono.
 Generalizando, si hay alguna sustitución que
involucra X y que haga que la premisa de la
implicación idéntica a las oraciones que ya
están en la base de conocimiento, entonces
podemos afirmar la conclusión de la implicación,
después de aplicar la sustitución.
 En el caso anterior, {X / m1} permite realizar
esto.
Modus Ponens Generalizado
 En realidad Modus Ponens puede servirnos
para más cosas. Supongamos que en vez de
saber que posee(nono,m1), supiéramos que
todos los países del mundo poseen el proyectil
m1:
 Y posee(Y,m1)
 Y nos gustaría concluir que vende(west, nono,
m1). Esta inferencia podría realizarse si
aplicáramos primero la Eliminación Universal
con la sustitución {Y / nono} y obtener así
posee(nono,m1).
Modus Ponens Generalizado
 Entonces, suponiendo que la BC contiene:
 proyectil(m1)
 Y posee(Y,m1)
 X proyectil(X)  posee(nono,X)  vende(west, nono, X)
 Y se quiere inferir que
 vende(west, nono, m1)
 Mediante modus ponens generalizado, esto se puede
hacer en un solo paso, determinando una sustitución
tanto para las variables de la implicación como para las
variables de las oraciones que se quieren cotejar.
 La sustitución {X / m1, Y / nono} a las premisas posee(Y,
m1) y posee(nono,X) las convierte en idénticas.
Modus Ponens Generalizado
 Modus Ponens Generalizado: Para
todas las oraciones atómicas pi, pi’ y q, en
las que existe una sustitución  tal que
SUST(, pi’ ) = SUST(, pi’) para toda i:
p1’, p2’, …, pn’, (p1  p2  …  pn  q)
SUST(, q)
Modus Ponens Generalizado
 Para esta regla hay n+1 premisas: las n
oraciones atómicas pi’ y una implicación.
 Hay una conclusión: el resultado obtenido
mediante la aplicación de la sustitución a la q
consecuente.
 Ejemplo, en el caso de West y el proyectil:
 p1’ : proyectil(m1)
 p2’ : posee(Y,m1)
 : {X/m1, Y/nono}
p1 : proyectil(X)
p2 : posee(nono,X)
q: vende(west, nono, X)
 SUST(,q): vende(west, nono, m1)
Modus Ponens Generalizado
 El Modus Ponens generalizado es una regla de
inferencia eficiente por las tres razones siguientes:
 1. Sus pasos son más globales, combina varias inferencias
pequeñas en una sola.
 2. Los pasos que realiza son sensatos: utiliza sustituciones que
garantizan su utilidad, en vez de probar al azar la Eliminación
Universal. El algoritmo de unificación utiliza dos oraciones y
produce una sustitución mediante la cual las oraciones
anteriores resultan idénticas, siempre y cuando exista tal
sustitución.
 3. Consta de un paso de compilación previa mediante el que
todas las oraciones de la base de conocimiento se convierten a
una forma canónica. Si esto se hace desde el principio, se
ahorra tiempo al no tener que hacer conversiones durante la
prueba.
Modus Ponens Generalizado
 Forma canónica
 Para utilizar Modus Ponens Generalizado, todas las
oraciones de la base de conocimiento deben estar
expresadas en forma tal que coincidan con una de las
premisas de la regla del Modus Ponens; de no ser así no
será posible utilizarlas.
 La forma canónica del Modus Ponens Generalizado
determina que cada oración de la base de conocimientos
sea una oración atómica, o una implicación con una
conjunción de oraciones atómicas del lado izquierdo y un
solo átomo a la derecha.
 A este tipo de oraciones se les denomina oraciones de
Horn; a la base de conocimientos formada
exclusivamente por oraciones de Horn se dice que está en
“forma normal de Horn”.
Modus Ponens Generalizado
 Forma canónica
 La conversión en oraciones de Horn se realiza cuando
aquellas son introducidas por primera vez en la BC,
usando:
 Eliminación Existencial
 Y-Eliminación
 Ejemplo:
 X posee(nono,X)  proyectil(X)
 Se convierte en
 posee(nono,m1)
 proyectil(m1)
 Una vez eliminados los cuantificadores existenciales,
los cuantificadores universales se “abrevian”:
 Y posee(Y,m1) se escribe como posee(Y,m1)
Modus Ponens Generalizado
 Unificación
 Lo que hace la rutina de unificación
UNIFICAR es convertir dos oraciones p y q
en una sustitución mediante la cual p y q
resultan idénticas. De no existir tal
unificación, UNIFICAR produce una falla.
 Formalmente:
 UNIFICAR(p,q) = , donde SUST(,p) = SUST(,q)
  se conoce como el unificador de las dos
oraciones.
Modus Ponens Generalizado
 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)
Modus Ponens Generalizado
 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)
Modus Ponens Generalizado
 Unificación
 Al unificar el antecedente de la regla con
cada una de las oraciones de la BC
obtenemos:
 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
Modus Ponens Generalizado
 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. Realmente, en la base de
conocimientos se hubiera colocado conoce(w,isabel) y si se
hubiera unificado.
 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}
Modus Ponens Generalizado
 Unificación
 Realmente, cuando existe una sustitución que
hace que los dos argumentos sean
semejantes, existe una cantidad infinita de
sustituciones.
 Sin embargo, UNIFICAR debe producir el
unificador más general (UMG), que es la
sustitución con la mínima implicación del
enlace de las variables.
Modus Ponens Generalizado
 Regreso a la verificación de muestra
 Resolución del problema de la venta de proyectiles mediante
Modus Ponens Generalizado: Primero hay que expresar la BC
en la forma de Horn:
 estadounidense(X)  arma(Y)  nación(Z)  hostil(Z) 









vende(X,Z,Y)  delincuente(X)
posee(nono,m1)
proyectil(m1)
posee(nono,X)  proyectil(X)
 vende(west,nono,X)
proyectil(X)  arma(X)
enemigo(X,estados_unidos)  hostil(X)
estadounidense(west)
nación(nono)
enemigo(nono,estados_unidos)
nación(estados_unidos)
(22)
(23)
(24)
(25)
(26)
(27)
(28)
(29)
(30)
(31)
Modus Ponens Generalizado
 Regreso a la verificación de muestra
 La demostración consta sólo de cuatro pasos:
 De (24) y (26), usando Modus Ponens:
 proyectil(m1)
(24)
 proyectil(X)  arma(X)
(26)
 arma(m1)
(32)
Modus Ponens Generalizado
 Regreso a la verificación de muestra
 De (30) y (27), usando Modus Ponens
 enemigo(X,estados_unidos)  hostil(X)
 enemigo(nono,estados_unidos)
 hostil(nono)
(27)
(30)
(33)
Modus Ponens Generalizado
 Regreso a la verificación de muestra
 De (23), (24) y (25), usando Modus Ponens:
 posee(nono,m1)
(23)
 proyectil(m1)
(24)
 posee(nono,X)  proyectil(X) 
vende(west,nono,X)
(25)
 vende(west,nono,m1)
(34)
Modus Ponens Generalizado
 Regreso a la verificación de muestra
 De (28), (32), (29), (33), (34) y (22), usando
Modus Ponens:
 estadounidense(X)  arma(Y)  nación(Z) 
hostil(Z)  vende(X,Z,Y)  delincuente(X)
 estadounidense(west)
 nación(nono)
 arma(m1)
 hostil(nono)
 vende(west,nono,m1)
 delincuente(west)
(22)
(28)
(29)
(32)
(33)
(34)
(35)
Encadenamiento hacia delante y
hacia atrás
 La regla de Modus Ponens Generalizado se
puede usar de dos formas:
 Empezando por las oraciones que están en la base
de conocimientos y generar nuevas conclusiones, de
las que, a su vez, se pueden obtener nuevas
inferencias. A esto se le conoce como
encadenamiento hacia delante (forward chaining).
 O bien, se puede empezar por algo que se desea
demostrar, se buscan las oraciones que nos permitan
llegar a tal conclusión y, por último, tratar de
establecer las premisas correspondientes. A esto se
le conoce como encadenamiento hacia atrás
(backward chaining), dado que utiliza el modus
ponens en sentido inverso.
Encadenamiento hacia delante y
hacia atrás
 Algoritmo de encadenamiento hacia
delante
 Renombramiento
 Composición
 Activado por datos
Encadenamiento hacia delante y
hacia atrás
 Algoritmo de encadenamiento hacia atrás
Completez
 Incompleto
 Teorema de Completez
 Algoritmo de Resolución
 Semidecidible
Resolución: Un procedimiento
completo de inferencia
Resolución: Un procedimiento
completo de inferencia
 La regla de inferencia de resolución
 Resolución generalizada (disyunciones)
 Resolución generalizada (implicaciones)
Resolución: Un procedimiento
completo de inferencia
 Formas canónicas de resolución
 Forma normal conjuntiva
 Forima implicativa normal
Resolución: Un procedimiento
completo de inferencia
 Pruebas de resolución
 Factorización
 Refutación
Resolución: Un procedimiento
completo de inferencia
 Conversión a la forma normal
 Eskolemización
 Función de Skolem
Resolución: Un procedimiento
completo de inferencia
 Prueba de ejemplo
Resolución: Un procedimiento
completo de inferencia
 Cómo arreglárselas con la igualdad
 Demodulación
 Paramodulación
Resolución: Un procedimiento
completo de inferencia
 Estrategias de resolución
 Preferencia por la unidad
 Cláusula unitaria
 Conjunto de apoyo
 Conjunto de apoyo
 Resolución de entrada
 Resolución de entrada
 Resolución lineal
 Subsuposición
 Subsuposición
Completez de una resolución
 Completa en cuanto a refutación
 Universo de Herbrand
 Saturación
 Base de Herbrand
 Teorema de Herbrand
 Cierre de la resolución
 Teorema de resolución de base
 Premisa de transferencia
Descargar

Inteligencia Artificial