Lógica de primer orden

La lógica de primer orden (LPO) o cálculo de predicados de primer orden es cualquier sistema de la lógica matemática que extiende la lógica proposicional empleando variables, predicados y cuantificadores de variables. A su vez es extendida por la lógica de segundo orden.

La lógica con predicados de primer orden tiene capacidad para definir prácticamente a todas las matemáticas.

Introducción

La lógica de primer orden es aquella en donde solamente se cuantifican las variables individuales. Estas últimas corresponden al sujeto de una oración, desde la perspectiva de la gramática usual.

P. ej. la frase "Los hombres son mortales"

El sujeto "hombres" está cuantificado de manera universal, es decir, "Todos los hombres" y hace la referencia universal de que "Todos los hombres son mortales".

También existe lo que se llama cuantificación existencial, y se utiliza el término cuantificador de "algunos" de tal forma que en la oración, "Algunos hombres son valientes" establece que cuando menos un hombre es valiente. Ahora bien, los cuantificadores recaen en una entidad abstracta y sustituible, de allí el nombre de "variable", porque puede cambiarse. Por ejemplo, en la frase "Todos los hombres son mortales" establece que, para cualquier entidad x, si x es un hombre, entonces, x es mortal. Dejando establecido que, si la entidad tiene el atributo de ser un hombre, entonces la entidad tiene el atributo de ser mortal.

Mientras que la frase "Algunos hombres son valientes" establece que, cuando menos una entidad x, tiene el atributo de ser un hombre y tiene el atributo de ser valiente. Es decir, tiene dos atributos. Debe quedar en claro que la primera proposición "Todos los hombres son mortales" es una implicación lógica, pero está oscurecida por el lenguaje ordinario, la implicación se formula como: para cualquier $x$, si $x$ es hombre, entonces, $x$ es mortal. Esta proposición es completamente distinta cuando se trata de una oración con cuantificador existencial: la frase "Algunos hombres son valientes" no es una implicación lógica, sino una entidad que tiene dos atributos.

El mecanismo simbólico que han diseñado los filósofos a través del tiempo para la cuantificación universal de las variables individuales, es encerrar entre paréntesis la variable individual, de tal forma que la frase "Todos los hombres son mortales" queda (por el momento) simbolizada como:

($\forall x$) si x es hombre, entonces, x es mortal

Su lectura podría leerse como: toda entidad x que es un hombre, es una entidad que es mortal. Claro está que también puede ser escrita con la variable y como:

(y) si y es humano, entonces, y es mortal.

Mientras el símbolo de cuantifiación existencial es :(∃x) quedando (por el momento) simbolizada la frase "algunos hombres son valientes" como:(∃x) / x es humano & x es valiente.

A primera vista parece no parece tener mucha importancia, pero la cuantificación es esencial para el razonamiento en lenguaje usual, así como para los razonamientos matemáticos.

Si tenemos la expresión matemática $x+y=z$ no expresa nada, no es verdadera ni falsa, pero si agregamos los cuantificadores expresará una oración que es o verdadera o falsa. El problema de la gran dificultad que los estudiantes muestran en las matemáticas es por la falta de la explicación referente a los cuantificadores. Si cuantificamos,

$\forall x\forall y\exists z(x+y=z)$ es verdadera

Pues establece que, un número cualquiera, sumado con otro número cualquiera, da igual a algún número (y sólo uno).

Mientras que $\forall x\forall y\forall z(x+y=z)$ es falsa.

Pues establece que, cualquier número x, sumado con cualquier otro número y, da igual a cualquier número (z)

El método matemático común, usa las letras: x, y, z para dejar "entendido" que tienen un cuantificador universal (pueden ser sustituidas por cualquier número) y les llaman "variables" mientras que las letras: a, b, c son aquellos números que tienen un cuantificador existencial y les llaman "constantes". Nuestra expresión de ($\forall$x)($\forall$y)(∃z) x + y = z queda simbolizada como:

x + y = a

Que es más cómoda que la anterior. Sin embargo, la falta de conocimiento de la cuantificación o la falta de explicación adecuada a los estudiantes causa grandes confusiones en la comprensión adecuada de las matemáticas.

La expresión:

($\forall$x) (∃y) x > y

