析取正态形式和令人满意的是P（DNFSAT）

Question

我正在读到一种以正常形式进行分离的语言，是P语言中的一种语言，但是没有解释，有人可以告诉我为什么吗？

Answer 1

要使DNF中的表达式为真，您只需要将其单个析取子句正确即可。典型的子句将是a ^ b ^ 〜c或类似的东西，因此您将A和B设置为true，并且C为false。

因此，算法将是：

1. 找到一些不是自相矛盾的析取子句。 （即它同时包含x和〜x）。
2. 如果所有分离的子句都包含一些自相矛盾，则无法满足整个表达式。
3. 如果甚至有一个子句都没有自相矛盾，那么变量的明显分配使该子句是正确的。在这种情况下，整个表达式为真。