Download "Siempre hay alguien a quien todos aman." El orden
Document related concepts
Transcript
Lógica de primer orden Esta lógica tiene un alcance ontológico más amplio que la lógica propositiva. Considera que el mundo está constituido por: OBJETOS: perro, casa, guerra, año, etc. PROPIEDADES: verde, grande, larga, de madera, etc. RELACIONES: hermana de, sucedió luego de, alquila el, etc. FUNCIONES: padre de, amigo de, uno más que, etc. La lógica de primer orden dota a sus usuarios de la libertad de describir todas las cosas de la manera que sea más apropiada para el dominio. Y es universal, en el sentido de que es capaz de expresar todo aquello que se pueda programar. Sintaxis y semántica Signos de constantes: en la interpretación respectiva deberá especificarse a que objeto del mundo se está haciendo referencia mediante el signo de una constante. Ejemplos: A, B, C, María, Lorena, ... Signos de predicado: una interpretación específica que mediante un signo de predicado se hace referencia a una relación particular de un modelo. Las relaciones entre objetos se definen mediante un conjunto de Tuplas que las satisfacen. Ejemplos: Redondo, No Hermano, Hermano, Sucesor, Elemento, ... Signos de funciones: Algunas relaciones son funcionales, es decir, un determinado objeto está relacionado justamente con otro objeto mediante la relación. Ejemplos: Una persona tiene exactamente otra persona que es su padre. Una persona bípeda tiene exactamente una pierna izquierda Un ángulo tiene exactamente un dado valor para su coseno Términos: Un término es una expresión lógica que se refiere a un objeto. Por lo tanto, los signos de constante son términos. En algunos casos resulta más facil utilizar un signo de función que un signo de constante. Ejemplo: PiernaIzquierdaDe(ReyJuan) se refiere a la pierna izquierda del rey Juan Oraciones Atómicas Ahora que ya contamos con términos para referirnos a objetos y signos de predicado para referirnos a relaciones, combinémoslos para formar oraciones atómicas, mediante las que se afirman hechos. Hermano(Ricardo,Juan) afirma que Ricardo es hermano de Juan. Es válido que una oración atómica tenga términos complejos como argumentos: Casado(PadreDe(Ricardo), MadreDe(Juan)) afirma que el padre de Ricardo está casado con la madre de Juan (dentro de una adecuada interpretación). 1 Oraciones Complejas Mediante los conectores lógicos se pueden construir oraciones más complicadas, como en el cálculo proposicional. La semántica de las oraciones formadas utilizando los conectores lógicos es idéntica a la del caso de las proposiciones. Mayor(Juan,50)\/ Menor(Juan, 20) Hermano(Ricardo,Juan)/\ Hermano(Juan,Ricardo) Mayor(Juan,50) => ¬Menor(Juan, 20) ¬Heramno(Roberto, Ricardo) Cuantificadores Los cuantificadores nos dejan expresar propiedades de colecciones de objetos en forma compacta. Cuantificación universal es el cuantificador universal “para todo” x Gato (x) => Mamífero (x) equivale a: Gato (Silvestre) => Mamífero(Silvestre) ^ Gato (Tom) => Mamífero (Tom) ^ Gato (Felix) => Mamífero (Felix) ^ ...... Cuantificación existencial es el cuantificador existencial “existe” x Gato (x) => Mamífero (x) Gato (Silvestre) => Mamífero (Silvestre) v Gato (Tom) => Mamífero (Tom) v Gato (Felix) => Mamífero (Felix) v ...... Cuantificadores anidados En el caso de oraciones más complicadas, se utilizan más de un cuantificador en ellas. A veces se usan varios cuantificadores del mismo tipo x,yMadre(x,y) => Hijo(y,x) Mezcla de cuantificadores: x yAma(x,y) "Todas las personas aman a alguien." <> y xAma(x,y) "Siempre hay alguien a quien todos aman." El orden de los cuantificadores es muy importante. 2 Fórmula bien configurada Antes de ser utilizada una variable, deberá introducirse un cuantificador. y P (x) es una oración incorrecta porque x no está cuantificada. El término fórmula bien configurada o fbc se emplea para calificar oraciones en las que todas sus variables se han introducido adecuadamente. Igualdad Para formular aseveraciones en las que dos términos se refieren a un mismo objeto se utiliza el símbolo de igualdad. Por ejemplo: Padre(Juan)=Enrique está afirmando que el objeto al que hace referencia Padre(Juan) y al objeto al que alude Enrique son lo mismo. Lógica de Orden Superior Mediante la lógica de orden superior es posible cuantificar relaciones y funciones al igual que objetos. Por ejemplo es posible afirmar que dos objetos son iguales si y sólo si todas las propiedades que se le aplican son equivalentes: x,y(x=y) <=> (p p(x) <=> p(y)) También es posible afirmar que dos funciones son iguales si y sólo si para todos los argumentos su valor es el mismo: f,g (f =g) <=> (x f(x) = g(x)) Las lógicas de orden superior tienen más capacidad expresiva que la lógica de primer orden; sin embargo no se sabe mucho acerca de como razonar adecuadamente mediante la lógica de orden superior. 3 7.2 Extensiones Y Variaciones En La Notación Lógica de orden superior Mediante la lógica de orden superior es posible cuantificar relaciones y funciones al igual que objetos. Por ejemplo, mediante la lógica de orden superior es posible afirmar que dos objetos son iguales si y sólo si todas las propiedades que se les aplican son equivalentes: x.y (x=y) ( p p(x) p(y)) O se puede afirmar que dos funciones son iguales si y sólo si para todos los argumentos, su valor es el mismo: f,g (f=g) ( x f(x)=g(x)) La lógica de orden superior tiene más capacidad expresiva que la de primer orden Expresiones funcionales y de predicado usando el operador λ En ocasiones resulta conveniente construir predicados y funciones complejas a partir de componentes sencillos, así como a partir de estos se pueden construir oraciones complejas, o términos complejos a partir de otros más sencillos. El operador λ tradicionalmente se utiliza para este efecto. La función mediante la que se obtiene la diferencia de los cuadrados de sus primeros y segundos argumentos se expresa como: λ x,y x2 – y2 Esta expresión λ se aplica a los argumentos para producir un término lógico de la misma manera que lo haría una función común: (λx,y x2 – y2)(25,24) = 252 – 242 = 49 Es también útil generar expresiones λ y emplearlas en los predicados; por ejemplo, el predicado de dos ubicaciones “son de distinto género y tienen la misma dirección”, se escribe: λx,y Género(x) ≠ Género(y) ^ Dirección(x) = Dirección(Y) La aplicación de una expresión λ de predicado a una determinada cantidad de argumentos produce una oración lógica. El Cuantificador de Unicidad ! El operador se utiliza para decir que algunos objetos existen. Por ejemplo, se emplea la notación: ! Rey (x) Para expresar que “existe un objeto especifico x que satisface Rey(X)”, o dicho de otra manera, “existe precisamente un rey”. x Rey(x) ^ y Rey(y) x=y Si se supiera que solamente hay un rey, hubiéramos utilizado Rey en vez del predicado Rey(x). El siguiente ejemplo “Todo país tiene exactamente un gobernante”, es más compleja: c País(c) ! r Gobernante(r,c) 4 El Operador de Unicidad ι Para especificar la unicidad, a veces es mejor disponer de un término que represente directamente el objeto especifico, para esto se utiliza la notación ιx P(x). Para decir que “el único gobernante de Libertania está muerto”, o su equivalente “ la r que el gobernante de libertania está muerto”, escribiríamos: Muerto(ι r Gobernante(r, Libertania)) Lo que constituye una abreviación de la siguiente oración: ! rGobernanter(r,Libertania) ^ Muerto(r) 7.3 Uso De Una Lógica De Primer Orden En la representación del conocimiento, un dominio es un fragmento del mundo acerca del que deseamos expresar un determinado conocimiento. El dominio del parentesco El primer dominio que consideramos es aquel de los lazos familiares o parentesco. En este domino están presentes hechos tales como “Isabel es la madre de Carlos” y “Carlos es el padre de Guillermo”, y reglas como “Si x es la madre de y y y es el padre de z, entonces x es la abuela de z”. La mayoría de las relaciones de parentesco serán predicados binarios: Progenitor, Hermano, Hermana, Progenie, Hijo, Hija, Esposo, Esposa, Cónyuge, Abuelo, Nieto, Primo, Tío, Tía. Por ejemplo, la madre de alguien viene a ser su progenitor femenino: m,c Madre(c)=m Mujer(m)ΛPadre(m,c) El esposo de alguien es su cónyuge masculino: w,h Esposo(w,h) hhombre(h)ΛEsposa(h,w) Masculino y femenino son categorías disyuntivas: x Hombre(x) ¬Mujer(x) Progenitor y progenie son relaciones inversas: p,c Padre (p,c) Niño(c,p) Axiomas, definiciones y teoremas Los matemáticos crearon axiomas para capturas los hechos básicos acerca de un dominio, para definir otros conceptos en función de tales hechos básicos y para utilizar los axiomas y las definiciones para demostrar teoremas. 5 En matemáticas, un axioma independiente es aquel que no se puede obtener a partir de otros axiomas. Una axioma como x,y P(x,y)≡… se conoce comúnmente como definición de P, porque sirve para definir exactamente para qué objetos P se cumple y para cuáles no. El dominio de los conjuntos Es conveniente tener capacidad de representar conjuntos específicos, incluido el conjunto vacío. Necesitamos saber cómo construir conjuntos añadiendo un elemento a un conjunto o mediante la unión o intersección de dos conjuntos. Emplearemos el vocabulario normal de la teoría de los conjuntos: conjunto Vacío es una constante; Miembro y subconjunto son predicados; Intersección, Unión y Adyunción o Incorporación son funciones. Conjunto es un predicado únicamente válido en los conjuntos. Los ocho axiomas siguientes estipulan que: Los únicos conjuntos son el conjunto vacío y aquellos que resultan de incorporar algo a un conjunto. s Conjunto(s) (s=Conjunto vacío) V ( x,s2 Conjunto(s2)Λ s=Adyunto(x,s2)) El conjunto vacío es aquel que no tiene incorporado ningún elemento. (Es decir, no es posible descomponer ConjuntoVacío en un conjunto más pequeño ni en un elemento.) ¬ x,s adyunto(x,s)=Conjunto vacío La adyunción de un elemento que ya esté en el conjunto no produce efecto alguno. x,s Miembros(x,s) s=Adjuntos(x,s) los únicos miembros de un conjunto son los elementos que ya fueron incorporados a dicho conjunto. Otra manera de expresar esto mismo es diciendo que x es miembro de s si y sólo si s es igual a cierto conjunto s2 incorporado con cierto elemento y, en donde y es igual a x o x e sun miembro de s2. x,s Miembros(x,s) y,s2 (s=Adjunto(y,s2) Λ (x=y V Miembro(x,s2))) Un conjunto es es subconjunto de otro si y sólo si todos los miembros del primer conjunto son miembros del segundo conjunto. s1,s2 Sunconjunto(s1,s2) ( x Miembro (x,s1) Miembro(x,s2)) Dos conjuntos son iguales si y sólo si cada uno de ellos es un subconjunto del otro. s1,s2 (s1=s2) (Subconjunto(s1,s2)Λ Miembro(x,s2)) Un objeto es miembro de la intersección de dos conjuntos si y sólo si es también miembro de cada uno de los conjuntos. 6 x,s1,s2 Miembro(x,Intersección(s1,s2)) Miembro(x,s1)ΛMiembro(x,s2) Un objeto es miembro de la unión de dos conjuntos si y sólo si es también miembro de cada uno de los conjuntos. x,s1,s2 Miembro(x,Unión(s1,s2)) Miembro(x,s1) Λ Miembro(x,s2) El dominio de las listas es muy semejante al de los conjuntos. Como formular preguntas y obtener respuestas Para formular preguntas y obtener respuestas es necesario saber cómo se emplean Decir y Preguntar en la lógica de primer orden. Si deseáramos añadir las oraciones que se refieren al parentesco a una base de conocimientos BC; solicitaríamos: Decir(BC, ( m,c Madre(c) = m Mujer(m) ^ Padre(m,c)) Ahora si decimos: Decir(BC, (Mujer(Maxi) ^ Padre (Maxi,Mancha) ^ Padre(Mancha, Botas))) Podemos entonces: Preguntar(BC, Abuelo(Maxi,Botas)) Y obtener respuesta afirmativa. A las oraciones añadidas al utilizar DECIR se les denomina aseveraciones, y a las preguntas formuladas mediante PREGUNTAR se les conoce como consultas u objetivos (que no deberán confundirse con el término meta que se emplea para describir los estados que desea alcanzar un agente). Agentes Lógicos Para El Mundo Del Wumpus En temas anteriores como agentes basados en conocimiento y cómo podría construirse el agente para el mundo del wumpus, las limitaciones de l´0ogica proposicional no permitían la construcción del agente. Contando con la lógica de primer orden se cuenta con la capacidad de representación necesaria y podemos concentrarnos mas en cómo organizar el agente todo aquello que sap, de manera tal que las acciones que emprenda sean las adecuadas. LOGICA DE PRIMER ORDEN: Lenguaje de representación de propósito general basado en un compromiso ontológico con la existencia de objetos y de relaciones en el mundo. Consideraremos ahora 3 arquitecturas de agente: Agentes Reflejos, que se limitan a clasificar las percepciones recibidas y producen la respuesta respectiva, también se conocen como agentes tropistas. Ejemplo: Una planta heliotrópica siempre se orienta hacia el sol. * Agentes basados en modelos, los cuales construyen una representación interna del mundo y la emplean para producir sus acciones. 7 Agentes basados en metas, que elaboran metas y se esfuerzan por alcanzarlas. Pasos para la construcción del agente para el mundo del wumpus Definir la interface entre el ambiente y el agente. La oración debe incluir la percepción como el momento en que se produjo y para representar las etapas temporales se emplearan números enteros. Percepción ([Hedor, Brisa, Resplandor, Nada], 5) El agente debe responder con acción en un tiempo determinado. La acción debe ser una de las siguientes: Vuelta (Derecha), Vuelta (Izquierda), Adelante, Disparar, Tomar, Soltar, Saltar Un agente de reflejo simple El más sencillo de los agentes ya que funciona mediante reglas que conectan directamente percepciones y acciones, como reflejos o instintos. Ejemplo: Si el agente ve un resplandor tiene que alargar la mano y tomar para así recoger otro. Percepción ([Resplandor],t) Acción(Tomar,t) De esta forma se puede establecer una conexión entre los predicados anteriores y las posibles acciones. Esta regla es más flexible que la relación directa, puesto que permite utilizarla con otros medios para deducir que se está en Oro, por ejemplo cuando se tropieza con dicho oro. Es más de un ambiente complejo, la percepción puede ser todo un arreglo de valores de color y de tonos grises y las reglas de percepción tendrán que inferir cosas como “Hay una camioneta grande tras de mía la derecha con sus luces encendidas”. Limitaciones de los agentes reflejos simples Un agente óptimo deberá decidir entre recuperar el oro o determinar que es demasiado peligroso tomarlo, y entonces regresar al cuadro de partida y saltar fuera de la cueva. Un agente reflejo puro no sabe con seguridad cuándo Saltar, puesto que ni tener el oro ni estar en el cuadro inicial forman parte de la percepción. Son incapaces de evitar bucles infinitos. Supóngase que el agente tomó el oro y se dirige a casa, es probable que entre en alguno de los cuadros en los que estuvo antes y vuelva a tener la misma percepción. 8 Cómo representar los cambios en el mundo En el diseño del agente, todas las percepciones se añaden a la base de conocimiento y, en principio, el historial de percepciones está todo lo que hay que saber acerca del mundo. Si se incorporan reglas que se refieren a percepciones del pasado tan buenas como las actuales. Las reglas que describen la manera como cambia el mundo (o cómo no cambia) como reglas diacrónicas. Cálculo de situaciones Es el nombre dado para una manera particular de describir el cambio en la lógica de primer orden. Concibe el mundo como una secuencia de situaciones, cada una de las cuales es como una instantánea del estado del mundo. Cómo mantener un registro de la ubicación En el mundo del Wumpus la ubicación es quizás lo mas importante; aunque no lo pueda percibir directamente, el agente tiene que recordar dónde ha estado y qué fue lo que vio para así deducir en dónde se encuentran los precipicios y los Wumpus y también asegurarse de realizar una exploración completa en busca del oro. Como deducir propiedades ocultas del mundo Una vez que el agente sabe en donde se encuentra, esta en posibilidad de asociar cualidades con las ubicaciones, en vez de limitarse a relacionarlas con las situaciones. Un ejemplo de ello, es cuando un agente está en un sitio y percibe brisa, ese lugar entonces es airoso; si el agente percibe un hedor, el sitio es apestoso; este razonamiento lo podemos deducir con estas sentencias: 1,s Ent(Agente,1,s)ΛBrisa(s)=>Airoso(I) 1,s Ent(Agente,1,s)ΛOloroso(s)=>Hedor(I) Al descubrir que sitios son airosos o apestosos y mas importante aun cuando no lo son; el agente podrá deducir que cuadros no implican ningún riesgo y de esta forma usar esta información para buscar el oro. A los axiomas que escribiremos para capturar toda la información necesaria para hacer estas deducciones se les denomina sincrónicas, es decir, al mismo tiempo; puesto que relacionan las propiedades de un estado del mundo con otras propiedades del mismo estado del mundo. Existen dos tipos principales de reglas sincrónicas, que son: 9 Reglas casuales Reflejan la dirección de casualidad asumida en el mundo, cierta propiedad oculta del mundo provoca la generación de ciertas percepciones. Por ejemplo, reglas que especifiquen que los cuadros adyacentes a los Wumpus apestan y que los cuadros adyacentes a los precipicios son airosos: I1,I2,s En(Wumpus,I1,s)Λadyacente(I1,I2)=>Oloroso(I2) Los sistemas que razonan apoyados en reglas causales se denominan sistemas de razonamiento basado en modelos. Reglas de diagnóstico Las reglas de diagnóstico infieren la presencia de propiedades ocultas direct5amente desde la información derivada de las percepciones. En el ejemplo anterior, vimos ya dos reglas de diagnóstico: 1,s Ent(Agente,1,s)ΛBrisa(s)=>Airoso(I) 1,s Ent(Agente,1,s)ΛOloroso(s)=>Hedor(I) Al tratar de deducir la presencia de los Wumpus, las reglas de diagnóstico solo permiten obtener conclusiones muy pobres, por ejemplo, que si una ubicación apesta entonces el Wumpus esta en ese sitio o en una ubicación adyacente. 1,s En(Wumpus,I1)=> ( I2 En(Wumpus,I2,s)Λ(I2=I1Vadyacente(I1,I2)) Si bien las reglas de diagnostico parecerían ofrecer la información deseada de manera mas directa, es falso asegurar que permiten obtener las conclusiones mas sólidas a partir de la información disponible. Por ejemplo, la ausencia de hedor o brisa, implica que no hay ningún problema con los cuadros adyacentes OK. x,y,g,u,c,s Percepción([g,u,c,].t)Λ En(Agente,x,s)Λadyacente(x,u)=>OK(y) Pero hay veces que no hay problema en un cuadro OK, aun cuando abunden hedores o brisas. La regla basada en un modelo x,t (¬En(Wumpus,x,t)Λ¬Percepcion(x)) =>OK(x) es posiblemente la mejor manera de representar una situación segura. 10 La diferencia entre razonamiento basado en un modelo y el razonamiento por diagnostico es muy importante en muchas áreas de la IA. En particular, para el área de investigación, la regla de diagnostico ha hecho aportaciones importantes, en donde los métodos basados en la asociación directa entre síntomas y enfermedades (enfoque basado en diagnostico) se han ido reemplazando gradualmente por métodos donde se utiliza un modelo explicito del proceso de una enfermedad y de cómo se manifiesta en síntomas. Lo importante es tener presente que si los axiomas describen de manera correcta y total la manera como funciona el mundo y como se producen las percepciones; el procedimiento de inferencia obtendrá correctamente la descripción mas sólida del estado del mundo a partir de las percepciones disponibles. Preferencia de una acción en vez de otra Al momento, hemos visto que solo se disponen de dos formas para escoger acciones las cuales consisten en elaborar reglas que las recomienden con base en ciertas condiciones del mundo. Sin embargo, el explorar y desplazarse por cuadros señalados con OK, pero no tomando en cuenta los cuadros en los que se percibe un resplandor; por tanto, el considerarlas, seria arbitrario y significa que las reglas no son modulares: los cambios en las creencias del agente acerca de ciertos aspectos del mundo requerirán también de un consecuente cambio de reglas que se refieren a otros aspectos. Esta modularidad se facilita al separar los hechos referidos a acciones de los hechos referidos a las metas, lo que implica que nuestro agente se puede reprogramar tan solo con pedirle que haga algo diferente. Un primer paso consiste en describir que tan deseables son determinadas acciones y dejar a ala maquina de inferencias el decidir cual de las acciones es la mas deseable. Utilizando escalas simples, el agente deberá realizar una acción (por ejemplo excelente) siempre que la pueda encontrar, de no ser así, ir bajando el grado de aceptación de la acción. a,s Estupenda(a,s) => Accion(a,s) a,s Buena(a,s) Λ(¬Estupenda(b,s))=> Accion(a,s) a,s Regular(a,s) Λ(¬Estupenda(b,s) V Buena(bs))=> Accion(a,s) a,s Riesgosa(a,s) Λ(¬Estupenda(b,s) V Buena(b,s) V OK (b,s))=> Accion(a,s) A un sistema que consta de reglas como las anteriores se le denomina sistema de valor de las acciones. Nótese que las reglas no se refieren a lo que en si producen las acciones, sino a que tan deseables son: Hacia un agente basado en metas El anterior conjunto de aservaciones sobre el valor de las acciones basta para definir una política de exploración razonablemente inteligente. Es posible mostrar que un agente que utilice estos axiomas siempre tendrá éxito en encontrar el oro siempre que haya una secuencia de acciones seguras para hacerlo. Lo anterior ya es obtener bastante de un agente lógico. 11 Una vez encontrado el oro, las políticas deberán modificarse radicalmente. El objetivo ahora es regresar al cuadro de una partida a la brevedad posible. Lo que ahora desearíamos hacer es inferir que el agente tiene como meta encontrarse en la ubicación. s Sostener(oro,s)=> UbicacionMeta[1,1],s) La existencia de una meta explicita permite al agente diseñar una secuencia de acciones que permitirán alcanzar la meta. Existen por lo menos tres maneras de determinar tal secuencia: Inferencia No es difícil elaborar axiomas que nos permitan PREGUNTAR a la BC una secuencia de acciones que garantice alcanzar la meta sin riesgo. En el caso del mundo 4X4 del Wumpus, esto es posible, pero para mundos mayores las necesidades de computo resultan excesivamente grandes. De cualquier forma, tenemos el problema de diferenciar entre buenas y malas soluciones (estas ultimas son las que producen una larga serie de jugadas antes de lograr dar con la pista correcta) Búsqueda Se puede emplear un procedimiento de búsqueda preferente por lo mejor para encontrar una ruta que conduzca a la meta. Para ello, el agente deberá traducir su conocimiento de un conjunto de operadores, así como la correspondiente representación del estado, a fin de poder aplicar el algoritmo de búsqueda. Planificación Implica el uso de sistemas de razonamiento de propósito especial diseñados para razonar acerca de las acciones. 12