1 Inteligencia Artificial3.3 Inferencia en Lógica de Primer Orden

2 Objetivo Definir mecanismos de inferencia que permiten responder de manera eficiente a preguntas formuladas en lógica de primer orden.

3 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.

4 Reglas de inferencia relacionadas con cuantificadoresYa 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

5 Reglas de inferencia relacionadas con cuantificadoresSe 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)

6 Reglas de inferencia relacionadas con cuantificadoresEliminació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},)

7 Reglas de inferencia relacionadas con cuantificadoresEliminació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},)

8 Reglas de inferencia relacionadas con cuantificadoresIntroducció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},)

9 Ejemplo de una demostraciónDescripció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.”

10 Ejemplo de una demostraciónLo 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.

11 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)

12 Ejemplo de una demostración“Nono…tiene algunos proyectiles” X posee(nono,X)  proyectiles(X) (2)

13 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)

14 Ejemplo de una demostraciónTambién es necesario saber que los proyectiles son armas: X proyectiles(X)  arma (X) (4)

15 Ejemplo de una demostraciónY que a los enemigos de Estados Unidos se les considera como “hostiles”: X enemigo(X,estados_unidos)  hostil(X) (5)

16 Ejemplo de una demostración“…West, un estadounidense…”: estadounidense(west) (6) “El país Nono, …”: nación(nono) (7)

17 Ejemplo de una demostración“…Nono, enemigo de Estados Unidos…”: enemigo(nono, estados_unidos) (8) nación(estados_unidos) (9)

18 Ejemplo de una demostraciónLa 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)

19 Ejemplo de una demostraciónDe (10) y usando Y-Eliminación posee(nono,m1)  proyectiles(m1) (10) posee(nono,m1) (11) proyectiles(m1) (12)

20 Ejemplo de una demostraciónDe (4) y usando Eliminación Universal: X proyectiles(X)  arma (X) (4) proyectiles(m1)  arma (m1) (13)

21 Ejemplo de una demostraciónDe (12) y (13), usando Modus Ponens: proyectiles(m1) (12) proyectiles(m1)  arma (m1) (13) arma(m1) (14)

22 Ejemplo de una demostraciónDe (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)

23 Ejemplo de una demostraciónDe (15) y (10), usando Modus Ponens: posee(nono,m1)  proyectiles(m1)  vende(west, nono, m1) (15) posee(nono,m1)  proyectiles(m1) (10) vende(west, nono, m1) (16)

24 Ejemplo de una demostraciónDe (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)

25 Ejemplo de una demostraciónDe (5) y usando Eliminación Universal X enemigo(X,estados_unidos)  hostil(X) (5) enemigo(nono, estados_unidos)  hostil(nono) (18)

26 Ejemplo de una demostraciónDe (8) y (18), usando Modus Ponens enemigo(nono, estados_unidos) (8) enemigo(nono, estados_unidos)  hostil(nono) (18) hostil(nono) (19)

27 Ejemplo de una demostraciónDe (6), (7), (14), (16) y (19), usando Y-Introducción estadounidense(west) (6) nación(nono) (7) arma(m1) (14) vende(west, nono, m1) (16) hostil(nono) (19) estadounidense(west)  nación(nono)  arma(m1)  vende(west, nono, m1)  hostil(nono) (20)

28 Ejemplo de una demostraciónDe (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)

29 Modus Ponens GeneralizadoAquí 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)

30 Modus Ponens GeneralizadoAquí 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)

31 Modus Ponens GeneralizadoLa 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.

32 Modus Ponens GeneralizadoEn 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).

33 Modus Ponens GeneralizadoEntonces, 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.

34 Modus Ponens GeneralizadoModus 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)

35 Modus Ponens GeneralizadoPara 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) p1 : proyectil(X) p2’ : posee(Y,m1) p2 : posee(nono,X) : {X/m1, Y/nono} q: vende(west, nono, X) SUST(,q): vende(west, nono, m1)

36 Modus Ponens GeneralizadoEl 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.

37 Modus Ponens GeneralizadoForma 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”.

38 Modus Ponens GeneralizadoForma 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)

39 Modus Ponens GeneralizadoUnificació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.

40 Modus Ponens GeneralizadoUnificació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)

41 Modus Ponens GeneralizadoUnificació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)

42 Modus Ponens GeneralizadoUnificació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

43 Modus Ponens GeneralizadoUnificació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}

44 Modus Ponens GeneralizadoUnificació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.

45 Modus Ponens GeneralizadoRegreso 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) (22) posee(nono,m1) (23) proyectil(m1) (24) posee(nono,X)  proyectil(X)  vende(west,nono,X) (25) proyectil(X)  arma(X) (26) enemigo(X,estados_unidos)  hostil(X) (27) estadounidense(west) (28) nación(nono) (29) enemigo(nono,estados_unidos) (30) nación(estados_unidos) (31)

46 Modus Ponens GeneralizadoRegreso 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)

47 Modus Ponens GeneralizadoRegreso a la verificación de muestra De (30) y (27), usando Modus Ponens enemigo(X,estados_unidos)  hostil(X) (27) enemigo(nono,estados_unidos) (30) hostil(nono) (33)

48 Modus Ponens GeneralizadoRegreso 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)

49 Modus Ponens GeneralizadoRegreso 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) (22) estadounidense(west) (28) nación(nono) (29) arma(m1) (32) hostil(nono) (33) vende(west,nono,m1) (34) delincuente(west) (35)

50 Encadenamiento hacia delante y hacia atrásLa 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.

51 Encadenamiento hacia delante y hacia atrásAlgoritmo de encadenamiento hacia delante Renombramiento Composición Activado por datos

52 Encadenamiento hacia delante y hacia atrásAlgoritmo de encadenamiento hacia atrás

53 Completez Incompleto Teorema de Completez Algoritmo de ResoluciónSemidecidible

54 Resolución: Un procedimiento completo de inferencia

55 Resolución: Un procedimiento completo de inferenciaLa regla de inferencia de resolución Resolución generalizada (disyunciones) Resolución generalizada (implicaciones)

56 Resolución: Un procedimiento completo de inferenciaFormas canónicas de resolución Forma normal conjuntiva Forima implicativa normal

57 Resolución: Un procedimiento completo de inferenciaPruebas de resolución Factorización Refutación

58 Resolución: Un procedimiento completo de inferenciaConversión a la forma normal Eskolemización Función de Skolem

59 Resolución: Un procedimiento completo de inferenciaPrueba de ejemplo

60 Resolución: Un procedimiento completo de inferenciaCómo arreglárselas con la igualdad Demodulación Paramodulación

61 Resolución: Un procedimiento completo de inferenciaEstrategias de resolución Preferencia por la unidad Cláusula unitaria Conjunto de apoyo Resolución de entrada Resolución lineal Subsuposición

62 Completez de una resoluciónCompleta 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