Questão de Lógica Proposicional (conversão para CNF)

Resultado Final da Conversão para CNF

O aluno pediu o resultado final da fórmula em Forma Normal Conjuntiva (CNF). Vamos mostrar o passo a passo até a expressão final.

Expressão Original

A fórmula dada é: (D ∧ b0) ∨ (¬D ∧ b1) ∨ (¬b0 ∧ b1)

Passos para CNF

1. Distribuir as disjunções sobre as conjunções (usando a lei: A ∨ (B ∧ C) ≡ (A ∨ B) ∧ (A ∨ C)).
2. Aplicar distributividade passo a passo:

• Primeiro, distribuir (D ∧ b0) sobre o restante.
• Depois, distribuir os termos resultantes.

1. Simplificar cláusulas redundantes (ex: (A ∨ ¬A) é sempre verdadeiro).

CNF Final

Após a distribuição e simplificação, a CNF é:

(D ∨ ¬D ∨ ¬b0) ∧ (D ∨ ¬D ∨ b1) ∧ (b0 ∨ ¬D ∨ ¬b0) ∧ (b0 ∨ ¬D ∨ b1) ∧ (D ∨ b1 ∨ ¬b0) ∧ (D ∨ b1 ∨ b1)

Simplificando cláusulas redundantes:

• (D ∨ ¬D ∨ ¬b0) → True (pode ser removida).
• (b0 ∨ ¬D ∨ ¬b0) → True (pode ser removida).
• (D ∨ b1 ∨ b1) → (D ∨ b1).

CNF Simplificada:

(D ∨ ¬D ∨ b1) ∧ (b0 ∨ ¬D ∨ b1) ∧ (D ∨ b1 ∨ ¬b0)

Mas (D ∨ ¬D ∨ b1) é sempre verdadeiro (devido a D ∨ ¬D), então pode ser removido.

CNF Final (mínima):

(b0 ∨ ¬D ∨ b1) ∧ (D ∨ b1 ∨ ¬b0)

Isso pode ser reescrito como:

(¬D ∨ b0 ∨ b1) ∧ (D ∨ ¬b0 ∨ b1)

Esta é a Forma Normal Conjuntiva da expressão original.