Flashcard FC242140
Quais condições uma fórmula deve atender para estar em forma normal conjuntiva (CNF) ou disjuntiva (DNF)?
Outros Exercícios de Lógica
CESGRANRIO · 2010
Quais condições uma fórmula deve atender para estar em forma normal conjuntiva (CNF) ou disjuntiva (DNF)?
Mostrar resposta e comentário
Resposta
CNF: conjunção de disjunções de literais.DNF: disjunção de conjunções de literais.
Além disso, qualquer negação deve incidir apenas sobre literais (não sobre cláusulas).
Explicação:
• Em CNF cada fator é uma cláusula disjuntiva cujos componentes são literais, e a fórmula inteira é uma conjunção dessas cláusulas.
• Em DNF cada termo é uma conjunção de literais, e a fórmula inteira é uma disjunção desses termos.
• Se houver uma negação aplicando-se a uma expressão composta (ex.: ¬(A ∨ B)), a fórmula não está em CNF nem em DNF até que essa negação seja empurrada para os literais (por transformações como De Morgan).
Exemplo (CNF): \( (P \vee \neg R)\wedge(\neg Q \vee R \vee S) \) — conjunção de cláusulas disjuntivas de literais.
Exemplo (DNF): \( (P \wedge Q \wedge \neg R)\vee(\neg P \wedge S) \) — disjunção de conjunções de literais.
Contraexemplo: \( \neg(P \vee Q)\wedge(R\vee S) \) — não está em forma normal enquanto a negação incidir sobre a disjunção.
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/236956
Conteúdo do catálogo FC Concursos · Atualizado em