Interpretación (lógica)

Un lenguaje formal${\displaystyle {\mathcal {W}}}$se puede definir con el alfabeto${\displaystyle \alpha =\{\triangle ,\square \}}$y con una palabra estando en${\displaystyle {\mathcal {W}}}$si empieza con${\displaystyle \triangle }$y está compuesto únicamente por los símbolos${\displaystyle \triangle }$y${\displaystyle \square }$.

Una posible interpretación de${\displaystyle {\mathcal {W}}}$podría asignar el dígito decimal '1' a${\displaystyle \triangle }$y '0' a${\displaystyle \square }$. Entonces${\displaystyle \triangle \square \triangle }$denotaría 101 bajo esta interpretación de${\displaystyle {\mathcal {W}}}$.

En los casos específicos de la lógica proposicional y la lógica de predicados, los lenguajes formales considerados poseen alfabetos divididos en dos conjuntos: los símbolos lógicos ( constantes lógicas ) y los símbolos no lógicos. La idea subyacente a esta terminología es que los símbolos lógicos tienen el mismo significado independientemente del tema de estudio, mientras que el significado de los símbolos no lógicos varía según el área de investigación.

Las constantes lógicas siempre tienen el mismo significado en todas las interpretaciones del tipo estándar, de modo que solo cambian los significados de los símbolos no lógicos. Las constantes lógicas incluyen los símbolos cuantificadores ∀ ("todos") y ∃ ("algunos"), los símbolos de conectores lógicos ∧ ("y"), ∨ ("o"), ¬ ("no"), los paréntesis y otros símbolos de agrupación, y (en muchos tratamientos) el símbolo de igualdad =.

Algunos de los símbolos lógicos de un lenguaje (aparte de los cuantificadores) son conectores veritativo-funcionales que representan funciones de verdad  : funciones que toman valores de verdad como argumentos y devuelven valores de verdad como resultados (en otras palabras, son operaciones sobre los valores de verdad de las oraciones).

Los conectores veritativo-funcionales permiten construir oraciones compuestas a partir de oraciones más simples. De esta forma, el valor de verdad de la oración compuesta se define como una función de verdad determinada de los valores de verdad de las oraciones más simples. Los conectores suelen considerarse constantes lógicas , lo que significa que su significado es siempre el mismo, independientemente de las interpretaciones que se les den a los demás símbolos de una fórmula.

Así es como definimos los conectores lógicos en la lógica proposicional:

• ¬Φ es verdadero si y solo si Φ es falso.
• (Φ ∧ Ψ) es verdadero si y solo si Φ es verdadero y Ψ es verdadero.
• (Φ ∨ Ψ) es verdadero si y solo si Φ es verdadero o Ψ es verdadero (o ambos son verdaderos).
• (Φ → Ψ) es verdadero si y solo si ¬Φ es verdadero o Ψ es verdadero (o ambos son verdaderos).
• (Φ ↔ Ψ) es verdadero si y solo si (Φ → Ψ) es verdadero y (Ψ → Φ) es verdadero.

Así, bajo una interpretación dada de todas las letras de la oración Φ y Ψ (es decir, después de asignar un valor de verdad a cada letra), podemos determinar los valores de verdad de todas las fórmulas que las contienen como constituyentes, en función de los conectores lógicos. La siguiente tabla muestra cómo se ve esto. Las dos primeras columnas muestran los valores de verdad de las letras de la oración según las cuatro interpretaciones posibles. Las demás columnas muestran los valores de verdad de las fórmulas construidas a partir de estas letras, con valores de verdad determinados recursivamente.

