Quando s^{*}=s, em que s é uma proposição composta?

Passo 1

O enunciado pergunta: “Quando vale \,s^* = s, sendo s 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 s uma fórmula construída com os conectivos \land,\lor e possivelmente as constantes \top,\bot. O dual s^* de s obtém-se trocando
\land \longleftrightarrow \lor, \quad \top \longleftrightarrow \bot
sem alterar as letras proposicionais nem as negações que já estavam em s.

Passo 3

Caracterização de s^*=s. Pedir s^*=s 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 s é auto-dual.

Passo 4

Condição na tabela-verdade. Em termos de função booleana f correspondente a s, ser auto-dual equivale a
f(x_1,\dots,x_n)\;=\;f^*(x_1,\dots,x_n)
para todo vetor de entradas (x_1,\dots,x_n). Pela definição de dual, isso equivale a
f(x_1,\dots,x_n) \;=\; \neg\,f(\neg x_1,\dots,\neg x_n).
Ou seja, trocar cada entrada por seu oposto e depois negar o resultado dá o mesmo valor original.

Passo 5

Exemplos e observações
  1. Nenhuma fórmula que use \top ou \bot como constante pode ser auto-dual, pois trocar \top\leftrightarrow\bot mudaria seu valor.
  2. Fórmulas que usam só negações (e letras) são trivialmente auto-dual, já que não há \land,\lor,\top,\bot a trocar.
  3. 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 \;s^* = s\; ocorre exatamente quando s é auto-dual, isto é, quando
s(p_1,\dots,p_n)\;\equiv\;\neg\,s(\neg p_1,\dots,\neg p_n).

Exercícios de Livros Relacionados