如何将公式转换为 CNF？

Question

我知道将公式转换为 CNF 的 4 条规则，但我不太确定如何将它们应用于此公式 ((x v y) ^ ¬ z) ->w

有人可以帮我解释一下吗？谢谢！

Answer 1

将表达式转换为 CNF
的方法将公式转换为 CNF 的一种方法是：

写一个 truth table（只有公式计算结果为 false 的条件才相关）
在 truth table 的每个术语中反转所有文字
将结果项作为CNF个子句

这个食谱可以按如下方式合理化：
None 的子句必须为假，除非整个表达式为假。因此，每个子句都代表倒置表达式的一个最小项。为确保此项为假，none 的倒置文字可以为真。

对于 n 个输入变量，一个真值 table 有 2^n 项。所以这个方法只对小表达式实用

使用示例公式演示步骤

((x or y) and not z) implies w

真相table（F=表达式值）：

wxyz|F
----+-
0000|1
1000|1
0100|0
1100|1
0010|0
1010|1
0110|0
1110|1
0001|1
1001|1
0101|1
1101|1
0011|1
1011|1
0111|1
1111|1
----+-

错误项 (F = 0)：

wxyz|F
----+-
0100|0
0010|0
0110|0
----+-

反转文字并省略输出列：

wxyz
----
1011
1101
1001
----

结果 CNF 个子句：

(w or !x or y or z) and (w or x or !y or z) and (w or !x or !y or z)

生成的 CNF 个子句通过合并子句最小化：

(w or !x or z) and (w or !y or z)

如有疑问，可以询问Wolfram|Alpha。

从 Karnaugh map 可以清楚地看出如何将三个假项合并为两个子句：

             wx
       00  01  11  10
      +---+---+---+---+
   00 | 1 | 0 | 1 | 1 |
      +---+---+---+---+
   01 | 1 | 1 | 1 | 1 |
yz    +---+---+---+---+
   11 | 1 | 1 | 1 | 1 |
      +---+---+---+---+
   10 | 0 | 0 | 1 | 1 |
      +---+---+---+---+

如何将公式转换为 CNF？

How to convert formula to CNF?

boolean-logic

formula

conjunctive-normal-form