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

Question

如何将此等式转换为CNF？

¬((p ? ¬Q) ? R) ? (P ? R))

Answer 1

要将命题公式转换为合取范式,请执行以下两个步骤:

1. 将否定推入公式,反复应用德摩根定律,直到所有否定仅适用于原子.您获得了否定正规形式的公式.

   • ¬(p ? q) 至 (¬p) ? (¬q)

   • ¬(p ? q) 至 (¬p) ? (¬q)

2. 在结合处发生分离的情况下,反复应用分配法.一旦这不可能,公式就在CNF中.

   • p ? (q ? r) 至 (p ? q) ? (p ? r)

要获得析取范式的公式,只需在步骤2中应用?over 的分布?.

请注意 ?

?问题中使用的子集符号()只是逻辑蕴涵/蕴涵的替代符号,通常写为箭头(?).

Answer 2

http://en.wikipedia.org/wiki/Conjunctive_normal_form

将一阶逻辑转换为 CNF：

1. 转换为否定范式。
   1. 消除影响：转换 x ? y 到 ¬ x ? 是
   2. 向内移动 NOT。
2. 标准化变量
3. 对声明进行修改
4. 删除全称量词
5. 在 OR 上分布 AND。

（人工智能：现代方法 [1995...] Russel 和 Norvig）