Capítulo 7: Lógica de primer orden

En éste capítulo se presentará la lógica de primer orden, cuyos ontológicos son más amplios. Uno de ellos es considerar que el mundo está constituido por objetos, es decir, entes con identidades individuales y propiedades que los distinguen de otros objetos.

En estos objetos, existen diversos tipos de relaciones. Algunas de éstas son las funciones: relaciones entre una “entrada” corresponde a un solo “valor”. No es difícil ofrecer una lista de ejemplos, propiedades, relaciones y funciones:

• 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 mas que…

No se pretende afirmar que el mundo realmente está formado por objetos y relaciones, sino que el esquematizar el mundo de esta forma nos facilita la tarea de razonar sobre él. Mediante la lógica de primer orden también es posible expresar hechos sobre todos los objetos del universo.

Si bien la lógica de primer orden se ocupa de la existencia de los objetos y relaciones, su alcance ontológico no abarca cosas tales como categorías, tiempo y acontecimientos, aspectos que forman también buena parte del mundo.

La lógica de primer orden es universal en el sentido de ser capaz de expresar todo aquello que se pueda programar, se eligió el estudio de la representación del conocimiento y del razonamiento a través de la lógica de primer orden debido a que es hasta ahora el esquema que más se ha estudiado y se le conoce mejor.

7.1 Sintaxis 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 hay términos. Estos últimos representan objetos. Los signos que representan constantes, las variables y los signos de funciones sirven todos para construir términos; cuantificadores y los signos de predicados sirven para construir oraciones. En la siguiente figura se presenta toda la gramática de la lógica de primer orden, usando la forma de Backus-Naur.

A continuación se presenta una explicación más detallada de los elementos anteriores, la que incluye sintaxis como semántica.

• Signos constantes: A, B, C, Juan…

En la interpretación respectiva deberá especificarse a qué objeto del mundo se está haciendo referencia mediante el signo constante.

• Signos de predicado: Redondo, Hermano,…

Una interpretación específica que mediante un signo de predicado se hace referencia a una relación particular de un modelo. Por ejemplo, el signo Hermano hace referencia a una relación de hermandad. Hermano es un signo de predicado binario, por lo que la hermandad es una relación que vincula (o desvincula) pares de objetos.

• Signos de funciones: Coseno, PadreDe, PiernaIzquierdaDe…

Algunas relaciones son funciones, es decir, un determinado objeto está relacionado justamente con otro objeto mediante la relación. Por ejemplo, un ángulo le corresponde sólo un número que es un coseno; toda persona tiene alguien que es su padre.

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. A veces es más práctico utilizar una expresión pera referirse a un objeto. Por ejemplo, en español se utilizaría la expresión “La pierna izquierda del rey Juan”, en vez de asignar un nombre a su pierna.

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. Una oración atómica está formada por un signo de predicado y por una lista de términos entre paréntesis. Por ejemplo:

Hermano(Ricardo,Juan)

Las oraciones atómicas pueden llegar a tener argumentos que son términos complejos:

Casado(PadreDe(Ricardo),MadreDe(Juan))

Afirma que el padre de Ricardo Corazón de León está csado con la madre del rey Juan. Se dice que una oración atómica es verdadera si la relación que lude el signo de predicado es válida para los objetos a los que aluden los argumentos.

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. Por ejemplo:

• Hermano(Ricardo,Juan)  Hermano(Juan,Ricardo) es verdadera sólo cuando Juan es hermano de Ricardo y Ricardo es el hermano de Juan.

• Mayor(Juan,30) V Menor(Juan,30) está diciendo que si Juan es mayor de 30 o Juan es más joven de 30.

Cuantificadores

Ahora que ya contamos con una lógica que admite objetos, es natural el deseo de expresar propiedades de grupos completos de objetos en vez de enumerarlos por su nombre. Los cuantificadores nos permiten hacer esto. La lógica de primer orden contiene dos cuantificadores estándar, denominados universales y existenciales.

Cuantificación universal (
)

En español, lo que se intenta expresar es que por cualquier objeto x, si x es un gato, entonces x es un mamífero.

x Gato(x)
Mamífero(x)

en general se lee como “Para todo”. Por ejemplo, la oración
x P, en donde P es cualquier expresión lógica.

Gato(Mancha)
Mamífero(Mancha) 

Gato(Rebeca)
Mamífero(Rebeca) 

