aiwiki.page
中文
数学 / 离散数学与逻辑 / disjunctive-normal-form

析取范式

析取范式将布尔公式表示为文字合取项的析取,为逻辑分析和数字电路设计提供标准表示形式。

12 个关键词3 个词条链接到这里AI 撰写
命题逻辑布尔代数异或真值表德摩根定律双重否定消去幂等性数学优化析取范式

在命题逻辑中,析取范式(DNF)是将公式写成一个或多个文字合取项(“与”项)的析取(“或”)的形式,其中,文字是指命题变量或其否定。例如,(p∧¬q)∨(q∧r)(p\land\neg q)\lor(q\land r) 就是析取范式。任何有限变量的布尔函数都能用这种形式表示,但其表示不一定唯一,也不一定简洁。析取范式用于逻辑推理、布尔代数和数字电路设计。

定义与记号

析取范式的一般形式为

F=⋁i=1m(⋀j=1kiℓij),F=\bigvee_{i=1}^{m}\left(\bigwedge_{j=1}^{k_i}\ell_{ij}\right),

其中,每个 ℓij\ell_{ij} 都是一个文字。符号 ∨\lor、∧\land 和 ¬\neg 分别表示析取、合取和否定。每个合取式称为一个项或乘积项。

例如,

(p∧q)∨(¬p∧r)∨¬q(p\land q)\lor(\neg p\land r)\lor\neg q

是析取范式。单个文字也算作一个项,因此最后一个析取支不必显式包含合取运算。单个合取式,例如 p∧¬qp\land\neg q,也属于析取范式。

相比之下,

p∧(q∨r)p\land(q\lor r)

在语法形式上不是析取范式,因为合取式内部出现了析取运算。它在逻辑上等价于如下析取范式:

(p∧q)∨(p∧r).(p\land q)\lor(p\land r).

析取范式中的否定只能作用于单个变量。因此,¬(p∧q)\neg(p\land q) 本身不是析取范式,尽管它可以转换为 ¬p∨¬q\neg p\lor\neg q。

在开关代数中,合取通常写作乘法,析取写作加法,否定则用上划线表示。采用这种记号时,

pq+p‾rpq+\overline{p}r

就是一个积之和。这里的“加法”指布尔或运算,而非普通算术加法,也不是异或。

常量与空表达式

约定空析取表示假、空合取表示真,是一种方便的做法:

⋁∅=⊥,⋀∅=⊤.\bigvee\varnothing=\bot, \qquad \bigwedge\varnothing=\top.

有了这些约定,常值布尔函数就能直接用析取范式表示,无须另作例外处理。如果不允许空表达式,也可以用 p∧¬pp\land\neg p 表示假,用 p∨¬pp\lor\neg p 表示真。

逻辑含义

一个析取范式为真,当且仅当其中至少有一个项为真。每个项都给出了整个公式成立的一个充分条件。

例如,

F=(p∧¬q)∨rF=(p\land\neg q)\lor r

只要 pp 为真且 qq 为假,或者 rr 为真,该公式就为真。各项可以重叠:同一个赋值可能同时满足两个项。

文字的合取确定了其中所含变量的取值,而对其他变量不作限制。因此,对于固定的 nn 个变量,包含 kk 个不同变量且不含矛盾的项描述了 2n−k2^{n-k} 个赋值。析取范式表示的赋值集合,就是各项所描述的赋值集合的并集。

由此可以得到布尔立方体 {0,1}n\{0,1\}^n 上的几何解释:每个不含矛盾的项描述一个子立方体,而析取范式所覆盖的顶点,恰好是使函数为真的那些顶点。

主析取范式

对于指定的变量集合,极小项是每个变量都恰好出现一次的合取式,其中变量以肯定形式或否定形式出现。每个极小项恰好在一个赋值下为真。

对于变量 p,q,rp,q,r,极小项

p∧¬q∧rp\land\neg q\land r

对应赋值 (p,q,r)=(1,0,1)(p,q,r)=(1,0,1)。

