Lógica de primer orden

La lógica de primer orden, también llamada lógica de predicados o cálculo de predicados, es un sistema formal diseñado para estudiar la inferencia en los lenguajes de primer orden.​ Los lenguajes de primer orden son, a su vez, lenguajes con cuantificadores que alcanzan sólo a variables de individuo, y con predicados y funciones cuyos argumentos son sólo constantes o variables de individuo.​

La lógica de primer orden tiene el poder expresivo suficiente para definir a prácticamente todas las matemáticas.

Introducción

Como el desarrollo histórico y las aplicaciones de la lógica de primer orden están muy ligados a la matemática, en lo que sigue se hará una introducción que contemple e ilustre esta relación, tomando ejemplos tanto de la matemática como del lenguaje natural. Primero se introducen cada uno de los conceptos básicos del sistema, y luego se muestra cómo utilizarlos para analizar argumentos.

Predicados

Un predicado es una expresión lingüística que puede conectarse con una o varias otras expresiones para formar una oración.​ Por ejemplo, en la oración "Marte es un planeta", la expresión "es un planeta" es un predicado que se conecta con la expresión "Marte" para formar una oración. Y en la oración "Júpiter es más grande que Marte", la expresión "es más grande que" es un predicado que se conecta con dos expresiones, "Júpiter" y "Marte", para formar una oración.

Cuando un predicado se conecta con una sóla expresión, se dice que expresa una propiedad (la propiedad de ser un planeta), y cuando se conecta con dos o más expresiones, se dice que expresa una relación (la relación de ser más grande que). La lógica de primer orden no hace ningún supuesto, sin embargo, sobre si existen o no las propiedades o las relaciones. Sólo se ocupa de estudiar el modo en que hablamos y razonamos con expresiones lingúisticas.

En la lógica de primer orden, los predicados son tratados como funciones. Una función es, metafóricamente hablando, una máquina que recibe un conjunto de cosas, las procesa, y devuelve como resultado una única cosa. A las cosas que entran a las funciones se las llama argumentos,​ y a las cosas que salen, valores o imágenes. Considérese por ejemplo la siguiente función matemática:

f(x) = 2x

Esta función toma números como argumentos y devuelve más números como valores. Por ejemplo, si toma el número 1, devuelve el número 2, y si toma el 5, devuelve el 10. En la lógica de primer orden, se propone tratar a los predicados como funciones que no sólo toman números como argumentos, sino expresiones como "Marte", "Mercurio" y otras que se verán más adelante. De este modo, la oración "Marte es un planeta" puede transcribirse, siguiendo la notación propia de las funciones, de la siguiente manera:

Planeta(Marte)

O, más abreviadamente:

P(m)

En la matemática existen además funciones que toman varios argumentos. Por ejemplo:

f(x,y) = x + y

Esta función, si toma los números 1 y 2, devuelve el número 3, y si toma el -5 y el -3, devuelve el -8. Siguiendo esta idea, la lógica de primer orden trata a los predicados que expresan relaciones, como funciones que toman dos o más argumentos. Por ejemplo, la oración "Caín mató a Abel" puede formalizarse así:

Mató(Caín,Abel)

O abreviando:

M(c,a)

Este procedimiento puede extenderse para tratar con predicados que expresan relaciones entre muchas entidades. Por ejemplo, la oración "Ana está sentada entre Bruno y Carlos" puede formalizarse:

S(a,b,c)

Constantes de individuo

Una constante de individuo es una expresión lingüística que refiere a una entidad. Por ejemplo "Marte", "Júpiter", "Caín" y "Abel" son constantes de individuo. También lo son las expresiones "1", "2", etc., que refieren a números. Una entidad no tiene que existir para que se pueda hablar acerca de ella, de modo que la lógica de primer orden tampoco hace supuestos acerca de la existencia o no de las entidades a las que refieren sus constantes de individuo.

Variables de individuo

