Utilizando álgebra das proposições, encontre a expressão equivalente que é composta apenas por conectivos e (^) ou negação (~)
Passo 1
O enunciado dá a fórmula
e pede uma expressão logicamente equivalente que use apenas os conectivos
(e) e
(negação).
Ou seja: transformar a fórmula passo a passo até obter algo que contenha só e
.
Ou seja: transformar a fórmula passo a passo até obter algo que contenha só
Passo 2
Simplificar o membro esquerdo
. Há uma lei muito útil chamada lei da absorção que diz
Demonstração rápida por álgebra booleana: usando distributividade,
Como
, isso dá
e pela absorção (ou observando que
) concluímos
Intuição simples: se
é verdadeiro, a conjunção é verdadeira; se
é falso, a conjunção é falsa — logo é equivalente a
.
Passo 3
Simplificar o membro direito
. Pela lei da absorção (versão dual),
Uma demonstração: por distributividade
. Intuitivamente, se
já é verdadeiro, a disjunção vale
; se
é falso, então
também é falso — logo a disjunção é equivalente a
.
Passo 4
Com as simplificações dos dois lados, a fórmula original vira
Agora usamos a equivalência padrão da implicação:
Aplicando a
obtemos
Passo 5
Ainda resta a disjunção
. Para eliminar
usamos a forma de De Morgan:
Tomando
e
temos
Como
, isso se simplifica para
Essa expressão usa apenas
e
, como exigido.