Tautología (lógica)

En lógica matemática , una tautología (del griego antiguo : ταυτολογία ) es una fórmula que es verdadera independientemente de la interpretación de sus términos componentes , siendo solo las constantes lógicas las que tienen un significado fijo. Es una verdad lógica . Por ejemplo, una fórmula que afirma "la pelota es verde o la pelota no es verde" siempre es verdadera, independientemente de qué sea una pelota y de su color. El término tautología se usa generalmente, aunque no siempre, para referirse a fórmulas válidas de lógica proposicional .

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 afirmación repetitiva. En lógica, una fórmula es satisfacible si es verdadera bajo al menos una interpretación, y por lo tanto, una tautología es una fórmula cuya negación es insatisfacible. En otras palabras, no puede ser falsa.

Las proposiciones insatisfacibles, 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 denomina lógicamente contingente . Dicha fórmula puede ser verdadera o falsa según los valores asignados a sus variables proposicionales.

La notación del doble torniquete${\displaystyle \vDash S}$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${\displaystyle \top }$a veces se utiliza para denotar una tautología arbitraria, con el símbolo dual${\displaystyle \bot }$( falso ) que representa una contradicción arbitraria; en cualquier simbolismo, una tautología puede sustituir al valor de verdad " verdadero ", como se simboliza, por ejemplo, con "1". ^{[ 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 . ^{[ 2 ]} Una propiedad clave de las tautologías en la lógica proposicional es que existe un método efectivo para comprobar si una fórmula dada siempre se satisface (o, equivalentemente, si su negación es insatisfacible).

La definición de tautología puede extenderse a las oraciones en lógica de predicados , que pueden contener cuantificadores , una característica ausente en las oraciones de lógica proposicional. De hecho, en lógica proposicional no existe 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 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 lógica de predicados (es decir, oraciones que son verdaderas en todo modelo ).

Los antiguos griegos utilizaban el término tautología para describir una afirmación que se consideraba verdadera simplemente por repetirla dos veces; un significado peyorativo que aún se emplea 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 designar un tipo específico de fórmula proposicional, sin las connotaciones peyorativas que originalmente poseía.

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 implícita ( implicita ). En el primer caso, las proposiciones analíticas son tautológicas.

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 precisamente si puede derivarse mediante 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, enunciados sin 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 observaciones similares en Ciencia e Hipótesis en 1905. Si bien Bertrand Russell inicialmente argumentó en contra de estas observaciones de Wittgenstein y Poincaré, afirmando que las verdades matemáticas no solo no eran tautológicas sino sintéticas , posteriormente se pronunció a su favor en 1918.

Todo lo que constituye una proposición lógica debe ser, en cierto sentido, una tautología. Debe poseer alguna cualidad peculiar, que no sé cómo definir, propia de las proposiciones lógicas pero no de las demás.

En este contexto, proposición lógica se refiere a una proposición que puede demostrarse utilizando las leyes de la lógica.

Muchos lógicos de principios del siglo XX utilizaban el término «tautología» para referirse a cualquier fórmula universalmente válida, ya fuera de lógica proposicional o de lógica de predicados . En este sentido amplio, una tautología es una fórmula verdadera bajo todas las interpretaciones , o lógicamente equivalente a la negación de una contradicción. Tarski y Gödel siguieron este uso, que aparece en libros de texto como el de Lewis y Langford. ^{[ 3 ]} Este uso amplio del término es menos común hoy en día, aunque algunos libros de texto lo siguen utilizando. ^{[ 4 ] [ 5 ]}

Los libros de texto modernos suelen restringir el uso de la «tautología» a oraciones válidas de lógica proposicional, o a oraciones válidas de lógica de predicados que pueden reducirse a tautologías proposicionales mediante sustitución. ^{[ 6 ] [ 7 ]}

La lógica proposicional comienza con variables proposicionales , unidades atómicas que representan proposiciones concretas. Una fórmula consta de 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. Una valuación es una función que asigna a cada variable proposicional V (de verdad) o F (de falsedad). Así, utilizando las variables proposicionales A y B , los conectores binarios${\displaystyle \lor }$y${\displaystyle \land }$representando la disyunción y la conjunción respectivamente, y el conector unario${\displaystyle \lnot }$Al representar 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 uno de A y B V o F. Pero no importa cómo se haga esta asignación, la fórmula general resultará verdadera. Porque si el primer disyunto${\displaystyle (A\land B)}$Si no se satisface con una valoración particular, entonces se debe asignar F a A o B , lo que hará que a uno de los siguientes disyuntos se le asigne T. En lenguaje natural, o bien A y 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 misma es siempre verdadera, independientemente de la valoración que se utilice para las variables proposicionales . Existen infinitas tautologías.

En muchos de los siguientes ejemplos, A representa la afirmación "el objeto X está encuadernado", B representa "el objeto X es un libro" y C representa "el objeto X está en el estante". Sin un objeto X de referencia específico ,${\displaystyle A\to B}$ corresponde a la proposición "todas las cosas encuadernadas son libros".

• ${\displaystyle (A\lor \lno A)}$(" A o no A "), la ley del tercero excluido . Esta fórmula tiene solo una variable proposicional, A. Cualquier valoración para esta fórmula debe, por definición, asignar a A uno de los valores de verdad verdadero o falso , y asignar${\displaystyle \lnot }$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 implica B , entonces no B implica no A ", y viceversa), lo que expresa la ley de contraposición . Por ejemplo, "Si está encuadernado, es un libro; si no es un libro, no está encuadernado" y viceversa.
• ${\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, por lo tanto A debe ser verdadero"), que es el principio conocido como reducción al absurdo . Por ejemplo, "Si no está encuadernado, sabemos que es un libro; si no está encuadernado, sabemos que tampoco es un libro, por lo tanto, está encuadernado".
• ${\displaystyle \lnot (A\land B)\Leftrightarrow (\lnot A\lor \lnot B)}$("si no es A y B , entonces no es A o no es B ", y viceversa), lo que se conoce como la ley de De Morgan . "Si no es un libro y no está encuadernado, entonces estamos seguros de que no es un libro o que no está encuadernado", y viceversa.
• ${\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 hipotético . "Si está encuadernado, entonces es un libro y si es un libro, entonces está en ese estante, así que si está encuadernado, está en ese estante".
• ${\displaystyle ((A\lor B)\land (A\to C)\land (B\to C))\to C}$("si al menos una de A o B es verdadera, y cada una implica C , entonces C también debe ser verdadera"), que es el principio conocido como prueba por casos . "Los objetos encuadernados y los libros están en ese estante. Si es un libro o está encuadernado, está en ese estante".

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

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

El problema de determinar si una fórmula es una tautología es fundamental en la lógica proposicional. Si una fórmula contiene n variables, existen 2ⁿ ^valores distintos para dicha fórmula. Por lo tanto, la tarea de determinar si la fórmula es o no una tautología es finita y mecánica: basta con evaluar el valor de verdad de la fórmula bajo cada uno de sus posibles valores. Un método algorítmico para verificar que cada valor hace que la fórmula sea verdadera consiste en crear una tabla de verdad que incluya todos los valores posibles. ^{[ 2 ]}

Por ejemplo, consideremos la fórmula

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

Existen ocho posibles valoraciones para las variables proposicionales A , B y C , representadas por las tres primeras columnas de la siguiente tabla. Las columnas restantes muestran la veracidad 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.

Dado que cada fila de la última columna muestra una 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 demostración) 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 un ejemplo de dicho sistema). Una demostración de una tautología en un sistema deductivo 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ⁿ ^filas , lo cual se vuelve rápidamente inviable a medida que n aumenta). Los sistemas de demostración 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 presupone el principio del tercero excluido.

Se dice que una fórmula R implica tautológicamente una fórmula S si toda valoración que hace que R sea verdadera también hace que S sea verdadera. 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, dejemos${\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}$falso testamento${\displaystyle S}$falso. Pero cualquier valoración que haga${\displaystyle A}$verdadero voluntad hará${\displaystyle S}$cierto, porque${\displaystyle B\lor \lnot B}$es una tautología. Dejemos${\displaystyle R}$ser la fórmula${\displaystyle A\land C}$. Entonces${\displaystyle R\models S}$, porque cualquier valoración que satisfaga${\displaystyle R}$hará${\displaystyle A}$verdadero—y por lo tanto hace${\displaystyle S}$verdadero.

De la definición se deduce que si una fórmula${\displaystyle R}$es una contradicción, entonces${\displaystyle R}$implica tautológicamente cada fórmula, porque no hay valoración de la verdad que cause${\displaystyle R}$para ser cierto, y por lo tanto la definición de implicación tautológica se satisface trivialmente. De manera similar, si${\displaystyle S}$es una tautología, entonces${\displaystyle S}$está implícito tautológicamente en 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, sección 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}$.