Además de las constantes de individuo que hacen referencia a entidades determinadas, la lógica de primer orden cuenta con otras expresiones, las variables, cuya referencia no está determinada. Su función es similar a la de las expresiones del lenguaje natural como "él", "ella", "esto", "eso" y "aquello", cuyo referente varía con el contexto. Las variables generalmente se representan con letras minúsculas cerca del final del alfabeto latino, principalmente la x, y y z. Del mismo modo, en la matemática, la x en la función f(x) = 2x no representa ningún número en particular, sino que es algo así como un espacio vacío donde pueden insertarse distintos números. En conclusión, podemos representar una expresión como "esto es antiguo" con la expresión:

Antiguo(x)

O abreviadamente:

A(x)

Es evidente, sin embargo, que hasta que no se determine a qué refiere la x, no es posible asignar un valor de verdad a la expresión "esto es antiguo", del mismo modo que hasta que no se determine un número para la x en la función f(x) = 2x, no será posible calcular ningún valor para la función.

Por supuesto, al igual que con las constantes de individuo, las variables sirven también para formalizar relaciones. Por ejemplo, la oración "esto es más grande que aquello" se formaliza:

G(x,y)

Y también pueden combinarse constantes de individuo con variables. Por ejemplo en la oración "ella está sentada entre Bruno y Carlos":

S(x,b,c)

Cuantificadores

Considérese ahora la siguiente expresión matemática:

x > 3

Esta expresión no es ni verdadera ni falsa, y parece que no lo será hasta que no reemplazemos a la x por algún número cualquiera. Sin embargo, también es posible dar un valor de verdad a la expresión si se le antepone un cuantificador. Un cuantificador es una expresión que afirma que una condición se cumple para un cierto número de individuos.​ En la lógica clásica, los dos cuantificadores más estudiados son el cuantificador universal y el cuantificador existencial.​ El primero afirma que una condición se cumple para todos los individuos de los que se está hablando,​ y el segundo que se cumple para al menos uno de los individuos.​ Por ejemplo, la expresión "para todo x" es un cuantificador universal, que antepuesto a "x < 3", produce:

Para todo x, x < 3

Esta es una expresión con valor de verdad, en particular, una expresión falsa, pues existen muchos números (muchos x) que son mayores que tres. Anteponiendo en cambio la expresión "para al menos un x", un cuantificador existencial, se obtiene:

Para al menos un x, x < 3

La cual resulta ser una expresión verdadera.

Adviértase ahora, sin embargo, que el valor de verdad de las dos expresiones anteriores depende de qué números se esté hablando. Si cuando se afirma "para todo x, x < 3", se está hablando sólo de los números negativos, el cero y los positivos 1 y 2, entonces la afirmación es verdadera. Y si al afirmar "para al menos un x, x < 3" se está hablando solamente de los números 3, 4 y 5, entonces la afirmación es falsa. En lógica, a aquello de lo que se está hablando cuando se usa algún cuantificador, se lo llama el dominio de cuantificación.​

Esta maquinaria puede adaptarse fácilmente para formalizar oraciones con cuantificadores del lenguaje natural. Tómese por caso la afirmación "todos son amigables". Esta oración puede traducirse así:

Para todo x, x es amigable.

Y una oración como "alguien está mintiendo" puede traducirse:

Para al menos un x, x esta mintiendo.

También es frecuente traducir esta última oración así:

Existe al menos un x, tal que x está mintiendo.

A continuación se formalizan ambas oraciones, introduciendo a la vez la notación especial para los cuantificadores:

Para todo x, x es amigable.	$\forall x\ A(x)$
Existe al menos un x, tal que x está mintiendo.	$\exists x\ M(x)$

Conectivas

La lógica de primer orden incorpora además las conectivas de la lógica proposicional. Combinando las conectivas con los predicados, constantes, variables y cuantificadores, es posible formalizar oraciones como las siguientes:

Oración	Formalización
Sócrates es sabio y prudente.	$Ss\land Ps$
Si Sócrates es sabio, entonces también es prudente.	$Ss\to Ps\,$
Nadie es sabio y además prudente.	$\neg \exists x(Sx\land Px)$
Todos los sabios son prudentes.	$\forall x(Sx\to Px)$

Argumentos

Considérese el siguiente argumento clásico:

1. Todos los hombres son mortales.
2. Sócrates es un hombre.
3. Por lo tanto, Sócrates es mortal.

