formula - 如何将公式转换为 CNF？

Question

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

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

Answer 1

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

1. 写一个真值表（只有当公式计算为假时，这些术语才相关）
2. 在真值表的每个术语中反转所有文字
3. 将结果项作为CNF子句

这个秘诀可以如下合理化：
没有一个子句必须是假的，除非整个表达式是假的。因此，每个子句都表示倒置表达式的一个最小项。为了确保这个术语是假的，任何反转的文字都不能是真的。

对于 n 个输入变量，真值表有 2^n 个项。因此，这种方法只适用于小表达式。

使用示例公式演示这些步骤

((x or y) 而不是 z) 暗示 w

真值表（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。

从卡诺图可以清楚地看出，这三个假词是如何合并成两个子句的：

             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 |
      +---+---+---+---+