析取范式

DNF 把布尔条件整理成“成功方案清单”：每个项给出一组足以让公式为真的条件，外层析取表示满足其中一组即可。完全 DNF 进一步把每个变量的真假都写进项中，相当于把真值表中为真的行逐行抄成公式。由于任意真值表都能这样表示，$\mathrm{\neg },\wedge ,\vee$ 足以表达任意布尔函数。

合取范式公理库合取范式Conjunctive normal form · CNF由文字的析取形成子句，再对这些子句取合取所得的命题公式形状。（CNF）则像“约束清单”，所有子句都必须通过。这个结构差别影响判定方法：DNF 只要有一个不含矛盾的项就可满足；CNF 只要每个子句都永真，整个公式就永真。反过来判定 DNF 的永真性或 CNF 的可满足性，就需要处理各项或各子句之间的组合。

$(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\wedge q)\vee p$ 中，第一项的所有满足赋值都已被 $p$ 覆盖，因此整个公式可吸收为 $p$。

若一项同时含 $p$ 与 $\mathrm{\neg }p$，它恒假，可以整项删除。单个文字本身也可看作只有一个项、一个文字的 DNF；空合取项表示真，空析取表示假。这些约定把常量和退化情况一同纳入定义。

给定 DNF，若变量已编号为 $1,\dots ,N$，并可按编号常数时间访问标记表，就能逐项检查是否含互补文字。表中记录本项见过的正、负文字；一项结束后，只清除该项访问过的表项。以文字记录与项分隔符总数 $L$ 计输入长度，并假设 $N\le L$，初始化和整次扫描共需 $O(L)$ 时间：找到一个不含矛盾的项即判为可满足。转换的成本却可能很高：当 $n\ge 1$ 且这 $2n$ 个变量两两不同时，公式 $(p_1\vee q_1)\wedge \cdots \wedge (p_n\vee q_n)$ 的任何只使用原变量的等价 DNF 都至少需要 $2^n$ 个项。它有 $2^n$ 个极小满足赋值，每对变量恰有一个为真；一个可满足且保证原公式成立的合取项，必须在每一对中选定至少一个正文字，所以至多覆盖其中一个极小满足赋值。

可满足性容易判定，并不意味着满足赋值的精确计数也容易：不同项可能覆盖同一个赋值。不过，显式 DNF 的每项大小已知且易于抽样，随机近似计数公理库DNF 计数的覆盖抽样算法DNF approximate counting · Karp–Luby coverage algorithm在带项标签的样本空间中均匀抽样，为每个满足赋值保留唯一代表，从而在严格多项式时间内以高概率近似 DNF 的满足赋值数。可以在带项标签的样本中为每个赋值只保留一个代表，从而得到控制相对误差和失败概率的 FPRAS。

即使放宽为“等可满足”，若能在多项式时间内把任意命题公式转换成 DNF，结合上述线性判定算法，就会得到 $\mathrm{P}=\mathrm{NP}$。在通常采用的 $\mathrm{P}\ne \mathrm{NP}$ 假设下，因此不存在这样的转换。

公式 $P\leftrightarrow Q$ 的完全 DNF 是

固定变量集后，完全 DNF 由真值表中为真的行决定，除项与项内文字的排列外是唯一的。一般 DNF 则可以省略无关变量、合并条件，存在许多等价写法；寻找最小表示是另一项计算任务，Quine–McCluskey 等方法针对的正是这种化简。

DNF 适合表示按情形列出的条件。规则引擎中，一项可以表示一条规则的触发条件；数据库查询中，一项可以表示一组同时满足的筛选要求。一个满足赋值只要命中其中一个自洽项，就为公式可满足公理库可满足公式Satisfiable formula存在至少一个真值赋值使其为真的命题公式。提供了直接见证。

在布尔电路公理库布尔电路Boolean circuit由逻辑门构成的有限无环有向图，计算布尔函数。中，各合取项可由 AND 门计算，再用一个 OR 门汇总；若否定文字已作为输入提供，这就是两层 AND-OR 结构。逻辑最小化通过删除冗余项、合并条件等方式减少所需的门与输入连接。

DNF 与 CNF 经 De Morgan 律在否定下互换：否定一个 DNF 会把外层析取变成合取、内层合取变成析取。这使一类范式中的化简与判定问题，可以转为另一类范式中的对偶问题。