离散数学第三讲-范式与主范式

第三讲范式与主范式1.为什么引入范式？

命题公式千变万化，不易于研究其性质和应用。2.解决办法：将命题公式转化为逻辑等价的标准形。

范式----逻辑等价的标准形式1离散数学第三讲-范式与主范式讲授重点：范式与主范式的求法讲授难点：主范式的求法讲授内容：

1.范式析取范式合取范式

2.主范式主析取范式主合取范式

3.主析取范式的个数

第三讲范式与主范式2离散数学第三讲-范式与主范式1.文字：命题变元或命题变元否定，P,¬Q；2.质合取式：若干个文字的合取,P∧¬

Q∧R;3.质析取式：若干个文字的析取,P∨Q∨¬R;4.析取范式:若干质合取式的析取,若与公式A等价，则称它为A的析取范式。5.合取范式:若干质析取式的合取，若与公式A等价，则称它为A的合取范式。1、范式---析取范式与合取范式合取式---称为积析取式---称为和3离散数学第三讲-范式与主范式析取范式:合取范式:1、范式---析取范式与合取范式4离散数学第三讲-范式与主范式范式存在定理定理1：任意一个命题公式A都存在与之等价的

析取范式和合取范式。1、范式---析取范式与合取范式5离散数学第三讲-范式与主范式

1)、化成限定性公式；A中→，化成¬

，∧，∨；析取范式合取范式∨对∧的分配律（合取范式）E11:(P∧Q)P∨Q;E10:(P∨Q)

P∧Q

PP1、范式---析取范式与合取范式2)、将否定联结词¬移到命题变量的前面,

摩根律E10,E11；3)、消除多余的否定联结词，双否定律4)、用∧对∨的分配律化成，析取范式。常用公式6离散数学第三讲-范式与主范式

任给一个命题公式A,经过以上四步演算,即得到一个与A等值的析取范式或合取范式.任何命题公式的析取范式和合取范式都不是唯一的1、范式---析取范式与合取范式7离散数学第三讲-范式与主范式2、主范式-主析取范式与主合取范式特殊的质合取式1.小项极小项定义：8离散数学第三讲-范式与主范式

例如：2个变元P,Q

可构造4个极小项2、主范式极小项的个数：n个命题变元可以构成个极小项。我们把对应的十进制数当作足标,用mi表示这一项,即9离散数学第三讲-范式与主范式2、主范式一般，n个变元的极小项是:10离散数学第三讲-范式与主范式2、主范式2.主析取范式:若干个极小项的析取,若与公式A等价，则称它为A的主析取范式。求命题公式A′的主析取范式的步骤：1)求公式A的析取范式A′2)展开：若A′的某简单质合取式B中不含命题变项pi或其否定

pi,则将B展成如下形式：

BB∧TB∧(Pi∨Pi)(B∧Pi)∨(B∧Pi)3)消去：将重复出现的命题变项、矛盾式及重复出现的极小项都“消去”,如P∧P用P代,P∧P用F代,mi∨mi用mi代。4)排序：小项的序号从小到大。例2.求命题公式(P∧Q)∨R的主析取范式。11离散数学第三讲-范式与主范式例2.求命题公式(P∧Q)∨R的主析取范式。A(P∧Q)∨RP∧Q∧(R∨R)∨(P∨P)∧(Q∨Q)∧RP∧Q∧R∨P∧Q∧R∨P∧Q∧R∨P∧Q∧R∨

P∧Q∧R∨

P∧Q∧R

P∧Q∧R∨

P∧Q∧R∨

P∧Q∧R∨

P∧Q∧

R∨

P∧Q∧R

m1∨

m3∨

m5∨

m6∨

m7Σ(1,3,5,6,7)2、主范式12离散数学第三讲-范式与主范式2、主范式极小项的性质：1).极小项之间彼此不等价；2).极小项与使其为真的指派之间建立了一一对应关系3).主析取范式中，极小项与真值表中相应指派处公式真值为1的相对应。主析取范式与真值表的关系例如：极小项足标指派m5

---1011，0，1

