离散数学第三讲范式与主范式课件.ppt

1、离散数学第三讲范式与主范式2讲授重点：范式与主范式的求法讲授重点：范式与主范式的求法讲授难点：主范式的求法讲授难点：主范式的求法讲授内容：讲授内容：1.范式范式 析取范式析取范式 合取范式合取范式 2.主范式主范式 主析取范式主析取范式 主合取范式主合取范式 3.主析取范式的个数主析取范式的个数 第三讲第三讲 范式与主范式范式与主范式31.1.文字文字：命题变元或命题变元否定，：命题变元或命题变元否定，P,P,Q Q；2.2.质合取式质合取式：若干个文字的合取：若干个文字的合取,P P Q R;Q R;3.3.质析取式质析取式：若干个文字的析取：若干个文字的析取,P Q P Q R;R;4.4

2、.析取范式析取范式:若干质合取式的析取若干质合取式的析取,若与公式若与公式A A等价，等价，则称它为则称它为A A 的析取范式。的析取范式。5.5.合取范式合取范式:若干质析取式的合取若干质析取式的合取，若与公式，若与公式A A等价，等价，则称它为则称它为A A 的合取范式。的合取范式。1 1、范式、范式-析取范式与合取范式析取范式与合取范式合取式合取式-称为积称为积 析取式析取式-称为和称为和4合合取取范范式式时时，单单个个质质析析取取式式也也是是：质质析析取取式式1mB)1m(BBBAim21 析取范式析取范式时，单个质合取式也是时，单个质合取式也是：质合取式：质合取式1nA),1n(AA

3、AAin21 析取范式析取范式:合取范式合取范式:1、范式、范式-析取范式与合取范式析取范式与合取范式5范式存在定理范式存在定理定理定理1 1：任意任意一个命题公式一个命题公式A A都存在都存在与之等价的与之等价的 析取范式析取范式和和合取范式合取范式。1、范式、范式-析取范式与合取范式析取范式与合取范式6 1)1)、化成限定性公式；、化成限定性公式；A A中中，化成化成 ，；分分配配律律 E14 )QP()QP()QP()QP()PQ()QP(QP:EQPQP:E1514 析取范式析取范式合取范式合取范式对对的分配律的分配律 （合取范式）（合取范式）E11:(PQ)P Q;E10:(PQ)P

4、 Q PP1 1、范式、范式-析取范式与合取范式析取范式与合取范式2)2)、将否定联结词、将否定联结词移到命题变量的前面移到命题变量的前面,摩根律摩根律E10,E11E10,E11；3)3)、消除多余的否定联结词，、消除多余的否定联结词，双否定律双否定律4)4)、用、用对对的的分配律分配律化成，析取范式。化成，析取范式。常用公式常用公式7v 任给一个命题公式任给一个命题公式A,A,经过以上四步演算经过以上四步演算,即得到一个与即得到一个与A A等值的等值的析取范式析取范式或或合取范式合取范式.v任何命题公式的析取范式和合取范式都任何命题公式的析取范式和合取范式都不是唯一不是唯一的的1、范式、范

5、式-析取范式与合取范式析取范式与合取范式82 2、主范式、主范式-主析取范式与主合取范式主析取范式与主合取范式 iiinnnPPPPPPPPPPPPn,产产生生的的小小项项，命命题题公公式式称称为为由由的的形形如如个个命命题题变变元元设设有有212121一次一次必出现一次，且仅出现必出现一次，且仅出现不同时存在，二者之一不同时存在，二者之一与与的顺序确定；的顺序确定；iinPPPPP.,.2121),(12102121 nrnrmmPPPn特殊的质合取式特殊的质合取式1.1.小项小项 iiiiiPPPP为为为为,01极小项定义：极小项定义：9 例如：例如：2 2 个变元个变元P P,Q Q 可

6、构造可构造 4 4 个极小项个极小项2 2、主范式、主范式极小项的个数：极小项的个数：n个命题变元可以构成个命题变元可以构成 个极小项。个极小项。n20001 1 10010 0 10100 1 01000 0 0QP QP QP QP Q Pmmmm 0123 我们把对应的十进制数当作足标我们把对应的十进制数当作足标,用用m mi i表示这一项表示这一项,即即QPmQPmQPmQPm 3210102 2、主范式、主范式一般，一般，n n个变元的极小项是个变元的极小项是:nnnPPPPmPPPPmPPPPmn 3211232113210112、主范式、主范式2.2.主析取范式主析取范式:若干个

7、极小项的析取若干个极小项的析取,若与公式若与公式A A等价，则称它等价，则称它为为A A 的主析取范式。的主析取范式。FPP ,PPP 求命题公式求命题公式A的主析取范式的步骤：的主析取范式的步骤：1)1)求公式求公式A A 的析取范式的析取范式AA2)2)展开：若展开：若AA的某简单的某简单质合取式质合取式B B中不含命题变项中不含命题变项p pi i或其否定或其否定 p pi i,则将则将B B展成如下形式：展成如下形式：B BT B(Pi Pi)(BPi)(B Pi)3)3)消去：将重复出现的命题变项、消去：将重复出现的命题变项、矛盾式矛盾式及重复出现的极小项都及重复出现的极小项都“消消