La tarea de la lógica de primer orden consiste en determinar por qué los argumentos como éste resultan válidos. Para eso, el primer paso es traducirlos a un lenguaje más preciso, que pueda ser analizado mediante métodos formales. Según lo visto más arriba, la formalización de este argumento es la siguiente:

1. $\forall x(Hx\to Mx)$
2. $Hs\,$
3. $\therefore Ms$

Sistema formal

Alfabeto

El alfabeto de un sistema Q de lógica de predicados de primer orden sin identidad consta de los siguientes símbolos:

• Un conjunto finito pero arbitrariamente grande de constantes de individuo: $\{a,b,c,d,...\}\,$

• Un conjunto finito pero arbitrariamente grande de variables: $\{x,y,z,x_{1},x_{2},y_{9},...\}\,$

• Un conjunto finito pero arbitrariamente grande de funciones: $\{f,g,o,l,b,...\}\,$

• Un conjunto finito pero arbitrariamente grande de letras de predicado: $\{P,A,S,N,...\}\,$

• El conjunto de conectivas lógicas heredadas de la lógica proposicional: $\{\neg ,\land ,\lor ,\to ,\leftrightarrow \}$

• El conjunto de cuantificadores: $\{\forall ,\exists \}$

• Los paréntesis izquierdo y derecho: $\{(,)\}\,$

Algunas observaciones con respecto a lo anterior:

• La identidad a veces se considera parte de la lógica de primer orden. En ese caso, el símbolo de identidad se incluye en el vocabulario y se comporta sintácticamente como un predicado binario. Este caso se llama a veces lógica de primer orden con identidad.
• Las constantes en realidad son funciones de aridad 0, de modo que es posible omitir las constantes y permitir a las funciones tener cualquier aridad. Sin embargo, tradicionalmente se usa el término "función" sólo para funciones de aridad mayor o igual a 1.
• En la definición anterior los predicados deben tener aridad mayor o igual que 1. Es posible permitir predicados de aridad 0; estos podrían ser considerados como variables proposicionales de la lógica proposicional.
• Hay diferentes convenciones acerca de dónde poner los paréntesis; por ejemplo, una podría ser ∀x o (∀x). A veces se usan dos puntos (:) o punto (.) en vez de parentesis para desambiguar fórmulas. Una notación interesante pero poco usual es la notación polaca, donde se omiten todos los paréntesis, y se escribe ∧, ∨, delante de los argumentos en vez de entre ellos. La notación polaca es compacta pero poco común por ser difícil para ser leída por los humanos.
• Una observación técnica es que si existe un símbolo de función de aridad 2 representando el par ordenado (o símbolo de predicado de aridad 2 representando la relación) no se necesitan funciones y predicados de aridad mayor que 2.

Usualmente se considera que el conjunto de constantes, funciones y relaciones forman un lenguaje, mientras que las variables, los operadores lógicos y cuantificadores se los considera pertenecientes a la lógica. Por ejemplo, el lenguaje de la teoría de grupos consiste de una constante (el elemento identidad), una función de aridad 1 (la inversa), una función de aridad 2 (el producto), y una relación de aridad 2 (la igualdad), omitida por los autores que incluyen la igualdad en la lógica subyacente.

Gramática

La gramática define las fórmulas bien formadas de Q de la siguiente manera:

Primero se define la noción de término:

1. Cualquier constante es un término.
2. Cualquier variable es un término.
3. Cualquier expresión $f(t_{1},...,t_{n})\,$, donde $f\,$ es un símbolo de función de aridad $n\geq 1$, y $(t_{1},...,t_{n})\,$ es una secuencia de n términos, es un término.
4. Ninguna otra cosa es un término.

Luego se define recursivamente el conjunto de las fórmulas bien formadas de Q a través de las siguientes reglas:

1. Si $P\,$ es una letra de predicado de aridad $n\geq 1$, y $(t_{1},...,t_{n})\,$ es una secuencia de n términos, entonces $P(t_{1},...,t_{n})\,$ es una fórmula bien formada de Q. A estas fórmulas se las llama fórmulas atómicas de Q. Se llama variables libres a todas las variables que aparezcan entre los términos. Algunas fórmulas atómicas bien formadas son:
   $P(a),G(x),R(a,b),S(x,y,a),T(a,f(c)),D(s,g(x,y),e)\,$
   Para simplificar la lectura y la escritura, sin embargo, cuando no hay ningún símbolo de función involucrado, generalmente se omiten los paréntesis y se escribe:
   $Pa,Gx,Rab,Sxya\,$