Gato(Félix)
Mamífero(Félix) 

Las variables constituyen términos por sí mismas, que también puede servir como argumento de una función, por ejemplo, HijoDe(x). cuando un término no tiene variables se le conoce como término de base.

Cuantificador existencial (
)

Se pueden hacer afirmaciones acerca de algún objeto en el universo sin tener que nombrarlo, mediante un cuantificador existencial. Para afirmar, por ejemplo, que Mancha tiene una hermana que es un gato, escribiremos:

x Hermana(x,Mancha)  Gato(x)

se lee: “Existe…” En general,
x P es verdadero si P es verdadero para cierto objeto del universo.

Así como
nos perecería ser el conector natural para
,  es el conector natural que se emplea con
.

Cuantificadores anidados

Frecuentemente desearíamos expresar oraciones más complejas utilizando cuantificadores múltiples. El caso más sencillo es cuando los cuantificadores son de mismo tipo. Por ejemplo:

”Para toda x y toda y, si x es el padre de y, entonces y es el hijo de x” se convierte en:

x,y Padre(x,y)
Hijo(y,x)

x,y equivale a
x
y.

“Todas las personas aman a alguien”, significa que cada una de las personas ama a alguien:

x,
y Amores(x,y)

“Siempre hay alguien a quien todos aman” se expresa:

y
x Amores(x,y)

Relaciones entre
y

Ambos calificadores están estrechamente relacionados entre sí mediante la negación. Cuando alguien afirma que a todos les desagradan las espinacas, está afirmando también que no hay nadie a quien le gusten; y viceversa:

x ¬Le gustan(x,espinacas) es equivalente a ¬
Le gustan(x,espinacas)

“A todos les gusta el elado”, significa que no hay nadie a quien no le guste el helado:

x ¬Le gustan(x,helado) es equivalente a ¬
x ¬Le gustan(x,helado)

Puesto que en realidad
es una conjunción de objetos del universo y
es su disyunción, es natural que obedezcan las leyes de Morgan. Estas leyes, correspondientes a oraciones cuantificadas y no cuantificadas son las siguientes:

x ¬P " ¬
x P ¬P  ¬Q " ¬(P V Q)

¬
x P "
x ¬ P ¬(P  Q) " ¬P V ¬Q

x P " ¬
x ¬P P  Q " ¬(¬P V ¬Q)

x P " ¬
x ¬P P V Q " ¬(¬P  ¬Q)

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

Se puede considerar que la igualdad es un símbolo de predicado con un significado previamente definido, es decir, aquel significado que se fija para referirse a la relación de identidad.

7.2 Extensiones y variaciones en la notación

Lógica de orden superior

Lógica de primer orden se basa en el hecho de que con ella se cuantifican objetos, 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. Por ejemplo, mediante la lógica de orden superior es posible afirmar que dos objetos son iguales si y sólo si todas la propiedades son equivalentes:

x,y (x=y)
(
p p(x)
p(y))

o también podríamos 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(y))

Las lógicas de orden superior tienen más capacidad expresiva que la lógica de primer orden.

Expresiones funcionales y predicado usando el operador 

Para convertir el término x2-y2 en una función necesitamos decir cuáles son sus argumentos. El operador  (la letra griega lambda) 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

El cuantificador de unicidad
!

Se ha visto ya como utilizar
para decir que algunos objetos existen. Algunos autores emplean la notación:

!x Rey(x)

para expresar que “existe un objeto específico x que satisface Rey(x)” o de manera más informal que “existe precisamente un rey”.

El operador de unicidad

Aunque es conveniente emplear
! Para especificar la unicidad, hay veces que es mejor disponer de un término que represente directamente el objeto específico. Para este efecto comúnmente se utiliza la notación x P(x). (El signo es la letra griega iota). Para decir que “el único gobernante de Libertania ha 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 oración siguiente:

! R Gobernante(r, Libertania)  Muerto(r)

Variaciones en la notación

Las siguientes son algunas de estas variaciones:

Elemento de la sintaxis	En este libro	En otros libros
Negación (no)	¬P	~P
Conjunción (y)	P  Q	P&Q P.Q PQ P,Q
Disyunción (o)	P V Q	P|Q P;Q P+Q
Implicación (si)	P Q	P!Q PQ
Equivalencia (si si)	P Q	P"Q< P!Q
Universalidad (Todos)	x P(x)	( X)P(x) xP(x) P(x)
Existencia (existe)	x P(x)	( x)P(x) VxP(x) P(Skolemi)
Relación	R(x,y)	(R x y) Rxy xRy