8、去去”,如如PPPP用用P P代代,P,P P P用用F F代代,m,mi immi i用用m mi i代。代。4)4)排序：小项的序号从小到大。排序：小项的序号从小到大。例例2.2.求命题公式求命题公式(PQ)R(PQ)R的的主析取范式。主析取范式。12例例2.2.求命题公式求命题公式(PQ)R(PQ)R的主析取范式。的主析取范式。A(PQ)R PQ(R R)(P P)(Q Q)R PQRPQ RPQRP QR PQR P QR PQR PQ R P Q R PQ R P QR m1 m3 m5 m6 m7 (1,3,5,6,7)2、主范式、主范式132、主范式、主范式极小项的性质：极小项的

9、性质：1).极小项之间彼此不等价；极小项之间彼此不等价；2).极小项与使其为真的指派之间建立了一一对应关系极小项与使其为真的指派之间建立了一一对应关系3).主析取范式中，极小项与真值表中相应指派处公式真主析取范式中，极小项与真值表中相应指派处公式真值为值为1的相对应。的相对应。主析取范式与真值表的关系主析取范式与真值表的关系例如：例如：极小项极小项 足标足标 指指 派派m5-101 1-101 1，0 0，1 1 RQP 14 iiinnnPPPPPPPPPPPPn,产生的大项，产生的大项，称为由称为由的命题公式的命题公式形如形如个命题变元个命题变元设有设有212121一次一次必出现一次，且仅

10、出现必出现一次，且仅出现不同时存在，二者之一不同时存在，二者之一与与的顺序确定；的顺序确定；iinPP.P,P,P.2121 iiiiinrnPPPPrMMPPPn为为为为,),(01121021212、主范式、主范式3.大项大项极大项：极大项：154.主合取范式主合取范式 若干个大项的合取若干个大项的合取,若与公式若与公式A等价，则称它为等价，则称它为A 的主合的主合取范式。取范式。2、主范式、主范式例例4 求求(PQ)R的主合取范式的主合取范式.求命题公式求命题公式A A的主合取范式的步骤：的主合取范式的步骤：（1）先求出合取范式）先求出合取范式A.（2）若）若A的某简单析取式的某简单析取

11、式B中不含命题变项中不含命题变项Pi,或其否定或其否定 Pi,则将则将B展成如下形式：展成如下形式：B BF B(Pi Pi)(BPi)(B Pi).16例例4 求求(PQ)R的主合取范式的主合取范式.2 2、主范式、主范式解：解：(PQ)R (PR)(QR)(合取范式合取范式)(P(Q Q)R)(P P)QR)(PQR)(P QR)(PQR)(PQR)(PQR)(P QR)(PQR)M0M2M4 (0,2,4)其中其中 表示合取表示合取.171.极小项与极大项的关系极小项与极大项的关系一个命题公式的主析取范式和主合取范式紧密相关一个命题公式的主析取范式和主合取范式紧密相关,在它们的简在它们的

12、简记式中记式中,代表极小项和极大项的足标是互补的代表极小项和极大项的足标是互补的,mi Mi,Mi mi.2.原命题原命题A与其否命题与其否命题 A的关系的关系设命题公式设命题公式A中含中含n个命题变元，且设个命题变元，且设A的的主析取范式中主析取范式中含含k个个极极小项小项mil,mi2,mik则则 A的主析取范式中必含的主析取范式中必含2n-k个极小项个极小项,设为设为mjl,mj2,即即 A mjl mj2 A A (mjl mj2 )mjl mj2 Mjl Mj2 极小项与极大项之间的关系极小项与极大项之间的关系18(1)求出求出A的主析取范式中的主析取范式中没包含没包含的极小项的极小

