Semántica de Primer Orden
David Baños Abril
Una vez que disponemos de un lenguaje formalizado, la Semántica de Primer Orden nos permitirá dotar de un significado a las fórmulas. De esta forma podremos resolver si dicha fórmula es o no verdadera bajo cierta interpretación.
Semántica de Primer Orden
De una fórmula como ∀x[P(x) ⊻ F(x)] podremos afirmar que es una fórmula bien formada, pero no alcanzaremos a decir si es cierta o es falsa. Debemos dotarla de una interpretación que nos permite juzgar su veracidad. Al igual que en Lógica Proposicional, en Lógica de Primer Orden habrá fórmulas verdaderas bajo cierta interpretación pero que sean falsas en otra. También habrá fórmulas válidas en toda interpretación.
Hemos apuntado que los predicados establecen conjuntos de elementos. Así, dotar de significado una oración como ∀x[P(x)] implica poner en relación el conjunto del predicado P con el conjunto de valores que puede asumir x. Podremos comprobar como la oración será verdadera si y solo sí ambos conjuntos son iguales.
Es por ello que nuestro primer paso será establecer los métodos a partir de los cuales dotaremos de significado a una fórmula. Tras ello, nuestra misión será asignar a cada una de esas interpretaciones un valor de verdad.
Interpretación de un Lenguaje de Primer Orden
Interpretación
En la Lógica Proposicional discriminar los valores de verdad de las fórmulas consistía en contemplar todas las posibles combinaciones de verdad de las variables proposicionales que constituyesen dicha fórmula.
En Semántica de Primer Orden, debido al uso de cuantificadores, el concepto de interpretación será algo más complicado. Llamamos interpretación I de un Lenguaje de Primer Orden Λ a una estructura formada por cuatro tipos de elementos: un universo de elementos, las interpretaciones de cada predicado, las interpretaciones de cada función y las interpretaciones de cada constante que aparezcan en dicho lenguaje.
El Universo de una Interpretación
El universo U es el conjunto de elementos que cumplen el papel de ser el ámbito de aplicación de los símbolos extralógicos de un Lenguaje de Primer Orden. Esto es, dado un lenguaje Λ con predicados, constantes y funciones, una interpretación I nos permitirá que:
– cada símbolo de predicado P de aridad n = 1 le corresponda un subconjunto P^{I} de U. Cuando nos referíamos a que un predicado equivalía a un conjunto de elementos nos referíamos precisamente a este P^{I}. Para predicados de más de un argumento (aridad n > 1) el conjunto P^{I} no será un subconjunto de U sino de U^{n}, es decir, será un conjunto de relaciones de n elementos, todos pertenecientes a U.
– Cada símbolo de constante c se interprete con un elemento de U que llamaremos c^{I}.
– A cada símbolo de función f le corresponda un elemento de U que llamaremos f^{I}, para cada interpretación de sus argumentos.
Cada interpretación podrá tener su propio universo, pero solo y exclusivamente uno. Notar que pueden existir dos interpretaciones distintas para un mismo lenguaje aun compartiendo un mismo universo si las interpretaciones para cada símbolo extralógico (predicado, constantes y funciones) son diferentes.
Ejemplo de Interpretación
Símbolos Extralógicos del Lenguaje Λ_{1}
– Constantes: c
– Predicados: P(x, c), S(y), C(v, d)
Interpretación I_{1} para el Lenguaje Λ_{1}
– U^{1} = {Conde Dooku, Obi-Wan, Yoda, Darth Maul, Darth Vader, Anakin, Darth Sidious, Qui-Gon Jin, Mace Windu}
– c^{I_{1}} = Darth Sidious
–P^{I_{1}} = {〈Darth Maul, Darth Sidious〉, 〈Conde Dooku, Darth Sidious〉, 〈Darth Vader, Darth Sidious〉}
– S^{I_{1}} = {Conde Dooku, Darth Maul, Darth Vader, Darth Sidious}
– C^{I_{1}} = {〈Anakin, Conde Dooku〉, 〈Obi-Wan, Darth Maul〉, 〈Darth Maul, Qui-Gon Jin〉}
Verdad en una Interpretación
Una vez que tengamos una estructura que asigne interpretaciones a los símbolos el siguiente paso será asociar cada una de esas interpretaciones con un valor de verdad. Esto lo conseguiremos con una función matemática de verdad a la que llamaremos v^{I_{1}}(A). Esta nos devolverá o bien 1 (verdadera) o bien 0 (falsa) cuando le introducimos una fórmula A como argumento.
La idea es que si por ejemplo tengo una fórmula tal que ∃x[J(x)] dicha función v^{I} devuelva 1 cuando el conjunto J^{I} tenga al menos un elemento, es decir, existe al menos un individuo de U que cumple la propiedad J. De la misma manera nos devolverá 1 introduciendo ∀x[J(x)] solo si el conjunto J^{I} es del mismo tamaño que U, o lo que es lo mismo, si todos los elementos de U cumplen la propiedad J. También nos devolverá verdadero en T(c_{1}) si c^{I}_{1} esta dentro de T^{I}.
Veracidad en oraciones
Recordemos que llamábamos oraciones a aquellas fórmulas cuyas apariciones de variables eran todas ligadas, es decir, asociadas a cuantificadores. Como se puede comprobar, la interpretación establece un único ámbito de aplicación para todas las variables, que es el universo. Es por ello que, en el caso de las oraciones, el procedimiento de verificación implica registrar, uno por uno, cada elemento de U para comprobar si se encuentra en el conjunto del predicado. En el caso de predicados de aridad n implicaría chequear cada combinación de n elementos de U.
Siguiendo el ejemplo que hemos expuesto antes se podrá comprobar como:
Una vez chequeado cada predicado, la veracidad de la fórmula recae en los conectores. La forma de resolverlo es la misma que con la Lógica Proposicional. Debe quedar claro que, tratándose de oraciones cuantificadas, la letra minúscula que asuma cada variable es irrelevante. Esto no se aplica a las constantes.
Veracidad con variables libres
Cuando en algún punto de nuestra fórmula exista una variable libre entonces no podremos utilizar el método antes expuesto. Sin cuantificadores, no estamos indicando el ámbito de aplicación de una variable. Así, es imposible verificar con el ejemplo galáctico de antes una fórmula como P(a, c) ∧ S(a). ¿Qué es a?¿Un elemento concreto?¿Puede adoptar varios valores del universo?
Verificar una fórmula con una variable libre exige establecer una interpretación explícita de la variable en cuestión. Por ejemplo, sí tendría sentido lo siguiente:
puesto que indicamos como debe interpretarse a exactamente. Otro tipo de interpretaciones de a podrían hacer que la fórmula no fuese correcta. De esto se deduce que, la misma fórmula con variables libres puede tener distintos valores de verdad incluso bajo una misma interpretación. Esto no ocurre con las oraciones con cuantificadores.
Modelos y Satisfactibilidad
Llamamos modelos a las interpretaciones que hacen cierta a una fórmula A. En notación sería I \models A, que viene a decir que A es verdadera en I.
Continuando con los ejemplos previos, la interpretación I_{1} es un modelo para la oración ∃y[S(y)] puesto que v^{I_{1}}(∃y[S(y)]) = 1. Cuando el resultado de la función de verdad sea 0 no será un modelo.
Fórmulas satisfactibles y válidas
Al igual que en la Lógica Proposicional, en la de predicados tendremos fórmulas bien formadas que serán ciertas bajo algunas interpretaciones, ciertas bajo cualquier interpretación y que no son ciertas en ninguna interpretación. A las primeras las llamamos fórmulas satisfactibles, mientras que las segundas son fórmulas válidas, igual que las que vimos en Lógica Proposicional. Un ejemplo de fórmula válida es ∀x [P(x)] ↔ ¬∃x[¬P(x)] cuya veracidad es evidente. En notación ponemos \models A, sin hacer referencia a ninguna interpretación concreta.
Consecuencia Lógica
Una misma interpretación hará ciertas a un conjunto de fórmulas. En el ejemplo previo, todas las fórmulas que den como resultado 1 pertenecen a un mismo modelo, el universo de Star Wars. Sin embargo, dos fórmulas que tengan dicha interpretación como modelo, pueden no compartir otras modelos diferentes.
Así, podemos establecer una vinculación entre fórmulas incluso más estrecha que la de formar parte de un mismo modelo. A esta relación se le conoce como consecuencia lógica, uno de los conceptos de la Semántica de Primer Orden más importantes.
La definición de consecuencia lógica es sencilla. Una fórmula B es consecuencia de una fórmula A cuando en toda interpretación que haga a A verdadera, B sea también verdadera. Decimos que A \models B. En otras palabras, no puede existir un caso de un modelo de A que no sea modelo para B.
Decibilidad en la Lógica de Primer Orden
El planteamiento que hemos ofrecido hasta ahora sobre la Semántica de Primer Orden se debe principalmente a los trabajos del gran matemático polaco Alfred Tarski, a principios del siglo pasado. Debemos resaltar una propiedad interesante de esta Semántica de Primer Orden. En Lógica Proposicional, verificar una fórmula era cuestión de generar una tabla de verdad en la que apareciesen las distintas combinaciones de valores de verdad de cada variable. Eso nos resultaba en una tabla que era arbitrariamente larga pero nunca infinita.
La definición expuesta de interpretación en la Lógica de Primer Orden permite universos con un número infinito de elementos y también interpretaciones de predicados como conjuntos de infinitos elementos. Esto será algo habitual cuando usemos esta lógica para hablar sobre propiedades aritméticas y el universo de una interpretación sea por ejemplo, el conjunto de números naturales. Esto significa que no es posible ir chequeando cada combinación de valores para comprobar si es o no cierta bajo una determinada interpretación, pues esto sería una tarea infinita. En otras palabras, puede no existir un procedimiento computable para comprobar la veracidad de una fórmula bajo ciertas interpretaciones. Esto es una de las metapropiedades de la Lógica de Primer Orden que veremos en un futuro.
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.
