(1.2.4)--ch1-第五讲离散数学离散数学.pdf

离散数学离散数学 Discrete Mathematics 1.7 对偶式与范式对偶式与范式 1.对偶式对偶式 定义定义1-7.1 在给定的命题公式在给定的命题公式 A中中,将联结词将联结词和和互换互换,若有特殊变元若有特殊变元F 和和T亦相互取代亦相互取代,所得公式所得公式 A*称为称为A的的对偶式对偶式(dualistic formula).显然显然,A*与与 A互为对偶式互为对偶式.例例1.写出下列公式的对偶式写出下列公式的对偶式 (1)(PQ)R；(2)(PQ)T;(3)PQ 解解.(2)(PQ)F;(3)因因 PQ (PQ)(PQ)*=(PQ)PQ(1)(PQ)R;注意注意.(1)对含有对含有,之外联结词的公式之外联结词的公式,必须在利用逻辑等价必须在利用逻辑等价演算将其它联结词消去后才能求其对偶式演算将其它联结词消去后才能求其对偶式.(2)一般情况下一般情况下,公式与其对偶式不是逻辑等价的公式与其对偶式不是逻辑等价的.定义定义1-7.2.2.范式范式(normal form)一个命题公式称为一个命题公式称为合取范式合取范式(disjunctive normal form),当且仅当它具有形式：当且仅当它具有形式：A1A2An (n1)如如:P Q,(PQ)(P QR),Q P.其中其中A1,An 都是由都是由命题变元或其否定命题变元或其否定所组成的所组成的析取式析取式.定义定义1-7.3.一个命题公式称为一个命题公式称为析取范式析取范式(conjunctive normal form),当且仅当它具有形式：当且仅当它具有形式：A1A2 An (n1)如如:P Q,(PQ)(P QR),Q P.其中其中A1,An 都是由都是由命题变元或其否定命题变元或其否定所组成的所组成的合取式合取式.显然显然,任何合任何合(析析)取范式的对偶式是析取范式的对偶式是析(合合)取范式取范式.说明：说明：形如形如 PQ R,P Q的公式既是的公式既是析取析取范式范式,又是又是合取合取范式范式.例例1.求求(P(QR)S 的析取范式和合取范式的析取范式和合取范式 (P(QR)S P (QR)S P(Q R)S (PS)(Q R)(PSQ)(PS R)解解.(析取范式析取范式)（合取范式）（合取范式）(P(QR)S 将否定联结词消去或内移到各命题变元之前将否定联结词消去或内移到各命题变元之前.利用下列利用下列 等价式等价式 求命题公式的范式的基本步骤求命题公式的范式的基本步骤:使用命题定律将公式中的联结词化归成使用命题定律将公式中的联结词化归成,及及.P P 利用结合律利用结合律,分配律等将公式转化为析取范式或合取范式分配律等将公式转化为析取范式或合取范式.(PQ)P Q (PQ)P Q 例例2.求求(PQ)(PQ)的析取范式与合取范式的析取范式与合取范式 解解.(PQ)(P Q)(PQ)(P Q)因为因为 AB (AB)(A B)(P Q PQ)(PQ)(PQ)(PQ)(P Q)F(PQ)(P Q)(PQ)(P Q)(合取范式合取范式)(PQ)P)(PQ)Q)(P P)(PQ)(P Q)(Q Q)(PQ)(P Q)(析取范式析取范式)(析取范式析取范式)3.命题公式的主范式命题公式的主范式 例如例如:两个变元两个变元 P 和和Q,其小项为其小项为 3.1 主析取范式主析取范式 小项的概念和性质小项的概念和性质 定义定义1-7.4 n 个命题变元的合取式个命题变元的合取式,称作称作小项小项或或布尔合取布尔合取.其中每个命题变元与其否定不同时出现其中每个命题变元与其否定不同时出现,但二者之一必须出但二者之一必须出现一次且仅出现一次现一次且仅出现一次.一般的一般的n个命题变元共形成个命题变元共形成2n个小项个小项 三个命题变元三个命题变元 P,Q,R 的小项是的小项是:P Q R,P QR,P Q R,PQR,P Q R,P QR,PQ R,PQR.P Q，PQ，P Q，PQ.为简化小项的书写和表示为简化小项的书写和表示,特编码如下特编码如下:将命题变元按字典序排列将命题变元按字典序排列,并且把并且把命题变元与命题变元与1对应对应,命题命题 变元的否定与变元的否定与0对应对应,则可对则可对2n个小项按二进制编码个小项按二进制编码,则每个则每个 小项惟一地对应一个二进制数小项惟一地对应一个二进制数,把该二进制数转化成十进制数把该二进制数转化成十进制数i,并将所对应小项并将所对应小项记为记为mi,用这种编码所求得用这种编码所求得2n个小项的真值表个小项的真值表,可明显地反映出小项的性质可明显地反映出小项的性质 例例.两个命题变量两个命题变量P,Q,的小项的编码的小项的编码 m00=PQ,m01=P Q,m10=PQ,m11=P Q,两个变元两个变元P和和Q的小项的真值表的小项的真值表:P Q 0 0 0 1 1 0 1 1 P Q PQ P Q PQ 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 m(二二)m00 m01 m10 m11 m(十十)m0 m1 m2 m3 小项有如下性质小项有如下性质(1)每一个小项当其每一个小项当其真值指派与编码相同真值指派与编码相同时时,其真值其真值 为为T,在其余在其余2n-1种真值指派情况下均为种真值指派情况下均为F.(2)没有两个小项是等价的没有两个小项是等价的,即是说各小项的真值表即是说各小项的真值表都是不同的；都是不同的；(3)任意两个不同的小项的合取式是永假式任意两个不同的小项的合取式是永假式:mimj F,ij.(4)所有小项之析取为永真式所有小项之析取为永真式:m0m1 mk T,k=2n-1.210=niim 定义定义1-7.5.对于给定的命题公式对于给定的命题公式,若有一个等价公式若有一个等价公式,它仅由它仅由 小项的析取小项的析取所组成所组成,则称该等价式为原命题公式的则称该等价式为原命题公式的主析取范式主析取范式.主析取范式定义与存在定理主析取范式定义与存在定理 定理定理1-7.3.在真值表中在真值表中,一个公式的一个公式的真值为真值为T 的指派所对应的指派所对应 的小项的析取的小项的析取,即为此公式的的主析取范式即为此公式的的主析取范式.例例3.给定给定PQ,P Q,(P Q),求这些公式的主析取范式求这些公式的主析取范式.P Q PQ P Q (P Q)0 0 1 1 0 1 0 1 1 1 0 1 0 1 1 1 1 1 1 0 由定理由定理7.3 知知:PQ (P Q)PQ (PQ)(P Q)(P Q)(P Q)(PQ)(P Q)(PQ)(P Q)(PQ)主析取范式的求法主析取范式的求法 法一法一:真值表法真值表法 例例4:设一公式设一公式 A的真值表如下的真值表如下,求求A的主析取范式的主析取范式.P Q R A 1 1 1 1 1 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 0 1 0 0 0 0 1 0 0 0 0 1 A A的主析取范式为的主析取范式为(P Q R)(P Q R)(P Q R)练习练习:求求(P Q)Q的主析取范式的主析取范式.P Q 0 0 1 1 0 1 0 1 (P Q)Q(P Q)(P Q)(P Q)Q 0 1 0 1 例例5.求求(P Q)(P R)(Q R)的主析取范式的主析取范式.(P Q)(PR)(Q R)解解.(P Q (R R)(P R (Q Q)(Q R (P P)(P Q R)(P QR)(P Q R)(PQ R)(P Q R)(P Q R)(P Q R)(P QR)(P Q R)(PQ R)2)除去除去 A中所有为永假的析取项中所有为永假的析取项;法二法二:公式化归法公式化归法 1)将公式将公式 A化为析取范式化为析取范式 A;3)将将A中重复出现的合取项和相同变元都消去中重复出现的合取项和相同变元都消去;4)若若A中某合取项中某合取项 B中不含命题变元中不含命题变元 Pi,添加添加(Pi Pi ),然后应用分配律展开然后应用分配律展开.即即 B B TB (Pi Pi)(B Pi)(B Pi).例例6.求求 P(PQ)(QP)的主析取范式的主析取范式 解解.P(PQ)(QP)P (P Q)(Q P)P (P Q P)(Q Q P)P (P P Q)(P Q)P (P Q)(P(QQ)(P Q)(P Q)(PQ)(P Q)(PQ)R)(PQ)R)(P Q)R)(P Q)R)(P R)(Q R)(PQR)(P Q R)练习练习.求求(P Q)R的主析取范式的主析取范式.解解.(PQ)R (Q R(PP)(PQR)(P Q R)(P R(QQ)(PQ R)(P Q R)(PQR)(P Q R)(PQ R)(P Q R)(PQR)定义定义1-7.6 n个命题变元的析取式个命题变元的析取式,称作称作布尔析取布尔析取或或大项大项.其中每个命题变元与其否定不同时出现其中每个命题变元与其否定不同时出现,但但 二者之一必须二者之一必须 出现一次且仅出现一次出现一次且仅出现一次.3.2 主合取范式主合取范式(major conjunctive normal form)大项的概念和性质大项的概念和性质 一般的一般的n个命题变元共有个命题变元共有2n个大项个大项.例如例如:两个变元两个变元 P 和和Q，其大项为：，其大项为：P Q，P Q，P Q，P Q.将命题变元按字典序排列将命题变元按字典序排列,并把并把命题变元与命题变元与0对应对应,命题变命题变 元的否定与元的否定与1对应对应,则可对则可对2n个大项按二进制进行编码个大项按二进制进行编码,则每则每 个大项惟一地对应一个二进制数个大项惟一地对应一个二进制数,把该二进制数转化成十进把该二进制数转化成十进 制数为制数为i,并将所对应小项记为并将所对应小项记为Mi,用这种编码所求得用这种编码所求得2n个大项个大项 的真值表的真值表,可明显地反映出大项的性质可明显地反映出大项的性质 为简化大项的书写和表示为简化大项的书写和表示,特编码如下特编码如下 例例.两个命题变量两个命题变量P,Q 的大项的编码的大项的编码:M00=P Q,M01=P Q M10=P Q,M11=P Q 两个变元两个变元P和和Q的大项的真值表的大项的真值表:P Q 0 0 0 1 1 0 1 1 P Q P Q P Q P Q 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 M(二二)M00 M01 M10 M11 M(十十)M0 M1 M2 M3 3)任何两个不同大项之析取是永真的任何两个不同大项之析取是永真的,即即 MiMjT,ij;大项的性质大项的性质 2)没有两个大项是等价的没有两个大项是等价的;4)所有大项之合取为永假所有大项之合取为永假，即即 210niiM M0M1Mk F,k=2n-1;1)每个大项当其真值指派与编码相同时每个大项当其真值指派与编码相同时,其真值为其真值为0,在其余在其余2n-1种真值指派情况下均为种真值指派情况下均为1.主合取范式的定义与其存在定理主合取范式的定义与其存在定理 对于给定的命题公式对于给定的命题公式,若有一个等价公式若有一个等价公式,它仅由它仅由 大项的合取大项的合取所组成所组成,则称该等价式为原命题公式的则称该等价式为原命题公式的主合取范式主合取范式.定义定义1.7.7 定理定理1-7.4:在命题公式在命题公式 A的真值表中的真值表中,真值为真值为F 的指派对应的的指派对应的 大项的合取大项的合取,即为即为A的主合取范式的主合取范式.主合取范式的求法主合取范式的求法 法一：真值表法法一：真值表法 求公式求公式(PR)(PQ)的的主析取范式和主析取范式和主合取范式主合取范式.P Q R PR PQ(PR)(PQ)0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 0 1 0 1 1 1 1 1 1 1 0 0 0 0 1 1 0 1 0 0 0 0 1 1 主析取范式主析取范式:主合取范式主合取范式:(PQ R)(P QR)(P Q R)(P Q R)(PQ R)(PQ R)(P Q R)(P QR)法二：公式化归法法二：公式化归法 2)除去除去A中所有为永真的合取项；中所有为永真的合取项；1)将公式将公式A化为合取范式化为合取范式 A；3)将将A中重复出现的析取项和相同变元都消去中重复出现的析取项和相同变元都消去;4)若若A中某合取项中某合取项B中不含命题变元中不含命题变元Pi,添加添加(Pi Pi),然后应用分配律展开然后应用分配律展开.即即 B B F B(Pi Pi)(B Pi)(B Pi).例例7.求求(P Q)(P R)的主合取范式的主合取范式 解解.原式原式(P Q)P)(P Q)R)(P P)(Q P)(P R)(Q R)(Q R)(P P)(Q P)(R R)(P R)(Q Q)(P Q R)(P Q R)(P R Q)(P R Q)(P Q R)(P Q R)(P Q R)(P Q R)(P Q R)(P Q R)3.主析取范式与主合取范式之间的关系主析取范式与主合取范式之间的关系(PR)(PQ)(PQ R)(P QR)(P Q R)(PR)(PQ)(P Q R)(PQ R)(PQ R)(P Q R)(P QR)m001 m110 m111=1,6,7 (为为主析取范式主析取范式)M000 M010 M011 M100 M101=0,2,3,4,5 (为为主合取范式主合取范式)可以看出可以看出:一个命题公式的主合取范式中的大项的下标一个命题公式的主合取范式中的大项的下标 与其主析取范式的小项的下标之并集恰作成全体与其主析取范式的小项的下标之并集恰作成全体 n 位二进位二进 制数的集合制数的集合(即即0,1,2n-1的二进制表示的二进制表示).于是于是,如果已知如果已知 一个命题的主合取范式一个命题的主合取范式,则立即可写出它的主析取范式则立即可写出它的主析取范式,反之反之 亦然亦然.例如例如,设命题公式设命题公式 Am0 m1 m5 m7，则，则 AM2 M3 M4 M6 求公式的成真求公式的成真/成假赋值：成假赋值：若公式若公式 A中含有中含有n个命题变元个命题变元,且且A的主析取范式含的主析取范式含s 个小项个小项,则则A有有s 个成真赋值个成真赋值,有有2n-s个成假赋值个成假赋值.(即主析取范式中的小即主析取范式中的小项对应的编码是公式项对应的编码是公式 A的成真赋值的成真赋值;反之主合取范式中的大反之主合取范式中的大项对应的编码是公式项对应的编码是公式 A的成假赋值的成假赋值).4.主范式的应用主范式的应用 例如例如 (PQ)R m1 m3 m5 m6 m7 成真赋值为成真赋值为 001,011,101,110,111;成假赋值为成假赋值为 000,010,100.类似地，由类似地，由主合取范式主合取范式也立即求出也立即求出成假赋值成假赋值和成和成真真赋值赋值.2)若若A为矛盾式当且仅当为矛盾式当且仅当A 的的主合取主合取范式含全部范式含全部2n个个大大项项.此时此时,记记A的主析取范式为的主析取范式为0.判断公式的类型判断公式的类型 1)若若A为重言式当且仅当为重言式当且仅当A的的主析取主析取范式含全部范式含全部2n个小项个小项.此时此时,记记A的主合取范式为的主合取范式为1.3)若若 A为可满足式为可满足式当且仅当当且仅当,A的主析的主析(合合)取范式中至少含取范式中至少含 一个且不含全部小一个且不含全部小(大大)项项.设公式设公式A中含中含n个命题变元个命题变元,则则 例例8 用主析取范式判断公式的类型用主析取范式判断公式的类型 (1)A(PQ)Q (2)B P(P Q)(3)C(P Q)R (1)A (P Q)Q (P Q)Q 0 矛盾式矛盾式 (2)B P (P Q)1 m0 m1 m2 m3 重言式重言式 (3)C (P Q)R (P Q)R (P Q R)(P Q R)(P Q R)(P Q R)(PQ R)(P Q R)m0 m1 m3 m5 m7 可满足式可满足式 解解 设公式设公式A,B中共含有中共含有n个命题变元个命题变元,按按n个命题变元求出个命题变元求出A,B的主析的主析(合合)取范式取范式 A,B.若若A=B,则则AB,否则否则A、B不不等价等价.判断两个命题公式是否等价判断两个命题公式是否等价 例例9.试判断下列各组公式是否等价试判断下列各组公式是否等价.(1)P(QR)与与(PQ)R (2)P(QR)与与(PQ)R 解解.P(QR)=m0 m1 m2 m3 m4 m5 m7 (P Q)R=m0 m1 m2 m3 m4 m5 m7 (PQ)R=m1 m3 m4 m5 m7 显见显见,(1)中的两公式等价中的两公式等价,而而(2)的不等价的不等价.解实际问题解实际问题 例例10 某单位要从某单位要从 A,B,C三人中选派若干人出国考察三人中选派若干人出国考察,需满足需满足下述条件下述条件:(1)若若A去去,则则C必须去必须去;(2)若若B去去,则则C不能去不能去;(3)A和和B必须去一人且只能去一人必须去一人且只能去一人.问有几种可能的选派方案问有几种可能的选派方案?解解 设设 P:派派A去去,Q:派派B去去,R:派派C去去(1)P R,(2)QR,(3)(PQ)(P Q)求下式的成真赋值求下式的成真赋值 (PR)(Q R)(P Q)(P Q)求公式的求公式的主析取主析取范式范式 (PR)(QR)(PQ)(P Q)(P R)(QR)(PQ)(P Q)(PQ)(PR)(RQ)(RR)(PQ)(P Q)(PQ)(PQ)(PR)(PQ)(RQ)(PQ)(PQ)(P Q)(PR)(P Q)(RQ)(P Q)(PQ R)(P QR)成真赋值成真赋值:101,010 结论结论:方案方案1 派派A与与C去去,方案方案2 派派B去去 解决此类问题的步骤为：解决此类问题的步骤为：2)写出各复合命题写出各复合命题 1)将简单命题符号化；将简单命题符号化；3)写出由写出由2)中复合命题组成的合取式中复合命题组成的合取式;4)求求3)中所得公式的主析取范式中所得公式的主析取范式.范范式式 析取析取范式范式 小项及性质小项及性质 求法求法 大大项及性质项及性质 公式推演法公式推演法 求法求法 真值表法真值表法 主析取主析取 范式范式 主合取主合取 范式范式 互补互补 应应用用 求公式成真求公式成真(假假)赋值赋值 判断公式类型判断公式类型 解决实际问题解决实际问题 判断两公式是否等价判断两公式是否等价 公公 式式 标标 准准 型型 合取范式合取范式 本节主要介绍了对偶式、对偶原理、本节主要介绍了对偶式、对偶原理、析析(合合)取范式、小取范式、小(大大)项、项、(主主)析析(合合)取范式取范式.重点掌握重点掌握:(主主)析析(合合)取范式的求法取范式的求法.小结小结