13、项mj1,mj2,.(2)求出与求出与(1)中极小项下标相同的极大项中极小项下标相同的极大项Mj1,Mj2,.(3)由以上极大项构成的合取式为由以上极大项构成的合取式为A的主合取范式的主合取范式.knjm 2knjM 23.主析取范式与主合取范式的关系主析取范式与主合取范式的关系极小项与极大项之间的关系极小项与极大项之间的关系），（主合取范式主合取范式），（主析取范式主析取范式例题：例题：420MMM76531R)Q42076531 mmmmm(P A19 一个命题公式的真值表是唯一的一个命题公式的真值表是唯一的,因此一个命题公式的因此一个命题公式的主主析取范式析取范式(主合取范式主合取范式)

14、也是唯一的。也是唯一的。2、主范式、主范式 两个命题公式如果有相同的两个命题公式如果有相同的主析取范式主析取范式(主合取范式主合取范式),),那么两个命题公式是逻辑等价的。那么两个命题公式是逻辑等价的。定理定理2 2：在真值表中使一个命题公式：在真值表中使一个命题公式A A的真值为真的真值为真(假假)的的指派所对应的小项指派所对应的小项(大项大项)的析取的析取(合取合取)，即为，即为A A的主析取的主析取范式范式(主合取范式主合取范式)。20A A：(PQ)R(PQ)RB B：m m001001 m m011011 m m101101 m m110110 m111m111 (1)(1)对使对使

15、A A的真值为真的指派，由于它所对应的真值为真的指派，由于它所对应的小项在的小项在B B中，所以此类指派也使中，所以此类指派也使B B的真值的真值为真。为真。(2)(2)对使对使A A的真值为假的指派，由于它所对应的真值为假的指派，由于它所对应的小项不在的小项不在B B中，所以此类指派也使中，所以此类指派也使B B的真的真值为假。值为假。故故A A与与B B同真假，从而逻辑等价同真假，从而逻辑等价例：例：2、主范式、主范式(PQ)R(PQ)R的的主析取范式主析取范式(PQ)R(PQ)R m m001001mm011011mm101101mm110110m111m111 (1,3,5,6,7)(

16、1,3,5,6,7)21n主范式的应用主范式的应用 利用主范式可以求解判问题或者证明等价式成立。利用主范式可以求解判问题或者证明等价式成立。2、主范式、主范式(1)(1)判定命题公式的类型判定命题公式的类型 根据主范式的定义和定理，也可以判定含根据主范式的定义和定理，也可以判定含n n个命题变个命题变元的公式，其关键是先求出给定公式的主范式元的公式，其关键是先求出给定公式的主范式；其次按；其次按下列条件判定之：下列条件判定之：(a a)若若A A，或，或A A可化为与其等价的、含可化为与其等价的、含2 2n n个小项的主个小项的主析取范式，则析取范式，则A A为永真式。为永真式。(b b)若若

17、A A，或，或A A可化为与其等价的、含可化为与其等价的、含2 2n n个大项的主个大项的主合取范式，则合取范式，则A A为永假式。为永假式。(c c)若若A A不与不与或者或者等价，且又不含等价，且又不含2 2n n个小项或者大个小项或者大项，则项，则A A为可满足的。为可满足的。22（2 2）证明命题公式是否等价）证明命题公式是否等价 由于任一公式的主范式是唯一的，所以将给定的公式求出由于任一公式的主范式是唯一的，所以将给定的公式求出其主范式，若主范式相同，则给定两公式是等价的。其主范式，若主范式相同，则给定两公式是等价的。2、主范式、主范式23当n=1时,极小项有21=2个，即P,P。主

18、析取范式有 :PPfPfPfFf4321没有极小项 全部极小项 3 3、主析取范式的个数、主析取范式的个数 2224 当当n n=2=2 时，极小项有时，极小项有 2 22 2=4=4 个，即个，即P PQ Q，P PQ Q ，P PQ Q ，P PQ Q。主析取范式有。主析取范式有 3 3、主析取范式的个数、主析取范式的个数 4225 共共2 22 22 2=16=16 个。以此类推个。以此类推,n n个命题变元个命题变元,可构造可构造2 22 2n n个不同个不同的主析取范式的主析取范式(包括包括F F)。这个数字增长非常快。这个数字增长非常快,如如n n=3=3时时2 22 23 3=256,=256,n n=4=4 时时2 22 24 4=65 536=65 536。主合取范式和主析取范式是一一对应的主合取范式和主析取范式是一一对应的,因此因此,n n个命个命题变元题变元,也可构造也可构造2 22 2n n个不同的主合取范式个不同的主合取范式(包括包括T T)。3 3、主析取范式的个数、主析取范式的个数