Questão de Lógica Proposicional: Conversão para Forma Normal Conjuntiva (CNF)

Resolução Completa para CNF

Vou mostrar a resolução passo a passo, assumindo uma fórmula típica como exemplo (já que a imagem não foi transcrita). O processo é geral e aplicável.

Passo 1: Eliminar Implicações

• Se houver setas (→), substitua por: A → B ≡ ¬A ∨ B.
• Exemplo: Se a fórmula tem D → b0, transforme em ¬D ∨ b0.

Passo 2: Empurrar Negativas (Leis de De Morgan)

• Use ¬(A ∧ B) ≡ ¬A ∨ ¬B e ¬(A ∨ B) ≡ ¬A ∧ ¬B.
• Exemplo: Se tem ¬(D ∧ b1), vira ¬D ∨ ¬b1.
• Continue até todas as negações estarem em literais (variáveis ou suas negações).

Passo 3: Distribuir Disjunções sobre Conjunções

• Aplique a lei: A ∨ (B ∧ C) ≡ (A ∨ B) ∧ (A ∨ C).
• Exemplo: Se tem (¬D ∨ b0) ∨ (b1 ∧ b2), distribua para obter (¬D ∨ b0 ∨ b1) ∧ (¬D ∨ b0 ∨ b2).
• Repita até a fórmula ser uma conjunção de cláusulas (disjunções de literais).

Passo 4: Resultado Final

• CNF é uma conjunção (∧) de cláusulas, onde cada cláusula é uma disjunção (∨) de literais.
• Exemplo de CNF: (¬D ∨ b0) ∧ (¬D ∨ ¬b1) ∧ (b1 ∨ b2).

Análise

• Conceito-chave: CNF é essencial para algoritmos de resolução e SAT solvers.
• Dica: Sempre verifique se a fórmula está totalmente simplificada.

Conclusão

A resolução segue esses passos sequenciais. Para uma fórmula específica da imagem, aplique-os diretamente.