Ahora es más fácil ver qué hace que una fórmula sea lógicamente válida. Consideremos la fórmula F : (Φ ∨ ¬Φ). Si nuestra función de interpretación hace que Φ sea verdadera, entonces ¬Φ se vuelve falsa por la función de negación. Dado que el disyunto Φ de F es verdadero bajo esa interpretación, F es verdadera. Ahora bien, la única otra interpretación posible de Φ la hace falsa, y si es así, ¬Φ se vuelve verdadera por la función de negación. Esto haría que F fuera verdadera nuevamente, ya que uno de los disyuntos de F , ¬Φ, sería verdadero bajo esta interpretación. Dado que estas dos interpretaciones para F son las únicas interpretaciones lógicas posibles, y dado que F resulta verdadera para ambas, decimos que es lógicamente válida o tautológica.

Dada una signatura σ, el lenguaje formal correspondiente se conoce como el conjunto de fórmulas σ. Cada fórmula σ se construye a partir de fórmulas atómicas mediante conectores lógicos; las fórmulas atómicas se construyen a partir de términos utilizando símbolos de predicado. La definición formal del conjunto de fórmulas σ procede en sentido inverso: primero, los términos se ensamblan a partir de los símbolos de constante y función junto con las variables. Luego, los términos se pueden combinar en una fórmula atómica utilizando un símbolo de predicado (símbolo de relación) de la signatura o el símbolo de predicado especial "=" para la igualdad (véase la sección " Interpretación de la igualdad" más adelante). Finalmente, las fórmulas del lenguaje se ensamblan a partir de fórmulas atómicas utilizando los conectores lógicos y los cuantificadores.

Para atribuir significado a todas las oraciones de un lenguaje de primer orden, se necesita la siguiente información.

• Un dominio de discurso ^{[ a ]} D , que generalmente debe ser no vacío (véase más abajo).
• Para cada símbolo constante, un elemento de D como su interpretación.
• Para cada símbolo de función n- aria, una función n -aria de D a D como su interpretación (es decir, una función D ⁿ  → D ). 
• Para cada símbolo de predicado n -ario, una relación n -aria en D como su interpretación (es decir, un subconjunto de D ⁿ ).

Un objeto que contiene esta información se conoce como una estructura ( de signatura σ), o σ-estructura, o L -estructura (de lenguaje L), o como un "modelo".

La información especificada en la interpretación proporciona información suficiente para asignar un valor de verdad a cualquier fórmula atómica, después de que cada una de sus variables libres , si las hay, haya sido reemplazada por un elemento del dominio. El valor de verdad de una oración arbitraria se define entonces inductivamente utilizando el esquema T , que es una definición de semántica de primer orden desarrollada por Alfred Tarski. El esquema T interpreta los conectores lógicos utilizando tablas de verdad, como se explicó anteriormente. Así, por ejemplo, φ ∧ ψ se satisface si y solo si tanto φ como ψ se satisfacen.

Esto plantea la cuestión de cómo interpretar las fórmulas de la forma ∀ x φ( x ) y ∃ x φ( x ) . El dominio del discurso constituye el rango de estos cuantificadores. La idea es que la oración ∀ x φ( x ) es verdadera bajo una interpretación exactamente cuando se satisface cada instancia de sustitución de φ( x ), donde x se reemplaza por algún elemento del dominio. La fórmula ∃ x φ( x ) se satisface si existe al menos un elemento d del dominio tal que φ( d ) se satisface.

Estrictamente hablando, una instancia de sustitución como la fórmula φ( d ) mencionada anteriormente no es una fórmula en el lenguaje formal original de φ, porque d es un elemento del dominio. Hay dos maneras de abordar este problema técnico. La primera es pasar a un lenguaje más amplio en el que cada elemento del dominio se designa con un símbolo constante. La segunda es añadir a la interpretación una función que asigne cada variable a un elemento del dominio. Entonces, el esquema T puede cuantificar sobre variaciones de la interpretación original en las que se modifica esta función de asignación de variables, en lugar de cuantificar sobre instancias de sustitución.

Algunos autores también admiten variables proposicionales en la lógica de primer orden, las cuales deben interpretarse. Una variable proposicional puede existir por sí misma como una fórmula atómica. La interpretación de una variable proposicional es uno de los dos valores de verdad verdadero y falso. ^{[ 3 ]}