13离散数学第三讲-范式与主范式2、主范式3.大项极大项：14离散数学第三讲-范式与主范式4.主合取范式若干个大项的合取,若与公式A等价，则称它为A的主合取范式。2、主范式例4求(P∧Q)∨R的主合取范式.求命题公式A的主合取范式的步骤：（1）先求出合取范式A′.（2）若A′的某简单析取式B中不含命题变项Pi,或其否定Pi,则将B展成如下形式：

BB∨F

B∨(Pi∧Pi)(B∨Pi)∧(B∨Pi).15离散数学第三讲-范式与主范式例4求(P∧Q)∨R的主合取范式.2、主范式解：

(P∧Q)∨R

(P∨R)∧(Q∨R)(合取范式)

(P∨(Q∧Q)∨R)∧((P∧P)∨Q∨R)

(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)

(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)

M0∧M2∧M4

(0,2,4)

其中表示合取.16离散数学第三讲-范式与主范式极小项与极大项的关系一个命题公式的主析取范式和主合取范式紧密相关,在它们的简记式中,代表极小项和极大项的足标是互补的,mi

Mi,Mi

mi.原命题A与其否命题A的关系设命题公式A中含n个命题变元，且设A的主析取范式中含k个极小项mil,mi2,…,mik则

A的主析取范式中必含2n-k个极小项,设为mjl,mj2,…,,

即Amjl

∨mj2

∨…AA

(mjl

∨mj2

∨…)

mjl

∧mj2∧…∧

Mjl

∧Mj2

∧…∧极小项与极大项之间的关系17离散数学第三讲-范式与主范式(1)求出A的主析取范式中没包含的极小项mj1,mj2,···,.(2)求出与(1)中极小项下标相同的极大项Mj1,Mj2,···,.(3)由以上极大项构成的合取式为A的主合取范式.主析取范式与主合取范式的关系极小项与极大项之间的关系18离散数学第三讲-范式与主范式

一个命题公式的真值表是唯一的,因此一个命题公式的主析取范式(主合取范式)也是唯一的。2、主范式

两个命题公式如果有相同的主析取范式(主合取范式),那么两个命题公式是逻辑等价的。定理2：在真值表中使一个命题公式A的真值为真(假)的指派所对应的小项(大项)的析取(合取)，即为A的主析取范式(主合取范式)

。19离散数学第三讲-范式与主范式A：(P∧Q)∨RB：m001∨m011∨m101∨m110∨m111

(1)对使A的真值为真的指派，由于它所对应的小项在B中，所以此类指派也使B的真值为真。(2)对使A的真值为假的指派，由于它所对应的小项不在B中，所以此类指派也使B的真值为假。故A与B同真假，从而逻辑等价例：2、主范式(P∧Q)∨R的主析取范式(P∧Q)∨Rm001∨m011∨m101∨m110∨m111

Σ(1,3,5,6,7)

20离散数学第三讲-范式与主范式主范式的应用利用主范式可以求解判问题或者证明等价式成立。2、主范式(1)判定命题公式的类型根据主范式的定义和定理，也可以判定含n个命题变元的公式，其关键是先求出给定公式的主范式Ａ；其次按下列条件判定之：

(a)若AＴ，或A可化为与其等价的、含2n个小项的主析取范式，则A为永真式。

(b)若AＦ，或A可化为与其等价的、含2n个大项的主合取范式，则A为永假式。

(c)若A不与Ｔ或者Ｆ等价，且又不含2n个小项或者大项，则A为可满足的。21离散数学第三讲-范式与主范式（2）证明命题公式是否等价由于任一公式的主范式是唯一的，所以将给定的公式求出其主范式，若主范式相同，则给定两公式是等价的。2、主范式22离散数学第三讲-范式与主范式当n=1时,极小项有21=2个，即P,P。主析取范式有:没有极小项全部极小项3、主析取范式的个数

23离散数学第三讲-范式与主范式

当n=2时，极小项有22=4个，即┏P∧┏Q，┏P∧Q

，P∧┏Q

，P∧Q。主析取范式有3、主析取范式的个数

24离散数学第三讲-范式与主范式

共222=16个。以此类推,n个命题变元,可构造22n个不同的主析取范式(包括F)。这