expresa que hay un número "x" que es mayor a cualquier otro número "y", lo cual es verdadero. Es una propiedad numérica que afirma que no existe un número mayor que todos.

Sin embargo, los matemáticos generalmente no son precisos y raras veces cuantifican y causan mayor confusión. Por ejemplo, la expresión ax + b = c que corresponde a una función lineal del tipo f(x)= ax + b es ambigua, por que las letras a, b, c no están siendo utilizadas en el sentido anterior de "estar cuantificadas de forma existencial" , y si bien la letra x parece indicar que está cuantificada de manera universal, no es correcta tal suposición, surgida por la ambigüedad. El sentido que le dan los matemáticos es que las letras a, b, c son datos "conocidos" proporcionados en el problema a resolver. Mientras que "x" es el dato desconocido que no se proporciona en el problema y debe "encontrarse" para resolver la ecuación.

En la fórmula de punto pendiente: y2 - y1= m(x1 - x2) las letras están siendo usadas en otro sentido: en el sentido geométrico, de tal forma que se habla de "puntos" en el plano gráfico, de modo que las letras x hacen referencia a los puntos que se encuentran en las abscisas (línea horizontal) y las otras en las ordenadas (línea vertical). Al no estar cuantificadas y al estarse usando en otro sentido, esto provoca dificultades.

Las sentencias atómicas de la lógica de primer orden tienen la forma P(t₁, ... ,t_n) (un predicado con uno o más términos) en vez de las letras proposicionales como en la lógica proposicional. Usualmente, esto se escribe sin los paréntesis o comas.

Lo nuevo que tiene la lógica de primer orden que no está presente en la lógica proposicional es la cuantificación: si φ es cualquier sentencia, se introducen las nuevas construcciones ∀x φ y ∃x φ, que se leen "para todo x, φ" y "existe x, tal que φ". En la explicación usamos φ como φ(x). φ(a) representa el resultado de reemplazar todas las apariciones libres de x en φ(x) con a. Luego, ∀x φ(x) significa que φ(a) es verdadero para cualquier valor de a y ∃x φ significa que existe un a tal que φ(a) es verdadero. Los valores de las variables se toman del universo dado. Un refinamiento de la lógica de primer orden permite que las variables tomen valores de diferentes conjuntos.

La lógica de primer orden tiene suficiente poder expresivo para la formalización de diversas áreas de la matemática. Una teoría de primer orden consiste de un conjunto de axiomas (usualmente finitos o recursivamente numerables), y las declaraciones o "statements" deducibles de ellos. La teoría de conjuntos usual (Zermelo-Frankel) es un ejemplo de teoría de primer orden. Además, es generalmente aceptado que toda la matemática clásica puede ser formalizada en esta teoría. Hay otras teorías que comúnmente se formalizan independientemente en lógica de primer orden como la aritmética de Peano.

Definiendo la lógica de primer orden

El cálculo de predicados consiste de

• Reglas de formación (una definición recursiva del conjunto de las fórmulas).
• Un conjunto finito de reglas de inferencia.
• Un conjunto (posiblemente infinito numerable) de axiomas o esquemas axiomáticos.

Los axiomas considerados aquí son los axiomas lógicos los cuales son parte del cálculo de predicados. Más adelante se agregan axiomas no-lógicos en teorías de primer orden específicas: 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 formalizado 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 deducir los mismos teoremas de cualquier conjunto de axiomas no-lógicos).

Vocabulario

El "vocabulario" se compone de

1. Un conjunto de variables de predicado (o relaciones) cada una con cierta aridad ≥1, (aridad: número de argumentos necesarios para que un operador o función se pueda calcular) que se denotan habitualmente con letras máyusculas P, Q, R, ...
2. Un conjunto de constantes, habitualmente denotadas con letras minúsculas a, b, c, ...
3. Un conjunto de funciones, cada una con cierta aridad ≥ 1, la cuales se denotan habitualmente con letras minúsculas f, g, h, ...
4. Un conjunto infinito de variables, habitualmente denotadas por letras minúsculas x, y, z, ...
5. Operadores lógicos (o conectivos): : ¬ ("no" lógico), ∧ ("y" lógico), ∨ ("o" lógico), → (implicación), ↔ (si y sólo si).
6. Símbolos que denotan los cuantificadores: ∀ (cuantificación universal), ∃ (cuantificación existencial).
7. Paréntesis izquierdo y derecho.
8. A veces, pero no siempre, se incluye un símbolo de identidad o igualdad = .

