Tautología (lógica)

En lógica, una afirmación que siempre es cierta.

En lógica matemática , una tautología (del griego : ταυτολογία ) es una fórmula o afirmación que es verdadera en toda interpretación posible . Un ejemplo es "x=y o x≠y". De manera similar, "o la pelota es verde o la pelota no es verde" siempre es cierto, independientemente del color de la pelota.

El filósofo Ludwig Wittgenstein aplicó por primera vez el término a las redundancias de la lógica proposicional en 1921, tomando prestado de la retórica , donde una tautología es una declaración repetitiva. En lógica, una fórmula es satisfactoria si es verdadera bajo al menos una interpretación y, por tanto, una tautología es una fórmula cuya negación es insatisfactoria. En otras palabras, no puede ser falso. No puede ser falso.

Los enunciados insatisfactorios, tanto por negación como por afirmación, se conocen formalmente como contradicciones . Una fórmula que no es ni una tautología ni una contradicción se dice que es lógicamente contingente .

Una fórmula de este tipo puede convertirse en verdadera o falsa en función de los valores asignados a sus variables proposicionales. La notación de doble torniquete se utiliza para indicar que S es una tautología. La tautología a veces se simboliza con "V pq " y la contradicción con "O pq ". El símbolo de la tee se utiliza a veces para denotar una tautología arbitraria, y el símbolo dual ( falsum ) representa una contradicción arbitraria; en cualquier simbolismo, una tautología puede sustituir el valor de verdad " verdadero ", simbolizado, por ejemplo, por "1". ^[1] ${\displaystyle \vDash S}$ ${\displaystyle \top }$ ${\displaystyle \bot }$

Las tautologías son un concepto clave en lógica proposicional , donde una tautología se define como una fórmula proposicional que es verdadera bajo cualquier posible valoración booleana de sus variables proposicionales . ^[2] Una propiedad clave de las tautologías en lógica proposicional es que existe un método eficaz para comprobar si una fórmula dada siempre se cumple (equiv., si su negación es insatisfactoria).

La definición de tautología se puede extender a oraciones en lógica de predicados , que pueden contener cuantificadores , una característica ausente en las oraciones de lógica proposicional. ^[3] De hecho, en lógica proposicional, no hay distinción entre una tautología y una fórmula lógicamente válida . En el contexto de la lógica de predicados, muchos autores definen una tautología como una oración que se puede obtener tomando una tautología de la lógica proposicional y reemplazando uniformemente cada variable proposicional por una fórmula de primer orden (una fórmula por variable proposicional). El conjunto de tales fórmulas es un subconjunto propio del conjunto de oraciones lógicamente válidas de la lógica de predicados (es decir, oraciones que son verdaderas en cada modelo ).

Historia

La palabra tautología fue utilizada por los antiguos griegos para describir una afirmación que se afirmaba como verdadera simplemente por decir lo mismo dos veces, un significado peyorativo que todavía se usa para tautologías retóricas . Entre 1800 y 1940, la palabra adquirió un nuevo significado en lógica, y actualmente se utiliza en lógica matemática para denotar cierto tipo de fórmula proposicional, sin las connotaciones peyorativas que poseía originalmente.

En 1800, Immanuel Kant escribió en su libro Lógica :

La identidad de conceptos en los juicios analíticos puede ser explícita ( explícita ) o no explícita ( implícita ). En el primer caso las proposiciones analíticas son tautológicas.

Aquí, la proposición analítica se refiere a una verdad analítica , una afirmación en lenguaje natural que es verdadera únicamente por los términos involucrados.

En 1884, Gottlob Frege propuso en sus Grundlagen que una verdad es analítica exactamente si puede derivarse utilizando la lógica. Sin embargo, mantuvo una distinción entre verdades analíticas (es decir, verdades basadas únicamente en el significado de sus términos) y tautologías (es decir, declaraciones desprovistas de contenido).

En su Tractatus Logico-Philosophicus de 1921, Ludwig Wittgenstein propuso que los enunciados que pueden deducirse mediante deducción lógica son tautológicos (vacíos de significado), además de ser verdades analíticas. Henri Poincaré había hecho comentarios similares en Science and Hypothesis en 1905. Aunque Bertrand Russell al principio argumentó en contra de estos comentarios de Wittgenstein y Poincaré, afirmando que las verdades matemáticas no sólo no eran tautólogas sino que eran sintéticas , más tarde habló a favor de ellas en 1918. :

Todo lo que es una proposición lógica tiene que ser, en un sentido u otro, como una tautología. Tiene que ser algo que tenga alguna cualidad peculiar, que no sé cómo definir, que pertenezca a las proposiciones lógicas pero no a otras.

Aquí, la proposición lógica se refiere a una proposición que se puede demostrar utilizando las leyes de la lógica.

