Lógica de Primer Orden: una Introducción Informal

Pese a las virtudes que ofrece un sistema de representación y razonamiento formal como la Lógica Proposicional (LP), esta puede ser no apropiada para expresar ciertos tipos de conocimiento. Por ejemplo, una sentencia tan sencilla como:

Algunas máquinas son inteligentes

solo dispone de una posible representación en LP, como variable proposicional, ya que es una afirmación atómica, perdiendo el grano fino que permita extraer, y reutilizar, un mayor conocimiento de su estructura. Así, si representamos esta sentencia por una variable proposicional, el sistema no será capaz de diferenciar su contenido de una frase similar pero que da una información bien distinta:

Las máquinas son inteligentes

La primera afirmación no se refiere específicamente a ningún conjunto de máquinas, pero tampoco informa de una propiedad general de las mismas, solo indica que existe un conjunto de máquinas que son inteligentes.

Este tipo de carencias, y muchas otras que surgen cuando intentamos modelar una información más rica, es la que nos debe llevar a la conclusión de que la LP puede que no sea apropiada para modelar cierto tipo de afirmaciones y razonamiento.

Parte del problema que muestra la LP es que no tiene capacidad para diferenciar propiedades en familias de elementos de un dominio. O bien habla de objetos particulares que tienen una descripción propia (un nombre que los identifica), o habla de propiedades del dominio completo como una unidad. No tiene capacidad de ajuste fino.

La Lógica de Primer Orden (LPO) viene a solucionar este tipo de problemas:

• Permite hacer cuantificación sobre los objetos de un dominio, por ejemplo, puede expresar cosas como: "Todas las máquinas son inteligentes”, “Algunas máquinas funcionan correctamente”, etc.
• Permite representar propiedades de los objetos particulares del dominio por medio de predicados y funciones.
• Permite trabajar con subconjuntos de objetos que pueden venir caracterizados por propiedades que se describen por medio de propiedades y funciones.

Con el fin de aterrizar las ideas que vamos a introducir aquí, trabajaremos a lo largo de esta entrada con la formalización de la siguiente base de conocimientos acerca del mundo romano:

• Marco era pompeyano.
• Todos los pompeyanos eran romanos.
• Cada romano, o era leal a César, o le odiaba.
• Todo el mundo es leal a alguien.
• La gente sólo intenta asesinar a aquellos a quienes no es leal.
• Marco intentó asesinar a César.
• Todo pompeyano es leal a su padre.

Para ello, formalmente, un LPO, $L$, está compuesto por los siguientes elementos (lo que se denomina sintaxis en el ámbito de la definición de lenguajes formales):

• Un conjunto, finito o numerable, de símbolos de constantes para designar objetos: $C=\{c_1,c_2,\dots\}=\{a,b,c,\dots\}$ (no tenemos porqué tener designadores para todos los objetos del mundo modelado, quizás solo de algunos de ellos).
  En el ejemplo anterior, objetos (individuos) como César y Marco necesitarían de símbolos específicos para poder referrirnos a ellos y expresar las afirmaciones en las que intervienen. Así pues, en nuestro lenguaje tomaremos $C=\{{\bf Marco}, {\bf Cesar}\}$.
• Un conjunto, finito o numerable, de símbolos para designar funciones: $F=\{f_1,f_2,\dots\}=\{f,g,h,\dots\}$ (cada función tiene una aridad propia, que indica el número de argumentos que recibe como entrada).
  De nuevo, en el ejemplo anterior encontramos una función que asocia objetos a objetos, en este caso, asociada al concepto padre, que denotaremos por $f$, por lo que $F=\{f\}$, y para un objeto del mundo, por ejemplo, $Marco$, $f(Marco)$ representa a su padre.
• Un conjunto, finito o numerable, de símbolos para designar predicados: $P=\{P_1,P_2,\dots\}=\{P,Q,R,\dots\}$ (cada predicado tiene una aridad propia, que indica el número de objetos que relaciona).
  En este caso, disponemos de varios predicados en el ejemplo que necesitamos formalizar, concretamente: $P(a)$ para decir que $a$ es pompeyano, $R(a)$ para expresar que $a$ es romano, $L(a,b)$ para indicar que $a$ es leal a $b$, $O(a,b)$ para indicar que $a$ odia a $b$, $IA(a,b)$ para indicar que $a$ intentó asesinar a $b$.

