Inteligencia Artificial3.2 Lgica de Primer Orden

ObjetivoPresentar una lgica suficiente para construir agentes basados en el conocimiento.

IntroduccinLa lgica proposicional es uno de los lenguajes de representacin ms sencillos, que permite mostrar las cuestiones fundamentales.Sin embargo, su ontologa es muy limitada, y abarca slo aquellos mundos constituidos por hechos. La lgica de primer orden tiene alcances ontolgicos ms amplios. Considera el mundo constituido por objetos y propiedades que los distingan.

IntroduccinEntre estos objetos hay varios tipos de relaciones, algunas de las cuales son las funciones.EjemplosObjetos: gente, casas, nmeros, teoras, Ronald McDonald, colores, juegos de bisbol, guerras, siglos, Relaciones: hermano de, mayor que, dentro de, parte de, de color, sucedi luego de, es el dueo de, Propiedades: rojo, redondo, de varios pisos, falso, lo mejor, Funciones: padre de, mejor amigo de, tercer tiempo de, uno ms que,

IntroduccinUno ms dos es igual a tresObjetos: uno, dos, tres, uno ms dos.Relacin: es igual aFuncin: msLos cuadros cercanos al wumpus apestanObjetos: cuadros, wumpusPropiedad: apestososRelacin: cercanaEl malvado rey Juan gobern Inglaterra en 1200Objetos: Juan, Inglaterra, 1200Relacin: gobernPropiedades: malvado, rey

Sintaxis y semnticaEn la lgica proposicional, cada expresin es una oracin, que representa un hecho. En la lgica de primer orden hay oraciones, pero tambin trminos que representan objetos. Los signos que representan constantes, las variables y los signos de funciones sirven todos para construir trminos; los cuantificadores y los signos de predicados sirven para construir oraciones.

Sintaxis y semnticaElementosSignos de constantes: A, B, C, JuanSignos de predicado: Redondo, HermanoEjemplo, Hermano hace referencia al conjunto de tuplas { }Signos de funciones: Coseno, PadreDe, PiernaIzquierdaDeSon relaciones de en las que un objeto est relacionado justamente con otro objeto.

Sintaxis y semnticaTrminosUn trmino es una expresin lgica que se refiere un objeto. Los signos de constante son trminos.A veces es ms prctico utilizar una expresin para referirse a un objeto, por ejemplo, en vez de LaPiernaIzquierdaDeJuan es ms prctico usar PiernaIzquierdaDe(Juan)

Sintaxis y semnticaOraciones atmicasLos trminos y signos de predicado se combinan para formar oraciones atmicas, mediante las que se afirman hechos.Una oracin atmica est formada por un signo de predicado y por una lista de trminos entre parntesis, ejemploHermano (Ricardo, Juan)Casado (PadreDe (Ricardo), MadreDe (Juan))Se dice que una oracin atmica es verdadera si la relacin a la que alude el signo de predicado es vlida para los objetos a los que aluden los argumentos.

Sintaxis y semnticaOraciones complejasMediante los conectores lgicos se pueden construir oraciones ms complicadas, como en clculo proposicional, ejemplo:Hermano (Ricardo, Juan) Hermano (Juan, Ricardo)Mayor (Juan, 30) Menor (Juan, 30)Mayor (Juan, 30) Menor (Juan, 30)Hermano (Robin, Juan)

Sintaxis y semnticaCuantificadoresLos cuantificadores permiten expresar propiedades de grupos completos de objetos en vez de enumerarlos por sus nombres.La lgica de primer orden contiene dos cuantificadores estndar, denominados universales y existenciales.

Sintaxis y semnticaCuantificacin universal ()Facilita la expresin de reglas generales, ejemplo: en vez de decir Mancha es un gato y Mancha es un mamfero se usa:x Gato (x) Mamfero (x) Lo cual equivale aGato (Mancha) Mamfero (Mancha) Gato (Rebeca) Mamfero (Rebeca) Gato (Flix) Mamfero (Flix) Gato (Juan) Mamfero (Juan)

Sintaxis y semnticaCuantificacin universal ()Por lo tanto la primera expresin ser valida si y slo si todas estas ltimas son tambin verdaderas, es decir, si P es verdadera para todos los objetos x del universo. Por lo tanto, a se le conoce como cuantificador universal.Cuando un trmino no tiene variables se le conoce como trmino de base.

Sintaxis y semnticaCuantificacin existencial ()Con ella podemos hacer afirmaciones sobre cualquier objeto del universo sin tener que nombrarlo, ejemplo, si queremos decir que Mancha tiene un hermano que es un gato:x Hermano (x, Mancha) Gato (x)En general, x P es verdadero si P es verdadero para cierto objeto del universo.