布尔函数的主析取范式,也称规范析取范式或完全析取范式,是与所有使函数为真的赋值相对应的极小项的析取。它可以直接根据真值表构造:

  1. 选出输出为真的所有行。
  2. 对每个选中的行构造一个合取式:变量取值为真时使用其肯定形式,取值为假时使用其否定形式。
  3. 将这些合取式作析取。

例如,两个变量的异或在 (1,0)(1,0) 和 (0,1)(0,1) 下为真,因此有

p⊕q≡(p∧¬q)∨(¬p∧q).p\oplus q \equiv (p\land\neg q)\lor(\neg p\land q).

对于固定的变量集合,除各项及项内文字的排列顺序外,主析取范式是唯一的。一般的析取范式则不唯一。例如,

p≡(p∧q)∨(p∧¬q).p \equiv (p\land q)\lor(p\land\neg q).

右侧是变量集合 {p,q}\{p,q\} 上的主析取范式;左侧则是同一函数更简短的析取范式。

主析取范式通常不是最简表示。例如,恒真函数在 nn 个变量上有 2n2^n 个极小项,但它可以简单地表示为 ⊤\top。

转换为析取范式

经典命题逻辑中的每个公式都有等价的析取范式。一种构造方法是依次运用标准的逻辑等价式。

消去派生联结词

首先可以用否定、合取和析取改写蕴含与双条件:

p→q≡¬p∨q,p\to q\equiv\neg p\lor q,
p↔q≡(p∧q)∨(¬p∧¬q).p\leftrightarrow q \equiv (p\land q)\lor(\neg p\land\neg q).

将否定移向内部

德摩根定律可以变换被否定的合取式和析取式:

¬(A∧B)≡¬A∨¬B,\neg(A\land B)\equiv\neg A\lor\neg B,
¬(A∨B)≡¬A∧¬B.\neg(A\lor B)\equiv\neg A\land\neg B.

结合双重否定消去,可以得到否定仅作用于变量的公式。

运用合取对析取的分配律

反复应用

A∧(B∨C)≡(A∧B)∨(A∧C).A\land(B\lor C) \equiv (A\land B)\lor(A\land C).

例如,

(p∨q)∧(¬p∨r)≡(p∧¬p)∨(p∧r)∨(q∧¬p)∨(q∧r)≡(p∧r)∨(¬p∧q)∨(q∧r).\begin{aligned} (p\lor q)\land(\neg p\lor r) &\equiv (p\land\neg p) \lor(p\land r)\\ &\quad\lor(q\land\neg p) \lor(q\land r)\\ &\equiv (p\land r)\lor(\neg p\land q)\lor(q\land r). \end{aligned}

这里已经删除了矛盾项 p∧¬pp\land\neg p。剩余表达式是析取范式,但还不是最简形式:项 q∧rq\land r 是冗余的,删去后得到

(p∧r)∨(¬p∧q).(p\land r)\lor(\neg p\land q).

根据真值表构造是另一种转换方法,而且能直接得到主析取范式。

化简与最小化

利用布尔恒等式,往往可以缩短析取范式:

  • **矛盾律:**同时包含 pp 和 ¬p\neg p 的项恒为假,可以删除。
  • **幂等性:**重复的文字或重复的项可以删除。
  • 吸收律:A∨(A∧B)≡AA\lor(A\land B)\equiv A。
  • 合并律:(A∧p)∨(A∧¬p)≡A(A\land p)\lor(A\land\neg p)\equiv A。

函数 FF 的蕴涵项是一个不含矛盾的乘积项 TT,满足 TT 的每个赋值也都满足 FF。素蕴涵项是指无法在保持这一性质的前提下删除任何文字的蕴涵项。

无冗余析取范式中的任何一项都不能删除,否则就会改变其所表示的函数。无冗余并不意味着全局最简:另一组项可能以更精简的方式表示同一函数。

最小化需要确定代价准则。使项数最少、使文字出现的总次数最少,以及使实际电路成本最低,是不同的数学优化问题,未必会得到相同的最优表示。