Sea S _A​${\displaystyle C\lor D}$y sea S _B${\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)}$

También es una tautología.

Un sistema axiomático es completo si toda tautología es un teorema (derivable de los axiomas). Un sistema axiomático es correcto si todo 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 automatizada de teoremas .

El método de 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 última columna 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 eficaz , lo que significa que, con 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 numerable fijo es un conjunto decidible .

Sin embargo, como procedimiento eficiente , las tablas de verdad se ven limitadas por el hecho de que el número de valoraciones que deben comprobarse aumenta como 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 las tablas 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 tiempo razonable.

El problema de determinar si existe alguna valoración que haga verdadera una fórmula es el problema de satisfacibilidad booleana ; el problema de comprobar tautologías es equivalente a este problema, porque verificar que una oración S es una tautología es equivalente a verificar que no existe ninguna valoración que la satisfaga.${\displaystyle \lnot S}$El problema de satisfacibilidad booleana es NP-completo y, por consiguiente, la tautología es co-NP-completa . Se cree ampliamente que (de forma equivalente para todos los problemas NP-completos) ningún algoritmo de tiempo polinomial puede resolver el problema de satisfacibilidad, aunque algunos algoritmos funcionan bien en clases especiales de fórmulas o terminan rápidamente en muchas instancias. ^{[ 8 ]}

La definición fundamental de tautología se encuentra en el contexto de la lógica proposicional. Sin embargo, esta definición puede extenderse a las oraciones de la lógica de primer orden . ^{[ 9 ]} Estas oraciones pueden contener cuantificadores, a diferencia de las oraciones de la 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 todo modelo, y tautologías (o validez tautológica ), 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 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${\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 lógica de primer orden. De manera similar, en un lenguaje de primer orden con una relación unaria símbolos R , S , T , la siguiente oración 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))}$.

Que una fórmula dada sea una tautología depende del sistema formal de lógica que se utilice. Por ejemplo, la siguiente fórmula es una tautología de la lógica clásica, pero no de la lógica intuicionista :

${\displaystyle \neg \neg A\to A}$

• Bocheński, JM (1959) Précis de lógica matemática , traducido de las ediciones francesa y alemana por Otto Bird, Dordrecht , Holanda Meridional : D. Reidel .
• Enderton, HB (2002) 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, Dover Publications , 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.

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