Hay varias variaciones menores listadas a continuación:

• El conjunto de símbolos primitivos (operadores y cuantificadores) a veces varía. Algunos símbolos pueden ser omitidos como primitivos y tomados como abreviatura. Por ejemplo (P ↔ Q) es una abreviatura para (P → Q) ∧ (Q → P). Por otro lado, es posible incluir otros operadores como primitivos, como la constante de verdad ⊤ ("top") para "verdadero" y la constante de falsedad ⊥ ("bottom") para "falso" (estos operadores tienen aridad 0), la barra de Sheffer (Sheffer stroke) (P | Q). El mínimo número de símbolos primitivos requeridos es uno, pero si nos restringimos a los operadores listados anteriormente necesitamos tres, por ejemplo ¬, ∧, y ∀ son suficientes.
• Algunos libros y documentos más antiguos usan la notación φ ⊃ ψ para φ → ψ, ~φ para ¬φ, φ & ψ para φ ∧ ψ, y numerosas notaciones para los cuantificadores; por ejemplo, ∀x φ puede estar escrito como (x)φ.
• La igualdad a veces se considera parte de la lógica de primer orden. En ese caso, el símbolo de igualdad 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 igualdad.
• Las constantes en realidad son funciones de aridad 0, de esta manera puede ser 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 las relaciones deber tener aridad mayor o igual que 1. Es posible permitir relaciones de aridad 0; estas podrían ser consideradas como variables proposicionales.
• 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.

Reglas de formación

Las reglas de formación definen el lenguaje de la lógica de primer orden como Lenguaje formal de la siguiente manera.

Un conjunto de términos es definido recursivamente por las siguientes reglas:

1. Cualquier constante es un término (sin variables libres)
2. Cualquier variable es un término (cuya única variable libre es sí misma)
3. Cualquier expresión f(t₁,...,t_n) de n≥1 argumentos (donde cada argumento t_i es un término y f es un símbolo de función de aridad n) es un término. Sus variables libres son las variables libres de cualquiera de los términos t_i.
4. Cláusula de clausura: ninguna otra cosa es un término.

El conjunto de fórmulas bien formadas (usualmente llamadas fbf, en inglés wff, o simplemente fórmulas) son definidas recursivamente por las siguientes reglas:

1. Predicados simples y complejos Si P es una relación de aridad n ≥ 1 y los a_i son términos entonces P (a₁,...,a_n) es bien formado. Sus variables libres son la variables libres de cualquiera de sus términos a_i. Si se considera la igualdad parte de la lógica, entonces (a₁ = a₂) está bien formada. Todas esas fórmula se llaman atómicas.
2. Cláusula Inductiva I: Si φ es una fórmula bien formada, entonces ¬ φ es una fórmula bien formada. Sus variables libres son las variables libres de φ.
3. Cláusula Inductiva II: Si φ y ψ son fórmulas bien formadas, entonces (φ ∧ ψ), (φ ∨ ψ), (φ → ψ), (φ ↔ ψ) son fórmulas bien formadas. Sus variables libres son las variables libres de φ o ψ.
4. Cláusula Inductiva III: Si φ es una fórmula bien formada, ∀ x φ y ∃ x φ son fórmulas bien formadas, pudiéndose usar cualquier otra variable en lugar de x. Sus variables libres son las variables libres de φ distintas de x. Cualquier instancia de x (u otra variable reemplazando x en esta construcción) se dice ligada (no libre) en ∀ x φ y ∃ x φ.
5. Cláusula de clausura: Ninguna otra cosa es una fórmula bien formada.

En la práctica, si P es una relación de aridad 2, habitualmente se escribe "a P b" en vez de "P a b"; por ejemplo, 1 < 2 en vez de <(1, 2). Análogamente si f es una función de aridad 2, a veces escribimos "a f b" en vez de "f(a, b)"; por ejemplo, escribimos 1 + 2 en vez de +(1, 2). También es común omitir algunos paréntesis si esto no conduce a una ambigüedad.

