《离散数学(对偶和范式).ppt》由会员分享，可在线阅读，更多相关《离散数学(对偶和范式).ppt（35页珍藏版）》请在三一办公上搜索。
1、1,1.5 对偶与范式,对偶式与对偶原理 析取范式与合取范式 主析取范式与主合取范式,2,对偶式和对偶原理,定义 在仅含有联结词,的命题公式A中，将换成,换成，若A中含有0或1，就将0换成1，1换成0，所得命题公式称为A的对偶式，记为A*.从定义不难看出，(A*)*还原成A显然，A也是A*的对偶式。可见A与A*互为对偶式。,3,对偶式和对偶原理,定理 设A和A*互为对偶式，p1,p2,pn是出现在A和A*中的全部命题变项，将A和A*写成n元函数形式，则(1)A(p1,p2,pn)A*(p1,p2,pn)(2)A(p1,p2,pn)A*(p1,p2,pn)(1)表明，公式A的否定等价于其命题变元
2、否定的对偶式；(2)表明，命题变元否定的公式等价于对偶式之否定。,4,对偶式和对偶原理,定理（对偶原理）设A，B为两个命题公式，若A B，则A*B*.有了等值式、代入规则、替换规则和对偶定理，便可以得到更多的永真式，证明更多的等值式，使化简命题公式更为方便。,5,判定问题,真值表等值演算范式,6,析取范式与合取范式,文字:命题变项及其否定的总称如 p,q简单析取式:有限个文字构成的析取式如 p,q,pq,pqr,简单合取式:有限个文字构成的合取式如 p,q,pq,pqr,注意：一个命题变元或其否定既可以是简单合取式，也可是简单析取式，如p，q等。,7,析取范式与合取范式,定理：简单合取式为永假
3、式的充要条件是：它同时含有某个命题变元及其否定。定理：简单析取式为永真式的充要条件是：它同时含有某个命题变元及其否定。,8,析取范式与合取范式,简单析取式:有限个文字构成的析取式如 p,q,pq,pqr,简单合取式:有限个文字构成的合取式如 p,q,pq,pqr,析取范式:由有限个简单合取式组成的析取式 A1A2Ar,其中A1,A2,Ar是简单合取式合取范式:由有限个简单析取式组成的合取式 A1A2Ar,其中A1,A2,Ar是简单析取式,9,析取范式与合取范式(续),范式:析取范式与合取范式的总称公式A的析取范式:与A等值的析取范式公式A的合取范式:与A等值的合取范式说明：单个文字既是简单析取
4、式，又是简单合取式形如 pqr,pqr 的公式既是析取范式，又是合取范式(为什么?),10,命题公式的范式,定理 任何命题公式都存在着与之等值的析取范式与合取范式.求公式A的范式的步骤：(1)消去A中的,（若存在）（消去公式中除、和以外公式中出现的所有联结词）(2)否定联结词的内移或消去（使用(P)P和德摩根律）(3)使用分配律 对分配（析取范式）对分配（合取范式）公式的范式存在，但不惟一，这是它的局限性,11,求公式的范式举例,例 求下列公式的析取范式与合取范式(1)A=(pq)r解(pq)r(pq)r（消去）pqr（结合律）这既是A的析取范式（由3个简单合取式组成的析取式），又是A的合取范
5、式（由一个简单析取式组成的合取式）,12,求公式的范式举例(续),(2)B=(pq)r解(pq)r(pq)r（消去第一个）(pq)r（消去第二个）(pq)r（否定号内移德摩根律）这一步已为析取范式（两个简单合取式构成）继续：(pq)r(pr)(qr)（对分配律）这一步得到合取范式（由两个简单析取式构成）,13,极小项与极大项,定义 在含有n个命题变项的简单合取式(简单析取式)中，若每个命题变项均以文字的形式在其中出现且仅出现一次，而且第i（1in）个文字出现在左起第i位上，称这样的简单合取式（简单析取式）为极小项（极大项）.例如，两个命题变元p和q，其构成的小项有pq，pq，pq和pq；而三个
6、命题变元p、q和r，其构成的小项有pqr，pqr，pqr，pqr，pqr，pqr，pqr，pqr。,14,极小项与极大项,定义 在含有n个命题变项的简单合取式(简单析取式)中，若每个命题变项均以文字的形式在其中出现且仅出现一次，而且第i（1in）个文字出现在左起第i位上，称这样的简单合取式（简单析取式）为极小项（极大项）.例如，由两个命题变元p和q，构成大项有pq，pq，pq，pq；三个命题变元p，q和r，构成pqr，pqr，pqr，pqr，pqr，pqr，pqr，pqr。,15,极小项与极大项,说明：n个命题变项产生2n个极小项和2n个极大项 2n个极小项（极大项）均互不等值 用mi表示第i
7、个极小项，其中i是该极小项成真赋值的十进制表示.（将命题变元按字典序排列，并且把命题变元与1对应，命题变元的否定与0对应，则可对2n个小项依二进制数编码）用Mi表示第i个极大项，其中i是该极大项成假赋值的十进制表示。（将n个命题变元排序，并且把命题变元与对应，命题变元的否定与对应，则可对2n个大项按二进制数编码）mi(Mi)称为极小项(极大项)的名称.mi与Mi的关系:mi Mi,Mi mi,16,极小项与极大项(续),由p,q两个命题变项形成的极小项与极大项,17,由p,q,r三个命题变项形成的极小项与极大项,小项的性质：,(a)没有两个小项是等价的，即是说各小项的真值表都是不同的；(b)任
8、意两个不同的小项的合取式是永假的：mimj，ij。(c)所有小项之析取为永真：mi。(d)每个小项只有一个解释为真，且其真值1位于主对角线上。,18,大项的性质：,(a)没有两个大项是等价的。(b)任何两个不同大项之析取是永真的，即MiMj，ij。(c)所有大项之合取为永假，即 Mi。(d)每个大项只有一个解释为假，且其真值0位于主对角线上。,19,20,主析取范式与主合取范式,主析取范式:由极小项构成的析取范式主合取范式:由极大项构成的合取范式例如，n=3,命题变项为p,q,r时，(pqr)(pqr)m1m3 是主析取范式(pqr)(pqr)M1M5 是主合取范式 A的主析取范式:与A等值的
9、主析取范式 A的主合取范式:与A等值的主合取范式.,21,主析取范式与主合取范式(续),定理 任何命题公式都存在着与之等值的主析取范式和主合取范式,并且是惟一的.用等值演算法求公式的主范式的步骤：(1)先求析取范式（合取范式）(2)将不是极小项（极大项）的简单合取式（简 单析取式）化成与之等值的若干个极小项的析 取（极大项的合取），需要利用同一律（零 律）、排中律（矛盾律）、分配律、幂等律等.(3)极小项（极大项）用名称mi（Mi）表示，并按角标从小到大顺序排序.,22,主析取范式与主合取范式(续),用等值演算法求公式的主范式的步骤：(1)先求析取范式(2)删除析取范式中所有为永假的简单合取式
10、(3)用等幂律化简简单合取式中同一命题变元的重复出现为一次出现，如ppp。(4)用同一律补进简单合取式中未出现的所有命题变元，如q，则pp（qq)，并用分配律展开之，将相同的简单合取式的多次出现化为一次出现，这样得到了给定公式的主析取范式。,从A的主析取范式求其主合取范式的步骤,(a)求出A的主析取范式中设有包含的小项。(b)求出与(a)中小项的下标相同的大项。(c)做(b)中大项之合取，即为A的主合取范式。例如，(pq)qm1m3，则(pq)qM0M2。,23,24,求公式的主范式,例 求公式 A=(pq)r的主析取范式与主合 取范式.(1)求主析取范式(pq)r(pq)r,（析取范式）(p
11、q)(pq)(rr)(pqr)(pqr)m6m7,25,求公式的主范式(续),r(pp)(qq)r(pqr)(pqr)(pqr)(pqr)m1m3m5m7,代入并排序，得(pq)r m1m3m5 m6m7（主析取范式）,26,求公式的主范式(续),(2)求A的主合取范式(pq)r(pr)(qr),（合取范式）pr p(qq)r(pqr)(pqr)M0M2,27,求公式的主范式(续),qr(pp)qr(pqr)(pqr)M0M4,代入并排序，得(pq)r M0M2M4（主合取范式）,28,主范式的用途与真值表相同,(1)求公式的成真赋值和成假赋值 例如(pq)r m1m3m5 m6m7，其成真赋
12、值为001,011,101,110,111，其余的赋值 000,010,100为成假赋值.类似地，由主合取范式也可立即求出成 假赋值和成真赋值.,29,主范式的用途(续),(2)判断公式的类型 设A含n个命题变项，则 A为重言式A的主析取范式含2n个极小项 A的主合取范式为1.A为矛盾式 A的主析取范式为0 A的主合析取范式含2n个极大项A为非重言式的可满足式A的主析取范式中至少含一个且不含全部极小项A的主合取范式中至少含一个且不含全部极大项,30,主范式的用途(续),例 用主析取范式判断下述两个公式是否等值：p(qr)与(pq)r p(qr)与(pq)r解 p(qr)=m0m1m2m3 m4
13、m5 m7(pq)r=m0m1m2m3 m4m5 m7(pq)r=m1m3 m4m5 m7显见，中的两公式等值，而的不等值.,(3)判断两个公式是否等值,说明：由公式A的主析取范式确定它的主合取范式，反之亦然.用公式A的真值表求A的主范式.,31,主范式的用途(续),例 某公司要从赵、钱、孙、李、周五名新毕业的大学生中选派一些人出国学习.选派必须满足以下条件：(1)若赵去，钱也去；(2)李、周两人中至少有一人去；(3)钱、孙两人中有一人去且仅去一人；(4)孙、李两人同去或同不去；(5)若周去，则赵、钱也去.试用主析取范式法分析该公司如何选派他们出国？,32,例(续),解此类问题的步骤为：将简单
14、命题符号化 写出各复合命题 写出由中复合命题组成的合取式 求中所得公式的主析取范式,33,例(续),解 设p：派赵去，q：派钱去，r：派孙去，s：派李去，u：派周去.(1)(pq)(2)(su)(3)(qr)(qr)(4)(rs)(rs)(5)(u(pq)(1)(5)构成的合取式为 A=(pq)(su)(qr)(qr)(rs)(rs)(u(pq),34,例(续),A(pqrsu)(pqrsu)结论：由可知，A的成真赋值为00110与11001，因而派孙、李去（赵、钱、周不去）或派赵、钱、周去（孙、李不去）.A的演算过程如下:A(pq)(qr)(qr)(su)(u(pq)(rs)(rs)（交换律)B1=(pq)(qr)(qr)(pqr)(pqr)(qr)（分配律）,35,例(续),B2=(su)(u(pq)(su)(pqs)(pqu)（分配律）B1B2(pqrsu)(pqrsu)(qrsu)(pqrs)(pqru)再令 B3=(rs)(rs)得 A B1B2B3(pqrsu)(pqrsu)注意：在以上演算中多次用矛盾律要求：自己演算一遍,