Observa que hablamos de "símbolos", porque estamos definiendo un lenguaje, pero lo hacemos desde un punto de vista completamente formal, sin preocuparnos por el significado de lo que podamos escribir en él. Eso lo veremos más adelante en lo que podríamos denominar la semántica del lenguaje, que depende del uso que se le dé.

Además de estos elementos, un LPO necesita también otros símbolos que le permitan componer fórmulas y expresiones más complejas, y que son, esencialmente, una extensión de los mismos símbolos que usábamos para la LP:

1. $\neg$, $\wedge$, $\vee$, $\rightarrow$, $\leftrightarrow$: conectivas lógicas usuales y con el mismo uso que se le dio en LP.
2. $=$: un predicado especial para la igualdad. No es obligatorio, pero si lo añadimos, significa la igualdad habitual en la que $a=b$ si y sólo si $a$ y $b$ son el mismo objeto.
3. $V=\{x_1, x_2, \dots\}=\{x,y,z,\dots\}$: un conjunto numerable de variables con las que podemos representar objetos del mundo que estamos describiendo.
4. $\exists$, $\forall$: cuantificadores existencial y universal, habituales en la formalización matemática estándar que, en combinación con el uso de variables, permiten extender las propiedades particulares que podemos referenciar en objetos del mundo a propiedades de conjuntos de objetos.
5. $($ $,$ $)$: símbolos de puntuación auxiliares para facilitar la escritura y lectura de las expresiones que escribamos.

Una formalización de las sentencias anteriores sería:

