 |
Jogo do Galo
(Foto: Karolina K. / FreeImages) CC BY-NC
|
No artigo Lógica Proposicional - Árvore de Refutação foi apresentado um algoritmo que auxilia no descobrimento de uma tautologia e as principais tautologias. É vantajoso saber este algoritmo, porque as vezes ele nos economiza tempo.
Neste artigo aprenderemos sobre a equivalência lógica de uma proposição qualquer, como descobrir se uma sentença é logicamente equivalente a outra e algumas propriedades da equivalência, porque muitas vezes nos deparamos com equivalências lógica, mas não percebemos e acabamos concordando com a mesma que anteriormente tínhamos descordado.
Por exemplo, nos deparamos com as seguintes sentenças:
- Se João tirar nota dez, então ele pode jogar Pokémon GO.
- João não vai tirar nota dez ou ele vai jogar Pokémon GO.
Percebeu a importância de saber equivalência lógica? Mutias vezes podemos dizer e ouvir a mesma sentença, mas de diversas formas.
Equivalência
Diz-se que uma proposição $$\text{A}$$ é logicamente equivalente ou apenas equivalente a uma proposição $$\text{B}$$ se as tabelas-verdade destas duas proposições são idênticas.
Indica-se que a proposição $$\text{A}$$ é equivalente a proposição $$\text{B}$$ com a notação: $$\text{A}$$ $$\Longleftrightarrow$$ $$\text{B}$$ ou $$\text{A}$$ $$\equiv$$ $$\text{B}$$.
Em particular, se as proposições $$\text{A}$$ e $$\text{B}$$ são ambas tautologias ou são ambas contradições, então são equivalentes.
Como verificar se duas proposições $$\text{P}$$ e $$\text{Q}$$ são equivalentes logicamente?
Observação importante: os símbolos $$\leftrightarrow$$ e $$\Longleftrightarrow$$ são distintos, pois, o primeiro é de operação lógica, enquanto que o segundo é de relação.
Em particular, se as proposições $$\text{A}$$ e $$\text{B}$$ são ambas tautologias ou são ambas contradições, então são equivalentes.
Como verificar se duas proposições $$\text{P}$$ e $$\text{Q}$$ são equivalentes logicamente?
- Construa a tabela-verdade de $$\text{P}$$.
- Construa a tabela-verdade de $$\text{Q}$$, usando os mesmos valores de variáveis para as afirmações que formam a proposição.
- Verifique se a última coluna das tabelas-verdade de $$\text{P}$$ e $$\text{Q}$$ são idênticas para cada combinação de valores verdade. Se forem, $$\text{P}$$ e $$\text{Q}$$ são equivalentes logicamente, caso contrário não.
Verifique se a fórmula $$\text{P}$$ $$\rightarrow$$ $$\text{Q}$$ é logicamente equivalente a $$\neg\text{P}$$ $$\vee$$ $$\text{Q}$$.
Inicialmente, construímos a tabela-verdade da sentença $$\text{P}$$ $$\rightarrow$$ $$\text{Q}$$. Logo, teremos:
Após a construção da tabela-verdade da primeira sentença, devemos fazer o mesmo com a segunda, mas usando os mesmo valores de variáveis. Logo, teremos:
Como a última coluna das tabelas-verdade são idênticas, considerando o valor verdade e sua ordem, concluímos que elas realmente são equivalentes, como apresentado no início deste artigo.
Segue um quadro resumo com as equivalências mais comuns em provas:
Inicialmente, construímos a tabela-verdade da sentença $$\text{P}$$ $$\rightarrow$$ $$\text{Q}$$. Logo, teremos:
| $$\text{P}$$ | $$\text{Q}$$ | $$\text{P}$$ $$\rightarrow$$ $$\text{Q}$$ |
|---|---|---|
V
|
V
|
V
|
V
|
F
|
F
|
F
|
V
|
V
|
F
|
F
|
V
|
Após a construção da tabela-verdade da primeira sentença, devemos fazer o mesmo com a segunda, mas usando os mesmo valores de variáveis. Logo, teremos:
| $$\text{P}$$ | $$\text{Q}$$ | $$\neg\text{P}$$ | $$\neg\text{P}$$ $$\vee$$ $$\text{Q}$$ |
|---|---|---|---|
V
|
V
|
F
|
V
|
V
|
F
|
F
|
F
|
F
|
V
|
V
|
V
|
F
|
F
|
V
|
V
|
Observação importante: caso o leitor não saiba construir uma tabela-verdade, veja construção de tabela-verdade de uma fórmula sem árvore de decomposição ou construção de tabela-verdade de uma fórmula com árvore de decomposição.
Como a última coluna das tabelas-verdade são idênticas, considerando o valor verdade e sua ordem, concluímos que elas realmente são equivalentes, como apresentado no início deste artigo.
Segue um quadro resumo com as equivalências mais comuns em provas:
| Proposição | Equivalência |
|---|---|
$$\text{P}$$ $$\wedge$$ $$\text{Q}$$
|
$$\text{Q}$$ $$\wedge$$ $$\text{P}$$
|
$$\text{P}$$ $$\vee$$ $$\text{Q}$$
|
$$\text{Q}$$ $$\vee$$ $$\text{P}$$
|
$$\text{P}$$ $$\rightarrow$$ $$\text{Q}$$
|
$$\neg$$$$\text{Q}$$ $$\rightarrow$$ $$\neg$$$$\text{P}$$
|
$$\text{P}$$ $$\rightarrow$$ $$\text{Q}$$
|
$$\neg$$$$\text{P}$$ $$\vee$$ $$\text{Q}$$
|
$$\text{P}$$ $$\rightarrow$$ $$\text{Q}$$
|
$$\text{P}$$ suficiente $$\text{Q}$$
|
$$\text{Q}$$ $$\leftarrow$$ $$\text{P}$$
|
$$\text{Q}$$ necessário $$\text{P}$$
|
$$\text{P}$$ $$\leftrightarrow$$ $$\text{Q}$$
|
$$\text{P}$$ necessário e suficiente $$\text{Q}$$
|
A equivalência é recíproca, ou seja, se x é equivalente a y, y é equivalente a x.
Tautologias e equivalência lógica
A proposição $$\text{A}$$ é equivalente à proposição $$\text{B}$$, se e somente se a bicondicional é tautologia.Se as proposições $$\text{A}$$ e $$\text{B}$$ são equivalentes, então, têm tabelas-verdade idênticas, e por conseguinte o valor lógico da bicondicional ($$\leftrightarrow$$) é sempre verdade, ou seja, é tautológica. Reciprocamente, se a bicondicional é tautológica, então a última coluna da sua tabela-verdade encerra somente com a letra V, e por conseguinte os valores lógicos respectivos das proposições $$\text{A}$$ e $$\text{B}$$ são ambos verdadeiros ou ambos falsos, isto é, estas duas proposições são equivalentes.
Portanto, a toda equivalência lógica corresponde uma bicondicional tautológica, e vice-versa.
Vejamos alguns exemplos:
A bicondicional $$(\text{P}$$ $$\wedge$$ $$\neg$$$$\text{Q}$$ $$\rightarrow$$ $$\text{R})$$ $$\leftrightarrow$$ $$(\text{P}$$ $$\rightarrow$$ $$\text{Q})$$, onde $$\text{R}$$ é uma proposição cujo valor lógico é falso, é tautológica, pois, a última coluna da sua tabela-verdade encerra somente com a letra V. Vejamos:
| $$(\text{P}$$ | $$\wedge$$ | $$\neg$$ | $$\text{Q}$$ | $$\rightarrow$$ | $$\text{R})$$ | $$\leftrightarrow$$ | $$(\text{P}$$ | $$\rightarrow$$ | $$\text{Q})$$ |
|---|---|---|---|---|---|---|---|---|---|
V
|
F
|
F
|
V
|
V
|
F
|
V
|
V
|
V
|
V
|
V
|
V
|
V
|
F
|
F
|
F
|
V
|
V
|
F
|
F
|
F
|
F
|
F
|
V
|
V
|
F
|
V
|
F
|
V
|
V
|
F
|
F
|
V
|
F
|
V
|
F
|
V
|
F
|
V
|
F
|
1
|
3
|
2
|
1
|
4
|
1
|
5
|
1
|
2
|
1
|
Portanto, as proposições $$(\text{P}$$ $$\wedge$$ $$\neg$$$$\text{Q}$$ $$\rightarrow$$ $$\text{R})$$ e $$(\text{P}$$ $$\rightarrow$$ $$\text{Q})$$ são equivalentes, isto é, simbolicamente: $$(\text{P}$$ $$\wedge$$ $$\neg$$$$\text{Q}$$ $$\rightarrow$$ $$\text{R})$$ $$\equiv$$ $$(\text{P}$$ $$\rightarrow$$ $$\text{Q})$$ ou $$(\text{P}$$ $$\wedge$$ $$\neg$$$$\text{Q}$$ $$\rightarrow$$ $$\text{R})$$ $$\Longleftrightarrow$$ $$(\text{P}$$ $$\rightarrow$$ $$\text{Q})$$.
A bicondicional $$(\text{P}$$ $$\wedge$$ $$\text{Q}$$ $$\rightarrow$$ $$\text{R})$$ $$\leftrightarrow$$ $$(\text{P}$$ $$\rightarrow$$ $$(\text{Q}$$ $$\rightarrow$$ $$\text{R}))$$ é tautológica, pois, a última coluna da tabela-verdade encerra comente com a letra V. Vejamos:
| $$(\text{P}$$ | $$\wedge$$ | $$\text{Q}$$ | $$\rightarrow$$ | $$\text{R})$$ | $$\leftrightarrow$$ | $$(\text{P}$$ | $$\rightarrow$$ | $$(\text{Q}$$ | $$\rightarrow$$ | $$\text{R}))$$ |
|---|---|---|---|---|---|---|---|---|---|---|
V
|
V
|
V
|
V
|
V
|
V
|
V
|
V
|
V
|
V
|
V
|
V
|
V
|
V
|
F
|
F
|
V
|
V
|
F
|
V
|
F
|
F
|
V
|
F
|
F
|
V
|
V
|
V
|
V
|
V
|
F
|
V
|
V
|
V
|
F
|
F
|
V
|
F
|
V
|
V
|
V
|
F
|
V
|
F
|
F
|
F
|
V
|
V
|
V
|
V
|
F
|
V
|
V
|
V
|
V
|
F
|
F
|
V
|
V
|
F
|
V
|
F
|
V
|
V
|
F
|
F
|
F
|
F
|
F
|
V
|
V
|
V
|
F
|
V
|
F
|
V
|
V
|
F
|
F
|
F
|
V
|
F
|
V
|
F
|
V
|
F
|
V
|
F
|
1
|
2
|
1
|
3
|
1
|
4
|
1
|
3
|
1
|
2
|
1
|
Portanto, as condicionais $$\text{P}$$ $$\wedge$$ $$\text{Q}$$ $$\rightarrow$$ $$\text{R}$$ e $$\text{P}$$ $$\rightarrow$$ $$(\text{Q}$$ $$\rightarrow$$ $$\text{R})$$ são equivalentes, isto é, simbolicamente: $$(\text{P}$$ $$\wedge$$ $$\text{Q}$$ $$\rightarrow$$ $$\text{R})$$ $$\Longleftrightarrow$$ $$(\text{P}$$ $$\rightarrow$$ $$(\text{Q}$$ $$\rightarrow$$ $$\text{R}))$$ ou $$(\text{P}$$ $$\wedge$$ $$\text{Q}$$ $$\rightarrow$$ $$\text{R})$$ $$\equiv$$ $$(\text{P}$$ $$\rightarrow$$ $$(\text{Q}$$ $$\rightarrow$$ $$\text{R}))$$.
As proposições $$x$$ $$=$$ $$1$$ $$\wedge$$ $$x$$ $$\not<$$ $$3$$ e $$\neg$$$$(x$$ $$<$$ $$3$$ $$\wedge$$ $$x$$ $$=$$ $$1)$$ não são equivalentes, pois, a bicondicional: $$(x$$ $$=$$ $$1$$ $$\wedge$$ $$x$$ $$\not<$$ $$3)$$ $$\leftrightarrow$$ $$\neg$$$$(x$$ $$<$$ $$3$$ $$\wedge$$ $$x$$ $$=$$ $$1)$$ não é tautológica, conforme se vê pela sua tabela-verdade:
| $$(x$$ $$=$$ $$1$$ | $$\wedge$$ | $$x$$$$\not<$$$$3)$$ | $$\leftrightarrow$$ | $$\neg$$ | $$(x$$$$<$$$$3$$ | $$\wedge$$ | $$x$$$$=$$$$1)$$ |
|---|---|---|---|---|---|---|---|
V
|
V
|
F
|
F
|
F
|
V
|
V
|
V
|
V
|
V
|
V
|
V
|
V
|
F
|
F
|
V
|
F
|
F
|
F
|
F
|
V
|
V
|
F
|
F
|
F
|
V
|
V
|
V
|
V
|
F
|
F
|
F
|
Observação importante: toda equivalência lógica corresponde uma bicondicional tautológica e vice-versa, ou seja, as tabelas-verdade das duas devem ser idênticas sendo todas verdadeiras ou falsas.
Propriedades da Equivalência Lógica
Há várias equivalências lógicas que são extremamente úteis. Eis uma lista de algumas das mais comuns:
- Comutação: $$\text{A}$$ $$\vee$$ $$\text{B}$$ $$\Longleftrightarrow$$ $$\text{B}$$ $$\vee$$ $$\text{A}$$.
- Comutação: $$\text{A}$$ $$\wedge$$ $$\text{B}$$ $$\equiv$$ $$\text{B}$$ $$\wedge$$ $$\text{A}$$.
- Comutação: $$\text{A}$$ $$\leftrightarrow$$ $$\text{B}$$ $$\Longleftrightarrow$$ $$\text{B}$$ $$\leftrightarrow$$ $$\text{A}$$.
- Dupla negação: $$\neg$$$$\neg$$$$\text{A}$$ $$\equiv$$ $$\text{A}$$.
- Idempotência: $$\text{A}$$ $$\Longleftrightarrow$$ $$\text{A}$$ $$\wedge$$ $$\text{A}$$.
- Idempotência: $$\text{A}$$ $$\equiv$$ $$\text{A}$$ $$\vee$$ $$\text{A}$$.
- Leis de De Morgan: $$\neg$$$$(\text{A}$$ $$\wedge$$ $$\text{B})$$ $$\Longleftrightarrow$$ $$\neg$$$$\text{A}$$ $$\vee$$ $$\neg$$$$\text{B}$$.
- Leis de De Morgan: $$\neg$$$$(\text{A}$$ $$\vee$$ $$\text{B})$$ $$\equiv$$ $$\neg$$$$\text{A}$$ $$\wedge$$ $$\neg$$$$\text{B}$$.
- Leis de De Morgan: $$(\text{A}$$ $$\wedge$$ $$\text{B})$$ $$\Longleftrightarrow$$ $$\neg$$$$(\neg$$$$\text{A}$$ $$\vee$$ $$\neg$$$$\text{B})$$.
- Leis de De Morgan: $$(\text{A}$$ $$\vee$$ $$\text{B})$$ $$\equiv$$ $$\neg$$$$(\neg$$$$\text{A}$$ $$\wedge$$ $$\neg$$$$\text{B})$$.
- Equivalência Material: $$\text{A}$$ $$\leftrightarrow$$ $$\text{B}$$ $$\Longleftrightarrow$$ $$(\text{A}$$ $$\rightarrow$$ $$\text{B})$$ $$\wedge$$ $$(\text{B}$$ $$\rightarrow$$ $$\text{A})$$.
- Regra de Clavius: $$\neg\text{A}$$ $$\rightarrow$$ $$\text{A}$$ $$\equiv$$ $$\text{A}$$.
- Associação: $$\text{P}$$ $$\wedge$$ $$(\text{Q}$$ $$\wedge$$ $$\text{R})$$ $$\Longleftrightarrow$$ $$(\text{P}$$ $$\wedge$$ $$\text{Q})$$ $$\wedge$$ $$\text{R}$$.
- Associação: $$\text{P}$$ $$\vee$$ $$(\text{Q}$$ $$\vee$$ $$\text{R})$$ $$\equiv$$ $$(\text{P}$$ $$\vee$$ $$\text{Q})$$ $$\vee$$ $$\text{R}$$.
- Distribuição: $$\text{P}$$ $$\wedge$$ $$(\text{Q}$$ $$\vee$$ $$\text{R})$$ $$\Longleftrightarrow$$ $$(\text{P}$$ $$\wedge$$ $$\text{Q})$$ $$\vee$$ $$(\text{P}$$ $$\wedge$$ $$\text{R})$$.
- Distribuição: $$\text{P}$$ $$\vee$$ $$(\text{Q}$$ $$\wedge$$ $$\text{R})$$ $$\equiv$$ $$(\text{P}$$ $$\vee$$ $$\text{Q})$$ $$\wedge$$ $$(\text{P}$$ $$\vee$$ $$\text{R})$$.
- Transposição (Condicional): $$\text{P}$$ $$\rightarrow$$ $$\text{Q}$$ $$\Longleftrightarrow$$ $$\neg\text{Q}$$ $$\rightarrow$$ $$\neg\text{P}$$.
- Implicação Material (Condicional): $$\text{P}$$ $$\rightarrow$$ $$\text{Q}$$ $$\equiv$$ $$\neg\text{P}$$ $$\vee$$ $$\text{Q}$$.
- Exportação: $$(\text{P}$$ $$\wedge$$ $$\text{Q})$$ $$\rightarrow$$ $$\text{R}$$ $$\Longleftrightarrow$$ $$\text{P}$$ $$\rightarrow$$ $$(\text{Q}$$ $$\rightarrow$$ $$\text{R})$$.
- Método de demonstração por absurdo: $$\text{P}$$ $$\wedge$$ $$\neg\text{Q}$$ $$\rightarrow$$ $$\text{R}$$ $$\equiv$$ $$\text{P}$$ $$\rightarrow$$ $$\text{Q}$$.
- Regra de Exportação-Importação: $$(\text{P}$$ $$\wedge$$ $$\text{Q}$$ $$\rightarrow$$ $$\text{R})$$ $$\Longleftrightarrow$$ $$(\text{P}$$ $$\rightarrow$$ $$(\text{Q}$$ $$\rightarrow$$ $$\text{R}))$$.
O leitor está convidado a verificar a veracidade destas propriedades.
O que você aprendeu
Este artigo teve como meta apresentar ao leitor um conceito, conhecido como equivalência lógica, e suas propriedades importante na lógica proposicional e fundamental para a continuação deste tema. Especificamente, você aprendeu:
- O que é uma equivalência.
- Como descobrir se duas fórmulas são equivalentes.
- A equivalência é reciproca.
- Algumas propriedades da equivalência.
- As equivalências mais comuns em provas.
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.
ALMEIDA, M; OLIVEIRA, R; MARIANO, F. Raciocínio Lógico e Matemática para Concursos Cespe/UnB: Teoria e Questões Resolvidas. 1. ed. Rio de Janeiro: Elsevier, 2013. 201 p.
COPPIN. B. Inteligência Artificial. 1. ed. Rio de Janeiro: LTC, 2013. 635p.
FILHO, E. A. Iniciação à Lógica Matemática. 1. ed. São Paulo: Nobel, 2002. 204 p.
GERSTING, J. L. Fundamentos Matemáticos para a Ciência da Computação. 3. ed. Rio de Janeiro: LTC, 1995. 518 p.
Para citar esse artigo:
Comentários
Postar um comentário