7.3 Uso de una lógica de primer orden

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.

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.

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.

Notaciones especiales para conjuntos, listas y aritmética

La notación es una mera abreviación de la notación de la lógica de primer orden normal. A este tipo de aplicaciones de la notación se le conoce como azúcar sintáctica. Entre los matemáticos hay menos consenso por lo que se refiere a la notación para las listas; nosotros hemos optado por utilizar la notación de Prolog:

(/) = 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 U 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))

Como formular preguntas y obtener respuestas

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

7.4 Agentes lógicos para el mundo de Wumpus

Consideremos ahora tres arquitectitas de agente: agentes reflejos, que se limitan a clasificar las percepciones recibidas y producen la respuesta respectiva; agentes basados en modelos, los cuales construyen una representación interna del mundo y la emplean para producir sus reacciones; y agentes basados en metas, que elaboran metas y se esfuerzan por alcanzarlas.

El primer paso en la construcción de un agente para el mundo de wumpus (o para cualquier otro mundo) consiste en definir la interface entre el ambiente y el agente. La oración correspondiente a la percepción debe incluir tanto la percepción como el momento en que ésta se produjo; de lo contrario el agente podría confundirse y no saber cuándo vio qué. Para representar las etapas temporales se emplearán números enteros. Una típica oración de percepción sería la siguiente:

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, Satar

7.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. Por ejemplo, si el agente ve un resplandor, tiene que alargar la mano y tomar, para así recoger el oro:

s,b,u,c,t Percepción([s,b,Resplandor,u,c],t)Acción(Tomar,t)

Limitaciones de los agentes reflejos simples

El mundo de wumpus es difícil para los simples agentes reflejos. Los agentes reflejos también son incapaces de evitar bucles infinitos.

7.6 Cómo representar los cambios en el mundo

La elaboración de tales reglas resultaría inconcebiblemente tediosa a menos que adoptáramos ciertos patrones de razonamiento que correspondan al mantenimiento de un modelo interno del mundo o de, por lo menos, sus aspectos más relevantes.

Es posible demostrar que 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, siempre y cuando estas oraciones se vayan actualizando en cuanto llegue una percepción y en cuanto se efectúe una acción.

Las reglas que describen la manera como cambia el mundo (o como no cambia) se conocen reglas diacrónicas, del griego “a través del tiempo”. La representación del cambio es una de las más importantes áreas de la representación del conocimiento.

Cálculo de situaciones

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 mantener un registro de la ubicación

El mundo de wumpus, conocer la ubicación es quizás lo más importante; aunque no la pueda percibir directamente, el agente tiene que recordar en dónde ha estado y qué fue lo que vio para así deducir donde se encuentran los precipicios y los wumpus y también para asegurarse de realizar una exploración completa en busca del oro.

• En qué dirección se encuentra (un ángulo expresado en grados, en donde 0 grados indica que está ausente a lo largo del eje X, y 90 grados indica que está en el eje Y, etc.)

Orientación(Agente,S0)=0

• Cómo están distribuidas las ubicaciones (un “mapa” sencillo). El mapa está firmado por valores de la función UbicaciónHacia, en donde se toman ubicación y dirección y se proporciona la ubicación que corresponda al paso siguiente de la dirección dada.

x,y UbicaciónHacia([x,y],0)=[x+1,y]

x,y UbicaciónHacia([x,y],90)=[x,y+1]

x,y UbicaciónHacia([x,y],180)=[x-1,y]

x,y UbicaciónHacia([x,y],270)=[x,y-1]

• Todo lo que se sepa acerca del contenido de las ubicaciones (detalles geográficos del mapa). En las líneas siguientes, se supone que las ubicaciones que rodean a la cueva de 4x4 tienen muros, y que otras ubicaciones no los tienen.

x,y Muro[x,y](x=0 V x=5 V y=0 V y=5)

• Qué efectos tienen las acciones en la ubicación. Sólo el avanzar produce un cambio de ubicación y sólo si no hay un muro adelante. El axioma estado sucesor correspondiente a la ubicación es:

