Download 3.2 Lógica de primer orden

Inteligencia Artificial
3.2 Lógica de Primer Orden
Objetivo

Presentar una lógica suficiente para
construir agentes basados en el
conocimiento.
Introducción



La lógica proposicional es uno de los lenguajes
de representación más sencillos, que permite
mostrar las cuestiones fundamentales.
Sin embargo, su ontología es muy limitada, y
abarca sólo aquellos mundos constituidos por
hechos.
La lógica de primer orden tiene alcances
ontológicos más amplios. Considera el mundo
constituido por objetos y propiedades que los
distingan.
Introducción


Entre estos objetos hay varios tipos de relaciones,
algunas de las cuales son las funciones.
Ejemplos




Objetos: gente, casas, números, teorías, Ronald McDonald,
colores, juegos de béisbol, guerras, siglos, …
Relaciones: hermano de, mayor que, dentro de, parte de, de
color, sucedió luego de, es el dueño de, …
Propiedades: rojo, redondo, de varios pisos, falso, lo mejor, …
Funciones: padre de, mejor amigo de, tercer tiempo de, uno
más que, …
Introducción

“Uno más dos es igual a tres”




“Los cuadros cercanos al wumpus apestan”




Objetos: uno, dos, tres, uno más dos.
Relación: es igual a
Función: más
Objetos: cuadros, wumpus
Propiedad: apestosos
Relación: cercanía
“El malvado rey Juan gobernó Inglaterra en 1200”



Objetos: Juan, Inglaterra, 1200
Relación: gobernó
Propiedades: malvado, rey
Sintaxis y semántica


En la lógica proposicional, cada expresión es una
oración, que representa un hecho. En la lógica
de primer orden hay oraciones, pero también
términos que representan objetos.
Los signos que representan constantes, las
variables y los signos de funciones sirven todos
para construir términos; los cuantificadores y los
signos de predicados sirven para construir
oraciones.
Sintaxis y semántica

Elementos


Signos de constantes: A, B, C, Juan…
Signos de predicado: Redondo, Hermano…


Ejemplo, Hermano hace referencia al conjunto de
tuplas {<Rey Juan, Ricardo Corazón de León>
<Ricardo Corazón de León, rey Juan>}
Signos de funciones: Coseno, PadreDe,
PiernaIzquierdaDe…

Son relaciones de en las que un objeto está
relacionado justamente con otro objeto.
Sintaxis y semántica

Términos


Un término es una expresión lógica que se
refiere un objeto. Los signos de constante son
términos.
A veces es más práctico utilizar una expresión
para referirse a un objeto, por ejemplo, en
vez de LaPiernaIzquierdaDeJuan es más
práctico usar PiernaIzquierdaDe(Juan)
Sintaxis y semántica

Oraciones atómicas


Los términos y signos de predicado se combinan para
formar oraciones atómicas, mediante las que se
afirman hechos.
Una oración atómica está formada por un signo de
predicado y por una lista de términos entre
paréntesis, ejemplo



Hermano (Ricardo, Juan)
Casado (PadreDe (Ricardo), MadreDe (Juan))
Se dice que una oración atómica es verdadera si la
relación a la que alude el signo de predicado es válida
para los objetos a los que aluden los argumentos.
Sintaxis y semántica

Oraciones complejas

Mediante los conectores lógicos se pueden
construir oraciones más complicadas, como
en cálculo 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 semántica

Cuantificadores


Los cuantificadores permiten expresar
propiedades de grupos completos de objetos
en vez de enumerarlos por sus nombres.
La lógica de primer orden contiene dos
cuantificadores estándar, denominados
universales y existenciales.
Sintaxis y semántica

Cuantificación universal ()

Facilita la expresión de reglas generales,
ejemplo: en vez de decir “Mancha es un gato”
y “Mancha es un mamífero” se usa:


x Gato (x)  Mamífero (x)
Lo cual equivale a

Gato (Mancha)  Mamífero (Mancha)  Gato
(Rebeca)  Mamífero (Rebeca)  Gato (Félix) 
Mamífero (Félix)  Gato (Juan)  Mamífero (Juan)
…
Sintaxis y semántica