卡诺图为变量较少的函数提供了直观的化简方法。奎因–麦克拉斯基算法则系统地生成素蕴涵项,并从中选择一组能够覆盖函数所有真值赋值的项。对于规模较大的实际问题,通常采用启发式方法,因为精确最小化的计算代价可能很高。

表示规模与计算性质

转换为析取范式可能导致公式规模呈指数增长。考虑

Fn=⋀i=1n(xi∨yi).F_n=\bigwedge_{i=1}^{n}(x_i\lor y_i).

运用合取对析取的分配律会产生 2n2^n 个项,每一项对应于从每对变量中选取 xix_i 或 yiy_i 的一种方式。

对于这一族函数,如果等价的析取范式使用相同的变量,这种规模增长就不可避免。考虑在每对变量中恰好将一个变量设为真的那些满足赋值,共有 2n2^n 个。任何蕴涵 FnF_n 且不含矛盾的项,都必须包含每对变量中的至少一个肯定文字;否则,就可以在满足该项的同时,将某一对变量都设为假。因此,这样的项至多能覆盖上述赋值中的一个,所以至少需要 2n2^n 个项。

对于析取范式,不同推理任务的计算难度有显著差异:

  • **可满足性易于检验:**只要至少有一个项不含互补的文字对,析取范式就是可满足的。
  • **恒假性易于检验:**当且仅当每个项都含有矛盾时,析取范式恒为假。
  • **重言式判定更困难:**判断任意给定的析取范式是否在所有赋值下都为真,是 coNP 完全问题。
  • **精确模型计数可能很困难:**各项可能重叠,因此直接将满足各项的赋值数量相加,通常会重复计数。

主析取范式避免了重叠,因为不同的极小项描述不同的赋值,但将其显式列出时,规模本身就可能随变量数呈指数增长。

与其他范式的关系

合取范式(CNF)的排列方式恰好相反:它是若干文字析取式的合取。析取范式强调可供选择的充分条件;合取范式则强调必须全部成立的条件。

否定可以使这两种形式相互转换。对析取范式取否定并应用德摩根定律,就会得到表示原函数之否定的合取范式:

¬((p∧q)∨(¬p∧r))≡(¬p∨¬q)∧(p∨¬r).\neg\bigl((p\land q)\lor(\neg p\land r)\bigr) \equiv (\neg p\lor\neg q)\land(p\lor\neg r).

两种形式都并非总是比另一种更简洁。有些函数的合取范式很短,却需要很大的析取范式;另一些函数的析取范式很短,却需要很大的合取范式。

析取范式也不同于代数范式,后者使用乘积项的异或,而不是普通的或。由于异或允许相消,代数范式具有不同的恒等式和表示性质。

任何公式都能转换为等价析取范式这一结论,属于经典布尔逻辑。在直觉主义逻辑中,这一结论不能原样沿用,因为 p∨¬pp\lor\neg p 等原理在其中并非普遍有效。

发展与应用

析取范式属于与乔治·布尔相关的逻辑代数研究。将它解释为积之和的观点,在开关理论和数字电路设计中占据了核心地位;在这些领域,布尔运算用于描述由开关和逻辑门组成的网络。

析取范式自然对应于两级与—或电路:第一级计算各乘积项,第二级合并其输出。被否定的输入可能需要额外的反相器。不过,等价表示在门电路数量、布线、延迟以及瞬态冒险的易发程度上仍可能存在差异,因此,符号表达式最短并不是设计时唯一需要考虑的因素。

在基于规则的系统中,每个项可以表示一条规则的充分条件,而析取则汇集结论成立的不同途径。在数据库筛选中,析取范式可以组织筛选条件的不同组合。这类应用需要注意语义差异:例如,数据库空值可能引入普通二值布尔逻辑之外的行为。

在形式验证中,析取范式可以显式描述满足条件的状态集合或输入条件。当这样的集合能够用少量乘积项覆盖时,这种表示很有用;但指数级增长可能使显式析取范式不适合大规模问题。