Durante la década de 1930 se desarrolló la formalización de la semántica de la lógica proposicional en términos de asignaciones de verdad. El término “tautología” comenzó a aplicarse a aquellas fórmulas proposicionales que son verdaderas independientemente de la verdad o falsedad de sus variables proposicionales. Algunos de los primeros libros sobre lógica (como Symbolic Logic de CI Lewis y Langford, 1932) utilizaron el término para cualquier proposición (en cualquier lógica formal) que sea universalmente válida. Es común en presentaciones posteriores a esta (como Stephen Kleene 1967 y Herbert Enderton 2002) usar tautología para referirse a una fórmula proposicional lógicamente válida, pero mantener una distinción entre "tautología" y "lógicamente válida" en el contexto de la primera. Lógica de orden (ver más abajo) .

Fondo

La lógica proposicional comienza con variables proposicionales , unidades atómicas que representan proposiciones concretas. Una fórmula consta de variables proposicionales conectadas por conectivos lógicos, construidas de tal manera que la verdad de la fórmula general puede deducirse de la verdad o falsedad de cada variable. Una valoración es una función que asigna cada variable proposicional a T (para verdad) o F (para falsedad). Entonces, usando las variables proposicionales A y B , los conectivos binarios y que representan disyunción y conjunción respectivamente, y el conectivo unario que representa negación , se puede obtener la siguiente fórmula: . ${\displaystyle \lor }$ ${\displaystyle \land }$ ${\displaystyle \lnot }$ ${\displaystyle (A\land B)\lor (\lnot A)\lor (\lnot B)}$

Una valoración aquí debe asignar a cada uno de A y B T o F. Pero no importa cómo se haga esta asignación, la fórmula general resultará verdadera. Porque si la primera conjunción no se satisface con una valoración particular, entonces a uno de A y B se le asigna F, lo que hará que a uno de los siguientes disyuntos se le asigne T. ${\displaystyle (A\land B)}$

Definición y ejemplos

Una fórmula de lógica proposicional es una tautología si la fórmula en sí es siempre cierta, independientemente de qué valoración se utilice para las variables proposicionales . Hay infinitas tautologías. Ejemplos incluyen:

• ${\displaystyle (A\lor \lnot A)}$(" A o no A "), la ley del tercero excluido . Esta fórmula tiene sólo una variable proposicional , A. Cualquier valoración de esta fórmula debe, por definición, asignar a A uno de los valores de verdad verdadero o falso , y asignarle a A el otro valor de verdad. Por ejemplo, "El gato es negro o el gato no es negro". ${\displaystyle \lnot }$
• ${\displaystyle (A\to B)\Leftrightarrow (\lnot B\to \lnot A)}$("si A implica B , entonces no- B implica no- A ", y viceversa), que expresa la ley de contraposición . Por ejemplo, "Si es un libro, es azul; si no es azul, no es un libro".
• ${\displaystyle ((\lnot A\to B)\land (\lnot A\to \lnot B))\to A}$("si no- A implica tanto B como su negación no- B , entonces no- A debe ser falso, entonces A debe ser verdadero"), que es el principio conocido como reductio ad absurdum . Por ejemplo, "Si no es azul, es un libro, si no es azul, tampoco es un libro, entonces es azul".
• ${\displaystyle \lnot (A\land B)\Leftrightarrow (\lnot A\lor \lnot B)}$("si no son A y B , entonces no A o no B ", y viceversa), que se conoce como ley de De Morgan . "Si no es azul y un libro, entonces o no es un libro o no es azul"
• ${\displaystyle ((A\to B)\land (B\to C))\to (A\to C)}$("si A implica B y B implica C , entonces A implica C "), que es el principio conocido como silogismo . "Si es un libro, entonces es azul y si es azul, entonces está en ese estante, luego, si es un libro, está en ese estante".
• ${\displaystyle ((A\lor B)\land (A\to C)\land (B\to C))\to C}$("si al menos uno de A o B es verdadero, y cada uno implica C , entonces C también debe ser verdadero"), que es el principio conocido como prueba por casos . "Los libros y las cosas azules están en ese estante. Si es un libro o es azul, está en ese estante".

Una tautología mínima es una tautología que no es el ejemplo de una tautología más corta.

• ${\displaystyle (A\lor B)\to (A\lor B)}$Es una tautología, pero no mínima, porque es una instanciación de . ${\displaystyle C\to C}$

Verificando tautologías

El problema de determinar si una fórmula es una tautología es fundamental en la lógica proposicional. Si hay n variables en una fórmula, entonces hay 2 ⁿ valoraciones distintas para la fórmula. Por lo tanto, la tarea de determinar si la fórmula es o no una tautología es finita y mecánica: sólo es necesario evaluar el valor de verdad de la fórmula bajo cada una de sus posibles valoraciones. Un método algorítmico para verificar que cada valoración hace que la fórmula sea verdadera es hacer una tabla de verdad que incluya todas las valoraciones posibles. ^[2]

