Tautologia

Tautologia (lógica)

Origem: Wikipédia, a enciclopédia livre.

Na lógica proposicional, uma tautologia (do grego ταυτολογία) é uma fórmula proposicional que é verdadeira para todas as possíveis valorações de suas variáveis proposicionais. Por exemplo, a fórmula proposicional [pic 1]("A ou não-A") é uma tautologia, porque é verdadeira para todas as valorações de A. Existem exemplos mais complexos tais como [pic 2]("A e B; ou não-A; ou não-B"). O primeiro a usar o termo lógica proposicional foi o filósofo Ludwig Wittgenstein em 1921.

A negação de uma tautologia é uma contradição ou antilogia, uma fórmula proposicional que é falsa independentemente dos valores de verdade de suas variáveis. Tais proposições são ditas insatísfatíveis. Reciprocamente, a negação de uma contradição é uma tautologia. Uma fórmula que não é nem uma tautologia nem uma contradição é dita logicamente contingente. Tal fórmula pode ser verdadeira ou falsa dependendo dos valores atribuídos para suas variáveis proposicionais.

Uma propriedade fundamental das tautologias é que existe um procedimento efetivo para testar se uma dada fórmula é sempre satisfeita (ou, equivalentemente, se seu complemento é insatisfatível). Um método deste tipo usa as tabelas-verdade. O problema de decisão de determinar se uma fórmula é satisfatível é o problema de satisfabilidade booleano, um exemplo importante de um problema NP-completo na teoria da complexidade computacional.

A notação [pic 3]é usada para indicar que S é uma tautologia. O símbolo [pic 4]é algumas vezes usado para denotar uma tautologia arbitrária, com o símbolo dual [pic 5](falsum) representando uma contradição arbitrária.

Índice

• 1 História
• 2 Fundamentação teórica
• 3 Definição e exemplos
• 4 Verificando tautologias
• 5 Implicação tautológica
• 6 Substituição
• 7 Verificação eficiente e o problema da satisfabilidade booleana
• 8 Tautologias versus validades na lógica de primeira ordem
• 9 Referências
• 10 Ver também 

• 10.1 Formas normais
• 10.2 Tópicos relacionados à lógica

História

A palavra tautologia foi usada na Grécia antiga para descrever um enunciado que era verdadeiro meramente pelo fato de dizer a mesma coisa duas vezes, um significado pejorativo que ainda é usado para tautologias retóricas. Entre 1800 e 1940, a palavra ganhou novo significado na lógica, e é corriqueiramente usada para denotar um certo tipo de fórmula proposicional, sem as conotações pejorativas que possuía anteriormente.

Durante a década de 30, a formalização da semântica da lógica proposicional em termos de valores verdade foi desenvolvida. O termo tautologia começou a ser aplicado a fórmulas proposicionais que são verdadeiras independente da verdade ou falsidade de suas variáveis proposicionais. Alguns livros sobre lógica (tais como Symbolic Logic de Lewis e Langford, 1932) usaram o termo para todas as proposições (em toda a lógica formal) que são universalmente válidas. É comum em publicações após esta (tais como Kleene 1967 e Ederton 2002) usar o termo tautologia para referir-se a uma fórmula proposicional logicamente válida, mas manter a distinção entre tautologia e logicamente válida no contexto da lógica de primeira ordem.

Fundamentação teórica

A lógica proposicional começa com variáveis proposicionais, unidades atômicas que representam proposições concretas. Uma fórmula consiste de variáveis proposicionais conectadas através de conectivos lógicos em uma forma a fazer sentido, de tal modo que a fórmula inteira pode ser deduzida unicamente da verdade ou falsidade de cada variável. Uma valoração é uma função que atribui para cada variável proposicional V (para verdadeiro) ou F (para falso). Por exemplo, usando as variáveis proposicionais A e B, os conectivos binários [pic 6]e [pic 7]representando disjunção e conjunção, respectivamente, e o conectivo unário [pic 8]representando negação, a seguinte fórmula pode ser obtida:

[pic 9].

Uma valoração aqui deve atribuir para cada A e B um dos valores V ou F. Mas não importa como a atribuição é feita, a fórmula como um todo se tornará verdadeira. De fato se o primeiro disjunto [pic 10]não for satisfeito por uma valoração particular, então para uma das variáveis A ou B é atribuído F, o que fará com que algum dos outros dois disjuntos seja V.

Definição e exemplos

Uma fórmula da lógica proposicional é uma tautologia se a fórmula é sempre verdadeira independentemente de qual valoração seja usada para as variáveis proposicionais.

Existem infinitas tautologias. Alguns exemplos.

• [pic 11]("P ou não-P"), a lei do terceiro excluído. Esta fórmula tem somente uma variável proposicional , P. Qualquer valoração para esta fórmula deve, por definição, atribuir um dos valores de verdade verdadeiro ou falso para P, e atribuir o valor de verdade restante para [pic 12]P (isto é, se P é verdadeiro, então [pic 13]P é falso, e se P é falso, então [pic 14]P é verdadeiro).

• [pic 15]("se A implica B então não-B implica não-A", e vice-versa), o qual expressa a lei da contraposição.

Verificando tautologias

O problema de se determinar se uma fórmula é uma tautologia é fundamental na lógica proposicional. A definição sugere um método: proceda por casos e verifique que todas as valorações possíveis satisfazem a fórmula. Um método algorítmico que verifica que toda valoração faz com que a fórmula em questão seja verdadeira, é fazer uma tabela de verdade, que inclui todos as possíveis valorações. Por exemplo, considere a fórmula:

[pic 16]