A veces es útil expresar que "P(x) se cumple para exactamente un x". Esto se nota habitualmente:

∃!x P(x)

También puede ser expresado como: ∃x (P(x) ∧ ∀y (P(y) → (x = y)))

Substitución

Si t es un término y φ(x) es una fórmula posiblemente conteniendo x como una variable libre entonces φ(t) se define como el resultado de reemplazar 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 φ por otros que no coincidan con las variables libres de t. Para ver por qué esta condición es necesaria, consideremos la fórmula φ(x) dada por ∀y y≤x ("x es máximo"). Si t es un término sin y como variable libre, entonces φ(t) dice que t es máximo. Sin embargo, si t es y la fórmula φ(y) es ∀y y≤y lo cual no dice que y es máximo. El problema es que la variable libre y de t (=y) se volvió ligada al substituir y por x φ(x). Luego para formar φ(y) primero debemos cambiar la variable ligada y de φ por otra cosa, digamos z. Así φ(y) es entonces ∀z z≤y. Olvidar esta condición es una notoria causa de errores.

Ejemplos: El lenguaje de los grupos abelianos ordenados tiene una constante 0, una función unaria −, una función binaria +, y una relación binaria ≤. Así

• 0, x, y son términos atómicos
• +(x, y), +(x +(y (−z))) son términos, usualmente notado como x + y, x + (y + (−z))
• +(x, y) = 0, ≤ +(x +(y (−z))) +(x, y) son fórmulas atómicas, usualmente notado como x + y = 0, x + y−z ≤ x + y,
• (∀x ∃y ≤ +(x y) z) ∧ (∃x +(x, y) = 0) es una fórmula, usualmente notado como (∀x ∃y x + y ≤ z) ∧ (∃x x + y = 0).

Igualdad

Hay varias convenciones diferentes para usar la igualdad (o identidad) en la lógica de primer orden. Esta sección resume las principales. Todas las convenciones dan esencialmente los mismos resultados y difieren principalmente en la terminología.

• La convención más común para igualdad es incluir el símbolo de igualdad como un símbolo lógico primitivo y agregar los axiomas de igualdad a los axiomas de la lógica de primer orden. Los axiomas de igualdad son:

x = x

x = y → f(...,x,...) = f(...,y,...) para cualquier función f

x = y → (P(...,x,...) → P(...,y,...)) para cualquier relación P (incluyendo la igualdad)

• La siguiente convención más común es incluir el símbolo de igualdad como una de las relaciones de la teoría y agregar los axiomas de igualdad 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 igualdad. Los axiomas son los mismos. La única diferencias 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 igualdad en términos de las relaciones. Esto se hace definiendo que dos términos s y t son iguales si y sólo si ninguna relación presenta cambios reemplazando s por t en cualquier argumento. Por ejemplo, en teoría de conjuntos con una relación ∈, definiríamos s = t como una abreviatura para ∀x (s ∈ x ↔ t ∈ x) ∧ ∀x (x ∈ s ↔ x ∈ t). Esta definición de igualdad automáticamente satisface los axiomas de igualdad.
• En algunas teorías es posible dar definiciones ad hoc para igualdad. Por ejemplo, en una teoría de órdenes parciales con una relación ≤ podríamos definir s = t como una abreviatura para s ≤ t ∧ t ≤ s.

Reglas de Inferencia

La regla de inferencia modus ponens es la única requerida de la lógica proposicional para la formalización dada aquí. Esto indica que si se prueba φ y φ → ψ, entonces se puede deducir ψ.

La regla de inferencia llamada Generalización universal es característica del cálculo de predicados. Se puede expresar como

si $\vdash \phi$ entonces $\vdash \forall x\,\phi$

donde φ es un teorema del cálculo de predicados ya probado.

Nótese que la regla de generalización es análoga a la regla de necesidad de la lógica modal, que es:

si $\vdash P$ entonces $\Box P$

Axiomas de cuantificadores

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

• PRED-1: (∀x Z(x)) → Z(t)
• PRED-2: Z(t) → (∃x Z(x))
• PRED-3: (∀x (W → Z(x))) → (W → ∀x Z(x))
• PRED-4: (∀x (Z(x) → W)) → (∃x Z(x) → W)

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.