como convertemos (a ∧ b) ↔ c na forma CNF?
Depois de fazer uma tabela de verdade, o que eu descobri foi:
(¬ (a ∧ b) ∨ c) ∧ ((a ∧ b) ∨ c) ∧ ((a ∧ b) ∨ ¬ c)
Mas agora acho difícil converter isso em CNF. Não tenho ideia de como mudar o ∧ de modo que se tornem ∨ dentro das cláusulas.
O que estou fazendo é usar o (a ∧ b) ec para formar o CNF. Mas isso não está me levando a lugar nenhum.
Consultei meus colegas de curso, que disseram que eu deveria usar a, be c para formar o CNF. Acho que eles estão certos, mas não sei por que estou errado.
Devo usar apenas as proposições atômicas, em vez de usar a proposição composta? É por isso que estou batendo em uma parede de tijolos aqui?
Se eu usar as proposições atômicas, isso não seria um significado diferente do que usar a proposição composta (a ∧ b)?
Por favor ajude. Muito obrigado.
Respostas
$(a\land b)\leftrightarrow c$ torna-se $$(a\land b\land c)\lor(\neg a\land\neg c)\lor(\neg b\land\neg c)$$Este é o DNF. Para obter o CNF, distribuímos OR sobre AND, removendo combinações que contêm coisas como$a\lor\neg a$ e cláusulas contidas em outras cláusulas: $$(a\lor\neg c)\land(b\lor\neg c)\land(c\lor\neg a\lor\neg b)$$