a,d,p,s En(p,l,Resultado(a,s))[(a=HaciaAdelante 

l=UbicaciónAdelante(p,s)  ¬Muro(l)) V (En(p,l,s)  a"Muro)]

• Qué efectos tienen las acciones en la orientación. El girar es la única acción que modifica la orientación. El axioma estado sucesor de la orientación es:

a,d,p,s Orientación(p,Resultado(a,s))=d
[(a=DarVuelta(A la derecha 

d=Modo(Orientación(p,s)-90,360)) V (a=DarVuelta(A la izquierda  d=Modo(orientación(ps)+90,360)) V ((Orientación(p,s)=d  ¬(a=DarVuelta(A la derecha  a=DarVuelta(a la derecha  a= )))

Además de llevar un registro de la ubicación y del oro, el agente también debe contar con este registro para saber si el wumpus está vivo o muerto.

7.7 Cómo deducir propiedades ocultas del mundo

Una vez que es agente sabe dónde se encuentra, está en posibilidad de asociar cualidades con las ubicaciones, en vez de limitarse a relacionarlas con las situaciones. Por ejemplo, si un agente está en un sitio y percibe una brisa, ese lugar es entonces airoso; si el agente percibe hedor, el sitio es apestoso:

l,s En(Agente,l,s)Brisas(s)
Airoso(l)

l,s En(Agente,l,s)Oloroso(s)
Hedor(l)

Al descubrir qué sitios son airosos o apestosos (y lo que es más importante, cuáles no son apestosos ni airosos) el agente podrá deducir qué cuadros no implica ningún riesgo (utilizamos el predicado OK para representar lo anterior); esta información servirá para buscar el oro.

A los axiomas que escribiremos para capturar toda la información necesaria para hacer estas deducciones se les denomina reglas sincrónicas (“al mismo tiempo”). Existen dos tipos principales de reglas sincrónicas:

• Reglas causales: las reglas casuales reflejan la dirección de causalidad asumida en el mundo. Por ejemplo, reglas que especifiquen que los cuadrados adyacentes a los wumpus apestan y que los cuadrados adyacentes a los precipicios son airosos:

l1,l2,s En(Wumpus,l1,s)Adyacente(l1,l2)Oloroso(l2)

l1,l2,s En(Precipicio,l1,s)Adyacente(l1,l2)Airoso(l2)

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 directamente desde la información derivada de las percepciones.

l,s En(Agente,l,s)Brisa(s)
Airoso(l)

l,s En(Agente,l,s)Oloroso(s)
Hedor(l)

7.8 Preferencia de una acción en vez de otra

Hasta ahora, la única manera de que disponemos para escoger acciones consiste en elaborar reglas que las recomienden con base en ciertas condiciones del mundo. Por ejemplo, en general, es buena idea explorar desplazandose por cuadros señalados con OK, pero no en aquellos que se percibe un resplandor en el piso. Por lo tanto, las reglas de que disponemos para explorar deberán mencionar también el resplandor. Esto parecería 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 combio de reglas que se refieren a otros aspectos.

Las metas describen qué tan deseables son los estados de resultados, independientemente de cómo se logren.

7.9 Hacia un agente basado en metas

Es posible mostrar que un agente que utilice axiomas siempre tendrá el éxito en encontrar el oro siempre que haya una secuencia de acciones seguras para hacerlo.

El objetivo ahora es regresar al cuadro de partida a la brevedad posible. Lo que ahora desearíamos hacer es inferir que el agente ahora tiene como meta encontrarse en la ubicación [1,1];

s Sostener(Oro,s)
UbicaciónMeta([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 para determinar tal secuencia:

• Inferenca: No es difícil elaborar axiomas que nos permitan Preguntar a la BC una secuencia de acciones que garantice alcanzar la meta sin riesgo.

• Búsqueda: Se puede emplear un procedimiento de búsqueda preferente por los mejor para encontrar una ruta que conduzca a la meta.

• Planificación: Implica el uso de sistemas de razonamiento de propósito especial diseñados para razonar acerca de las acciones.

Oración ! Oración Atómica

| Oración Conector Oración

| Cuantificador variable,… oración

| ¬ Oración

| (Oración)

Oración atómica ! Predicado (Término,…) | Término = Término

Término !
|  | V |

Cuantificador !
|

Constante ! A | X1 | Juan | …

Variable ! a | x | s | …

Predicado ! Antes | TieneColor | Lloviendo | …

Función ! Madre | PiernaIzquierdaDe | …