Tautologia

...

[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]

Existem 8 possíveis valorações para as variáveis proposicionais A, B, C, representadas pelas três primeiras colunas da seguinte tabela.

A

B

C

[pic 17]

[pic 18]

[pic 19]

[pic 20]

[pic 21]

V

V

V

V

V

V

V

V

V

V

F

V

F

F

F

V

V

F

V

F

V

V

V

V

V

F

F

F

V

V

V

V

F

V

V

F

V

V

V

V

F

V

F

F

V

F

V

V

F

F

V

F

V

V

V

V

F

F

F

F

V

V

V

V

Pelo fato de que cada linha da última coluna contém um V, a sentença em questão é de fato uma tautologia.

Também é possível definir um sistema dedutivo para a lógica proposicional, como uma variante mais simples dos sistemas dedutivos empregados para a lógica de primeira ordem. Uma demonstração de uma tautologia em um sistema de dedução apropriado pode ser bem menor que uma tabela de verdade completa (uma fórmula com n variáveis proposicionais requer uma tabela verdade com 2n linhas, a qual rapidamente se torna intratável à medida que n cresce). Sistemas dedutivos também são requeridos para o estudo da lógica proposicional intucionista, para a qual o método das tabelas de verdade não pode ser empregado.

Implicação tautológica

Diz-se que uma fórmula R implica tautologicamente em uma fórmula S se toda valoração que torna R verdadeira também torna S verdadeira. Esta situação é denotada por [pic 22]. É equivalente a afirmar que a fórmula [pic 23]é uma tautologia.

Por exemplo, seja S a sentença [pic 24]. Então S não é uma tautologia, pois qualquer valoração que torna A falso tornará S falso. Mas qualquer valoração que torna A verdadeiro tornará S verdadeiro, pois [pic 25]é uma tautologia. Seja R a fórmula [pic 26]. Então [pic 27], pois toda valoração que satisfaz R torna