合取范式 (CNF) 是命题公式的标准化表示法,规定每个公式都应写为析取的合取。每个 bool 公式都可以转换为 CNF。例如:
A | (B和C)
在 CNF 中的表示如下:
(A | B) & (A | C)
用 CNF 编写条件是编程的最佳实践吗?
最佳答案
不,这不是一个好主意。 Conjunctive normal form主要用于理论计算机科学。有求解 CNF 公式的算法,以及时间复杂度和 NP 难度的证明。
从实用的角度来看,您应该使用最“自然”描述逻辑的 bool 运算符来编写代码。这意味着充分利用嵌套表达式、XOR、否定等运算符。正如您所举的例子,CNF 经常与“自然性”这一目标相矛盾,因为表达式较长并且经常重复子表达式。
作为理论上的旁注,在最坏的情况下,包含 n 个运算符的无限制 bool 公式可以转换为长度以 n 为指数的 CNF 公式。因此,CNF 可能会极大地破坏公式。一系列示例说明了这种行为:
- (A 和 B)| (C & D) ==
(A | C)和(A | D)和(B | C)和(B | D)。 - (A 和 B)| (C & D) | (E & F) ==
(A | C | E) & (A | C | F) & (A | D | E) & (A | D | F) & (B | C | E) & (B | C | F) & (B | D | E) & (B | D | F)。 - (A 和 B)| (C & D) | (E 和 F)| (G & H) ==
(A | C | E | G) & (A | C | E | H) & (A | C | F | G) & (A | C | F | H) & (A | D | E | G) & (A | D | E | H) & (A | D | F | G) & (A | D | F | H) & (B | C | E | G) & (B | C | E | H) & (B | C | F | G) & (B | C | F | H) & (B | D | E | G) & (B | D | E | H) & (B | D | F | G) & (B | D | F | H)。
关于logic - 连取范式的书写条件,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36358673/