Tautologia (lógica)
fórmula proposicional verdadeira para todas valorações possíveis de suas variáveis / De Wikipedia, a enciclopédia encyclopedia
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 ("A ou não-A") é uma tautologia, porque é verdadeira para todas as valorações de A. Existem exemplos mais complexos tais como ("A e B; ou não-A; ou não-B"). O primeiro a aplicar o termo tautologia às redundâncias da lógica proposicional foi o filósofo Ludwig Wittgenstein em 1921 (anteriormente era usado exclusivamente na retórica).
Este artigo ou secção contém uma lista de referências no fim do texto, mas as suas fontes não são claras porque não são citadas no corpo do artigo, o que compromete a confiabilidade das informações. (Abril de 2021) |
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 é insatisfazível). Um método deste tipo usa as tabelas-verdade. O problema de decisão de determinar se uma fórmula é satisfazível é o problema de satisfabilidade booleano, um exemplo importante de um problema NP-completo na teoria da complexidade computacional.
A notação é usada para indicar que S é uma tautologia. O símbolo é algumas vezes usado para denotar uma tautologia arbitrária, com o símbolo dual (falsum) representando uma contradição arbitrária.