Tautología (lógica)

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

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 , y solo las constantes lógicas tienen un significado fijo. Por ejemplo, una fórmula que dice "la pelota es verde o la pelota no es verde" siempre es verdadera, independientemente de qué sea una pelota y de su color. La tautología se usa habitualmente, 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 afirmaciones insatisfactorias, 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 ser 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 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 al valor de verdad " true ", como se simboliza, por ejemplo, con "1". ^[1] ${\displaystyle \vDash S}$ ${\displaystyle \top }$ ${\displaystyle \bot }$

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 probar si una fórmula dada siempre se satisface (equiv., si su negación es insatisfacible).

La definición de tautología se puede extender a las oraciones de 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 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 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 cada modelo ).

Historia

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 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 declaració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 deducirse 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 solo 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 un sentido u otro, como una tautología. Tiene que ser algo que tenga alguna cualidad peculiar, que no sé cómo definir, que pertenece a las proposiciones lógicas pero no a otras.

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

Muchos lógicos de principios del siglo XX utilizaron el término «tautología» para designar cualquier fórmula que sea válida universalmente, ya sea una fórmula de lógica proposicional o de lógica de predicados . En este sentido amplio, una tautología es una fórmula que es verdadera bajo todas las interpretaciones , o que es lógicamente equivalente a la negación de una contradicción. Tarski y Gödel siguieron este uso y 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 continúan usándolo. ^{[4] [5]}

Los libros de texto modernos suelen restringir el uso de "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 por sustitución. ^{[6] [7]}

Fondo

La lógica proposicional comienza con las variables proposicionales , unidades atómicas que representan proposiciones concretas. Una fórmula consiste en variables proposicionales conectadas por conectivos lógicos, construidos de tal manera que la verdad de la fórmula general se puede deducir de la verdad o falsedad de cada variable. Una valoración es una función que asigna a cada variable proposicional T (para verdad) o F (para falsedad). Entonces, al usar las variables proposicionales A y B , los conectivos binarios y que representan la disyunción y la conjunción respectivamente, y el conectivo unario que representa la 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)}$

En este caso, una valoración debe asignar a cada uno de A y B T o F. Pero, independientemente de cómo se realice esta asignación, la fórmula general resultará verdadera. Porque si la primera disyunción no se satisface con una valoración particular, entonces a A o B se le debe asignar F, lo que hará que a una de las siguientes disyunciones se le asigne T. En lenguaje natural, o bien A y B son verdaderas o al menos una de ellas es falsa. ${\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 verdadera, independientemente de la valoración que se utilice para las variables proposicionales . Hay infinitas tautologías.

En muchos de los ejemplos siguientes, A representa la proposició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 referente específico, el objeto X , corresponde a la proposición "todas las cosas encuadernadas son libros". ${\displaystyle A\to B}$

• ${\displaystyle (A\lor \lnot A)}$(" A o no A "), la ley del tercio excluido . Esta fórmula tiene una sola 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 asignar 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), 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, entonces A debe ser verdadero"), que es el principio conocido como reductio ad absurdum . Por ejemplo, "Si no está encuadernado, sabemos que es un libro, si no está encuadernado, sabemos que tampoco es un libro, por lo que 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 ley de De Morgan . "Si no es a la vez un libro y está encuadernado, entonces estamos seguros de que no es un libro o de 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 debe ser verdadera también"), que es el principio conocido como prueba por casos . "Las cosas encuadernadas y los libros 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 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}$

Verificación de 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 2n ^valores distintos 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 uno de sus valores posibles. 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 cada valor posible. ^[2]

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.

Como 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 (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.

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 hace que S sea verdadera. Esta situación se denota como . 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 haga verdadera hará verdadera, porque es una tautología. Sea la fórmula . Entonces , porque cualquier valoración que satisfaga hará verdadera—y por lo tanto hace 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 desprende que si una fórmula es una contradicción, entonces implica tautológicamente toda fórmula, porque no hay valoración de verdad que haga que sea verdadera, y por tanto la definición de implicación tautológica se satisface trivialmente. De manera similar, si es una tautología, entonces está implicada tautológicamente por toda 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 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}$.

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

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 las oraciones con grandes cantidades 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 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 usar 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 existe alguna valoración que haga que una fórmula sea verdadera es el problema de satisfacibilidad booleano ; 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 satisfaga . El problema de satisfacibilidad booleano es NP-completo y, en consecuencia, la tautología es co-NP-completa . Se cree ampliamente que (equivalentemente 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 muchos casos. ^[8] ${\displaystyle \lnot S}$

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

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 . ^[9] 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 las 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, debido a que es una tautología de lógica proposicional, es una tautología en lógica de primer orden. De manera similar, en un lenguaje de primer orden con una relación unaria de símbolos 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 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 oración proposicional que no es una tautología de la lógica proposicional. ${\displaystyle A\to B}$

Tautologías en lógicas no clásicas

El 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}$

Véase 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. Lewis, CI; Langford, CH (1959). Lógica simbólica (2.ª ed.). Dover.
4. Hedman, Shawn (2004). Un primer curso de lógica . Oxford University Press. pág. 63.
5. Rautenberg, Wolfgang (2010). Una introducción concisa a la lógica matemática . Springer. pág. 64.
6. Enderton, Herbert (2001). Introducción matemática a la lógica . Academic Press. pág. 88.
7. Hinman, Peter (2010). Fundamentos de lógica matemática . Springer. pág. 98.
8. Consulte el solucionador SAT para obtener referencias.
9. "Nuevos miembros". Naval Engineers Journal . 114 (1): 17–18. Enero de 2002. doi :10.1111/j.1559-3584.2002.tb00103.x. ISSN  0028-1425.

Lectura adicional

• Bocheński, JM (1959) Précis of Mathematical Logic , traducido de las ediciones francesa y alemana de 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, 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.

Enlaces externos

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