Quando
, em que
é uma proposição composta?
Passo 1
O enunciado pergunta: “Quando vale
, sendo
uma proposição composta?” Aqui o conteúdo é o de dualidade em lógica proposicional. Para resolver, precisamos lembrar a definição de dual de uma fórmula e depois ver em que situação ele coincide com a própria fórmula.
Passo 2
Definição de dual. Seja
uma fórmula construída com os conectivos
e possivelmente as constantes
. O dual
de
obtém-se trocando
sem alterar as letras proposicionais nem as negações que já estavam em
.
Passo 3
Caracterização de
. Pedir
significa que, após fazer todas as trocas acima, a fórmula resultante é exatamente (ou, em lógica, equivalente a) a fórmula original. Dizemos então que
é auto-dual.
Passo 4
Condição na tabela-verdade. Em termos de função booleana
correspondente a
, ser auto-dual equivale a
para todo vetor de entradas
. Pela definição de dual, isso equivale a
Ou seja, trocar cada entrada por seu oposto e depois negar o resultado dá o mesmo valor original.
Passo 5
Exemplos e observações
- Nenhuma fórmula que use
ou como constante pode ser auto-dual, pois trocar mudaria seu valor. - Fórmulas que usam só negações (e letras) são trivialmente auto-dual, já que não há
a trocar. - Há fórmulas não-triviais self-dual em qualquer número ímpar de variáveis; por exemplo, em duas variáveis não há auto-duais, mas em três já existem.
Resposta
A igualdade
ocorre exatamente quando
é auto-dual, isto é, quando