布尔函数，DNF和CNF的作用是什么？

Question

布尔函数可以用析取范式(DNF)或合取范式(CNF)表示。有人能解释为什么这些表单很有用吗？

Answer 1

CNF很有用，因为这种形式直接描述了布尔SAT问题，虽然是NP完全的，但有许多不完整和启发式的指数时间求解器。CNF已进一步标准化为一种称为"DIMACS CNF file format“的文件格式，大多数求解器都可以使用该格式进行操作。因此，例如，芯片行业可以通过转换为DIMACS CNF并馈送到任何可用的求解器来验证其电路设计。Tseitin Transformation可以将电路转换为可均衡化的CNF。

DNF在实践中没有那么有用，但将公式转换为DNF意味着可以看到满足该公式的可能赋值的列表。不幸的是，通常情况下，将公式转换为DNF是困难的，并且可能导致指数爆炸(非常大的DNF)，这是显而易见的，因为一个公式可以有指数级的令人满意的赋值。

虽然与DNF相比，CNF可以是简洁的，但有时很难进行推理，因为例如，从电路转换时，它可能会失去结构，因此另一种简洁的形式将是有用的。and-inverter graph数据结构就是为此目的而设计的；它可以更紧密地模拟电路的结构，因此在某些类型的公式中更容易推理。然而，没有多少求解器对其进行操作。

其他形式包括：

维基百科(

• Binary Decision Diagram
• Propositional directed acyclic graph
• Negation normal form
• Others )

Answer 2

它有助于以某种标准的方式表达函数。有了它，就更容易自动完成许多算法。

例如，这两种形式都可以用于自动定理求解，即解析方法中的CNF。