Cuantificación universal ()


Por lo tanto la primera expresión será valida si
y sólo si todas estas últimas son también
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 término no tiene variables se le
conoce como término de base.
Sintaxis y semántica

Cuantificación 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 semántica

Cuantificación existencial ()

x Hermano (x, Mancha)  Gato (x) equivale
a las oraciones:


(Hermano
(Hermano
(Hermano
(Hermano
(Mancha, Mancha)  Gato (Mancha)) 
(Rebeca, Mancha)  Gato (Rebeca)) 
(Félix, Mancha)  Gato (Félix)) 
(Ricardo, Mancha)  Gato (Ricardo)) …
Así como  es el conector natural para , 
es el conector natural para .
Sintaxis y semántica

Cuantificadores anidados

“Para toda x y toda y, si x es el padre de y, entonces
y es el hijo de x”


“Para toda x y toda y, si x es hermano de y, entonces
y es hermano de x”


x,y Hermano (x,y)  Hermano (y,x)
“Todas las personas aman a alguien”


x,y Padre (x,y)  Hijo (y,x)
x y Aman (x,y)
“Siempre hay alguien a quien todos aman”

y x Aman (x,y)
Sintaxis y semántica


Una oración como x P (y), en la que y
carece de cuantificador, es incorrecta.
El término fórmula bien configurada o
fbc se emplea para calificar oraciones en
las que todas sus variables se han
introducido adecuadamente.
Sintaxis y semántica

Relaciones entre  y 


Ambos cuantificadores están estrechamente
relacionados entre sí mediante la negación.
“A todos les desagradan las espinacas”  “No hay
alguien a quien le gusten las espinacas”


x LeGustan(x, espinacas)  x LeGustan (x, espinacas)
“A todos les gusta el helado”  “No hay alguien a
quien no le guste el helado”

x LeGusta(x, helado)  x LeGusta (x, helado)
Sintaxis y semántica

Relaciones entre  y 

Puesto que  es una conjunción de objetos del
universo y  es su disyunción, es natural que
obedezcan las leyes de De Morgan:
x P  x P
x P  x P
x P  x P
x P  x P
P  Q  (P  Q)
(P  Q)  P  Q
P Q   (P  Q)
P Q   (P  Q)
Sintaxis y semántica

Igualdad

Para formular aseveraciones en las que los dos
términos se refieren a un mismo objeto se utiliza el
símbolo de igualdad:


Padre(Juan) = Enrique
El signo de igualdad sirve para describir las
propiedades de una función determinada o se puede
emplear en la negación para insistir en que dos
términos no son el mismo objeto:

x,y Hermano(Mancha, x)  Hermano(Mancha, y)  (x=y)
Extensiones en la Notación

Lógica de orden superior


El nombre lógica 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 lógica 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 Notación

Expresiones funcionales y de predicado
usando el operador .

El operador  se usa para convertir términos
en funciones, especificando sus argumentos:


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
Extensiones en la Notación

El cuantificador de unicidad !


Se utiliza para afirmar la existencia de un
objeto específico que satisface determinado
predicado.
“Existe un solo rey”


! Rey(x)
“Todo país tiene exactamente un
gobernante””

 c País(c)  ! r Gobernante(r, c)
Extensiones en la Notación

El operador de unicidad 


Se utiliza para representar directamente el
objeto específico, ejemplo:
“El único gobernante de Libertania está
muerto”


Muerto ( r Gobernante(r, Libertania))
Que es una abreviatura de

! r Gobernante (r, Libertania)  Muerto (r)
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.
Uso de una lógica de primer orden

El dominio del parentesco



En este dominio están 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 z”
Los objetos de este dominio son personas. Entre las propiedades
que poseen están el género 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 mayoría de las
relaciones de parentesco serán predicados binarios: Progenitor,
Hijo, Hermano, Hermana, Progenie, Hijo, Hija, Esposo, Esposa,
Cónyuge, Abuelo, Nieto, Primo, Tía, Tío.
Para Madre y Padre se usarán funciones, puesto que todo
mundo cuenta con ellos desde un punto de vista biológico.
Uso de una lógica de primer orden