Sintaxis y semnticaCuantificacin existencial ()x Hermano (x, Mancha) Gato (x) equivale a las oraciones:(Hermano (Mancha, Mancha) Gato (Mancha)) (Hermano (Rebeca, Mancha) Gato (Rebeca)) (Hermano (Flix, Mancha) Gato (Flix)) (Hermano (Ricardo, Mancha) Gato (Ricardo)) As como es el conector natural para , es el conector natural para .

Sintaxis y semnticaCuantificadores anidadosPara toda x y toda y, si x es el padre de y, entonces y es el hijo de xx,y Padre (x,y) Hijo (y,x)Para toda x y toda y, si x es hermano de y, entonces y es hermano de xx,y Hermano (x,y) Hermano (y,x)Todas las personas aman a alguienx y Aman (x,y)Siempre hay alguien a quien todos amany x Aman (x,y)

Sintaxis y semnticaUna oracin como x P (y), en la que y carece de cuantificador, es incorrecta.El trmino frmula bien configurada o fbc se emplea para calificar oraciones en las que todas sus variables se han introducido adecuadamente.

Sintaxis y semnticaRelaciones entre y Ambos cuantificadores estn estrechamente relacionados entre s mediante la negacin. A todos les desagradan las espinacas No hay alguien a quien le gusten las espinacasx LeGustan(x, espinacas) x LeGustan (x, espinacas)A todos les gusta el helado No hay alguien a quien no le guste el heladox LeGusta(x, helado) x LeGusta (x, helado)

Sintaxis y semnticaRelaciones entre y Puesto que es una conjuncin de objetos del universo y es su disyuncin, es natural que obedezcan las leyes de De Morgan:

Sintaxis y semnticaIgualdadPara formular aseveraciones en las que los dos trminos se refieren a un mismo objeto se utiliza el smbolo de igualdad:Padre(Juan) = EnriqueEl signo de igualdad sirve para describir las propiedades de una funcin determinada o se puede emplear en la negacin para insistir en que dos trminos no son el mismo objeto:x,y Hermano(Mancha, x) Hermano(Mancha, y) (x=y)

Extensiones en la NotacinLgica de orden superiorEl nombre lgica de primer orden se basa en el hecho de que con ella se cuantifican objetos (las entidades de primer orden que en realidad existen en el mundo), aunque no permiten cuantificar las relaciones o funciones que existen entre dichos objetos.Mediante la lgica de orden superior es posible cuantificar relaciones y funciones al igual que objetos.x,y (x=y) (p p(x) p(y))f,g (f=g) (x f(x) g(x))

Extensiones en la NotacinExpresiones funcionales y de predicado usando el operador .El operador se usa para convertir trminos en funciones, especificando sus argumentos:x,y x2 - y2Esta expresin se aplica a los argumentos para producir un trmino lgico de la misma manera que lo hara una funcin comn:(x,y x2 - y2) (25,24) = 252 242 = 49

Extensiones en la NotacinEl cuantificador de unicidad !Se utiliza para afirmar la existencia de un objeto especfico que satisface determinado predicado.Existe un solo rey! Rey(x)Todo pas tiene exactamente un gobernante c Pas(c) ! r Gobernante(r, c)

Extensiones en la NotacinEl operador de unicidad Se utiliza para representar directamente el objeto especfico, ejemplo:El nico gobernante de Libertania est muertoMuerto ( r Gobernante(r, Libertania)) Que es una abreviatura de ! r Gobernante (r, Libertania) Muerto (r)

Uso de una lgica de primer ordenEn la representacin del conocimiento, un dominio es un fragmento del mundo acerca del que deseamos expresar un determinado conocimiento.

Uso de una lgica de primer ordenEl dominio del parentescoEn este dominio estn presentes hechos tales como Isabel es la madre de Carlos y Carlos s el padre de Guillermo y reglas como Si x es la madre de y y y es padre de z, entonces x es la abuela de zLos objetos de este dominio son personas. Entre las propiedades que poseen estn el gnero y las relaciones que guardan entre s son las de padres, hermanos, esposos, etc. Por lo tanto, hay dos predicados unarios: Hombre y Mujer. La mayora de las relaciones de parentesco sern predicados binarios: Progenitor, Hijo, Hermano, Hermana, Progenie, Hijo, Hija, Esposo, Esposa, Cnyuge, Abuelo, Nieto, Primo, Ta, To.Para Madre y Padre se usarn funciones, puesto que todo mundo cuenta con ellos desde un punto de vista biolgico.