Dado que las interpretaciones de primer orden descritas aquí se definen en la teoría de conjuntos , no asocian cada símbolo de predicado con una propiedad ^{[ b ]} (o relación), sino con la extensión de esa propiedad (o relación). En otras palabras, estas interpretaciones de primer orden son extensionales ^{[ c ],} no intensionales .

Un ejemplo de interpretación${\displaystyle {\mathcal {I}}}$La definición del lenguaje L descrita anteriormente es la siguiente.

• Dominio: Un juego de ajedrez
• Constantes individuales: a: El rey blanco, b: La reina negra, c: El peón del rey blanco
• F(x): x es una pieza
• G(x): x es un peón
• H(x): x es negro
• I(x): x es blanco
• J(x, y): x puede capturar y

En la interpretación${\displaystyle {\mathcal {I}}}$de L:

• Las siguientes son oraciones verdaderas: F(a), G(c), H(b), I(a), J(b, c),
• Las siguientes son oraciones falsas: J(a, c), G(a).

Como se indicó anteriormente, por lo general se requiere una interpretación de primer orden para especificar un conjunto no vacío como el dominio del discurso. La razón de este requisito es garantizar que las equivalencias tales como $${\displaystyle (\phi \lor \exists x\psi )\leftrightarrow \exists x(\phi \lor \psi ),}$$ donde x no es una variable libre de φ, son lógicamente válidas. Esta equivalencia se cumple en todas las interpretaciones con un dominio no vacío, pero no siempre se cumple cuando se permiten dominios vacíos. Por ejemplo, la equivalencia $${\displaystyle [\forall y(y=y)\lor \exists x(x=x)]\equiv \exists x[\forall y(y=y)\lor x=x]}$$ falla en cualquier estructura con un dominio vacío. Por lo tanto, la teoría de la demostración de la lógica de primer orden se vuelve más compleja cuando se permiten estructuras vacías. Sin embargo, la ventaja de permitirlas es insignificante, ya que tanto las interpretaciones previstas como las interpretaciones interesantes de las teorías que se estudian tienen dominios no vacíos. ^{[ 4 ] [ 5 ]}

Las relaciones vacías no causan ningún problema en las interpretaciones de primer orden, ya que no existe una noción similar de pasar un símbolo de relación a través de un conector lógico, ampliando su alcance en el proceso. Por lo tanto, es aceptable que los símbolos de relación se interpreten como idénticamente falsos. Sin embargo, la interpretación de un símbolo de función siempre debe asignarle una función completa y bien definida.

La relación de igualdad se trata a menudo de forma especial en la lógica de primer orden y otras lógicas de predicados. Existen dos enfoques generales.

El primer enfoque consiste en tratar la igualdad como cualquier otra relación binaria. En este caso, si se incluye un símbolo de igualdad en la signatura, suele ser necesario añadir diversos axiomas sobre la igualdad a los sistemas axiomáticos (por ejemplo, el axioma de sustitución que establece que si a = b y se cumple R ( a ), entonces también se cumple R ( b )). Este enfoque de la igualdad resulta más útil al estudiar signaturas que no incluyen la relación de igualdad, como la signatura de la teoría de conjuntos o la de la aritmética de segundo orden, en la que solo existe una relación de igualdad para números, pero no para conjuntos de números.

El segundo enfoque consiste en tratar el símbolo de la relación de igualdad como una constante lógica que debe interpretarse mediante la relación de igualdad real en cualquier interpretación. Una interpretación que interpreta la igualdad de esta manera se conoce como modelo normal , por lo que este segundo enfoque equivale a estudiar únicamente las interpretaciones que resultan ser modelos normales. La ventaja de este enfoque es que los axiomas relacionados con la igualdad se satisfacen automáticamente en todo modelo normal, por lo que no es necesario incluirlos explícitamente en las teorías de primer orden cuando la igualdad se trata de esta manera. Este segundo enfoque a veces se denomina lógica de primer orden con igualdad , pero muchos autores lo adoptan para el estudio general de la lógica de primer orden sin comentarios.

