离散数学及应用 课件 1.4 范式

DiscreteMathematics鄢小虎

离散数学课前复习16个重要的等值式，还记得哪些？等值演算的基本思路是怎么样的？有哪些作用？1.4范式

析取范式与合取范式

主析取范式与主合取范式

课程引入

为什么需要范式？由上节等值演算可知，与一个给定命题等值而形式不同的命题可以有无穷多个。存在大量的命题公式看起来互不相同，实际上是等价的。需要通过标准形式，判断命题是否相等。（形似神似）

如何把命题化为标准形式（范式）？析取范式与合取范式

质析取式:有限个命题变项或其否定构成的析取式如p,

q,p

q,p

q

r,…质合取式:有限个命题变项或其否定构成的合取式如p,

q,p

q,p

q

r,…析取范式:由有限个质合取式组成的析取式

A1

A2

Ar,其中A1,A2,,Ar是质合取式合取范式:由有限个质析取式组成的合取式

A1

A2

Ar,其中A1,A2,,Ar是质析取式析取范式与合取范式(续)范式:析取范式与合取范式的总称

公式A的析取范式:与A等值的析取范式公式A的合取范式:与A等值的合取范式说明：

简单命题p,

q既是质析取式，又是质合取式命题公式的范式

定理

任何命题公式都存在着与之等值的析取范式与合取范式.求公式A的范式的步骤：

(1)消去A中的

,

（若存在）

(2)否定联结词

的内移或消去

(3)使用分配律

对

分配（析取范式）

对

分配（合取范式）公式的范式存在，但不唯一命题公式的范式

求范式的步骤：求公式的范式举例

解(p

q)

r

(

p

q)

r

（消去

）

p

q

r

（结合律）这既是A的析取范式（

A由3个质合取式

p、

q、

r组成的析取式），又是A的合取范式（将

p

q

r置换为P，A由一个质析取式组成的合取式P）例

求下列公式的析取范式与合取范式（1）A=(p

q)

r求公式的范式举例(续)解：

P

（P→Q）

P

（

P

Q）

（P

P）

（P

Q）

0

（P

Q）

P

Q(2)求P

（P→Q）的析取范式与合取范式（消去

）（分配律）（矛盾律）（同一律）P

Q既是析取范式，也是合取范式求公式的范式举例(续)解

(p

q)

r

(

p

q)

r

（消去第一个

）

(

p

q)

r

（消去第二个

）

(p

q)

r

（否定号内移——德

摩根律）这一步已为析取范式（由两个质合取式构成）继续：

(p

q)

r

(p

r)

(q

r)（

对

分配律）这一步得到合取范式（由两个质析取式构成）

(3)求B=(p

q)

r析取范式与合取范式课堂练习

习题12中(1)-(2)，计算析取范式、合取范式请同学上台推理极小项与极大项定义

在含有n个命题变项的质合取式(质析取式)中，若每个命题变项与其否定出现且仅出现一次，称这样的质合取式(质析取式)为极小项(极大项）.说明：n个命题变项产生2n个极小项和2n个极大项在极小项和极大项中文字均按下标或字母顺序排列用mi表示第i个极小项，其中i是该极小项成真赋值的十

进制表示.用Mi表示第i个极大项，其中i是该极大项成

假赋值的十进制表示,mi(Mi)称为极小项(极大项)的名称.

极小项与极大项(续)由p,q两个命题变项形成的极小项与极大项

公式

成真赋值名称

公式

成假赋值名称

p

q

p

qp

qp

q00011011m0m1m2m3

p

q

p

q

p

q

p

q

00011011

M0M1M2M3

极小项

极大项

由p,q,r三个命题变项形成的极小项与极大项

极小项

极大项

公式

成真赋值名称

公式

成假赋值名称

p

q

r

p

q

r

p

q

r

p

q

rp

q

rp

q

rp

q

rp

q

r000001010011100101110111m0m1m2m3m4m5m6m7p

q

r

p

q

r

p

q

r

p

q

r

p

q

r

p

q

r

p

q

r

p

q

r

000001010011100101110111M0M1M2M3M4M5M6M7

主析取范式与主合取范式

主析取范式:由极小项构成的析取范式主合取范式:由极大项构成的合取范式例如，n=3,命题变项为p,q,r时，

(

p

q

r)

(

p

q

r)

m1

m3

是主析取范式

(p

q

r)

(

p

q

r)

M1

M5

是主合取范式

A的主析取范式:与A等值的主析取范式

A的主合取范式:与A等值的主合取范式.

真值表求主析取范式与主合取范式

掌握例1.21的求法求主析取范式，找出表中真值为真的行，编码对应的极小项，组成的析取式求主合取范式，找出表中真值为假的行，编码对应的极大项，组成的合取式课堂练习

习题13中(1)，计算主析取范式、主合取范式请同学上台推理主析取范式与主合取范式

定理

任何命题公式都存在唯一的主析取范式和

主合取范式。作用：判断两个命题是否等值；判断公式的类型。对应关系主析（