Uso de una lgica de primer ordenEl dominio del parentescoLa madre de alguien es su progenitor femenino:m,c Madre(m,c) Mujer(m) Progenitor(m,c)El esposo de alguien es su cnyuge masculinow,h Esposo(h,w) Hombre(h) Cnyuge(h,w)Masculino y femenino son categoras disyuntas:x Hombre(x) Mujer(x)

Uso de una lgica de primer ordenEl dominio del parentescoProgenitor y progenie son relaciones inversas:p,c Progenitor(p,c) Progenie(c,p) Un(a) abuelo(a) es progenitor del progenitor de alguien:g,c Abuelo_a(g,c) p Progenitor(g,p) Progenitor(p,c)Un hermano es otro de los hijos de los progenitores de alguien:x,y Hermanos(x,y) x y p Progenitor(p,x) Progenitor(p,y)

Uso de una lgica de primer ordenAxiomas, definiciones y teoremasLos matemticos crean axiomas para capturar los hechos bsicos acerca de un dominio, para definir otros conceptos en funcin de tales hechos bsicos y para utilizar los axiomas y las definiciones para demostrar teoremas.Cmo saber si se han postulado una cantidad suficiente de axiomas de tal manera que un dominio quede completamente especificado? Postulando un conjunto de predicados bsicos en funcin de los cuales se pueden definir los dems.Y si tenemos demasiadas oraciones? Revisar cules oraciones no son necesarias y se pueden inferir con otras oraciones.

Uso de una lgica de primer ordenAxiomas, definiciones y teoremasSin embargo, hay axiomas independientes, que son aquellos que no se pueden obtener a partir de otros axiomas.Un axioma como x,y P(x,y) se conoce como definicin de P, porque sirve para definir exactamente para qu objetos P se cumple y para cules no.

Uso de una lgica de primer ordenEl dominio de los conjuntosEn este dominio, ConjuntoVaco es una constante, Miembro y Subconjunto son predicados; Interseccin, Unin y Adyuncin o Incorporacin son funciones. Conjunto es un predicado nicamente vlido en los conjuntos.Los ocho axiomas siguientes estipulan que:Los nicos conjuntos son el conjunto vaco y aquellos que resultan de incorporar algo a un conjuntos Conjunto(s) (s = ConjuntoVacio) (x,s2 Conjunto(s2) s=Adyunto(x, s2))

Uso de una lgica de primer ordenEl conjunto vaco es aquel que no tiene incorporado ningn elemento.x,s Adyunto(x, s) = ConjuntoVacoLa adyuncin de un elemento que ya est en el conjunto no produce efecto alguno.x,s Miembro(x,s) s = Adyunto(x,s)Los nicos miembros de un conjunto son los elementos que ya fueron incorporados a dicho conjunto.x,s Miembro(x) y,s2 (s=Adjunto(y, s2) (x=y Miembro(x,s2)))

Uso de una lgica de primer ordenUn conjunto es subconjunto de otro si y slo si todos los miembros del primer conjunto son miembros del segundo conjunto.s1,s2 Subconjunto(s1,s2) (x Miembro(x, s1) Miembro(x, s2)))Dos conjuntos son iguales si y slo si cada uno de ellos es subconjunto del otro.s1,s2 (s1 = s2) (Subconjunto(s1,s2) Miembro(s2, s1)))

Uso de una lgica de primer ordenUn objeto es miembro de la interseccin de dos conjuntos si y slo si es tambin miembro de cada uno de los conjuntos. x,s1,s2 Miembro (x, Interseccin(s1,s2)) Miembro (x,s1) Miembro (x,s2) Un objeto es miembro de la unin de dos conjuntos si y slo si es tambin miembro de uno de los dos conjuntosx,s1,s2 Miembro (x, Unin(s1,s2)) Miembro (x,s1) Miembro (x,s2)

Uso de una lgica de primer ordenNotaciones especiales para conjuntos, listas y aritmtica

Uso de una lgica de primer ordenCmo formular preguntas y obtener respuestasPara aadirle oraciones a la base de conocimientos BC, diramos:Decir(BC, (m,c Madre(m,c) Mujer(m) Progenitor(m,c)))Decir(BC, (Mujer(Maxi) Progenitor(Maxi,Mancha) Progenitor(Mancha,Botas)))Y luego podramos preguntarPreguntar(BC, Abuelo_a(Maxi, Botas))

Uso de una lgica de primer ordenCmo formular preguntas y obtener respuestasLas oraciones aadidas al utilizar DECIR se llaman aseveraciones.A las preguntas formuladas mediante PREGUNTAR se les conoce como consultas u objetivos.Tambin se pueden hacer preguntas bsicamente cuantificadas como:Preguntar(BC,x Hijo(x,Mancha))Las preguntas del tipo Existe una x tal que? se resuelve proporcionando esa x, mediante una sustitucin o lista de enlace.

