 |
Demente
(Foto: Robert Michie / FreeImages) CC BY-NC
|
No artigo Lógica proposicional - Tautologias, Contradições e Contingências foram apresentadas as classes que denominam uma fórmula dada, com base na sua tabela-verdade. Entre elas a que nos interessa são as tautologias.
As tautologias, como já observamos, constituem uma classe importante de fórmulas, pois, elas são sentenças verdadeiras, como vimos. Em ciência, sempre buscamos o conhecimento e isto implica particularmente na busca da verdade. Ao utilizarmos a linguagem da lógica clássica, então tal "verdade" se reflete, de modo particular, nas tautologias. Felizmente, para a lógica proposicional, há um método feito para "testar" se uma fórmula é tautologia ou não, por exemplo, valendo-se das tabelas-verdade.
Este artigo tem objetivo de estudar um outro algoritmo denominado árvore de refutação, também conhecido como tabela da refutação, para verificar se uma dada fórmula é tautologia ou contradição.
Árvore de Refutação de uma Tautologia
Passos para a construção da árvore de refutação de uma tautologia.
Iremos introduzir a árvore de refutação de uma tautologia através de três exemplos.
Verifique se a fórmula $$[(\text{A}$$ $$\wedge$$ $$\text{B})$$ $$\rightarrow$$ $$\text{A}]$$ é tautologia.
Inicialmente, traçamos linhas em número suficiente de colunas para cada fórmula atômica e conectivo componente. Logo, teremos:
Passos
|
Instruções
|
|---|---|
01
|
Trace linhas em número suficiente e colunas para cada fórmula atômica e conectivo componente.
|
02
|
Acrescente uma coluna de justificativa.
|
03
|
Suponha que a fórmula dada seja falsa. Escrevemos o valor verdade falso abaixo do último conectivo da fórmula em questão.
|
04
|
Coloque "Falseamento", na justificativa.
|
05
|
Veja a tabela-verdade do último conectivo e escreva os valores que resultem em falso, nas respectivas colunas.
|
06
|
Justifique com a tabela-verdade do conectivo.
|
07
|
Passamos a aplicar o raciocínio do passo 05 e 06, mas sempre visando o caminho mais "fácil".
|
08
|
Olhemos para a tabela resultante e se alguma sentença for verdadeira e falsa, em colunas divergentes, a fórmula trabalhada é tautologia.
|
Iremos introduzir a árvore de refutação de uma tautologia através de três exemplos.
Verifique se a fórmula $$[(\text{A}$$ $$\wedge$$ $$\text{B})$$ $$\rightarrow$$ $$\text{A}]$$ é tautologia.
Inicialmente, traçamos linhas em número suficiente de colunas para cada fórmula atômica e conectivo componente. Logo, teremos:
| $$[(\text{A}$$ | $$\wedge$$ | $$\text{B})$$ | $$\rightarrow$$ | $$\text{A}]$$ |
|---|---|---|---|---|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
Acrescentamos a coluna da justificativa com a mesma quantidade de linha das demais. Vejamos:
| $$[(\text{A}$$ | $$\wedge$$ | $$\text{B})$$ | $$\rightarrow$$ | $$\text{A}]$$ | Justificativa |
|---|---|---|---|---|---|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
Em sequência, suponha-se que a fórmula $$[(\text{A}$$ $$\wedge$$ $$\text{B})$$ $$\rightarrow$$ $$\text{A}]$$ seja falsa. Escrevemos o valor verdade falso abaixo do último conectivo da fórmula em questão. Ilustremos este passo abaixo:
| $$[(\text{A}$$ | $$\wedge$$ | $$\text{B})$$ | $$\rightarrow$$ | $$\text{A}]$$ | Justificativa |
|---|---|---|---|---|---|
-
|
-
|
-
|
F
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
Vemos que o último conectivo aplicado é o da implicação. Colocamos F na linha imediatamente abaixo e na coluna correspondente. No que o valor atribuído é o valor da fórmula "inteira", ou seja, ela é falsa.
A cada aplicação na árvore, devemos justificar. Vejamos:
| $$[(\text{A}$$ | $$\wedge$$ | $$\text{B})$$ | $$\rightarrow$$ | $$\text{A}]$$ | Justificativa |
|---|---|---|---|---|---|
-
|
-
|
-
|
F
|
-
|
Falseamento
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
Com base na tabela-verdade da implicação, a implicação é falsa se e somente se o antecedente, $$(\text{A}$$ $$\wedge$$ $$\text{B})$$, é verdadeiro e o consequente, $$\text{A}$$, é falso. Escrevemos estes valores na linha imediatamente seguinte, nas respectivas colunas. Logo, teremos:
| $$[(\text{A}$$ | $$\wedge$$ | $$\text{B})$$ | $$\rightarrow$$ | $$\text{A}]$$ | Justificativa |
|---|---|---|---|---|---|
-
|
-
|
-
|
F
|
-
|
Falseamento
|
-
|
V
|
-
|
-
|
F
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
A justificativa que devemos colocar é a tabela da implicação, porque com base nela concluirmos que para a fórmula ser falsa é necessário o consequente ser falso e o antecedente ser verdadeiro. Vejamos:
| $$[(\text{A}$$ | $$\wedge$$ | $$\text{B})$$ | $$\rightarrow$$ | $$\text{A}]$$ | Justificativa |
|---|---|---|---|---|---|
-
|
-
|
-
|
F
|
-
|
Falseamento
|
-
|
V
|
-
|
-
|
F
|
Tab. $$\rightarrow$$
|
-
|
-
|
-
|
-
|
-
|
-
|
Passamos a aplicar o raciocínio anterior nas duas fórmulas atômica. No caso de $$\text{A}$$ $$\wedge$$ $$\text{B}$$, ela é verdadeira. Consultando-se a tabela-verdade da conjunção, vemos que uma conjunção é verdadeira se e somente se ambas fórmulas $$\text{A}$$ e $$\text{B}$$ são verdadeiras, isto é, o valor verdade de $$\text{A}$$ e de $$\text{B}$$ é verdadeiro. No caso da fórmula da direita, não é necessário repetir o processo, pois ela já é atômica. Vejamos:
| $$[(\text{A}$$ | $$\wedge$$ | $$\text{B})$$ | $$\rightarrow$$ | $$\text{A}]$$ | Justificativa |
|---|---|---|---|---|---|
-
|
-
|
-
|
F
|
-
|
Falseamento
|
-
|
V
|
-
|
-
|
F
|
Tab. $$\rightarrow$$
|
V
|
-
|
V
|
-
|
-
|
Tab. $$\wedge$$
|
A justificativa é a tabela da conjunção.
Se olharmos para a tabela resultante, observamos que a sentença $$\text{A}$$ é verdadeira na primeira coluna e falsa na quinta coluna, ou seja, a sentença $$\text{A}$$ está sendo verdadeira e falsa ao mesmo tempo. Isto constitui, segundo as três leis do pensamento, uma inconsistência.
Como em lógica clássica supusemos que não existem inconsistências, algum passo que fizemos está "errado", ou seja é "falso". O único elo fraco acima é justamento o primeiro passo, quando supusemos que a fórmula $$[(\text{A}$$ $$\wedge$$ $$\text{B})$$ $$\rightarrow$$ $$\text{A}]$$ era falsa. Logo, o "errado" ou "falso" é supormos que $$[(\text{A}$$ $$\wedge$$ $$\text{B})$$ $$\rightarrow$$ $$\text{A}]$$ é falso. Portanto, concluímos que ela é sempre verdadeira. Ora, se $$[(\text{A}$$ $$\wedge$$ $$\text{B})$$ $$\rightarrow$$ $$\text{A}]$$ é sempre verdadeira, ela é tautologia, como queríamos provar.
Verifique se a fórmula $$[((\neg\text{A})$$ $$\wedge$$ $$(\text{A}$$ $$\vee$$ $$\text{B}))$$ $$\rightarrow$$ $$\text{B}]$$ é tautologia. Veja o vídeo abaixo:
Verifique se a fórmula $$((\text{A}$$ $$\wedge$$ $$(\text{B}$$ $$\vee$$ $$\text{C}))$$ $$\leftrightarrow$$ $$((\text{A}$$ $$\wedge$$ $$\text{B})$$ $$\vee$$ $$(\text{A}$$ $$\wedge$$ $$\text{C})))$$ é tautologia. Veja o vídeo abaixo:
Árvore de Refutação de uma Contradição
Podemos obter um algoritmo similar á árvore de refutação vista anteriormente para verificar se uma fórmula constitui uma contradição. Com efeito, basta supor, por absurdo, que a fórmula é verdadeira e cair num absurdo. Se isto ocorrer, fica provado que a fórmula é uma contradição.
Passos para a construção da árvore de refutação de uma tautologia.
Iremos introduzir a árvore de refutação de uma contradição através de um exemplo.
Verifique se a fórmula $$[\neg$$ $$(\text{A}$$ $$\rightarrow$$ $$(\text{B}$$ $$\rightarrow$$ $$\text{A}))]$$ é contradição.
Inicialmente, traçamos linhas em número suficiente e colunas para cada fórmula atômica e conectivo componente. Logo, teremos:
Passos para a construção da árvore de refutação de uma tautologia.
Passos
|
Instruções
|
|---|---|
01
|
Trace linhas em número suficiente e colunas para cada fórmula atômica e conectivo componente.
|
02
|
Acrescente uma coluna de justificativa.
|
03
|
Suponha que a fórmula dada seja verdadeira. Escrevemos o valor verdade verdade abaixo do último conectivo da fórmula em questão.
|
04
|
Coloque "Veracidade", na justificativa.
|
05
|
Veja a tabela-verdade do último conectivo e escreva os valores que resultem em falso, nas respectivas colunas.
|
06
|
Justifique com a tabela-verdade do conectivo.
|
07
|
Passamos a aplicar o raciocínio do passo 05 e 06, mas sempre visando o caminho mais "fácil".
|
08
|
Olhemos para a tabela resultante e se alguma sentença for verdadeira e falsa, em colunas divergente, a fórmula trabalhada é contradição.
|
Iremos introduzir a árvore de refutação de uma contradição através de um exemplo.
Verifique se a fórmula $$[\neg$$ $$(\text{A}$$ $$\rightarrow$$ $$(\text{B}$$ $$\rightarrow$$ $$\text{A}))]$$ é contradição.
Inicialmente, traçamos linhas em número suficiente e colunas para cada fórmula atômica e conectivo componente. Logo, teremos:
| $$[\neg$$ | $$(\text{A}$$ | $$\rightarrow$$ | $$(\text{B}$$ | $$\rightarrow$$ | $$\text{A}))]$$ |
|---|---|---|---|---|---|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
Acrescentamos a coluna da justificativa com a mesma quantidade de linha das demais. Vejamos:
| $$[\neg$$ | $$(\text{A}$$ | $$\rightarrow$$ | $$(\text{B}$$ | $$\rightarrow$$ | $$\text{A}))]$$ | Justificativa |
|---|---|---|---|---|---|---|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
Em sequência, suponha-se que a fórmula $$[\neg$$ $$(\text{A}$$ $$\rightarrow$$ $$(\text{B}$$ $$\rightarrow$$ $$\text{A}))]$$ seja verdadeira. Escrevemos o valor verdade verdadeiro abaixo do último conectivo da fórmula em questão. Ilustremos este passo abaixo:
| $$[\neg$$ | $$(\text{A}$$ | $$\rightarrow$$ | $$(\text{B}$$ | $$\rightarrow$$ | $$\text{A}))]$$ | Justificativa |
|---|---|---|---|---|---|---|
V
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
Vemos que o último conectivo aplicado é o da negação. Colocamos V na linha imediatamente abaixo e na coluna correspondente. No que o valor atribuído é o valor da fórmula "inteira", ou seja, ela é verdadeira.
A cada aplicação na árvore, devemos justificar. Vejamos:
| $$[\neg$$ | $$(\text{A}$$ | $$\rightarrow$$ | $$(\text{B}$$ | $$\rightarrow$$ | $$\text{A}))]$$ | Justificativa |
|---|---|---|---|---|---|---|
V
|
-
|
-
|
-
|
-
|
-
|
Veracidade
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
Com base na tabela-verdade da negação, a negação é verdadeira se e somente se a fórmula, que está sendo negada, é falsa. Escrevemos este valor na linha imediatamente seguinte, nas respectivas colunas. Logo, teremos:
Para a implicação ser falsa é necessário que o consequente, $$(\text{B}$$ $$\rightarrow$$ $$\text{A})$$, seja falso e o antecedente, $$\text{A}$$, seja verdadeiro. Vejamos:
A justificativa que devemos colocar é a tabela da implicação, porque com base nela concluirmos que para a fórmula ser falsa é necessário o conseguente ser falso e o antecedente ser verdadeiro. Vejamos:
Com base na tabela-verdade da implicação, a implicação é falsa se e somente se o antecedente, $$\text{B}$$, é verdadeiro e o consequente, $$\text{A}$$, é falso. Escrevemos estes valores na linha imediatamente seguinte, nas respectivas colunas. No caso da fórmula da esquerda, não é necessário repetir o processo, pois ela já é atômica. Vejamos:
A justificativa é a tabela da implicação.
Se olharmos para a tabela resultante, observamos que a sentença $$\text{A}$$ é verdadeira na segunda coluna e falsa na sexta coluna, ou seja, a sentença $$\text{A}$$ está sendo verdadeira e falsa simultaneamente. Isto constitui, segundo as três leis do pensamento, uma inconsistência.
Como em lógica clássica supusemos que não existem inconsistências, algum passo que fizemos está "errado", ou seja é "falso". O único elo fraco acima é justamento o primeiro passo, quando supusemos que a fórmula $$[\neg$$ $$(\text{A}$$ $$\rightarrow$$ $$(\text{B}$$ $$\rightarrow$$ $$\text{A}))]$$ era verdadeira. Logo, o "errado" ou "falso" é supormos que $$[\neg$$ $$(\text{A}$$ $$\rightarrow$$ $$(\text{B}$$ $$\rightarrow$$ $$\text{A}))]$$ é verdade. Portanto, concluímos que ela é sempre falsa. Ora, se $$[\neg$$ $$(\text{A}$$ $$\rightarrow$$ $$(\text{B}$$ $$\rightarrow$$ $$\text{A}))]$$ é sempre falsa, ela é contradição, como queríamos provar.
O raciocínio aplicado nos dois vídeos da tautologia servem para a contradição, mas iniciamos com veracidade e não com falsidade.
| $$[\neg$$ | $$(\text{A}$$ | $$\rightarrow$$ | $$(\text{B}$$ | $$\rightarrow$$ | $$\text{A}))]$$ | Justificativa |
|---|---|---|---|---|---|---|
V
|
-
|
-
|
-
|
-
|
-
|
Veracidade
|
-
|
-
|
F
|
-
|
-
|
-
|
Tab. $$\neg$$
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
Para a implicação ser falsa é necessário que o consequente, $$(\text{B}$$ $$\rightarrow$$ $$\text{A})$$, seja falso e o antecedente, $$\text{A}$$, seja verdadeiro. Vejamos:
| $$[\neg$$ | $$(\text{A}$$ | $$\rightarrow$$ | $$(\text{B}$$ | $$\rightarrow$$ | $$\text{A}))]$$ | Justificativa |
|---|---|---|---|---|---|---|
V
|
-
|
-
|
-
|
-
|
-
|
Veracidade
|
-
|
-
|
F
|
-
|
-
|
-
|
Tab. $$\neg$$
|
-
|
V
|
-
|
-
|
F
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
A justificativa que devemos colocar é a tabela da implicação, porque com base nela concluirmos que para a fórmula ser falsa é necessário o conseguente ser falso e o antecedente ser verdadeiro. Vejamos:
| $$[\neg$$ | $$(\text{A}$$ | $$\rightarrow$$ | $$(\text{B}$$ | $$\rightarrow$$ | $$\text{A}))]$$ | Justificativa |
|---|---|---|---|---|---|---|
V
|
-
|
-
|
-
|
-
|
-
|
Veracidade
|
-
|
-
|
F
|
-
|
-
|
-
|
Tab. $$\neg$$
|
-
|
V
|
-
|
-
|
F
|
-
|
Tab. $$\rightarrow$$
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
Com base na tabela-verdade da implicação, a implicação é falsa se e somente se o antecedente, $$\text{B}$$, é verdadeiro e o consequente, $$\text{A}$$, é falso. Escrevemos estes valores na linha imediatamente seguinte, nas respectivas colunas. No caso da fórmula da esquerda, não é necessário repetir o processo, pois ela já é atômica. Vejamos:
| $$[\neg$$ | $$(\text{A}$$ | $$\rightarrow$$ | $$(\text{B}$$ | $$\rightarrow$$ | $$\text{A}))]$$ | Justificativa |
|---|---|---|---|---|---|---|
V
|
-
|
-
|
-
|
-
|
-
|
Veracidade
|
-
|
-
|
F
|
-
|
-
|
-
|
Tab. $$\neg$$
|
-
|
V
|
-
|
-
|
F
|
-
|
Tab. $$\rightarrow$$
|
-
|
-
|
-
|
V
|
-
|
F
|
Tab. $$\rightarrow$$
|
A justificativa é a tabela da implicação.
Se olharmos para a tabela resultante, observamos que a sentença $$\text{A}$$ é verdadeira na segunda coluna e falsa na sexta coluna, ou seja, a sentença $$\text{A}$$ está sendo verdadeira e falsa simultaneamente. Isto constitui, segundo as três leis do pensamento, uma inconsistência.
Como em lógica clássica supusemos que não existem inconsistências, algum passo que fizemos está "errado", ou seja é "falso". O único elo fraco acima é justamento o primeiro passo, quando supusemos que a fórmula $$[\neg$$ $$(\text{A}$$ $$\rightarrow$$ $$(\text{B}$$ $$\rightarrow$$ $$\text{A}))]$$ era verdadeira. Logo, o "errado" ou "falso" é supormos que $$[\neg$$ $$(\text{A}$$ $$\rightarrow$$ $$(\text{B}$$ $$\rightarrow$$ $$\text{A}))]$$ é verdade. Portanto, concluímos que ela é sempre falsa. Ora, se $$[\neg$$ $$(\text{A}$$ $$\rightarrow$$ $$(\text{B}$$ $$\rightarrow$$ $$\text{A}))]$$ é sempre falsa, ela é contradição, como queríamos provar.
O raciocínio aplicado nos dois vídeos da tautologia servem para a contradição, mas iniciamos com veracidade e não com falsidade.
Principais Tautologias
A seguir listamos algumas das principais tautologias.
- Leis Comutativas: $$((\text{A}$$ $$\vee$$ $$\text{B})$$ $$\leftrightarrow$$ $$(\text{B}$$ $$\vee$$ $$\text{A}))$$.
- Leis Comutativas: $$((\text{A}$$ $$\wedge$$ $$\text{B})$$ $$\leftrightarrow$$ $$(\text{B}$$ $$\wedge$$ $$\text{A}))$$.
- Leis Comutativas: $$((\text{A}$$ $$\leftrightarrow$$ $$\text{B})$$ $$\leftrightarrow$$ $$(\text{B}$$ $$\leftrightarrow$$ $$\text{A}))$$.
- Leis Comutativas: $$(((\text{A}$$ $$\rightarrow$$ ($$\text{B}$$ $$\rightarrow$$ $$\text{C}))$$ $$\leftrightarrow$$ $$(\text{B}$$ $$\rightarrow$$ $$(\text{A}$$ $$\rightarrow$$ $$\text{C})))$$.
- Leis Associativas: $$(((\text{A}$$ $$\vee$$ $$\text{B})$$ $$\vee$$ $$\text{C})$$ $$\leftrightarrow$$ $$(\text{A}$$ $$\vee$$ $$(\text{B}$$ $$\vee$$ $$\text{C})))$$.
- Leis Associativas: $$(((\text{A}$$ $$\wedge$$ $$\text{B})$$ $$\wedge$$ $$\text{C})$$ $$\leftrightarrow$$ $$(\text{A}$$ $$\wedge$$ $$(\text{B}$$ $$\wedge$$ $$\text{C})))$$.
- Leis Distributivas: $$((\text{A}$$ $$\wedge$$ $$(\text{B}$$ $$\vee$$ $$\text{C}))$$ $$\leftrightarrow$$ $$(\text{A}$$ $$\wedge$$ $$\text{B})$$ $$\vee$$ $$(\text{A}$$ $$\wedge$$ $$\text{C})))$$.
- Leis Distributivas: $$((\text{A}$$ $$\vee$$ $$(\text{B}$$ $$\wedge$$ $$\text{C}))$$ $$\leftrightarrow$$ $$(\text{A}$$ $$\vee$$ $$\text{B})$$ $$\wedge$$ $$(\text{A}$$ $$\vee$$ $$\text{C})))$$.
- Leis Idempotentes: $$((\text{A}$$ $$\vee$$ $$\text{A})$$ $$\leftrightarrow$$ $$\text{A})$$.
- Leis Idempotentes: $$((\text{A}$$ $$\wedge$$ $$\text{A})$$ $$\leftrightarrow$$ $$\text{A})$$.
- Lei da Dupla Negação: $$(\text{A}$$ $$\leftrightarrow$$ $$(\neg$$$$(\neg$$$$\text{A}))$$.
- Lei do Terceiro Excluído: $$(\text{A}$$ $$\vee$$ $$(\neg$$$$\text{A}))$$.
- Lei da Não Contradição: $$(\neg$$$$(\text{A}$$ $$\wedge$$ $$(\neg$$$$\text{A})))$$.
- Lei da Transitividade da Implicação: $$((\text{A}$$ $$\rightarrow$$ $$\text{B})$$ $$\rightarrow$$ $$((\text{B}$$ $$\rightarrow$$ $$\text{C})$$ $$\rightarrow$$ $$(\text{A}$$ $$\rightarrow$$ $$\text{C})))$$.
- Leis do Silogismo Hipotético: $$(((\text{A}$$ $$\rightarrow$$ $$\text{B})$$ $$\wedge$$ $$(\text{B}$$ $$\rightarrow$$ $$\text{C}))$$ $$\rightarrow$$ $$(\text{A}$$ $$\rightarrow$$ $$\text{C}))$$.
- Leis da Contraposição: $$((\text{A}$$ $$\rightarrow$$ $$\text{B})$$ $$\leftrightarrow$$ $$((\neg$$$$\text{B})$$ $$\rightarrow$$ $$(\neg$$$$\text{A})))$$.
- Leis da Contraposição: $$((\text{A}$$ $$\rightarrow$$ $$(\neg$$$$\text{B}))$$ $$\leftrightarrow$$ $$(\text{B}$$ $$\rightarrow$$ $$(\neg$$$$\text{A}))$$.
- Lei da Exportação: $$(((\text{A}$$ $$\wedge$$ $$\text{B})$$ $$\rightarrow$$ $$\text{C})$$ $$\rightarrow$$ $$(\text{A}$$ $$\rightarrow$$ $$(\text{B}$$ $$\rightarrow$$ $$\text{C})))$$.
- Lei da Importação: $$((\text{A}$$ $$\rightarrow$$ $$(\text{B}$$ $$\rightarrow$$ $$\text{C}))$$ $$\rightarrow$$ $$((\text{A}$$ $$\wedge$$ $$\text{B})$$ $$\rightarrow$$ $$\text{C}))$$.
- Lei da Exportação e da Importação: $$(((\text{A}$$ $$\wedge$$ $$\text{B})$$ $$\rightarrow$$ $$\text{C})$$ $$\leftrightarrow$$ $$(\text{A}$$ $$\rightarrow$$ $$(\text{B}$$ $$\rightarrow$$ $$\text{C})))$$.
- Leis de Absorção: $$((\text{A}$$ $$\vee$$ $$(\text{A}$$ $$(\text{A}$$ $$\wedge$$ $$\text{B}))$$ $$\leftrightarrow$$ $$\text{A})$$.
- Leis de Absorção: $$((\text{A}$$ $$\wedge$$ $$(\text{A}$$ $$(\text{A}$$ $$\vee$$ $$\text{B}))$$ $$\leftrightarrow$$ $$\text{A})$$.
- Leis de Absorção: $$((\text{A}$$ $$\rightarrow$$ $$(\text{A}$$ $$\rightarrow$$ $$\text{B}))$$ $$\leftrightarrow$$ $$(\text{A}$$ $$\rightarrow$$ $$\text{B}))$$.
- Leis de Absorção: $$(((\text{A}$$ $$\rightarrow$$ $$\text{B})$$ $$\wedge$$ $$(\text{A}$$ $$\rightarrow$$ $$\text{C})))$$ $$\leftrightarrow$$ $$(\text{A}$$ $$\rightarrow$$ $$(\text{B}$$ $$\wedge$$ $$\text{C})))$$.
- Leis de De Morgan: $$((\neg$$$$(\text{A}$$ $$\vee$$ $$\text{B}))$$ $$\leftrightarrow$$ $$((\neg$$$$\text{A})$$ $$\wedge$$ $$(\neg$$$$\text{B})))$$.
- Leis de De Morgan: $$((\neg$$$$(\text{A}$$ $$\wedge$$ $$\text{B}))$$ $$\leftrightarrow$$ $$((\neg$$$$\text{A})$$ $$\vee$$ $$(\neg$$$$\text{B})))$$.
- Prova por Casos: $$((((\text{A}$$ $$\vee$$ $$\text{B})$$ $$\wedge$$ $$(\text{A}$$ $$\rightarrow$$ $$\text{C}))$$ $$\wedge$$ $$(\text{B}$$ $$\rightarrow$$ $$\text{C}))$$ $$\rightarrow$$ $$\text{C})$$.
- Prova por Contradição: $$((((\neg$$$$\text{A})$$ $$\rightarrow$$ $$\text{B})$$ $$\wedge$$ $$(\neg$$$$\text{B}))$$ $$\rightarrow$$ $$\text{A})$$.
- Prova por Contradição: $$((\text{A}$$ $$\rightarrow$$ $$(\neg$$$$\text{A}))$$ $$\rightarrow$$ $$(\neg$$$$\text{A}))$$.
- Prova por Contradição: $$(((\neg$$$$\text{A})$$ $$\rightarrow$$ $$\text{A})$$ $$\rightarrow$$ $$\text{A})$$.
- Prova por Contradição: $$(((\text{A}$$ $$\wedge$$ $$(\neg$$$$\text{B}))$$ $$\rightarrow$$ $$(\text{C}$$ $$\wedge$$ $$(\neg$$$$\text{C})))$$ $$\rightarrow$$ $$(\text{A}$$ $$\rightarrow$$ $$\text{B}))$$.
- Prova por Contradição: $$(((\text{A}$$ $$\wedge$$ $$(\neg$$$$\text{B}))$$ $$\rightarrow$$ $$(\neg$$$$\text{A}))$$ $$\rightarrow$$ $$(\text{A}$$ $$\rightarrow$$ $$\text{B}))$$.
- Prova por Contradição: $$(((\text{A}$$ $$\wedge$$ $$(\neg$$$$\text{B}))$$ $$\rightarrow$$ $$\text{B})$$ $$\rightarrow$$ $$(\text{A}$$ $$\rightarrow$$ $$\text{B}))$$.
- Lei do Destacamento: $$((\text{A}$$ $$\wedge$$ $$(\text{A}$$ $$\rightarrow$$ $$\text{B}))$$ $$\rightarrow$$ $$\text{B})$$.
- Modus Tollendo Tollens: $$(((\neg$$$$\text{B})$$ $$\wedge$$ $$(\text{A}$$ $$\rightarrow$$ $$\text{B}))$$ $$\rightarrow$$ $$(\neg$$$$\text{A}))$$.
- Modus Tollendo Ponens: $$(((\neg$$$$\text{A})$$ $$\wedge$$ $$(\text{A}$$ $$\rightarrow$$ $$\text{B}))$$ $$\rightarrow$$ $$\text{B})$$.
- Leis de Simplificação: $$((\text{A}$$ $$\wedge$$ $$\text{B})$$ $$\rightarrow$$ $$\text{A})$$.
- Leis de Simplificação: $$((\text{A}$$ $$\wedge$$ $$\text{B})$$ $$\rightarrow$$ $$\text{B})$$.
- Leis de Adição: $$(\text{A}$$ $$\rightarrow$$ $$(\text{A}$$ $$\vee$$ $$\text{B}))$$.
- Leis de Adição: $$(\text{B}$$ $$\rightarrow$$ $$(\text{A}$$ $$\vee$$ $$\text{B}))$$.
- Leis de Equivalência para a Implicação e Disjunção: $$((\text{A}$$ $$\rightarrow$$ $$\text{B})$$ $$\leftrightarrow$$ $$((\neg$$$$\text{A})$$ $$\vee$$ $$\text{B}))$$.
- Lei de Negação para a Implicação: $$((\neg$$$$(\text{A}$$ $$\rightarrow$$ $$\text{B}))$$ $$\leftrightarrow$$ $$(\text{A}$$ $$\wedge$$ $$(\neg$$$$\text{B})))$$.
- Leis para Proposições Bicondicionais: $$((\text{A}$$ $$\leftrightarrow$$ $$\text{B})$$ $$\leftrightarrow$$ $$((\text{A}$$ $$\rightarrow$$ $$\text{B})$$ $$\wedge$$ $$(\text{B}$$ $$\rightarrow$$ $$\text{A})))$$.
- Leis para Proposições Bicondicionais: $$((\text{A}$$ $$\leftrightarrow$$ $$\text{B})$$ $$\leftrightarrow$$ $$((\text{A}$$ $$\wedge$$ $$\text{B})$$ $$\vee$$ $$((\neg$$$$\text{A})$$ $$\wedge$$ $$(\neg$$$$\text{B}))))$$.
- Lei de Peirce: $$(((\text{A}$$ $$\rightarrow$$ $$\text{B})$$ $$\rightarrow$$ $$\text{A})$$ $$\rightarrow$$ $$\text{A})$$.
- Esquema B: $$(\text{A}$$ $$\rightarrow$$ $$(\text{B}$$ $$\rightarrow$$ $$\text{A})$$.
- Esquema C: $$(((\text{A}$$ $$\rightarrow$$ $$(\text{B}$$ $$\rightarrow$$ $$\text{C}))$$ $$\rightarrow$$ $$((\text{A}$$ $$\rightarrow$$ $$\text{B})$$ $$\rightarrow$$ $$(\text{A}$$ $$\rightarrow$$ $$\text{C})))$$.
- Lei da Identidade: $$(\text{A}$$ $$\rightarrow$$ $$\text{A})$$.
O que você aprendeu
O objetivo deste artigo foi apresentar mais uma ferramenta, capaz de auxiliar no descobrimento de uma tautologia, e as principais tautologias que veremos ao decorrer do aprendizado. Especificamente, você aprendeu:
- Árvore de refutação.
- Principais tautologias.
Continua em
Continuação de
Referência Bibliográfica
ABE, J. M; SCALZITTI, A; FILHO, J. I. S. Introdução à Lógica para a Ciência da Computação. 2. ed. São Paulo: Arte & Ciência, 2002. 247 p.
Para citar esse artigo:
Comentários
Postar um comentário