Existen otras razones para restringir el estudio de la lógica de primer orden a los modelos normales. En primer lugar, se sabe que cualquier interpretación de primer orden en la que la igualdad se interpreta mediante una relación de equivalencia y satisface los axiomas de sustitución para la igualdad puede reducirse a una interpretación elementalmente equivalente en un subconjunto del dominio original. Por lo tanto, el estudio de modelos no normales aporta poca generalidad adicional. En segundo lugar, si se consideran modelos no normales, toda teoría consistente tiene un modelo infinito; esto afecta a los enunciados de resultados como el teorema de Löwenheim-Skolem , que generalmente se formulan bajo el supuesto de que solo se consideran modelos normales.

Una generalización de la lógica de primer orden considera lenguajes con más de un tipo de variable. La idea es que los distintos tipos de variables representan diferentes tipos de objetos. Cada tipo de variable puede cuantificarse; por lo tanto, una interpretación para un lenguaje con múltiples tipos tiene un dominio separado para cada tipo de variable (existe una colección infinita de variables de cada tipo). Los símbolos de función y relación, además de tener aridades, se especifican de manera que cada uno de sus argumentos debe pertenecer a un tipo determinado.

Un ejemplo de lógica multicategórica se encuentra en la geometría euclidiana plana . Existen dos tipos: puntos y líneas. Hay un símbolo de relación de igualdad para puntos, otro para líneas y una relación de incidencia binaria E que toma una variable de punto y una variable de línea. La interpretación prevista de este lenguaje implica que las variables de punto abarcan todos los puntos del plano euclidiano , las variables de línea abarcan todas las líneas del plano, y la relación de incidencia E ( p , l ) se cumple si y solo si el punto p está sobre la línea l .

Dado un sistema formal simple (lo llamaremos uno${\displaystyle {\mathcal {FS'}}}$) cuyo alfabeto α consta únicamente de tres símbolos${\displaystyle \{\blacksquare ,\bigstar ,\blacklozenge \}}$y cuya regla de formación de fórmulas es:

'Cualquier cadena de símbolos de${\displaystyle {\mathcal {FS'}}}$que tiene al menos 6 símbolos de longitud y que no es infinitamente larga, es una fórmula de${\displaystyle {\mathcal {FS'}}}$. Nada más es una fórmula de${\displaystyle {\mathcal {FS'}}}$.'

El esquema de axioma único de${\displaystyle {\mathcal {FS'}}}$es:

"${\displaystyle \blacksquare \ \bigstar \ast \blacklozenge \ \blacksquare \ast }$" (dónde "${\displaystyle \ast }$" es una variable metasintáctica que representa una cadena finita de "${\displaystyle \blacksquare }$"s )

Una demostración formal puede construirse de la siguiente manera:

1. ${\displaystyle \blacksquare \ \bigstar \ \blacksquare \ \blacklozenge \ \blacksquare \ \blacksquare }$
2. ${\displaystyle \blacksquare \ \bigstar \ \blacksquare \ \blacksquare \ \blacklozenge \ \blacksquare \ \blacksquare \ \blacksquare }$
3. ${\displaystyle \blacksquare \ \bigstar \ \blacksquare \ \blacksquare \ \blacksquare \ \blacklozenge \ \blacksquare \ \blacksquare \ \blacksquare \ \blacksquare }$

En este ejemplo el teorema producido "${\displaystyle \blacksquare \ \bigstar \ \blacksquare \ \blacksquare \ \blacksquare \ \blacklozenge \ \blacksquare \ \blacksquare \ \blacksquare \ \blacksquare }$" puede interpretarse como "Uno más tres es igual a cuatro". Otra interpretación sería leerlo al revés como "Cuatro menos tres es igual a uno". ^{[ 9 ]}