Download "Siempre hay alguien a quien todos aman." El orden

Survey
yes no Was this document useful for you?
   Thank you for your participation!

* Your assessment is very important for improving the work of artificial intelligence, which forms the content of this project

Document related concepts

Lógica de primer orden wikipedia, lookup

Axioma wikipedia, lookup

Predicado (lógica) wikipedia, lookup

Lógica de segundo orden wikipedia, lookup

Igualdad matemática wikipedia, lookup

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