Agentes lgicos para el mundo de wumpusSe consideran tres arquitecturas:Agentes reflejosAgentes basados en modelosAgentes basados en metasLo primero que se debe hacer es definir la interfaz entre el agente y el ambiente.Percepcin([Hedor, Brisa, Resplandor, Nada],5)La accin del agente debe ser una de las siguientes:Vuelta(Derecha), Vuelta(Izquierda), Adelante, Disparar, Tomar, Soltar, Saltar

Agentes lgicos para el mundo de wumpusPara decidir cul es la mejor, la funcin HACER-CONSULTA-SOBRE-ACCION crea una consulta tal comoa Accin(a,5)

Un agente reflejo simpleEl ms sencillo de los agentes funciona mediante reglas que conectan directamente percepciones y acciones. Tales reglas se parecen a los reflejos o a los instintos, ejemplo:s,b,u,c,t Percepcin([s,b,Resplandor,u,c],t) Accin(Tomar,t)La relacin entre percepcin y accin puede estar regulada por reglas de percepcin, mediante las cuales se elabora una abstraccin de la entrada perceptual inmediata y se le convierte en formas ms tiles.b,g,u,c,t Percepcin([Hedor,b,g,u,c],t) Hedor(t)s,g,u,c,t Percepcin([s,Brisa,g,u,c],t) Brisa(t)s,b,u,c,t Percepcin([s,b,Resplandor,u,c],t) EnOro(t)

Un agente reflejo simpleDe esta forma, se puede establecer una conexin entre los predicados anteriores y las posibles acciones:t , EnOro(t) Accin(Tomar, t)

Un agente reflejo simpleLimitaciones de los agentes reflejos simplesEl mundo del wumpus es difcil para los simples agentes reflejos.La accin Saltar permite ver el porqu. Un agente reflejo puro no sabe con seguridad cundo saltar, puesto que ni tener el oro ni estar en el cuadro inicial son parte de su percepcin.Tambin son incapaces de evitar los ciclos infinitos.

Cmo representar los cambios en el mundoCualquier sistema que tome sus decisiones basndose en percepciones anteriores puede ser reelaborado para que en vez de tales percepciones utilice un conjunto de oraciones que se refieran al estado actual del mundo.Las reglas que describen la manera como cambia (o no cambia) el mundo se conocen como reglas diacrnicas, del griego a travs del tiempo.

Cmo representar los cambios en el mundoUna manera de manejar el cambio es sustituir oraciones en la BC. La inconveniencia es que pierde todo conocimiento acerca del pasado.Otra es que el agente pueda explorar estados del pasado y posibles estados del futuro, donde cada uno se representa mediante una BC diferenteEn principio, representar situaciones y acciones no es distinto que representar objetos ms concretos como los gatos y los reyes, o relaciones concretas como el hermanazgo.

Cmo representar los cambios en el mundoClculo de situacionesEs el nombre dado para una manera particular de describir el cambio en la lgica de primer orden.Concibe al mundo como una secuencia de situaciones, cada una de las cuales es como una instantnea del estado del mundo.Las situaciones se generan mediante acciones desde situaciones anteriores.

Cmo representar los cambios en el mundoClculo de situacionesPara hacer esto, se proporciona al predicado correspondiente un argumento de situacin adicional. Por ejemplo, en vez de usar En(Agente, ubicacin), tendramosEn(Agente, [1,1],S0 Agente, [1,2],S1)

Cmo representar los cambios en el mundoClculo de situacionesPara representar cmo cambia el mundo de una situacin a otra se emplea la funcin resultado:Resultado (HaciaAdelante,S0) =S1Resultado (DarVuelta(ALaDerecha, S1) =S2Resultado (HaciaAdelante,S2) =S3

Cmo representar los cambios en el mundoClculo de situacionesTambin se cuenta con:Axiomas de efecto, para definir el efecto que produce el realizar alguna accin.Axiomas de cuadro, para describir cmo el mundo permanece igualAxiomas de estado sucesor, para definir cuando un predicado es vlido despus de una accin siempre y cuando sea verdadero o lo siga siendo, y falso en cualquier otro caso.

Hacia un agente basado en metasUna vez encontrado el oro, las polticas deben modificarse radicalmente. El objetivo ahora es regresar al cuadro de partida a la brevedad posible. Lo que ahora desearamos es inferir que el agente tiene como meta encontrarse en la ubicacin [1,1].

Hacia un agente basado en metasLo anterior se puede lograr de tres maneras por lo menos:InferenciaBsquedaPlanificacin