Tautología (lógica)

En la lógica matemática, A Tautology (del griego antiguo: ταυτολογία ) es una fórmula o afirmación que es verdad en todas las interpretaciones posibles. Un ejemplo es " x = y o x ≠ y ". Del mismo modo, " 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 redundancias de 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 satisfactable si es verdadera bajo al menos una interpretación, y por lo tanto una tautología es una fórmula cuya negación es insatisfactoria. En otras palabras, no puede ser falso.

declaraciones insatisfactorias, tanto a través de la negación como a la afirmación, se conocen formalmente como contradicciones. Se dice que una fórmula que no es una tautología ni una contradicción es lógicamente contingente. Dicha fórmula puede hacerse verdadera o falsa en función de los valores asignados a sus variables proposicionales.

La doble notación volttil ${\displaystyle \vDash S}$ se utiliza para indicar que S es una tautología. La Tautología es a veces simbolizada por "Vpq", y contradicción por "Opq". El símbolo tee ${\displaystyle \top }$ a veces se utiliza para denotar una tautología arbitraria, con el doble símbolo ${\displaystyle \bot }$ (falso) representando una contradicción arbitraria; en cualquier simbolismo, una tautología puede ser sustituida por el valor de la verdad "verdad", como simbolizado, por ejemplo, por "1".

Las tautologías son un concepto clave en la 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. Una propiedad clave de las tautologías en la lógica proposicional es que existe un método efectivo para probar si una fórmula determinada siempre está satisfecha (equiv., Si su negación es insatisfactoria).

La definición de tautología puede extenderse a las oraciones en la lógica de predicado, que puede contener cuantificadores, una característica ausente de las oraciones de lógica proposicional. De hecho, en la 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 predicado, 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 adecuado del conjunto de oraciones lógicamente válidas de lógica de predicado (es decir, oraciones que son verdaderas en cada modelo).

La palabra tautología fue utilizada por los antiguos griegos para describir una afirmación que se consideraba verdadera por el mero hecho de decir lo mismo dos veces, un significado peyorativo que todavía se utiliza para las 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 un 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 los conceptos en los juicios analíticos puede ser explícita ()explicita) o no explícito ()implicita). En el caso anterior las proposiciones analíticas son tautológica.

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

En 1884, Gottlob Frege propuso en sus Grundlagen que una verdad es analítica exactamente si puede ser derivada mediante la lógica. Sin embargo, mantuvo una distinción entre verdades analíticas (es decir, verdades basadas únicamente en los significados de sus términos) y tautologías (es decir, enunciados carentes de contenido).

En su Tractatus Logico-Philosophicus de 1921, Ludwig Wittgenstein propuso que los enunciados que pueden deducirse por deducción lógica son tautológicos (vacíos de significado), además de ser verdades analíticas. Henri Poincaré había hecho observaciones similares en Ciencia e hipótesis en 1905. Aunque Bertrand Russell inicialmente argumentó en contra de estas observaciones de Wittgenstein y Poincaré, afirmando que las verdades matemáticas no sólo no eran tautológicas sino que eran sintéticas, más tarde se pronunció a favor de ellas en 1918:

Todo lo que es una proposición de la lógica tiene que ser en algún sentido o el otro como una tautología. Tiene que ser algo que tiene una cualidad peculiar, que no sé definir, que pertenece a proposiciones lógicas pero no a otros.