2. Si $\phi \,$ es una fórmula bien formada de Q, entonces $\neg \phi \,$ también lo es. Sus variables libres son las variables libres de $\phi \,$.
3. Si $\phi \,$ y $\psi \,$ son fórmulas bien formadas de Q, entonces $(\phi \land \psi )$, $(\phi \lor \psi )$, $(\phi \to \psi )$ y $(\phi \leftrightarrow \psi )$ también lo son. Sus variables libres son las variables libres de $\phi \,$ o $\psi \,$.
4. Si $\phi \,$ es una fórmula bien formada de Q, entonces $\forall x(\phi )\,$ y $\exists x(\phi )\,$ también lo son, pudiéndose usar cualquier otra variable en lugar de x. Sus variables libres son las variables libres de $\phi \,$ distintas de x. A cualquier instancia de x (u otra variable reemplazando x en esta construcción) se la llama ligada (no libre) en $\forall x(\phi )\,$ y $\exists x(\phi )\,$.
5. Sólo las expresiones que pueden ser generadas mediante las cláusulas 1 a 4 en un número finito de pasos son fórmulas bien formadas de Q.

Según esta gramática, algunos ejemplos de fórmulas bien formadas (no atómicas) son:

$\forall x(Px),\forall x(Da),\exists y(Ryyy),\forall x(\exists y(Gyaxbc)),\exists x(Bx\land Nxo),\forall x(Pxs\to \exists y(Kxyo\land \forall z(Rxyz)))$

Y algunos ejemplos de fórmulas mal formadas son:

$x,a,P,xaT,\forall ,\exists x,\exists \forall x(Bx),\exists xy(Nxy)$

Cuando no hay riesgo de confusión, es normal omitir ciertos paréntesis para simplificar la lectura y la escritura. Por ejemplo:

$\forall x\ Px$  en vez de  $\forall x(Px)$

$\forall x\forall y\exists z(Px\to Ryz)$  en vez de  $\forall x(\forall y(\exists z(Px\to Ryz)))$

Para ciertas relaciones muy utilizadas de aridad 2, generalmente se escribe a R b en vez de R(a,b). Por ejemplo, 2 > 1 en vez de >(2,1), y 4 = 4 en vez de =(4,4). Análogamente, si f es un símbolo de función de aridad 2, a veces se escribe a f b en vez de f(a,b). Por ejemplo, 1 + 2 en vez de +(1, 2).

Substitución de variables libres

Las nociones de variable libre y variable ligada se introducen para evitar un posible error en el proceso de substitución. Supongamos por un momento la fórmula $\forall x(x\leq y)$. Intuitivamente, esta fórmula dice que para todo x, x es menor o igual que y (es decir, que y es máximo). En esta fórmula, y es una variable libre, o sea que no está bajo el alcance de ningún cuantificador. Si substituimos y por cualquier otro término t, entonces la fórmula pasará a decir que t es máximo. Pero supongamos ahora que substituimos a y por x mismo (a fin de cuentas, x es un término). En ese caso, y pasa a estar ligada por un cuantificador universal, porque la nueva fórmula es: $\forall x(x\leq x)$. Pero esta fórmula ya no dice de un término que es máximo, sino algo muy distinto. Para evitar este tipo de desplazamiento de significado, convenimos que al substituir una variable libre por un término cualquiera, hay que evitar que las variables libres en el nuevo término queden ligadas por algún cuantificador. Es decir, que permanezcan libres.

Dicho de una manera más general, si t es un término y $\phi (x)\,$ es una fórmula que posiblemente contiene a x como una variable libre, entonces $\phi (t)\,$ es el resultado de substituir todas las apariciones libres de x por t, suponiendo que ninguna variable libre en t se vuelva ligada en este proceso. Si alguna variable libre de t se volviera ligada, entonces para substituir t por x se necesita cambiar los nombres de las variables ligadas de $\phi (x)\,$ por otros que no coincidan con las variables libres de t.

