离散数学对偶和范式名师优质课获奖市赛课一等奖课件.ppt

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,本幻灯片资料仅供参考，不能作为科学依据，如有不当之处，请参考专业资料。,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本幻灯片资料仅供参考，不能作为科学依据，如有不当之处，请参考专业资料。,1.5,对偶与范式,对偶式与对偶原理,析取范式与合取范式,主析取范式与主合取范式,第1页,1,对偶式和对偶原理,定义,在仅含有联结词,命题公式,A,中，将换成,换成，若,A,中含有,0,或,1,，就将,0,换成,1,，,1,换成,0,，所得命题公式称为,A,对偶式,，记为,A,*,.,从定义不难看出，,(,A,*,),*,还原成,A,显然，,A,也是,A,*,对偶式。可见,A,与,A,*,互为对偶式。,第2页,2,对偶式和对偶原理,定理,设,A,和,A,*,互为对偶式，,p,1,p,2,p,n,是出现在,A,和,A,*,中全部命题变项，将,A,和,A,*,写成,n,元函数形式，,则,(1),A,(,p,1,p,2,p,n,),A,*,(,p,1,p,2,p,n,),(2),A,(,p,1,p,2,p,n,),A,*,(,p,1,p,2,p,n,),(1),表明，公式,A,否定等价于其命题变元否定对偶式；,(2),表明，命题变元否定公式等价于对偶式之否定。,第3页,3,对偶式和对偶原理,定理（对偶原理）,设,A,，,B,为两个命题公式，,若,A,B,，则,A,*,B,*,.,有了等值式、代入规则、替换规则和对偶定理，便能够得到更多永真式，证实更多等值式，使化简命题公式更为方便。,第4页,4,判定问题,真值表,等值演算,范式,第5页,5,析取范式与合取范式,文字,:,命题变项及其否定总称,如,p,q,简单析取式,:,有限个文字组成析取式,如,p,q,p,q,p,q,r,简单合取式,:,有限个文字组成合取式,如,p,q,p,q,p,q,r,注意：一个命题变元或其否定既能够是简单合取式，也可是简单析取式，如,p,，,q,等。,第6页,6,析取范式与合取范式,定理：,简单合取式为永假式充要条件是：它同时含有某个命题变元及其否定。,定理：,简单析取式为永真式充要条件是：它同时含有某个命题变元及其否定。,第7页,7,析取范式与合取范式,简单析取式,:,有限个文字组成析取式,如,p,q,p,q,p,q,r,简单合取式,:,有限个文字组成合取式,如,p,q,p,q,p,q,r,析取范式,:,由有限个简单合取式组成析取式,A,1,A,2,A,r,其中,A,1,A,2,A,r,是,简单合取式,合取范式,:,由有限个简单析取式组成合取式,A,1,A,2,A,r,其中,A,1,A,2,A,r,是,简单析取式,第8页,8,析取范式与合取范式,(,续,),范式,:,析取范式与合取范式总称,公式,A,析取范式,:,与,A,等值析取范式,公式,A,合取范式,:,与,A,等值合取范式,说明：,单个文字既是简单析取式，又是简单合取式,形如,p,q,r,p,q,r,公式既是析取范式，,又是合取范式,(,为何,?),第9页,9,命题公式范式,定理,任何命题公式都存在着与之等值析取范式,与合取范式,.,求公,式,A,范式步骤：,(1),消去,A,中,（若存在）（,消去公式中除,、,和,以外公式中出现全部联结词,）,(2),否定联结词,内移或消去（,使用,(,P,),P,和德,摩根律,）,(3),使用分配律,对,分配（析取范式）,对,分配（合取范式）,公式范式存在，但,不惟一,，这是它不足,第10页,10,求公式范式举例,例,求以下公式析取范式与合取范式,(,1),A,=(,p,q,),r,解,(,p,q,),r,(,p,q,),r,（消去,）,p,q,r,（结合律）,这既是,A,析取范式（由,3,个简单合取式组成析,取式），又是,A,合取范式（由一个简单析取式,组成合取式）,第11页,11,求公式范式举例,(,续,),(,2),B,=(,p,q,),r,解,(,p,q,),r,(,p,q,),r,（消去第一个,）,(,p,q,),r,（消去第二个,）,(,p,q,),r,（否定号内移,德摩根律）,这一步已为析取范式（两个简单合取式组成）,继续：,(,p,q,),r,(,p,r,),(,q,r,),（,对,分配律）,这一步得到合取范式（由两个简单析取式组成）,第12页,12,极小项与极大项,定义,在含有,n,个命题变项简单合取式,(,简单析取式,),中，,若每个命题变项均以文字形式在其中出现且仅出现一,次，而且第,i,（,1,i,n,）个文字出现在左起第,i,位上，称这么,简单合取式（简单析取式）为,极小项,（,极大项,）,.,比如，两个命题变元,p,和,q,，其组成小项有,p,q,，,p,q,，,p,q,和,p,q,；而三个命题变元,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,。,第13页,13,极小项与极大项,定义,在含有,n,个命题变项简单合取式,(,简单析取式,),中，,若每个命题变项均以文字形式在其中出现且仅出现一,次，而且第,i,（,1,i,n,）个文字出现在左起第,i,位上，称这么,简单合取式（简单析取式）为,极小项,（,极大项,）,.,比如，由两个命题变元,p,和,q,，组成大项有,p,q,，,p,q,，,p,q,，,p,q,；三个命题变元,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,。,第14页,14,极小项与极大项,说明：,n,个命题变项产生,2,n,个极小项和,2,n,个极大项,2,n,个极小项（极大项）均互不等值,用,m,i,表示第,i,个极小项，其中,i,是该极小项成真赋值十进制表示,.,（,将命题变元按字典序排列，而且把命题变元与,1,对应，命题变元否定与,0,对应，则可对,2,n,个小项依二进制数编码,）,用,M,i,表示第,i,个极大项，其中,i,是该极大项成假赋值十进制表示,。（,将,n,个命题变元排序，而且把命题变元与对应，命题变元否定与对应，则可对,2,n,个大项按二进制数编码,）,m,i,(,M,i,),称为极小项,(,极大项,),名称,.,m,i,与,M,i,关系,:,m,i,M,i,M,i,m,i,第15页,15,极小项与极大项,(,续,),由,p,q,两个命题变项形成极小项与极大项,公式,成真赋值,名称,公式,成假赋值,名称,p,q,p,q,p,q,p,q,0 0,0 1,1 0,1 1,m,0,m,1,m,2,m,3,p,q,p,q,p,q,p,q,0 0,0 1,1 0,1 1,M,0,M,1,M,2,M,3,极小项,极大项,第16页,16,由,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,0 0 0,0 0 1,0 1 0,0 1 1,1 0 0,1 0 1,1 1 0,1 1 1,m,0,m,1,m,2,m,3,m,4,m,5,m,6,m,7,p,q,r,p,q,r,p,q,r,p,q,r,p,q,r,p,q,r,p,q,r,p,q,r,0 0 0,0 0 1,0 1 0,0 1 1,1 0 0,1 0 1,1 1 0,1 1 1,M,0,M,1,M,2,M,3,M,4,M,5,M,6,M,7,第17页,17,小项性质：,(,a,),没有两个小项是等价，即是说各小项真值表都是不一样；,(,b,),任意两个不一样小项合取式是永假：,m,i,m,j,，,i,j,。,(,c,),全部小项之析取为永真：,m,i,。,(,d,),每个小项只有一个解释为真，且其真值,1,位于主对角线上。,第18页,18,大项性质：,(,a,),没有两个大项是等价。,(,b,),任何两个不一样大项之析取是永真，即,M,i,M,j,，,i,j,。,(,c,),全部大项之合取为永假，即,M,i,。,(,d,),每个大项只有一个解释为假，且其真值,0,位于主对角线上。,第19页,19,主析取范式与主合取范式,主析取范式,:,由极小项组成析取范式,主合取范式,:,由极大项组成合取范式,比如，,n,=3,命题变项为,p,q,r,时，,(,p,q,r,),(,p,q,r,),m,1,m,3,是,主析取范式,(,p,q,r,),(,p,q,r,),M,1,M,5,是,主合取范式,A,主析取范式,:,与,A,等值主析取范式,A,主合取范式,:,与,A,等值主合取范式,.,第20页,20,主析取范式与主合取范式,(,续,),定理,任何命题公式都存在着与之等值主析取范,式和主合取范式,而且是惟一,.,用等值演算法求公式主范式步骤：,(1),先求析取范式（合取范式）,(2),将不是极小项（极大项）简单合取式（简,单析取式）化成与之等值若干个极小项析,取（极大项合取），需要利用同一律（零,律）、排中律（矛盾律）、分配律、幂等律等,.,(3),极小项（极大项）用名称,m,i,（,M,i,）表示，并,按角标从小到大次序排序,.,第21页,21,主析取范式与主合取范式,(,续,),用等值演算法求公式主范式步骤：,(1),先求析取范式,(2),删除析取范式中全部为永假简单合取式,(3),用等幂律化简简单合取式中同一命题变元重复出现为一次出现，如,p,p,p,。,(4),用同一律补进简单合取式中未出现全部命题变元，如,q,，则,p,p,（,q,q,),，并用分配律展开之，将相同简单合取式屡次出现化为一次出现，这么得到了给定公式主析取范式。,第22页,22,从,A,主析取范式求其主合取范式步骤,(,a,),求出,A,主析取范式中设有包含小项。,(,b,),求出与,(,a,),中小项下标相同大项。,(,c,),做,(,b,),中大项之合取，即为,A,主合取范式。,比如，,(,p,q,),q,m,1,m,3,，则,(,p,q,),q,M,0,M,2,。,第23页,23,求公式主范式,例,求公式,A,=(,p,q,),r,主析取范式与主合,取范式,.,(,1),求主析取范式,(,p,q,),r,(,p,q,),r,（析取范式）,(,p,q,),(,p,q,),(,r,r,),(,p,q,r,),(,p,q,r,),m,6,m,7,第24页,24,求公式主范式,(,续,),r,(,p,p,),(,q,q,),r,(,p,q,r,),(,p,q,r,),(,p,q,r,),(,p,q,r,),m,1,m,3,m,5,m,7,代入并排序，得,(,p,q,),r,m,1,m,3,m,5,m,6,m,7,（,主析取范式）,第25页,25,求公式主范式,(,续,),(,2),求,A,主合取范式,(,p,q,),r,(,p,r,),(,q,r,),（合取范式）,p,r,p,(,q,q,),r,(,p,q,r,),(,p,q,r,),M,0,M,2,第26页,26,求公式主范式,(,续,),q,r,(,p,p,),q,r,(,p,q,r,),(,p,q,r,),M,0,M,4,代入并排序，得,(,p,q,),r,M,0,M,2,M,4,（主合取范式）,第27页,27,主范式用途,与真值表相同,(,1),求公式成真赋值和成假赋值,比如,(,p,q,),r,m,1,m,3,m,5,m,6,m,7,，,其成真赋值为,001,011,101,110,111,，,其余赋值,000,010,100,为,成假赋值,.,类似地，由主合取范式也可马上求出成,假赋值和成真赋值,.,第28页,28,主范式用途,(,续,),(,2),判断公式类型,设,A,含,n,个命题变项，则,A,为重言式,A,主析取范式含,2,n,个极小项,A,主合取范式为,1.,A,为矛盾式,A,主析取范式为,0,A,主合析取范式含,2,n,个极大项,A,为非重言式可满足式,A,主析取范式中最少含一个且不含全部极小项,A,主合取范式中最少含一个且不含全部极大项,第29页,29,主范式用途,(,续,),例,用主析取范式判断下述两个公式是否等值：,p,(,q,r,),与,(,p,q,),r,p,(,q,r,),与,(,p,q,),r,解,p,(,q,r,)=,m,0,m,1,m,2,m,3,m,4,m,5,m,7,(,p,q,),r,=,m,0,m,1,m,2,m,3,m,4,m,5,m,7,(,p,q,),r,=,m,1,m,3,m,4,m,5,m,7,显见，中两公式等值，而不等值,.,(,3),判断两个公式是否等值,说明：,由公式,A,主析取范式确定它主合取范式，反之亦然,.,用公式,A,真值表求,A,主范式,.,第30页,30,主范式用途,(,续,),例,某企业要从赵、钱、孙、李、周五名新毕,业大学生中选派一些人出国学习,.,选派必须,满足以下条件：,(1),若赵去，钱也去；,(2),李、周两人中最少有一人去；,(3),钱、孙两人中有一人去且仅去一人；,(4),孙、李两人同去或同不去；,(5),若周去，则赵、钱也去,.,试用主析取范式法分析该企业怎样选派他们出,国？,第31页,31,例,(,续,),解这类问题步骤为：,将简单命题符号化,写出各复合命题,写出由中复合命题组成合取式,求,中所得公式主析取范式,第32页,32,例,(,续,),解,设,p,：派赵去，,q,：派钱去，,r,：派孙去，,s,：派李去，,u,：派周去,.,(1)(,p,q,),(2)(,s,u,),(3)(,q,r,),(,q,r,),(4)(,r,s,),(,r,s,),(5)(,u,(,p,q,),(1)(5),组成合取式为,A,=(,p,q,),(,s,u,),(,q,r,),(,q,r,),(,r,s,),(,r,s,),(,u,(,p,q,),第33页,33,例,(,续,),A,(,p,q,r,s,u,),(,p,q,r,s,u,),结论：由可知，,A,成真赋值为,00110,与,11001,，,因而派孙、李去（赵、钱、周不去）或派赵、钱、,周去（孙、李不去）,.,A,演算过程以下,:,A,(,p,q,),(,q,r,),(,q,r,),(,s,u,),(,u,(,p,q,),(,r,s,),(,r,s,),（交换律,),B,1,=(,p,q,),(,q,r,),(,q,r,),(,p,q,r,),(,p,q,r,),(,q,r,),（分配律）,第34页,34,例,(,续,),B,2,=(,s,u,),(,u,(,p,q,),(,s,u,),(,p,q,s,),(,p,q,u,),（分配律）,B,1,B,2,(,p,q,r,s,u,),(,p,q,r,s,u,),(,q,r,s,u,),(,p,q,r,s,),(,p,q,r,u,),再令,B,3,=(,r,s,),(,r,s,),得,A,B,1,B,2,B,3,(,p,q,r,s,u,),(,p,q,r,s,u,),注意：在以上演算中屡次用矛盾律,要求：自己演算一遍,第35页,35,