Aquí, 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 libros tempranos sobre lógica (como Symbolic Logic de C. I. 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 (como Stephen Kleene 1967 y Herbert Enderton 2002) utilizar tautología para referirse a una fórmula proposicional lógicamente válida, pero manteniendo una distinción entre "tautología" y "lógicamente válida". en el contexto de la lógica de primer orden (ver más abajo).

La lógica proposicional comienza con variables proposición, unidades atómicas que representan proposiciones concretas. A fórmula consiste en variables proposicionales conectadas por conectores lógicos, construidas de tal manera que la verdad de la fórmula general se puede deducir de la verdad o falsedad de cada variable. A Valoración es una función que asigna cada variable proposición a T (para la verdad) o F (para la falsedad). Así que utilizando las variables proposición A y B, los conectores binarios ${\displaystyle \lor }$ y ${\displaystyle \land }$ representando la disyunción y la conjunción respectivamente, y el ${\displaystyle \lnot }$ representando la negación, se puede obtener la siguiente fórmula:${\displaystyle (A\land B)\lor (\lnot A)\lor (\lnot B)}$.

Una valoración aquí debe asignar a cada una de las A y B T o F. Pero no importa cómo se haga esta asignación, la fórmula general se hará realidad. Por si el primer disyunto ${\displaystyle (A\land B)}$ no está satisfecho por una valoración particular, entonces A o B debe ser asignado F, que hará que uno de los siguientes disyuntos para ser asignado T. En lenguaje natural, tanto A como B son verdaderos o al menos uno de ellos es falso.

Una fórmula de lógica proposicional es una tautología si la fórmula en sí es siempre verdadera, independientemente de la valoración que se utilice para las variables proposicionales. Hay infinitas tautologías. Algunos ejemplos son:

• ${\displaystyle (A\lor \lnot A)}$ (""A o no A"), la ley del centro excluido. Esta fórmula sólo tiene una variable proposicional, A. Cualquier valoración de esta fórmula debe, por definición, asignar A uno de los valores de la verdad verdadero o falso, y asignar ${\displaystyle \lnot }$A el otro valor de verdad. Por ejemplo, "El gato es negro o el gato no es negro".
• ${\displaystyle (A\to B)\Leftrightarrow (\lnot B\to \lnot A)}$ ("si" A implicación BEntonces no...B implica no-A", y viceversa), que expresa la ley de la contraposición. Por ejemplo, "Si es un libro, es azul; si no es azul, no es un libro" y viceversa.
• ${\displaystyle (\lnot A\to B)\land (\lnot A\to \lnot B)\to A}$ ("si no...A implica que B y su negación no-BEntonces no...A debe ser falso, entonces A debe ser verdad"), 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, así que es azul".
• ${\displaystyle \lnot (A\land B)\Leftrightarrow (\lnot A\lor \lnot B)}$ "si no ambos A y BEntonces no...A o no...B", y viceversa), que se conoce como la ley de De Morgan. "Si no es azul y un libro, entonces no es un libro o no es azul" y viceversa.
• ${\displaystyle (A\to B)\land (B\to C))\to (A\to C)}$ ("si" A implicación B y B implicación CEntonces A implicación C"), que es el principio conocido como el silogismo hipotético. "Si es un libro, entonces es azul y si es azul, entonces está en ese estante, entonces 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 verdad, y cada uno implica CEntonces C debe ser verdad también"), que es el principio conocido como prueba por los 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 la instancia de una tautología más breve.

• ${\displaystyle (A\lor B)\to (A\lor B)}$ es una tautología, pero no una mínima, porque es una instantánea ${\displaystyle C\to C}$.

El problema de determinar si una fórmula es una tautología es fundamental en la lógica proposicional. Si hay n variables presentes 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 hay que 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 valor hace que la fórmula sea verdadera es hacer una tabla de verdad que incluya todas las posibles valoraciones.

Por ejemplo, considere la fórmula

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

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

⁠${\displaystyle A}$⁠	⁠${\displaystyle B}$⁠	⁠${\displaystyle C}$⁠	${\displaystyle A\land B}$	${\displaystyle (A\land B)\to C}$	${\displaystyle B\to C}$	${\displaystyle A\to (B\to C)}$	${\displaystyle (A\land B)\to C)\Leftrightarrow (A\to (B\to C)}$
T	T	T	T	T	T	T	T
T	T	F	T	F	F	F	T
T	F	T	F	T	T	T	T
T	F	F	F	T	T	T	T
F	T	T	F	T	T	T	T
F	T	F	F	T	F	T	T
F	F	T	F	T	T	T	T
F	F	F	F	T	T	T	T

Como cada fila de la última columna 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 (véase 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, lo que rápidamente se vuelve inviable a medida que n aumenta). También se requieren sistemas de prueba 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 tercio excluido.

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

Por ejemplo, vamos ${\displaystyle S.$ Ser ${\displaystyle A\land (B\lor \lnot B)}$. Entonces... ${\displaystyle S.$ no es una tautología, porque cualquier valoración que haga ${\displaystyle A}$ falsa voluntad ${\displaystyle S.$ falso. Pero cualquier valoración que haga ${\displaystyle A}$ verdadera voluntad ${\displaystyle S.$ verdadero, porque ${\displaystyle B\lor \lnot B}$ es una tautología. Vamos. ${\displaystyle R.$ ser la fórmula ${\displaystyle A\land C}$. Entonces... ${\displaystyle R\models S}$, porque cualquier valoración satisfactoria ${\displaystyle R.$ hará ${\displaystyle A}$ verdadero, y así hace ${\displaystyle S.$ Cierto.

De la definición se desprende que si una fórmula ${\displaystyle R.$ es una contradicción, entonces ${\displaystyle R.$ tautológicamente implica cada fórmula, porque no hay valoración de la verdad que causa ${\displaystyle R.$ para ser verdad, y por lo tanto la definición de implicación tautológica es trivialmente satisfecha. Del mismo modo, si ${\displaystyle S.$ es una tautología, entonces ${\displaystyle S.$ es tautológicamente implicado por cada fórmula.

Existe un procedimiento general, la regla de sustitución, que permite construir tautologías adicionales a partir de una tautología dada (Kleene 1967 sec. 3). Supongamos que S es una tautología y que 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}$.

Vamos. S_A Ser ${\displaystyle C\lor D}$ y dejar S_B Ser ${\displaystyle C\to E}$.

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

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

también es una tautología.

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.

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

El método de las tablas de verdad ilustrado anteriormente es demostrablemente correcto: la tabla de verdad para una tautología terminará en una columna con solo T, mientras que la tabla de verdad para una oración que no es una tautología contendrá una fila cuya columna final es F, y la valoración correspondiente a esa fila es una valoración que no satisface la oración que se está probando. Este método para verificar tautologías es un procedimiento efectivo, 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 o contable fijo 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 se deben verificar aumenta en 2^k, donde k es el número de variables en la fórmula. Este crecimiento exponencial en la longitud 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 actual no puede ejecutar el algoritmo en un período de tiempo factible.

El problema de determinar si hay alguna valoración que haga realidad una fórmula es el problema de satisfiabilidad booleana; el problema de comprobar las tautologías es equivalente a este problema, porque verificar que una frase S es una tautología equivalente a verificar que no hay valoración satisfactoria ${\displaystyle \lnot S}$. The Boolean satisfiability problem is NP-complete, and consequently, tautology is co-NP-complete. Se cree ampliamente que (equivalentemente para todos los problemas completos de NP) ningún algoritmo polinomio-tiempo puede resolver el problema de satisfiabilidad, aunque algunos algoritmos funcionan bien en clases especiales de fórmulas, o terminar rápidamente en muchos casos.

La definición fundamental de una tautología se encuentra en el contexto de la lógica proposicional. Sin embargo, la definición se puede extender a las oraciones de lógica de primer orden. 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 las valideces lógicas, oraciones que son verdaderas en todos los modelos, y las tautologías (o, valideces tautológicas), que son un subconjunto propio de las validez lógicas de primer orden. En el contexto de la lógica proposicional, estos dos términos coinciden.

Una tautología en la lógica de primer orden es una frase 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). Por ejemplo, porque ${\displaystyle A\lor \lnot A}$ es una tautología de la lógica proposicional, ${\displaystyle (\forall x(x=x))\lor (\lnot \forall x(x=x)}$ es una tautología en primera orden lógica. Del mismo modo, en un idioma de primer orden con símbolos de relación no deseados R,S,T, la siguiente frase es una tautología:

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

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

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

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

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

• Forma normal algebraica
• Forma normal conjuntiva
• Forma normal disjuntiva
• Optimización logística

• Bocheński, J. M. (1959) Précis de Mathematical Logic, traducido de las ediciones francesa y alemana por Otto Bird, Dordrecht, Holanda del Sur: D. Reidel.
• Enderton, H. B. (2002) A Mathematical Introduction to Logic, Harcourt/Academic Press, ISBN 0-12-238452-0.
• Kleene, S. C. (1967) Lógica Matemática, reimpresión 2002, Dover Publications, ISBN 0-486-42533-9.
• Reichenbach, H. (1947). Elementos de la lógica simbólica, reimpreso de 1980, Dover, ISBN 0-486-24004-5
• Wittgenstein, L. (1921). "Logisch-philosophiche Abhandlung", Annalen der Naturphilosophie (Leipzig), v. 14, págs. 185 a 262, reimpreso en traducción al inglés Tractatus logico-philosoficus, Nueva York y Londres, 1922.

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