Por ejemplo, considere la fórmula

${\displaystyle ((A\land B)\to C)\Leftrightarrow (A\to (B\to C)).}$

Existen 8 valoraciones posibles para las variables proposicionales A , B , C , representadas por las tres primeras columnas de la siguiente tabla. Las columnas restantes muestran la verdad de las subfórmulas de la fórmula anterior, culminando en una columna que muestra el valor de verdad de la fórmula original bajo cada valoración.

Debido a que cada fila de la columna final muestra T , se verifica que la oración en cuestión es una tautología.

También es posible definir un sistema deductivo (es decir, un sistema de prueba) para la lógica proposicional, como una variante más simple de los sistemas deductivos empleados para la lógica de primer orden (ver Kleene 1967, Sec 1.9 para uno de esos sistemas). Una prueba de una tautología en un sistema de deducción apropiado puede ser mucho más corta que una tabla de verdad completa (una fórmula con n variables proposicionales requiere una tabla de verdad con 2 ⁿ líneas, que rápidamente se vuelve inviable a medida que n aumenta). Los sistemas de prueba también son necesarios para el estudio de la lógica proposicional intuicionista , en la que no se puede emplear el método de las tablas de verdad porque no se supone la ley del tercero excluido.

Implicación tautológica

Se dice que una fórmula R implica tautológicamente una fórmula S si cada valoración que hace que R sea verdadera también causa que S sea verdadera. Esta situación se denota . Es equivalente a que la fórmula sea una tautología (Kleene 1967 p. 27). ${\displaystyle R\models S}$ ${\displaystyle R\to S}$

Por ejemplo, sea . Entonces no es una tautología, porque cualquier valoración que haga falsa, hará falsa. Pero cualquier valoración que se haga verdadera se hará verdadera, porque es una tautología. Sea la fórmula . Entonces , porque cualquier valoración satisfactoria será verdadera y, por tanto, será verdadera. ${\displaystyle S}$ ${\displaystyle A\land (B\lor \lnot B)}$ ${\displaystyle S}$ ${\displaystyle A}$ ${\displaystyle S}$ ${\displaystyle A}$ ${\displaystyle S}$ ${\displaystyle B\lor \lnot B}$ ${\displaystyle R}$ ${\displaystyle A\land C}$ ${\displaystyle R\models S}$ ${\displaystyle R}$ ${\displaystyle A}$ ${\displaystyle S}$

De la definición se deduce que si una fórmula es una contradicción, entonces tautológicamente implica toda fórmula, porque no existe una valoración de verdad que haga que sea verdadera, por lo que la definición de implicación tautológica se satisface trivialmente. De manera similar, si es una tautología, entonces está tautológicamente implícita en cada fórmula. ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle S}$

Sustitución

Existe un procedimiento general, la regla de sustitución , que permite construir tautologías adicionales a partir de una tautología determinada (Kleene 1967 sec. 3). Supongamos que S es una tautología y para cada variable proposicional A en S se elige una oración fija S _A. Entonces la oración obtenida al reemplazar cada variable A en S con la oración correspondiente S _A también es una tautología.

Por ejemplo, sea S la tautología:

${\displaystyle (A\land B)\lor \lnot A\lor \lnot B}$.

Sean S _A y S B. _{_} _ _ ${\displaystyle C\lor D}$ ${\displaystyle C\to E}$

De la regla de sustitución se deduce que la oración:

${\displaystyle ((C\lor D)\land (C\to E))\lor \lnot (C\lor D)\lor \lnot (C\to E)}$

Completitud y solidez semántica

Un sistema axiomático es completo si cada tautología es un teorema (derivable de axiomas). Un sistema axiomático es sólido si cada teorema es una tautología.

Verificación eficiente y el problema de satisfacibilidad booleana

El problema de construir algoritmos prácticos para determinar si oraciones con un gran número de variables proposicionales son tautologías es un área de investigación contemporánea en el área de la demostración automatizada de teoremas .

El método de las tablas de verdad ilustrado anteriormente es demostrablemente correcto: la tabla de verdad de una tautología terminará en una columna con solo T , mientras que la tabla de verdad de una oración que no es una tautología contendrá una fila cuya columna final es F , y la La valoración correspondiente a esa fila es una valoración que no satisface la frase que se está probando. Este método para verificar tautologías es un procedimiento eficaz , lo que significa que, dados recursos computacionales ilimitados, siempre se puede utilizar para determinar mecánicamente si una oración es una tautología. Esto significa, en particular, que el conjunto de tautologías sobre un alfabeto finito fijo o contable es un conjunto decidible .