Identidad

Hay varias maneras diferentes de introducir la noción de identidad en la lógica de primer orden, pero todas con esencialmente las mismas consecuencias. Esta sección resume las principales:

• La manera más común de introducir a la identidad es incluyendo al símbolo entre los primitivos, y agregando axiomas que definan el comportamiento del mismo. Estos son:

$\forall x(x=x)$

$\forall x\forall y{\bigg (}(x=y)\to \forall f{\Big (}(f(...x...)=f(...y...){\Big )}{\bigg )}$

$\forall x\forall y{\bigg (}(x=y)\to \forall P{\Big (}(P(...x...)\leftrightarrow P(...y...){\Big )}{\bigg )}$

• Otra manera es incluir al símbolo de identidad como una de las relaciones de la teoría y agregar los axiomas de identidad a la teoría. En la práctica esta convención es casi indistinguible de la anterior, salvo en el caso inusual de las teorías sin noción de identidad. Los axiomas son los mismos. La única diferencia es que unos se llaman axiomas lógicos y los otros axiomas de la teoría.
• En las teorías sin funciones y con un número finito de relaciones, es posible definir la identidad en términos de las relaciones. Esto se hace definiendo que dos términos a y b son iguales si y sólo si ninguna relación presenta cambios reemplazando a por b en cualquier argumento. Por ejemplo, en teoría de conjuntos con una relación de pertenencia ( $\in \,$ ), definiríamos $a=b\,$ como una abreviación para $\forall x((a\in x)\leftrightarrow (b\in x))\land ((x\in a)\leftrightarrow (x\in b))$ Esta definición de identidad automáticamente satisface los axiomas de identidad.
• En algunas teorías es posible dar definiciones ad hoc para la identidad. Por ejemplo, en una teoría de órdenes parciales con una relación de menor o igual ( $\leq \,$ ) podríamos definir $a=b\,$ como una abreviación para $(a\leq b)\land (b\leq a)$

Reglas de inferencia

La lógica de primer orden tiene dos reglas de inferencia. La primera es el modus ponens, heredada de la lógica proposicional. La segunda es la regla de Generalización universal, que es característica de la lógica de primer orden. La misma dice:

${\frac {\phi }{\forall x(\phi )}}$

Es decir: a partir de $\phi \,$ es posible concluir que $\forall x(\phi )$.

Nótese que la regla de generalización universal es análoga a la regla de Necesitación de la lógica modal.

Axiomas

Los axiomas considerados aquí son los axiomas lógicos los cuales son parte del cálculo de predicados. Al formalizar teorías de primer orden particulares (como la aritmética de Peano) se agregan axiomas no-lógicos específicos, es decir axiomas que no se consideran verdades de la lógica pero sí verdades de una teoría particular.

Cuando el conjunto de axiomas es infinito, se requiere de un algoritmo que pueda decidir para una fórmula bien formada si es un axioma o no. Más aún, debería existir un algoritmo que pueda decidir si la aplicación de una regla de inferencia es correcta o no.

Es importante notar que el cálculo de predicados puede ser axiomatizado de varias formas diferentes. No existe nada canónico sobre los axiomas y reglas de inferencia aquí dadas, pero cualquier formalización produce los mismos teoremas de la lógica (y permite deducir los mismos teoremas de cualquier conjunto de axiomas no-lógicos).

Los siguientes cuatro axiomas lógicos caracterizan un cálculo de predicados:

• $(\forall x\ \phi (x))\to \phi (a)$
• $\phi (a)\to (\exists x\ \phi (x))$
• $(\forall x\ \psi \to \phi (x))\to (\psi \to \forall x\ \phi (x))$
• $(\forall x\ \phi (x)\to \psi )\to (\exists x\ \phi (x)\to \psi )$

Poder expresivo

Con el fin de poder caracterizar problemas en las clases de complejidad computacional más conocidas, se suele añadir poder de expresión a la lógica de primer orden utilizando cuantificadores generalizados o de Lindström.

Véase también

• Lógica proposicional
• Lógica de segundo orden
• Cuantificador
• Argumento
• Cálculo
• Cálculo lógico