CNF

Definition / 释义

CNF 是 Conjunctive Normal Form 的缩写，常译为合取范式：在命题逻辑/布尔逻辑中，把公式写成若干个“子句（clause）”用 AND（∧） 连接的形式；每个子句内部通常是若干个“文字（literal）”用 OR（∨） 连接（如 \((A \lor \lnot B) \land (C \lor D)\)）。该术语在可满足性问题（SAT）、自动定理证明、计算复杂性等领域非常常见。

Pronunciation / 发音

/si en f/

Examples / 例句

Please convert the expression into CNF.
请把这个表达式转换成合取范式（CNF）。

In SAT solving, representing constraints in CNF makes it easier to apply standard algorithms.
在 SAT 求解中，把约束表示成 CNF 往往更便于使用标准算法。

Etymology / 词源

CNF 来自术语 Conjunctive Normal Form 的首字母缩写：conjunctive 表示“合取（用 AND 连接）”，normal form 表示“规范形式/标准形式”，强调把逻辑公式化为一种便于分析与计算的固定结构。

Related Words / 相关词

• Clause
• Literal
• DNF
• SAT
• Satisfiability
• Boolean
• Normal Form
• Implication

Literary Works / 文学与著作例证

• Introduction to the Theory of Computation（Michael Sipser）：在计算理论与复杂性章节中讨论与 CNF-SAT 相关的概念。
• Computers and Intractability: A Guide to the Theory of NP-Completeness（Garey & Johnson）：NP 完全性经典著作中常出现 CNF、CNF-SAT 等表述。
• Computational Complexity（Christos H. Papadimitriou）：涉及可满足性与规范形式表示时会用到 CNF。