析取范式

DNF 把布尔条件整理成"成功方案清单"：每个项描述一组足以让公式为真的条件，外层析取表示诸方案任选其一；完全 DNF 的每个 minterm 才会把所有变量的真假逐一写全。完全 DNF 就是把真值表"为真的行"逐行抄录成公式，因此它的存在性同时说明一件更深的事：$n$ 变量的任何布尔函数都能只用 $\mathrm{\neg },\wedge ,\vee$ 表达——这三个连接词在语义上是完备的。与合取范式公理库合取范式Conjunctive normal form · CNF由若干析取子句之合取构成且与原公式逻辑等价的标准形。的对偶值得并置记忆：CNF 是"约束清单"、逐条都得过，DNF 是"方案清单"、命中一条即可；相应地，DNF 看可满足性容易（有一个自洽的项就行），看永真性难，而 CNF 恰好反过来——同一个公式的两种范式各暴露一半信息。

析取范式把命题公式写成若干“完整或部分条件模式”的并：每个合取项描述一种使公式成立的局部赋值条件，外层析取收集所有成功模式。真值表能机械地产生主析取范式，但结果可能指数膨胀；逻辑等价变形可得到更短的 DNF。

$(p\wedge q)\vee (\mathrm{\neg }p\wedge r)$ 已是 DNF，可读作"要么 $p,q$ 同真，要么 $p$ 假而 $r$ 真"。把 $p\wedge (q\vee r)$ 分配为 $(p\wedge q)\vee (p\wedge r)$ 是最小的转换实例。化简规则：同时含 $p$ 与 $\mathrm{\neg }p$ 的项恒假，可整项删除；被别的项吸收的冗余项（如 $(p\wedge q)\vee p$ 中的 $p\wedge q$）可由吸收律去掉。退化约定与 CNF 对偶：空项（零个文字的合取）恒真，空析取恒假。

边界之一是可满足性判定的"免费午餐"错觉：给定 DNF，判满足只需扫一遍看是否存在不含互补文字的项，线性时间；但这不与 SAT 的难度矛盾——把任意公式转成等价 DNF 本身可能指数爆炸，例如 $(p_1\vee q_1)\wedge \cdots \wedge (p_n\vee q_n)$ 的任何等价 DNF 都需要 $2^n$ 个项，难度只是从判定转移到了转换。之二，与 CNF 不同，目前没有已知的 Tseitin 式多项式转换能把任意公式变成等可满足的 DNF；若这种转换能在多项式时间内产出多项式规模的结果，配合线性判定就会推出 $\mathrm{P}=\mathrm{NP}$，所以"不存在"只能在通常的 $\mathrm{P}\ne \mathrm{NP}$ 假设下断言。之三，完全 DNF 的唯一性依赖"包含全部变量"的规格，一般 DNF 远非唯一，最小化 DNF 表示（如 Quine–McCluskey 过程的目标）是另一个独立且计算上困难的问题。

公式 $P\leftrightarrow Q$ 的 DNF 可写为

公式 $P\vee (P\wedge Q)$ 可吸收为 $P$，说明 DNF 不唯一。空析取通常表示假，空合取表示真；若只要求“析取的合取项”，单个文字和常量也应按约定纳入。

DNF 是"按情形罗列"型知识的天然载体：规则引擎的决策条件、数据库查询的筛选谓词、模式匹配的分支穷举都以 DNF 形态书写；可满足公式公理库可满足公式Satisfiable formula存在至少一个真值赋值使其为真的命题公式。的一个满足赋值恰对应 DNF 中某个自洽项给出的"成功证书"。在电路侧，完全 DNF 对应两层的 AND-OR 结构（可编程逻辑阵列的积之和形式），是布尔电路公理库布尔电路Boolean circuit由逻辑门构成的有限无环有向图，计算布尔函数。综合的起点，随后的逻辑最小化以它为原料；复杂性理论中"多项式规模 DNF 表达能力有限"是电路下界研究的入门事实。理论上，DNF 与 CNF 经 De Morgan 律在否定下互换（$\mathrm{\neg }$ 把一种范式的标准形变为另一种），这一对偶贯穿布尔代数的表示理论。

真值表给出构造主 DNF 的算法，逻辑等价保证变形保持语义。DNF 用于规则系统、数据库查询和布尔函数最小化；与合取范式对偶，但 SAT 求解通常更偏好 CNF。