Una interpretación es una asignación de significado a los símbolos de un lenguaje formal . Muchos lenguajes formales utilizados en matemáticas , lógica e informática teórica se definen en términos exclusivamente sintácticos y, como tales, no tienen ningún significado hasta que se les da alguna interpretación. El estudio general de las interpretaciones de los lenguajes formales se denomina semántica formal .
Las lógicas formales que se estudian con más frecuencia son la lógica proposicional , la lógica de predicados y sus análogos modales , y para estas existen formas estándar de presentar una interpretación. En estos contextos, una interpretación es una función que proporciona la extensión de símbolos y cadenas de símbolos de un lenguaje objeto. Por ejemplo, una función de interpretación podría tomar el predicado T (para "alto") y asignarle la extensión { a } (para "Abraham Lincoln"). Todo lo que hace nuestra interpretación es asignar la extensión { a } a la constante no lógica T , y no hace una afirmación sobre si T debe representar alto y 'a' a Abraham Lincoln. La interpretación lógica tampoco tiene nada que decir sobre conectivos lógicos como 'y', 'o' y 'no'. Aunque podemos tomar estos símbolos para representar ciertas cosas o conceptos, esto no está determinado por la función de interpretación.
Una interpretación a menudo (pero no siempre) proporciona una manera de determinar los valores de verdad de las oraciones en un idioma. Si una interpretación dada asigna el valor Verdadero a una oración o teoría , la interpretación se denomina modelo de esa oración o teoría.
Un lenguaje formal consiste en un conjunto posiblemente infinito de oraciones (llamadas de diversas formas palabras o fórmulas ) construidas a partir de un conjunto fijo de letras o símbolos . El inventario del que se toman estas letras se llama alfabeto sobre el cual se define el lenguaje. Para distinguir las cadenas de símbolos que están en un lenguaje formal de las cadenas arbitrarias de símbolos, las primeras a veces se denominan fórmulas bien formadas (fbf). La característica esencial de un lenguaje formal es que su sintaxis se puede definir sin referencia a la interpretación. Por ejemplo, podemos determinar que ( P o Q ) es una fórmula bien formada incluso sin saber si es verdadera o falsa.
Un lenguaje formal se puede definir con el alfabeto y con una palabra que está en si comienza con y está compuesta únicamente por los símbolos y .
Una posible interpretación de podría asignar el dígito decimal '1' a y '0' a . Entonces denotaría 101 bajo esta interpretación de .
En los casos específicos de la lógica proposicional y la lógica de predicados, los lenguajes formales considerados tienen alfabetos que se dividen en dos conjuntos: los símbolos lógicos ( constantes lógicas ) y los símbolos no lógicos. La idea detrás de esta terminología es que los símbolos lógicos tienen el mismo significado independientemente del tema de estudio, mientras que los símbolos no lógicos cambian de significado dependiendo del área de investigación.
Las constantes lógicas siempre reciben el mismo significado en todas las interpretaciones del tipo estándar, de modo que solo se modifican los significados de los símbolos no lógicos. Las constantes lógicas incluyen los símbolos cuantificadores ∀ ("todos") y ∃ ("algunos"), los símbolos para conectivos lógicos ∧ ("y"), ∨ ("o"), ¬ ("no"), los paréntesis y otros símbolos de agrupación y (en muchos tratamientos) el símbolo de igualdad =.
Muchas de las interpretaciones que se estudian habitualmente asocian cada oración en un lenguaje formal con un único valor de verdad, ya sea Verdadero o Falso. Estas interpretaciones se denominan funciones de la verdad ; [ dudosas – discutir ] incluyen las interpretaciones habituales de la lógica proposicional y de primer orden. Se dice que las oraciones que se vuelven verdaderas mediante una asignación particular se satisfacen mediante esa asignación.
En la lógica clásica , ninguna oración puede volverse verdadera y falsa a la vez por la misma interpretación, aunque esto no es cierto en el caso de lógicas de saturación como la LP. [1] Sin embargo, incluso en la lógica clásica, es posible que el valor de verdad de la misma oración pueda ser diferente bajo diferentes interpretaciones. Una oración es consistente si es verdadera bajo al menos una interpretación; de lo contrario, es inconsistente . Se dice que una oración φ es lógicamente válida si se satisface con cada interpretación (si φ se satisface con cada interpretación que satisface ψ, entonces se dice que φ es una consecuencia lógica de ψ).
Algunos de los símbolos lógicos de un lenguaje (además 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 valores de verdad de oraciones).
Los conectores veritativo-funcionales permiten construir oraciones compuestas a partir de oraciones más simples. De esta manera, el valor de verdad de la oración compuesta se define como una determinada función de verdad de los valores de verdad de las oraciones más simples. Los conectores se suelen considerar constantes lógicas , lo que significa que el significado de los conectores es siempre el mismo, independientemente de las interpretaciones que se den a los demás símbolos de una fórmula.
Así es como definimos los conectivos lógicos en la lógica proposicional:
De modo que, 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 de la oración), podemos determinar los valores de verdad de todas las fórmulas que las tienen como constituyentes, como una función de los conectores lógicos. La siguiente tabla muestra cómo se ve este tipo de cosas. Las primeras dos columnas muestran los valores de verdad de las letras de la oración según lo determinado por las cuatro interpretaciones posibles. Las otras columnas muestran los valores de verdad de las fórmulas construidas a partir de estas letras de la oración, con valores de verdad determinados recursivamente.
Ahora es más fácil ver qué hace que una fórmula sea lógicamente válida. Tomemos la fórmula F : (Φ ∨ ¬Φ). Si nuestra función de interpretación hace que Φ sea verdadera, entonces ¬Φ se vuelve falsa por la conectiva de negación. Como el disyunto Φ de F es verdadero bajo esa interpretación, F es verdadero. Ahora bien, la única otra interpretación posible de Φ lo hace falso y, si es así, ¬Φ se vuelve verdadera por la función de negación. Eso haría que F fuera verdadera de nuevo, ya que uno de los disyuntos de F , ¬Φ, sería verdadero bajo esta interpretación. Como estas dos interpretaciones para F son las únicas interpretaciones lógicas posibles, y como F resulta verdadero para ambas, decimos que es lógicamente válida o tautológica.
Una interpretación de una teoría es la relación entre una teoría y un tema en cuestión cuando existe una correspondencia de varios a uno entre ciertos enunciados elementales de la teoría y ciertos enunciados relacionados con el tema en cuestión. Si cada enunciado elemental de la teoría tiene un correspondiente, se denomina interpretación completa ; de lo contrario, se denomina interpretación parcial . [2]
El lenguaje formal de la lógica proposicional consiste en fórmulas construidas a partir de símbolos proposicionales (también llamados símbolos oracionales, variables oracionales, variables proposicionales ) y conectores lógicos. Los únicos símbolos no lógicos en un lenguaje formal de lógica proposicional son los símbolos proposicionales, que a menudo se denotan con letras mayúsculas. Para que el lenguaje formal sea preciso, se debe fijar un conjunto específico de símbolos proposicionales.
El tipo estándar de interpretación en este contexto es una función que asigna cada símbolo proposicional a uno de los valores de verdad verdadero y falso. Esta función se conoce como función de asignación o valoración de verdad . En muchas presentaciones, se asigna literalmente un valor de verdad, pero algunas presentaciones asignan portadores de verdad en su lugar.
Para un lenguaje con n variables proposicionales distintas, hay 2 n interpretaciones posibles distintas. Para cualquier variable particular a , por ejemplo, hay 2 1 = 2 interpretaciones posibles: 1) a a se le asigna T , o 2) a a se le asigna F . Para el par a , b hay 2 2 = 4 interpretaciones posibles: 1) a ambas se les asigna T , 2) a ambas se les asigna F , 3) a a se le asigna T y b se le asigna F , o 4) a a se le asigna F y b se le asigna T .
Dada cualquier asignación de verdad para un conjunto de símbolos proposicionales, existe una extensión única de una interpretación para todas las fórmulas proposicionales construidas a partir de esas variables. Esta interpretación extendida se define inductivamente, utilizando las definiciones de la tabla de verdad de los conectivos lógicos discutidos anteriormente.
A diferencia de la lógica proposicional, donde todos los lenguajes son iguales, salvo por la elección de un conjunto diferente de variables proposicionales, existen muchos lenguajes de primer orden diferentes. Cada lenguaje de primer orden se define mediante una firma . La firma consiste en un conjunto de símbolos no lógicos y una identificación de cada uno de estos símbolos como un símbolo de constante, un símbolo de función o un símbolo de predicado . En el caso de los símbolos de función y predicado, también se asigna una aridad de número natural . El alfabeto para el lenguaje formal consiste en constantes lógicas, el símbolo de relación de igualdad =, todos los símbolos de la firma y un conjunto infinito adicional de símbolos conocidos como variables.
Por ejemplo, en el lenguaje de los anillos , hay símbolos constantes 0 y 1, dos símbolos de funciones binarias + y ·, y ningún símbolo de relación binaria. (Aquí la relación de igualdad se toma como una constante lógica).
Nuevamente, podríamos definir un lenguaje de primer orden L , como compuesto de símbolos individuales a, b y c; símbolos de predicado F, G, H, I y J; variables x, y, z; ninguna letra de función; ningún símbolo oracional.
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 la dirección opuesta: 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 (ver 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 cuantificadores.
Para atribuir significado a todas las oraciones de un lenguaje de primer orden, se necesita la siguiente información.
Un objeto que lleva esta información se conoce como estructura (de firma σ), o σ-estructura, o L -estructura (de lenguaje L), o como "modelo".
La información especificada en la interpretación proporciona suficiente información para dar 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 de manera inductiva utilizando el esquema T , que es una definición de semántica de primer orden desarrollada por Alfred Tarski. El esquema T interpreta los conectivos lógicos utilizando tablas de verdad, como se discutió anteriormente. Así, por ejemplo, φ ∧ ψ se satisface si y solo si se satisfacen tanto φ como ψ.
Esto deja la cuestión de cómo interpretar fórmulas de la forma ∀ x φ( x ) y ∃ x φ( x ) . El dominio del discurso forma el rango para 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 es reemplazado por algún elemento del dominio. La fórmula ∃ x φ( x ) se satisface si hay 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 manejar este problema técnico. La primera es pasar a un lenguaje más grande en el que cada elemento del dominio se nombra con un símbolo constante. La segunda es agregar a la interpretación una función que asigna cada variable a un elemento del dominio. Entonces el esquema T puede cuantificar sobre variaciones de la interpretación original en las que se cambia esta función de asignación de variable, en lugar de cuantificar sobre instancias de sustitución.
Algunos autores también admiten variables proposicionales en la lógica de primer orden, que luego también deben ser interpretadas. Una variable proposicional puede valerse 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. [4]
Dado que las interpretaciones de primer orden descritas aquí están definidas en la teoría de conjuntos , no asocian cada símbolo de predicado con una propiedad [5] (o relación), sino con la extensión de esa propiedad (o relación). En otras palabras, estas interpretaciones de primer orden son extensionales [6], no intensionales .
Un ejemplo de interpretación del lenguaje L descrito anteriormente es el siguiente.
En la interpretación de L:
Como se ha indicado anteriormente, normalmente se requiere una interpretación de primer orden para especificar un conjunto no vacío como dominio del discurso. La razón de este requisito es garantizar que las equivalencias, como cuando x no es una variable libre de φ, sean 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 falla en cualquier estructura con un dominio vacío. Por lo tanto, la teoría de la prueba de la lógica de primer orden se vuelve más complicada cuando se permiten estructuras vacías. Sin embargo, la ganancia de permitirlas es insignificante, ya que tanto las interpretaciones previstas como las interpretaciones interesantes de las teorías que la gente estudia tienen dominios no vacíos. [7] [8]
Las relaciones vacías no causan ningún problema para las interpretaciones de primer orden, porque no existe una noción similar de pasar un símbolo de relación a través de un conectivo 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 asignar una función bien definida y total al símbolo.
La relación de igualdad suele tratarse de manera 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 algo que no difiere de cualquier otra relación binaria. En este caso, si se incluye un símbolo de igualdad en la signatura, normalmente es necesario añadir varios axiomas sobre la igualdad a los sistemas axiomáticos (por ejemplo, el axioma de sustitución que dice que si a = b y R ( a ) se cumple, entonces R ( b ) también se cumple). Este enfoque de la igualdad es más útil cuando se estudian signaturas que no incluyen la relación de igualdad, como la signatura de la teoría de conjuntos o la signatura de la aritmética de segundo orden en la que solo hay una relación de igualdad para los números, pero no una relación de igualdad para el conjunto 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 ser interpretada por 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 es lo mismo que estudiar solo las interpretaciones que resultan ser modelos normales. La ventaja de este enfoque es que los axiomas relacionados con la igualdad se satisfacen automáticamente por cada modelo normal, por lo que no necesitan incluirse 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 se puede reducir a una interpretación elementalmente equivalente en un subconjunto del dominio original. Por lo tanto, hay poca generalidad adicional en el estudio de modelos no normales. En segundo lugar, si se consideran modelos no normales, entonces 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 establecen 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 variables. La idea es que diferentes 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 de variables tiene un dominio separado para cada uno de los tipos de variables que abarca (existe una colección infinita de variables de cada uno de los diferentes tipos). Los símbolos de función y relación, además de tener aridades, se especifican de modo que cada uno de sus argumentos debe provenir de un tipo determinado.
Un ejemplo de lógica de ordenación múltiple es la geometría euclidiana plana [ aclaración necesaria ] . Hay dos tipos: puntos y líneas. Hay un símbolo de relación de igualdad para puntos, un símbolo de relación de igualdad 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 hace que las variables de punto se extiendan a todos los puntos del plano euclidiano , la variable de línea se extienda a 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á en la línea l .
Un lenguaje formal para la lógica de predicados de orden superior es muy similar a un lenguaje formal para la lógica de primer orden. La diferencia es que ahora hay muchos tipos diferentes de variables. Algunas variables corresponden a elementos del dominio, como en la lógica de primer orden. Otras variables corresponden a objetos de tipo superior: subconjuntos del dominio, funciones del dominio, funciones que toman un subconjunto del dominio y devuelven una función del dominio a subconjuntos del dominio, etc. Todos estos tipos de variables se pueden cuantificar.
Existen dos tipos de interpretaciones que se emplean comúnmente para la lógica de orden superior. La semántica completa requiere que, una vez que se satisface el dominio del discurso, las variables de orden superior abarquen todos los elementos posibles del tipo correcto (todos los subconjuntos del dominio, todas las funciones desde el dominio hasta sí mismo, etc.). Por lo tanto, la especificación de una interpretación completa es la misma que la especificación de una interpretación de primer orden. La semántica de Henkin , que es esencialmente semántica de primer orden multiordenada, requiere que la interpretación especifique un dominio separado para cada tipo de variable de orden superior sobre el que se extenderá. Por lo tanto, una interpretación en la semántica de Henkin incluye un dominio D , una colección de subconjuntos de D , una colección de funciones desde D hasta D , etc. La relación entre estas dos semánticas es un tema importante en la lógica de orden superior.
Las interpretaciones de la lógica proposicional y de la lógica de predicados descritas anteriormente no son las únicas interpretaciones posibles. En particular, existen otros tipos de interpretaciones que se utilizan en el estudio de la lógica no clásica (como la lógica intuicionista ) y en el estudio de la lógica modal.
Las interpretaciones que se utilizan para estudiar la lógica no clásica incluyen los modelos topológicos, los modelos de valores booleanos y los modelos de Kripke . La lógica modal también se estudia utilizando los modelos de Kripke.
Muchos lenguajes formales están asociados a una interpretación particular que se utiliza para motivarlos. Por ejemplo, la signatura de primer orden de la teoría de conjuntos incluye solo una relación binaria, ∈, que pretende representar la pertenencia a un conjunto, y el dominio del discurso en una teoría de primer orden de los números naturales está destinado a ser el conjunto de números naturales.
La interpretación pretendida se llama modelo estándar (un término introducido por Abraham Robinson en 1960). [9] En el contexto de la aritmética de Peano , consiste en los números naturales con sus operaciones aritméticas ordinarias. Todos los modelos que son isomorfos al que se acaba de dar también se denominan estándar; todos estos modelos satisfacen los axiomas de Peano . También existen modelos no estándar de los axiomas de Peano (versión de primer orden de los) , que contienen elementos no correlacionados con ningún número natural.
Si bien la interpretación pretendida no puede tener una indicación explícita en las reglas sintácticas estrictamente formales , naturalmente afecta la elección de las reglas de formación y transformación del sistema sintáctico. Por ejemplo, los signos primitivos deben permitir la expresión de los conceptos que se van a modelar; las fórmulas oracionales se eligen de modo que sus contrapartes en la interpretación pretendida sean oraciones declarativas significativas ; las oraciones primitivas deben resultar como oraciones verdaderas en la interpretación; las reglas de inferencia deben ser tales que, si la oración es directamente derivable de una oración , entonces resulte ser una oración verdadera, con implicación de significado , como es habitual. Estos requisitos aseguran que todas las oraciones demostrables también resulten verdaderas. [10]
La mayoría de los sistemas formales tienen muchos más modelos de los que se pretendía que tuvieran (la existencia de modelos no estándar es un ejemplo). Cuando hablamos de "modelos" en las ciencias empíricas , queremos decir, si queremos que la realidad sea un modelo de nuestra ciencia, que hablemos de un modelo pretendido . Un modelo en las ciencias empíricas es una interpretación descriptiva fácticamente verdadera pretendida (o en otros contextos: una interpretación arbitraria no intencionada que se utiliza para aclarar dicha interpretación descriptiva fácticamente verdadera pretendida). Todos los modelos son interpretaciones que tienen el mismo dominio de discurso que el pretendido, pero otras asignaciones para constantes no lógicas . [11] [ página necesaria ]
Dado un sistema formal simple (que llamaremos a éste ) cuyo alfabeto α consta únicamente de tres símbolos y cuya regla de formación de fórmulas es:
El esquema de axioma único de es:
Una prueba formal se puede construir de la siguiente manera:
En este ejemplo, el teorema que se obtiene " " puede interpretarse como "Uno más tres es igual a cuatro". Una interpretación diferente sería leerlo al revés como "Cuatro menos tres es igual a uno". [12] [ página necesaria ]
Existen otros usos del término “interpretación” que se emplean comúnmente y que no se refieren a la asignación de significados a los lenguajes formales.
En la teoría de modelos , se dice que una estructura A interpreta una estructura B si existe un subconjunto definible D de A y relaciones y funciones definibles en D , de modo que B es isomorfo a la estructura con dominio D y estas funciones y relaciones. En algunos contextos, no se utiliza el dominio D , sino D módulo una relación de equivalencia definible en A. Para obtener información adicional, consulte Interpretación (teoría de modelos) .
Se dice que una teoría T interpreta otra teoría S si existe una extensión finita por definiciones T ′ de T tal que S está contenido en T ′.
![{\displaystyle [\para todo y(y=y)\lo \existe x(x=x)]\equiv \existe x[\para todo y(y=y)\lo \existe x=x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1103d5e6440cb56fa1c1cfeb394b2f4306fc9ae3)
