在布尔逻辑中，析取范式(DNF)是逻辑公式的标准化（或规范化），它是合取子句的析取。作为规范形式，它在自动定理证明中有用。一个逻辑公式被认为是 DNF 的，当且仅当它是一个或多个文字的一个或多个合取的析取。同合取范式（CNF）一样，在 DNF 中的命题算子是与、或和非。非算子只能用做文字的一部分，这意味着它只能领先于命题变量。

基本内容

析取范式与合取范式

在布尔逻辑中

基本内容

本节给出含n个命题变项的公式的两种规范表示方法。

要求:

了解简单析取式、简单合取式、析取范式、合取范式的概念

深刻理解极小项、极大项的定义，名称、下角标与成真(假)赋值的关系

熟练掌握求主析取(主合取)范式的方法。

会用主析取范式求公式的成真赋值、成假赋值、判断公式的类型、判断两个公式是否等值。

析取范式与合取范式

定义2.2 命题变项及其否定统称作文字。

仅由有限个文字构成的析取式称为简单析取式。

仅由有限个文字构成的合取式称为简单合取式。

例如，文字：p,┐q,r,q.

简单析取式: p,q,p∨q,p∨┐p∨r,┐p∨q∨┐r.

简单合取式: p,┐r,┐p∧r,┐p∧q∧r,p∧q∧┐q.

定理2.1（1）一个简单析取式是重言式当且仅当它同时含某个命题变项及它的否定。

（2）一个简单合取式是矛盾式当且仅当它同时含某个命题变项及它的否定。

定义2.3（1）由有限个简单合取式构成的析取式称为析取范式。

（2）由有限个简单析取式构成的合取式称为合取范式。

（3）析取范式与合取范式统称为范式。

例如，析取范式：（p┐∧q）∨r, ┐p∧q∧r, p∨┐q∨r.

合取范式:(p∨q∨r)∧(┐q∨r), ┐p∧q∧r, p∨┐q∨r.

定理2.2（1）一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式。

（2）一个合取范式是重言式当且仅当它的每个简单析取式都是重言式。

范式的特点：

（1） 范式中不出现联结词→、«，求范式时可消去：

A→Bó┐A∨B

A«Bó(┐A∨B)∧(A∨┐B)

（2）范式中不出现如下形式的公式：

┐┐A, ┐(A∧B), ┐(A∨B)

因为：┐┐AÛA

┐(A∧B)Û┐A∨┐B

┐(A∨B)Û┐A∧┐B

（3）在析取范式中不出现如下形式的公式：

A∧(B∨C)

在合取范式中不出现如下形式的公式：

A∨(B∧C)

因为：A∧(B∨C)Û(A∧B)∨(A∧C)

A∨(B∧C)Û(A∨B)∧(A∨C)

定理2.3 (范式存在定理)任一命题公式都存在着与之等值的析取范式与合取范式。

求范式的步骤：

1．消去联结词→、«；

2．消去否定号┐；

3．利用分配律。

命题公式的析取范式与合取范式都不是唯一的。

例2.7 求公式(p→q)↔r的析取范式与合取范式。

解: (1)合取范式：

(p→q)↔r Û (┐p∨q)↔ r

Û ((┐p∨q)→ r)∧(r→(┐p∨q))

Û (┐(┐p∨q)∨r)∧(┐r∨(┐p∨q))

Û ((p∧┐q)∨r)∧(┐p∨q∨┐r)

Û (p∨r)∧(┐q∨r)∧(┐p∨q∨┐r)

(2) 析取范式

(p→q)↔r Û ((p∧┐q)∨r)∧(┐p∨q∨┐r)

Û (p∧┐q∧┐p)∨(p∧┐q∧q)∨(p∧┐q∧┐r)∨(r∧┐p)∨(r∧q)∨(r∧┐r)

Û (p∧┐q∧┐r)∨(┐p∧r)∨(q∧r)

下面介绍命题公式的唯一规范化形式的范式：主析取范式与主合取范式。

在布尔逻辑中

析取范式(DNF)是逻辑公式的标准化（或规范化），它是合取子句的析取。作为规范形式，它在自动定理证明中有用。一个逻辑公式被认为是 DNF 的，当且仅当它是一个或多个文字的一个或多个合取的析取。同合取范式（CNF）一样，在 DNF 中的命题算子是与、或和非。非算子只能用做文字的一部分，这意味着它只能领先于命题变量。例如，下列公式都是 DNF:但如下公式不是 DNF:

NOT 是最外层的算子

一个 OR 嵌套在一个 AND 中

把公式转换成 DNF 要使用逻辑等价，比如双重否定除去、德·摩根定律和分配律。注意所有逻辑公式都可以转换成析取范式。但是，在某些情况下转换成 DNF 可能导致公式的指数性爆涨。例如，在 DNF 形式下，如下逻辑公式有 2 个项：