合取范式 (CNF) 是命题公式的标准化符号,它规定每个公式都应写为析取的合取。每个布尔公式都可以转换为 CNF。例如:
A | (B & C)
在 CNF 中有这样的表示:
(A | B) & (A | C)
在 CNF 中编写条件是编程的最佳实践吗?
合取范式 (CNF) 是命题公式的标准化符号,它规定每个公式都应写为析取的合取。每个布尔公式都可以转换为 CNF。例如:
A | (B & C)
在 CNF 中有这样的表示:
(A | B) & (A | C)
在 CNF 中编写条件是编程的最佳实践吗?
不,这不是一个好主意。合取范式主要用于理论计算机科学。CNF 中有求解公式的算法,以及关于时间复杂度和 NP-hardness 的证明。
从实用的角度来看,您应该使用最“自然”描述逻辑的布尔运算符编写代码。这意味着要充分利用嵌套表达式、XOR、否定等运算符。正如您举例说明的那样,CNF 经常与“自然”这一目标相矛盾,因为表达式更长并且经常重复子表达式。
作为理论方面的说明,在最坏的情况下,包含n 个运算符的不受限制的布尔公式可以转换为长度为n指数的 CNF 公式。因此,CNF 可能会大量破坏公式。说明此行为的一系列示例: