math - 如何将命题公式转换为合取范式(CNF)？

Question

已关闭。这个问题是 not about programming or software development 。目前不接受答案。

---

这个问题似乎不是关于 a specific programming problem, a software algorithm, or software tools primarily used by programmers 。如果您认为这个问题与 another Stack Exchange site 上的主题有关，您可以发表评论来解释问题可能在哪里得到解答。

已关闭10 个月前。

社区 10 个月前审核了是否重新开放此问题，并将其关闭:

原始关闭原因未解决

Improve this question

如何将此方程转换为 CNF？

¬((p ∨ ¬Q) ⊃ R) ⊃ (P ∧ R))

Answer 1

转换 propositional formula至 conjunctive normal form ，执行以下两个步骤:

1. 将负数插入公式中，重复应用 De Morgan's Law ，直到所有否定仅适用于原子。您获得 negation normal form 中的公式.

   • Ø(p ∨ q) 到 (Øp) ∧ (Øq)

   • Ø(p ∧ q) 到 (Øp) ∨ (Øq)

2. 重复应用distributive law其中合取发生析取。一旦这不再可能，公式就用 CNF 表示。

   • p ∨ (q ∧ r) 到 (p ∨ q) ∧ (p ∨ r)

要获得析取范式形式的公式，只需在步骤 2 中应用 ∧ 到 ∨ 的分布即可。

关于⊂

的注意事项

问题中使用的子集符号(⊂)只是逻辑蕴涵/蕴涵的替代表示法，通常写为箭头(⇒)。