Converta para CNF as fórmulas abaixo:
Passo 1
O enunciado pede para converter em forma normal conjuntiva (CNF) a fórmula
Vamos usar as equivalências padrões de lógica proposicional: eliminação de implicação, movimentação de negações (De Morgan) e, se necessário, distribuição de
sobre
.
Passo 2
Eliminamos as implicações pela equivalência
Aplicando à fórmula original:
Como
é equivalente a
, ficamos com
Passo 3
Usamos a associatividade e comutatividade da disjunção para agrupar tudo em uma única cláusula:
Passo 4
Observamos que
é uma tautologia (sempre verdadeira). Logo
é equivalente a uma tautologia também.
Passo 5
O CNF de uma fórmula que é tautologia é simplesmente a cláusula verdadeira, que denotamos por
.