Lenguaje de Primer Orden

David Baños Abril

El Lenguaje de Primer Orden, como el resto de lenguajes formales, requieren de un conjunto de símbolos, así como reglas de combinación entre ellos. El resultado son expresiones gramaticalmente correctas llamadas Fórmulas Bien Formadas que son las que usaremos para expresar al Lógica de Primer Orden.

Alfabeto de la Lógica de Primer Orden

Continuaremos nuestro estudio de la Lógica de Primer Orden, o Lógica de Predicados, formalizando todo lo que hemos planteado en el artículo previo. Comenzaremos estableciendo una sintaxis que nos permita distinguir fórmulas que están bien formadas de aquellas que no. Por el momento las fórmulas estarán vacías de significado alguno, solo nos interesa que sean sintácticamente correctas.

Símbolos Lógicos y Extralógicos

Para expresar la lógica haremos uso de un conjunto de símbolos que llamaremos alfabeto.

La Lógica de Primer Orden explota los recursos de la Lógica de Proposiciones. Es por ello que usaremos los conectores que vimos en artículos previos: ⊻  ¬  ∧  ∨  →  ↔. Además, también tendremos los símbolos y . Por último, necesitaremos de los paréntesis (, ) y los corchetes [ y ] para dar estructura a las fórmulas.

Hasta aquí los llamados símbolos lógicos, aquellos que son comunes a cualquier lenguaje formal de Lógica de Predicados. Pero necesitaremos algo más. Llamamos símbolos extralógicos a predicados, constantes y funciones. Esto es así porque el número e interpretación de estos símbolos depende del lenguaje. Diferentes predicados, funciones y constantes darán lugar a múltiples lenguajes formales. Es por ello que no existe un solo Lenguaje de Primer Orden, sino infinitos de ellos. El número de símbolos extralógicos en cada lenguaje será siempre finito.

Alfabeto de la Lógica de Primer Orden

Símbolos Lógicos
  • Conectores: ⊻  ¬  ∧  ∨  →  ↔
  • Cuantificadores: ∀  ∃
  • Paréntesis: (  )  [  ]
Símbolos Extralógicos
  • Predicados: P, R, T
  • Variables de individuo: x, y, a
  • Constantes: c_{1}, c_{2}, c_{3}
  • Funciones: f(x), g(x, y), h(z, p)

Lenguaje de Primer Orden

A un lenguaje cualquiera definido de manera que sea capaz de expresar la Lógica de Primer Orden lo llamaremos Λ y no será otra cosa que un conjunto de cadenas de diferente tamaño formadas por los símbolos del Alfabeto de Primer Orden que hemos apuntado antes. Un ejemplo de cadena de ese alfabeto podría ser «A∧∧(P))«. Pero si queremos que este lenguaje nos sirva para expresar la Lógica de Primer Orden, no queremos que cadenas como estas formen parte de dicho lenguaje, pues no podremos adjudicarles significado alguno. Deberemos entonces restringir los tipos de cadenas que vayan a formar parte de Λ.

Para ello será necesario definir nuestro lenguaje estableciendo que elementos pueden formar parte de el. Las expresiones que formen parte de Λ serán  fórmulas bien formadas.

Para establecer que fórmulas serán gramaticalmente correctas usaremos el método de definición inductiva, esto es, definir los elementos más básicos del lenguaje y con ellos también las reglas que permitan combinarlos, permitiendo así que nuestra definición acoja fórmulas cada vez más grandes y complejas.

Términos

Llamamos término (t) a toda variable individual o a una constante. Por ejemplo a, c_{1}, b

Si tenemos un conjunto de términos (t_{1}, t_{2}… t_{n}), el símbolo de la función f también será un término de la forma f(t_{1}, t_{2}… t_{n}). Este será el primero de los pasos inductivos para definir las expresiones de cualquier Lenguaje de Primer Orden.

De estas definiciones deducimos que un término o bien es un variable, o una constante o una función. La definición de símbolo de función nos permite aplicar el principio inductivo más de una vez. Esto posibilita generar términos con otros términos anidados como por ejemplo:  f(c, a, g(x, p(v, z)))

Fórmulas Atómicas

A partir de un símbolo de predicado y un conjunto de términos podemos construir una fórmula atómica. Los términos funcionarán como argumentos para dicho predicado. Por ejemplo, una fórmula atómica podría ser R(x, a) compuesto por un predicado binario y dos términos como argumentos.

Fórmulas