El dominio del parentesco

La madre de alguien es su progenitor
femenino:


El esposo de alguien es su cónyuge masculino


m,c Madre(m,c)  Mujer(m)  Progenitor(m,c)
w,h Esposo(h,w)  Hombre(h)  Cónyuge(h,w)
Masculino y femenino son categorías
disyuntas:

x Hombre(x)  Mujer(x)
Uso de una lógica de primer orden

El dominio del parentesco

Progenitor y progenie son relaciones inversas:


Un(a) abuelo(a) es progenitor del progenitor de
alguien:


p,c Progenitor(p,c)  Progenie(c,p)
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 lógica de primer orden

Axiomas, definiciones y teoremas



Los matemáticos crean axiomas para capturar 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.
¿Cómo saber si se han postulado una cantidad suficiente de
axiomas de tal manera que un dominio quede completamente
especificado? Postulando un conjunto de predicados básicos en
función de los cuales se pueden definir los demás.
¿Y si tenemos demasiadas oraciones? Revisar cuáles oraciones
no son necesarias y se pueden inferir con otras oraciones.
Uso de una lógica de primer orden

Axiomas, definiciones y teoremas


Sin 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 definición de P, porque sirve para
definir exactamente para qué objetos P se
cumple y para cuáles no.
Uso de una lógica de primer orden

El dominio de los conjuntos


En este dominio, ConjuntoVací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 = ConjuntoVacio)  (x,s2 Conjunto(s2) 
s=Adyunto(x, s2))
Uso de una lógica de primer orden

El conjunto vacío es aquel que no tiene
incorporado ningún elemento.


La adyunción de un elemento que ya esté en el
conjunto no produce efecto alguno.


x,s Adyunto(x, s) = ConjuntoVacío
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 lógica de primer orden

Un conjunto es subconjunto de otro si y sólo 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 sólo si cada uno de
ellos es subconjunto del otro.

s1,s2 (s1 = s2)  (Subconjunto(s1,s2)  Miembro(s2,
s1)))
Uso de una lógica de primer orden

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.


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 uno
de los dos conjuntos

x,s1,s2 Miembro (x, Unión(s1,s2))  Miembro (x,s1) 
Miembro (x,s2)
Uso de una lógica de primer orden