Sin embargo, como procedimiento eficiente , las tablas de verdad están limitadas por el hecho de que el número de valoraciones que deben verificarse aumenta a medida que 2 ^k , donde k es el número de variables en la fórmula. Este crecimiento exponencial en la duración del cálculo hace que el método de la tabla de verdad sea inútil para fórmulas con miles de variables proposicionales, ya que el hardware informático contemporáneo no puede ejecutar el algoritmo en un período de tiempo factible.

El problema de determinar si existe alguna valoración que haga verdadera una fórmula es el problema booleano de satisfacibilidad ; El problema de comprobar tautologías es equivalente a este problema, porque verificar que una oración S es una tautología equivale a verificar que no existe ninguna valoración que satisfaga . Se sabe que el problema de satisfacibilidad booleano es NP completo y se cree ampliamente que no existe ningún algoritmo de tiempo polinomial que pueda realizarlo. En consecuencia, la tautología es co-NP-completa . La investigación actual se centra en encontrar algoritmos que funcionen bien en clases especiales de fórmulas o que terminen rápidamente en promedio, aunque algunas entradas puedan hacer que demoren mucho más. ${\displaystyle \lnot S}$

Tautologías versus validez en la lógica de primer orden

La definición fundamental de una tautología se encuentra en el contexto de la lógica proposicional. La definición puede ampliarse, sin embargo, a oraciones en lógica de primer orden . ^[4] Estas oraciones pueden contener cuantificadores, a diferencia de las oraciones de lógica proposicional. En el contexto de la lógica de primer orden, se mantiene una distinción entre validez lógica , oraciones que son verdaderas en cada modelo, y tautologías (o validez tautológica ), que son un subconjunto propio de la validez lógica de primer orden. En el contexto de la lógica proposicional, estos dos términos coinciden.

Una tautología en lógica de primer orden es una oración que se puede obtener tomando una tautología de lógica proposicional y reemplazando uniformemente cada variable proposicional por una fórmula de primer orden (una fórmula por variable proposicional). Por ejemplo, porque es una tautología de la lógica proposicional, es una tautología de la lógica de primer orden. De manera similar, en un lenguaje de primer orden con símbolos de relación unaria R , S , T , la siguiente oración es una tautología: ${\displaystyle A\lor \lnot A}$ ${\displaystyle (\forall x(x=x))\lor (\lnot \forall x(x=x))}$

${\displaystyle (((\exists xRx)\land \lnot (\exists xSx))\to \forall xTx)\Leftrightarrow ((\exists xRx)\to ((\lnot \exists xSx)\to \forall xTx)).}$

Se obtiene reemplazando con , con y con en la tautología proposicional: . ${\displaystyle A}$ ${\displaystyle \exists xRx}$ ${\displaystyle B}$ ${\displaystyle \lnot \exists xSx}$ ${\displaystyle C}$ ${\displaystyle \forall xTx}$ ${\displaystyle ((A\land B)\to C)\Leftrightarrow (A\to (B\to C))}$

No todas las validezes lógicas son tautologías en la lógica de primer orden. Por ejemplo, la frase:

${\displaystyle (\forall xRx)\to \lnot \exists x\lnot Rx}$

es cierto en cualquier interpretación de primer orden, pero corresponde a la oración proposicional que no es una tautología de la lógica proposicional. ${\displaystyle A\to B}$

Ver también

Formas normales

• Forma normal algebraica
• Forma normal conjuntiva
• Forma normal disyuntiva
• Optimización lógica

Temas lógicos relacionados

Referencias

1. Weisstein, Eric W. "Tautología". mathworld.wolfram.com . Consultado el 14 de agosto de 2020 .
2. "tautología | Definición y hechos". Enciclopedia Británica . Consultado el 14 de agosto de 2020 .
3. "Tautología (lógica)". wikipedia.org .
4. "Nuevos miembros". Revista de ingenieros navales . 114 (1): 17-18. Enero de 2002. doi :10.1111/j.1559-3584.2002.tb00103.x. ISSN  0028-1425.

Otras lecturas

• Bocheński, JM (1959) Précis of Mathematical Logic , traducido de las ediciones francesa y alemana por Otto Bird, Dordrecht , Holanda Meridional : D. Reidel .
• Enderton, HB (2002) Una introducción matemática a la lógica , Harcourt / Academic Press , ISBN 0-12-238452-0 . 
• Kleene, SC (1967) Lógica matemática , reimpreso en 2002, Publicaciones de Dover , ISBN 0-486-42533-9 . 
• Reichenbach, H. (1947). Elementos de lógica simbólica , reimpreso en 1980, Dover, ISBN 0-486-24004-5 
• Wittgenstein, L. (1921). "Logisch-philosophiche Abhandlung", Annalen der Naturphilosophie (Leipzig), v. 14, págs. 185-262, reimpreso en traducción al inglés como Tractatus logico-philosophicus , Nueva York y Londres , 1922.

enlaces externos

• "Tautología", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]