3-CNF（three-conjunctive normal form，三合取范式）指一种布尔公式的标准形式：公式是若干个子句（clauses）的合取（AND），且每个子句是恰好三个文字（literals）的析取（OR）（有时也写作“至多三个”取决于教材约定）。它在计算复杂性理论中很常见，尤其用于研究 3-SAT 问题。
/θriː siː ɛn ɛf/
A 3-CNF formula has clauses with three literals.
3-CNF 公式的每个子句包含三个文字。
To reduce a problem to 3-SAT, we often convert the original Boolean expression into an equivalent 3-CNF form.
为了把一个问题归约到 3-SAT，我们常把原始布尔表达式转换成等价的 3-CNF 形式。
CNF 来自逻辑学术语 Conjunctive Normal Form（合取范式），表示“用 AND 连接若干子句”的规范写法；前缀 3- 表示对子句大小的限制：每个子句由三个文字通过 OR 连接而成。这种记法在计算机科学（尤其是可满足性与 NP 完全性证明）中被广泛采用。
Select Language