主析取范式

离散数学的课程中的内容

主析取范式是大学数学里一门名叫离散数学（Discrete mathematics）的课程中的内容，在离散数学的数理逻辑一节中，利用真值表和等值演算法可以化简或推证一些命题，但是当命题的变元的数目较多时，上述方法都显得不方便，所以需要给出把命题公式规范的方法，即把命题公式化成主合取范式和主析取范式的方法。

内容简介

析取范式(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∧¬r.

定理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)合取范式：

(2) 析取范式

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

详细介绍

定义：对于给定的命题公式A（P1，P2，P3，……，Pn），如果有一个仅由最小项的析取构成的等值式称为原命题公式的主析取范式。

定理：任意含n个命题变元的非永假式，其主析取范式是惟一的。

证明：（反证法）

假设非永假式A（P1，P2，P3，……，Pn）有两个不同的主析取范式A1和A2则A↔A1，A↔A2，故A1↔A2。由于A1和A2是两个不同的主析取范式，故至少存在一最小项mi，是mi只存在于A1和A2两者之一中，不妨设mi在A1中，而不再A2中。设mi在A1中有一组成真指派R，于是在R指派下，主析取范式A1为真，但在R指派情况下，主析取范式A2为假，这与A1↔A2相矛盾。

——证毕

求主析取范式与主合取范式

定义设A为恰含命题变元p1,…,pn的公式。公式A称为A的主析（合）取范式（major disjunctive(conjunctive) normal form），如果A是A的析（合）取范式，并且其每个合（析）取子句中p1,…,pn均恰出现一次。

据定义，公式¬(p→¬(p→q))的主析取范式是(p∧q)∨(p∧¬q)，而其主合取范式则应是(p∨q)∧(p∨¬q)。

例求公式(p∧q)∨r的主析取范式及主合取范式。

此即所求的主析取范式。另外

最后一式即为所求的主合取范式。

全国各地天气预报查询

上海市

市辖区

云南省

临沧市