Procedemos ahora a definir una fórmula de un Lenguaje de Primer Orden usando de nuevo el método de definición inductiva.

 – Toda fórmula atómica es una fórmula.

 – Si A y B son fórmulas cualesquiera, también lo serán A ⊻ B, ¬A, A ∧ B, A ∨ B, A → B y A ↔ B

 – Si A(a) es una fórmula con una variable libre a y sustituimos cada aparición de esa variable en la fórmula por una variable ligada x, entonces ∀[A(x)] y ∃[A(x)] serán también fórmulas.

Uso del meta-lenguaje

Debemos advertir que estas expresiones NO son fórmulas del lenguaje que estamos intentando definir. Pertenecen realmente a un meta-lenguaje utilizado para hablar de nuestro lenguaje Λ<, uno en el que símbolos como [latex]A[/latex] o [latex]B[/latex] representan fórmulas cualesquiera de dicho lenguaje de Primer Orden. Como podrá comprobarse, en nuestra definición de Lenguaje de Primer Orden no hemos establecido símbolos para representar fórmulas del propio lenguaje. Así, cuando decimos "Si [latex]A[/latex] es una fórmula también lo será [latex]¬A[/latex]" tanto esa "[latex]A[/latex]" como "[latex]¬A[/latex]" no formarán parte de [latex]Λ[/latex]. A este tipo de expresiones las llamamos  esquemas de fórmulas, pues representan potencialmente infinitas fórmulas. Debe quedar clara esta distinción pues se verá de forma recurrente en posteriores artículos.

Oraciones del Lenguaje de Primer Orden

En el artículo previo apuntamos la diferencia entre variables ligadas, asociadas a un cuantificador, y variables libres, que no estaban vinculadas con ningún cuantificador. Será importante esta distinción en nuestro Lenguaje de Primer Orden puesto que en ocasiones podríamos necesitar sustituir una variable por otra y estas sustituciones están restringidas.

Si vamos a las definiciones previas, nos daremos cuenta que las variables aparecen desde la definición base de término.  Pero estas variables son libres, y así se mantiene a no ser que apliquemos el último de los pasos inductivos de la definición de fórmula. Por ello, toda variable que aparezca en una fórmula atómica será siempre libre. Podremos sustituir una variable por otro, pero debemos tener cuidado de que no provoquemos con ello que otra variable antes libre acabe ligada. Por ejemplo, sustituir en ∃y[P(x, y, z)] la variable y por x resultaría en la fórmula ∃y[P(x, x, z)], la cual tiene un sentido completamente distinto a la fórmula inicial. Esta restricción se revelará muy útil cuando exploremos la Semántica de Primer Orden.

Llamamos fórmulas cerradas o también oraciones a las fórmulas en la que todas las apariciones de variables sean ligadas, por ejemplo: ∀x[∃y[R(x,y)] ∨ ∃z[R(x,z)]]. Notar que la fórmula ∀x[∃y[R(x,y)]] ∨ ∃z[R(x,z)] no es una oración pues la segunda aparición de la variable x es libre.

Fórmulas Bien Formadas

Con nuestro alfabeto y nuestra definición, la cual es válida para cualquier lenguaje de la Lógica de Primer Orden, hemos establecido las expresiones gramaticalmente correctas que usaremos para expresar dicha lógica. De la misma manera que la expresión "Щелкунчик" no pertenece al español pues no utiliza su alfabeto, las expresiones como "La  Vida  Breve" o "1 + 2  = 3" no serán fórmulas de ningún Lenguaje de Primer Orden por no ser cadenas del Alfabeto de Primer Orden. Tampoco pertenece al español "Der   Zauberflöte" a pesar de que usa su mismo alfabeto. Así tampoco fórmulas como "f(P(x,y))" o "R(z, y) ∨ c_{1}" formarán parte de Λ a pesar de usar el Alfabeto de Primer Orden.

El número de símbolos del Alfabeto de Primer Orden es siempre finito. Sin embargo, nuestra definición de lenguaje permite la aplicación del paso inductivo de forma sucesiva sin restricciones. Es decir, teniendo dos fórmulas, arbitrariamente grandes, siempre podremos crear una tercera que combine ambas. De esto se deduce que el número de expresiones de cualquier Lenguaje de Primer Orden es infinito.

Lecturas recomendadas

 – Kolmogórov, A.N. y Dragalin, A.G. (2013) Introducción a la lógica matemática.

 – de Swart, H. (2018) Philosophical and Mathematical Logic.