• $P({\bf Marco})$
• $\forall x\, ( P(x)\rightarrow R(x))$
• $\forall x\, (R(x)\rightarrow (L(x,{\bf Cesar})\vee O(x,{\bf Cesar}))$
• $\forall x\,\exists y\, L(x,y)$
• $\forall x\,\forall y\, (IA(x,y)\rightarrow \neg L(x,y))$
• $IA({\bf Marco},{\bf Cesar})$
• $\forall x\, (P(x)\rightarrow L(x, f(x)))$

Con este aparato, podemos definir formalmente cómo se escriben las expresiones correctas en este lenguaje, pero no nos vamos a centrar en tanto detalle (lo puedes encontrar en los apuntes oficiales de la asignatura de Lógica Informática), ya que su uso habitual en disciplinas de estudio conocidas (como matemáticas y física) nos proporciona suficientes ejemplos como para que podamos diferenciar las expresiones válidas de las no válidas sin posibilidad de error y sin necesidad de una farragosa definición formal. Lo único importante, porque lo usaremos más adelante, es diferenciar entre los tipos de expresiones que podemos construir:

• Aquellas expresiones que se identifican con posibles objetos se denominan términos, y están formadas a partir de constantes para hablar de objetos específicos, variables para hablar de objetos genéricos, y funciones aplicadas a otros términos más pequeños.
  En el ejemplo anterior, ${\bf Marco}$, $f({\bf Marco})$, $f(f({\bf Cesar}))$, $f(x)$, etc. son términos.
• Las expresiones que se identifican con afirmaciones sobre los objetos se denominan fórmulas, y están formadas a partir de predicados sobre términos, y construcciones lógicas de estos predicados (conjunciones, implicaciones, cuantificaciones, etc.).
  La formalización de las sentencias anteriores son ejemplos de fórmulas.

Observa que los LPO hablan de objetos, propiedades y funciones. Lo interesante es cuando estas expresiones se usan para hablar de mundos formados por objetos, con propiedades y funciones que tienen una interpretación con algún significado para nosotros.

A estos mundos que se pueden adaptar a un lenguaje particular, $L$, se les denomina comúnmente $L$-estructuras (un mundo se puede ajustar a muchos lenguajes, y un mismo lenguaje se pueden ajustar a muchos mundos posibles).

Así pues, informalmente, una $L$-estructura $M$ es un conjunto en el que cada símbolo del lenguaje $L$ se puede interpretar como un elemento, propiedad o función real en ese conjunto. De hecho, a la identificación concreta que dice cómo se interpreta cada símbolo de $L$ se le llama interpretación. Es esta interpretación la que da sentido a los elementos del lenguaje, que hasta este momento, no eran más que símbolos sin contenido, sin más utilidad que la de poder escribir expresiones correctamente.

Una intepretación "natural" del ejemplo anterior sería considerar el mundo antiguo formado por romanos y pompeyanos como conjunto de "objetos", y el significado natural de cada uno de los predicados, constantes y funciones. Pero no es la única interpretación posible. Podríamos considerar, en un alarde de imaginación y libertad, que el conjunto de objetos sobre el que se trabaja son los números naturales, donde ${\bf Marco}=0$, ${\bf Cesar}=1$, el padre de un individuo es el siguiente (es decir, por ejemplo, $f({\bf César})=2$), ser romano es ser par, ser pompeyano es ser múltiplo de 4, etc... Los términos y fórmulas escritas en el lenguaje no cambian, pero su interpretación (significado) en este nuevo mundo son completamente distintas, y habrá fórmulas que se verificarán con esta nueva interpretación que quizás en la natural no se verifiquen (o al revés).

Si queremos usar LPO para razonar acerca de lo que ocurre en el mundo, debemos ser capaces de describir el mundo sin que haya posibilidad de que las fórmulas sean verdaderas en estructuras que no tienen nada que ver con el mundo que estamos modelando. Esta tarea no es nada trivial, y a veces, por mucho que queramos especificar concretamente las propiedades que caracterizan el mundo de interés, podemos encontrar mundos extraños que verifican las mismas propiedades pero no son nuestro objeto de interés.

Pero, por lo menos, con el fin de modelar el conocimiento de dominios de forma lógica debemos precisar con claridad cuándo una fórmula es verdadera en una cierta estructura:

Diremos que una fórmula, $\varphi$, de $L$ es satisfactible si hay una $L$-estructura, $M$, donde se verifica la fórmula (con el significado estándar de los símbolos lógicos y la interpretación en esa estructura de los símbolos de constante, predicados y funciones), y en este caso se dice que la estructura es modelo de la fórmula: $M\models \varphi$. Esta idea se puede extender a un conjunto de fórmulas, $\Sigma$, que será satisfactible en una estructura si lo son todas sus fórmulas: $M\models \Sigma$.

Por ejemplo, en el mundo de los romanos con la interpretación natural se tiene que la fórmula $\forall x (P(x)\rightarrow R(x))$ se satisface (con la interpretación de los números naturales que hemos dado, también).

Y podemos definir el concepto fundamental que persigue la lógica acerca de cuándo podemos concluir una fórmula, $\varphi$, de un conjunto de fórmulas, $\Sigma$: $\Sigma\models \varphi$, y es que será así cuando, en todo mundo posible en el que $\Sigma$ se verifique, necesariamente $\varphi$ se verifica. Es decir:

Si $M$ es una $L$-estructura tal que $M\models \Sigma$, entonces $M\models \varphi$.

Observa que, si $\Sigma=\{\varphi_1,\dots,\varphi_n\}$ es un conjunto finito de fórmulas, entonces esta definición es equivalente a decir que $$M\models \varphi_1\wedge \dots\wedge \varphi_n \rightarrow \varphi$$
se tiene para cualquier $L$-estructura $M$.

Por ejemplo, tomando como $\Sigma$ el conjunto de sentencias formalizadas anteriormente, podríamos preguntarnos si de ellas se deduce (si es consecuencia lógica) si "Márco era leal a César" ($L({\bf Marco},{\bf Cesar})$), o no.

Al igual que se hace con la Lógica Proposicional, sería interesante ver de qué forma podemos dar métodos (y si son automatizables mejor) para comprobar si una fórmula es consecuencia lógica de un conjunto de fórmulas, métodos que no sean el de comprobar directamente la definición, que precisa de verificar la condición anterior sobre todos los mundos posibles, o estructuras.

Para entender cómo se diferencia ahora este objetivo en Primer Orden del equivalente en Proposicional es importante observar que, en Proposicional, si tenemos un conjunto finito de fórmulas que hacen uso de un conjunto finito de variables proposicionales, entonces el número de mundos posibles es finito, ya que consiste simplemente en todas las posibles combinaciones de valores de verdad de las afirmaciones, por lo que bastaría comprobar en cada uno de ellos si se tiene la condición anterior o no (es, esencialmente, lo que se hace con una tabla de verdad). Sin embargo, en Primer Orden no podemos afirmar lo mismo, los mundos son mucho más ricos y complejos, y aunque estemos trabajando con un conjunto finito de fórmulas que hacen uso de un conjunto finito de símbolos, no podemos asegurar que haya únicamente un número finito de mundos posibles, por lo que este método de comprobación exahustiva ya no es válido y hay que buscar métodos alternativos.

Mucho del trabajo realizado en LPO es ver hasta qué punto se pueden extrapolar y adaptar los métodos que funcionan en LP al caso de LPO. Una opción que sí nos trasladaría a una situación similar sería si pudiéramos asegurar que los mundos posibles son finitos y además tenemos un símbolo de constante para nombrar cada uno de ellos, porque en este caso realmente la LPO se estaría usando como una forma más abreviada de escribir fórmulas proposicionales (tendríamos todas las afirmaciones de lo que se puede decir acerca de los objetos del mundo describiéndolas una a una sobre cada objeto... un conjunto resultante de fórmulas muy grande, posiblemente infinito, pero muy simple). Es obvio que este no es el caso general, y de hecho en general no podemos afirmar que todos los mundos posibles (estructuras) vayan a ser finitas. Sin embargo, podemos usar esta idea para tratar de trabajar con una versión proposicional de nuestro lenguaje.

Si tenemos en cuenta que tenemos un conjunto de símbolos de constantes, y que los objetos del mundo solo se pueden referenciar en el lenguaje por medio de los términos, que son aquellas expresiones formadas por las combinaciones correctas de estos símbolos con los símbolos de función, entonces de forma efectiva solo podremos referenciar concretamente aquellos objetos del mundo que se puedan nombrar por medio de los términos que no hacen uso de las variables $x,y,z...$, que no representa objetos concretos, es decir, los términos cerrados.

Por ejemplo, $f({\bf Cesar})$ es un tèrmino cerrado, pero $f(x)$, no.

Ten en cuenta que el conjunto de términos cerrados puede ser infinito (basta que haya un símbolo de función y un símbolo de constante para que las combinaciones expresivas en estos términos explote).

Así pues, si consideramos el conjunto de las posibles fórmulas de $\Sigma$ pero instanciando sus variables libres (si las tienen) con los objetos que pueden conseguirse por medio de términos cerrados (lo más probable es que hubiera que añadir algunos símbolos nuevos de constantes y funciones para las fórmulas existenciales que hubiera en $\Sigma$, siguiendo un proceso de skolemnización), tendríamos un conjunto de fórmulas (mucho más grande) pero escrito en un lenguaje equivalente a uno proposicional y que diría exactamente lo mismo que dicen las fórmulas de $\Sigma$. En cierta forma, es el proceso de descomprimir la información que da $\Sigma$ usando las variables libres de un LPO reescribiendo las fórmulas en un lenguaje que habla solo de objetos concretos. Este proceso tan simple conceptualmente es el que está detrás de la famosa (y temida por los alumnos) extensión de Herbrand.

Por ejemplo, a partir de la fórmula $\forall x\, (P(x)\rightarrow R(x))$ del conjunto $\Sigma$ anterior obtendríamos las siguientes versiones sin variables (que hacen uso de términos cerrados únicamente):

$$P({\bf Marco})\rightarrow R({\bf Marco}),\  P({\bf Cesar})\rightarrow R({\bf Cesar})\\ P(f({\bf Marco}))\rightarrow R(f({\bf Marco})),\ P(f({\bf Cesar}))\rightarrow R(f({\bf Cesar}))\\ \cdots$$

que. esencialmente, son como fórmulas proposicionales que hacen uso de la "nuevas" variables proposicionales $P({\bf Marco})$, $R({\bf Marco})$, $P({\bf Cesar})$, $R({\bf Cesar})$, $P(f({\bf Marco}))$, ...

El conjunto de estas nuevas versiones con términos cerrados de las fórmulas de $\Sigma$ proporciona una especie de versión proposicional de la información que hay en $\Sigma$, y podríamos intentar aplicarles los métodos de razonamiento propios de los lenguajes LP (observa que estas nuevas fórmulas ya no tienen variables ni cuantificadores, que son la principal diferencia sintáctica entre LP y LPO).

No es la única técnica posible, ni siquiera la más sencilla y cómoda, pero sí la más inmediata que permite aplicar técnicas desarrolladas originalmente para LP al caso de los LPO. Estas técnicas, que se comportan de forma decidible en el caso de LP, se encuentran ante una explosión (a menudo infinita) en esta extensión, lo que hace que el caso LPO sea, en general, indecidible. En otras entradas de este curso puedes encontrar otras técnicas que podemos intentar transferir de LP a LPO.