boolean - 将查询转换为 CNF

Question

我最近一直在尝试学习逻辑，但我遇到了一个我做不到的查询，我不太确定我哪里出错了。将查询转换为 CNF 时，遇到这种特殊情况会怎么做？

(a AND NOT(b AND c)) AND (d OR e)
= (a AND NOT b) OR (a AND NOT c) AND (d OR e)
=

我将如何重新安排它以使其成为 CNF 形式？我做错了什么吗？

谢谢你的帮助，肖恩

score 0 · Accepted Answer

我使用符号：

^ for AND
v for OR 
~ for NOT

以下是如何在 CNF 中转换公式：

  (a ^ ~(b ^  c)) ^ (d v e)
= (a ^ (~b v ~c)) ^ (d v e)    // DeMorgan:   ~(A ^ B) <=> (~A v ~B)
=  a ^ (~b v ~c)  ^ (d v e)
= CNF

每个子句都由 AND 分隔，并且仅包含 OR。使用您的语法，它给出：

a AND (NOT b OR NOT c) AND (d OR e)

我希望它有帮助:)

1 回答 1