Notaciones especiales para conjuntos, listas y
aritmética
 = Conjunto vacío
{x} = Adjunto(x, Conjunto vacío)
{x,y} = Adjunto(x, Adjunto(y, Conjunto vacío)
{x,y|s} =Adjunto (x, Adjunto(y,s))
r  s = Unión(r,s)
r  s = Intersección (r,s)
x s = Miembro(x,s)
r  s = Subconjunto(r,s)
[] = Nada
[x] = Cons(x, Nada)
[x,y] =Cons(x, Cons(y,
Nada))
[x,y|l] =Cons(x, Cons(y, l))
Uso de una lógica de primer orden

Cómo formular preguntas y obtener
respuestas

Para añadirle oraciones a la base de
conocimientos BC, diríamos:
Decir(BC, (m,c Madre(m,c)  Mujer(m) 
Progenitor(m,c)))
 Decir(BC, (Mujer(Maxi)  Progenitor(Maxi,Mancha)
 Progenitor(Mancha,Botas)))


Y luego podríamos preguntar

Preguntar(BC, Abuelo_a(Maxi, Botas))
Uso de una lógica de primer orden

Cómo formular preguntas y obtener respuestas



Las oraciones añadidas al utilizar DECIR se llaman
aseveraciones.
A las preguntas formuladas mediante PREGUNTAR se
les conoce como consultas u objetivos.
También se pueden hacer preguntas básicamente
cuantificadas como:


Preguntar(BC,x Hijo(x,Mancha))
Las preguntas del tipo “¿Existe una x tal que…?” se
resuelve proporcionando esa x, mediante una
sustitución o lista de enlace.
Agentes lógicos para el mundo de
wumpus

Se consideran tres arquitecturas:




Lo primero que se debe hacer es definir la
interfaz entre el agente y el ambiente.


Agentes reflejos
Agentes basados en modelos
Agentes basados en metas
Percepción([Hedor, Brisa, Resplandor, Nada],5)
La acción del agente debe ser una de las
siguientes:

Vuelta(Derecha), Vuelta(Izquierda), Adelante,
Disparar, Tomar, Soltar, Saltar
Agentes lógicos para el mundo de
wumpus

Para decidir cuál es la mejor, la función
HACER-CONSULTA-SOBRE-ACCION crea
una consulta tal como

a Acción(a,5)
Un agente reflejo simple

El más 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 Percepción([s,b,Resplandor,u,c],t)  Acción(Tomar,t)
La relación entre percepción y acción puede estar
regulada por reglas de percepción, mediante las cuales
se elabora una abstracción de la entrada perceptual
inmediata y se le convierte en formas más útiles.




b,g,u,c,t Percepción([Hedor,b,g,u,c],t)  Hedor(t)
s,g,u,c,t Percepción([s,Brisa,g,u,c],t)  Brisa(t)
s,b,u,c,t Percepción([s,b,Resplandor,u,c],t)  EnOro(t)
…
Un agente reflejo simple

De esta forma, se puede establecer una
conexión entre los predicados anteriores y
las posibles acciones:

t , EnOro(t)  Acción(Tomar, t)
Un agente reflejo simple

Limitaciones de los agentes reflejos simples



El mundo del wumpus es difícil para los simples
agentes reflejos.
La acción Saltar permite ver el porqué. Un agente
reflejo puro no sabe con seguridad cuándo saltar,
puesto que ni tener el oro ni estar en el cuadro inicial
son parte de su percepción.
También son incapaces de evitar los ciclos infinitos.
Cómo representar los cambios en el
mundo


Cualquier sistema que tome sus decisiones
basándose 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 diacrónicas, del griego “a través
del tiempo”.
Cómo representar los cambios en el
mundo



Una 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
diferente
En principio, representar situaciones y acciones
no es distinto que representar objetos más
concretos como los gatos y los reyes, o
relaciones concretas como el hermanazgo.
Cómo representar los cambios en el
mundo

Cálculo de situaciones



Es el nombre dado para una manera
particular de describir el cambio en la lógica
de primer orden.
Concibe al mundo como una secuencia de
situaciones, cada una de las cuales es como
una “instantánea” del estado del mundo.
Las situaciones se generan mediante acciones
desde situaciones anteriores.
Cómo representar los cambios en el
mundo

Cálculo de situaciones

Para hacer esto, se proporciona al predicado
correspondiente un argumento de situación
adicional. Por ejemplo, en vez de usar
En(Agente, ubicación), tendríamos

En(Agente, [1,1],S0  Agente, [1,2],S1)
Cómo representar los cambios en el
mundo

Cálculo de situaciones

Para representar cómo cambia el mundo de
una situación a otra se emplea la función
resultado:
Resultado (HaciaAdelante,S0) =S1
 Resultado (DarVuelta(ALaDerecha, S1) =S2
 Resultado (HaciaAdelante,S2) =S3

Cómo representar los cambios en el
mundo

Cálculo de situaciones

También se cuenta con:
Axiomas de efecto, para definir el efecto que
produce el realizar alguna acción.
 Axiomas de cuadro, para describir cómo el
mundo permanece igual
 Axiomas de estado sucesor, para definir
cuando un predicado es válido después de una
acción siempre y cuando sea verdadero o lo siga
siendo, y falso en cualquier otro caso.

Hacia un agente basado en metas

Una vez encontrado el oro, las políticas
deben modificarse radicalmente. El
objetivo ahora es regresar al cuadro de
partida a la brevedad posible. Lo que
ahora desearíamos es inferir que el agente
tiene como meta encontrarse en la
ubicación [1,1].
Hacia un agente basado en metas

Lo anterior se puede lograr de tres
maneras por lo menos:



Inferencia
Búsqueda
Planificación