Conjunctive Normal Form

释义 Definition

合取范式（CNF）：一种将布尔逻辑公式写成标准结构的形式，即把公式表示为若干“子句（clause）”的合取（AND）；而每个子句通常是若干文字（literal）的析取（OR）。常见形式为：
[ (C_1) \land (C_2) \land \cdots \land (C_n) ] 其中每个 (C_i) 形如 ((x \lor \lnot y \lor z))。在可满足性问题（SAT）与自动推理中非常常用。（也存在如 3-CNF 等限制形式。）

发音 Pronunciation (IPA)

/kənˈdʒʌŋktɪv ˈnɔːrməl fɔːrm/

例句 Examples

The formula is already in conjunctive normal form.
这个公式已经是合取范式了。

To use a SAT solver, we first convert the constraints into conjunctive normal form so they can be processed as a set of clauses.
为了使用 SAT 求解器，我们先把约束转换为合取范式，这样就能以一组子句的形式进行处理。

词源 Etymology

conjunctive 来自 conjunction（“连接、合取”），源于拉丁语中表示“连接在一起”的词根；在逻辑里指用 AND（∧） 把多个部分“合在一起”。
normal form（“范式/标准形”）是数学与逻辑中的常见术语，指把表达式化为统一、便于处理的标准结构。合起来，conjunctive normal form 就是“用合取连接的标准形式”。

相关词 Related Words

• Boolean Formula
• Clause
• Literal
• Conjunction
• Disjunction
• Disjunctive Normal Form
• Satisfiability
• SAT Solver
• Resolution
• 3-CNF

文学与著作中的用例 Notable Works

• Logic in Computer Science: Modelling and Reasoning about Systems（Michael Huth & Mark Ryan）——在命题逻辑与自动证明部分讨论 CNF、子句与归结法。
• Artificial Intelligence: A Modern Approach（Stuart Russell & Peter Norvig）——在知识表示、推理与可满足性相关内容中使用 CNF 的表述。
• Computational Complexity（Christos H. Papadimitriou）——在 NP 完全性与 SAT 归约中常出现 CNF/3-CNF。
• Handbook of Satisfiability（Armin Biere 等编）——以 CNF 作为 SAT 求解的核心输入表示之一。