范式--离散数学

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,2.3,2.3.1 析取范式与合取范式,简单析取式与简单合取式,析取范式与合取范式,2.3.2 主析取范式与主合取范式,极小项与极大项,主析取范式与主合取范式,主范式的用途,1,2.3.1,析取范式与合取范式,1,、简单析取式与简单合取式,（,1,）文字,命题变元及命题变元的否定称为文字，并称命题变元为正文字，命题变元的否定为反文字。,如,p,、,q,等。,2,简单析取式（基本和）：由有限个文字构成的析取式。,如,p,q,p,q,p,q,r, ,如,p,q,p,q,p,q,r, ,简单合取式（基本积）：由有限个文字构成的合取式。,（,2,）简单析取式与简单合取式,3,简单析取式的一般形式为：,其中， 为,0,或,1,。,简单合取式的一般形式为：,其中， 为,0,或,1,。,在上述表达式中，当,b,j,=1,时取,P,ij,的正文字，,b,j,=0,时取,P,ij,的反文字。,（,3,）一般形式,4,（,4,）简单析取式与简单合取式的性质,定理2.3 (1) 一个简单析取式是重言式当且仅当它同时含,某个命题变元和它的否定。,(2) 一个简单合取式是矛盾式当且仅当它同时含某个命题变元和它的否定。,5,2,、析取范式与合取范式,（,1,）定义,定义,2.16,（,1,）由有限个简单合取式组成的析取式,A,1,A,2,A,r,，称为析取范式，,其中,A,1,A,2,A,r,是简单合取式。,（,2,）由有限个简单析取式组成的合取式,A,1,A,2,A,r,称为合取范式，其中,A,1,A,2,A,r,是简单析取式。,（,3,）析取范式与合取范式的统称为,范式,。,6,（,2,）析取范式与合取范式的性质,定理2.4 (1) 一个析取范式是矛盾式当且仅当它的每一个简单合取式都是矛盾式,(2) 一个合取范式是重言式当且仅当它的每一个简单析取式都是重言式,7,（,3,）范式存在定理,定理2.5 任何命题公式都存在着与之等值的析取范式与合,取范式。,这个定理意味着：,且,B,是范式。,8,（,4,）范式求解步骤,求公式,A,的范式的步骤：,(1) 消去,A,中的蕴涵词,和等价词,。,A,B,A,B,，,A,B,(,A,B,),(,A,B,),(2) 否定联结词,的内移或消去, ,A,A,，,(,A,B,),A,B,，,(,A,B,),A,B,(,3),使用分配律进行化简、整合。,A,(,B,C,),(,A,B,),(,A,C,),求合取范式,A,(,B,C,),(,A,B,),(,A,C,),求析取范式,9,举例,例1 求,(,p,q,),r,的析取范式与合取范式,解,(,p,q,),r,(,p,q,),r,(,p,q,),r,析取范式,(,p,r,),(,q,r,),合取范式,10,例,2,求,的合取范式。,解,原式,蕴含等值式,等价等值式,蕴含等值式,双重否定律,德,.,摩根定律,分配律,求公式 的合取范式。,11,例,3,范式的表达式不唯一。,12,2.3.2,主析取范式与主合取范式,1,、极大项与极小项,（,1,）定义,定义2.17 在含有,n,个命题变项的简单合取式(简单析取式),中，若每个命题变项均以文字的形式出现且仅出现一次，,而且第,i,(1,i,n,),个文字(按下标或字母顺序排列)出现在左,起第,i,位上，称这样的简单合取式（简单析取式）为极小项（极大项）。,13,说明,:,(1),n,个命题变项产生2,n,个极小项和2,n,个极大项。,(2) 2,n,个极小项(极大项)均互不等值。,(3) 用,m,i,表示第,i,个极小项，其中,i,是该极小项成真赋值的十,进制表示；用,M,i,表示第,i,个极大项，其中,i,是该极大项成假赋,值的十进制表示，,m,i,(,M,i,),称为极小项(极大项)的名称。,14,极小项 极大项,公式 成真赋值 名称 公式 成假赋值 名称,p,q,0 0,m,0,p,q,0 0,M,0,p,q,0 1,m,1,p,q,0 1,M,1,p,q,1 0,m,2,p,q,1 0,M,2,p,q,1 1,m,3,p,q,1 1,M,3,p,q,形成的极小项与极大项,2,个变元的极大项与极小项,15,（,2,）极大项与极小项的关系,定理2.6 设,m,i,与,M,i,是由同一组命题变项形成的极小项和极大项， 则,m,i,M,i,，,M,i,m,i,。,16,2,、主范式,（,1,）定义,主析取范式:由极小项构成的析取范式,主合取范式:由极大项构成的合取范式,例如，,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,是主合取范式,17,（,2,）主范式存在定理,定理2.7 任何命题公式都存在着与之等值的主析取范式和主合取范式,，,并且是惟一的。,18,（,3,）求主析取范式的步骤,设公式,A,含命题变项,p,1,p,2,p,n,(1) 求,A,的析取范式,A,=B,1,B,2,B,s,其中,B,j,是简单合取式,；,(2) 若某个,B,j,既不含,p,i, 又不含,p,i, 则将,B,j,展开成,B,j,B,j,(,p,i,p,i,) (,B,j,p,i,),(,B,j,p,i,),重复这个过程, 直到所有简单合取式都是长度为,n,的极小项为止；,(3) 消去重复出现的极小项, 即用,m,i,代替,m,i,m,i,；,(4) 将极小项按下标从小到大排列。,19,解 (1),(,p,q,),r,(,p,q,),r,p,q,(,p,q,),1,同一律,(,p,q,),(,r,r,),排中律,(,p,q,r,),(,p,q,r,),分配律,m,4,m,5,r,(,p,p,),(,q,q,),r,同一律, 排中律,(,p,q,r,),(,p,q,r,),(,p,q,r,),(,p,q,r,),m,0,m,2,m,4,m,6,分配律,得,(,p,q,),r,m,0,m,2,m,4,m,5,m,6,可记作, ,(0,2,4,5,6),例,4,求,(,p,q,),r,的主析取范式。,20,（,4,）求主合取范式的步骤,设公式,A,含命题变项,p,1,p,2,p,n,(1) 求,A,的合取范式,A,=,B,1,B,2,B,s,其中,B,j,是简单析取式；,(2) 若某个,B,j,既不含,p,i, 又不含,p,i, 则将,B,j,展开成,B,j,B,j,(,p,i,p,i,) (,B,j,p,i,),(,B,j,p,i,),重复这个过程, 直到所有简单析取式都是长度为,n,的极大项为止；,(3) 消去重复出现的极大项, 即用,M,i,代替,M,i,M,i,；,(4) 将极大项按下标从小到大排列。,21,例,5,求,(,p,q,),r,的主合取范式。,(,p,q,),r,(,p,r,),(,q,r,),p,r,p,0,r,同一律,p,(,q,q,),r,矛盾律, (,p,q,r,),(,p,q,r,),分配律,M,1,M,3,q,r,(,p,p,),q,r,同一律, 矛盾律, (,p,q,r,),(,p,q,r,),分配律,M,3,M,7,得,(,p,q,),r,M,1,M,3,M,7,可记作, ,(1,3,7),22,（,5,）范式的快速求取方法,设公式含有,n,个命题变项, 则,（,1,）长度为,k,的简单合取式可展开成2,n-k,个极小项的析取。,例如 公式含,p,q,r,q,(,p,q,r,),(,p,q,r,),(,p,q,r,),(,p,q,r,),m,2,m,3,m,6,m,7,（,2,）长度为,k,的简单析取式可展开成2,n-k,个极大项的合取,例如,p,r, (,p,q,r,),(,p,q,r,),M,1,M,3,23,实例,例,6 (1),求,A, (,p,q,),(,p,q,r,),r,的主析取范式,解：用快速求法,(1),p,q,(,p,q,r,),(,p,q,r,),m,2,m,3,p,q,r,m,1,r,(,p,q,r,),(,p,q,r,),(,p,q,r,),(,p,q,r,),m,1,m,3,m,5,m,7,得,A,m,1,m,2,m,3,m,5,m,7, ,(1,2,3,5,7),24,实例(续),(2) 求,B,p,(,p,q,r,),的主合取范式,解,p, (,p,q,r,),(,p,q,r,),(,p,q,r,),(,p,q,r,),M,4,M,5,M,6,M,7,p,q,r,M,1,得,B,M,1,M,4,M,5,M,6,M,7, ,(1,4,5,6,7),25,3,、主析取范式的用途,(1) 求公式的成真赋值和成假赋值,设公式,A,含,n,个命题变项,A,的主析取范式有,s,个极小项, 则,A,有,s,个成真赋值, 它们是极小项下标的二进制表示, 其余2,n,-,s,个赋值都是成假赋值,例如,(,p,q,),r,m,0,m,2,m,4,m,5,m,6,成真赋值: 000,010,100,101,110; 成假赋值: 001,011,111,26,(,2),判断公式的类型,设,A,含,n,个命题变项，则,：,（,1,）,A,为重言式当且仅当,A,的主析取范式含,2,n,个极小项；,（,2,）,A,为矛盾式当且仅当,A,的主析取范式不含任何极小项，记作,0；,（,3,）,A,为可满足式当且仅当,A,的主析取范式中至少含一个极小项。,27,例,7,用主析取范式判断公式的类型:,(1),A,(,p,q,),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 ,m,0,m,1,m,2,m,3,重言式,(3),C,(,p,q,),r,(,p,q,),r,(,p,q,r,)(,p,q,r,)(,p,q,r,),(,p,q,r,)(,p,q,r,)(,p,q,r,),m,0,m,1,m,3,m,5,m,7,非重言式的可满足式,28,(,3),判断两个公式是否等值,例,8,用主析取范式判断下面2组公式是否等值:,(1),p,与,(,p,q,)(,p,q,),解,p,p,(,q,q,) (,p,q,)(,p,q,),m,2,m,3,(,p,q,)(,p,q,) (,p,q,)(,p,q,),(,p,q,)(,p,q,),m,2,m,3,故,p,(,p,q,)(,p,q,),29,解： (,p,q,),r, (,p,q,r,)(,p,q,r,),(,p,q,r,)(,p,q,r,)(,p,q,r,)(,p,q,r,),m,1,m,3,m,5,m,6,m,7,p,(,q,r,) (,p,q,)(,p,r,),(,p,q,r,)(,p,q,r,)(,p,q,r,)(,p,q,r,),m,5,m,6,m,7,故 (,p,q,),r,p,(,q,r,),(2) (,p,q,),r,与,p,(,q,r,),30,应用题实例,例,9,某单位要从,A,B,C,三人中选派若干人出国考察, 需满,足下述条件:,(1) 若,A,去, 则,C,必须去;,(2) 若,B,去, 则,C,不能去;,(3),A,和,B,必须去一人且只能去一人.,问有几种可能的选派方案?,解 记,p,:,派,A,去,q,:,派,B,去,r,:,派,C,去,(1),p,r,(2),q,r, (3) (,p,q,),(,p,q,),求下式的成真赋值,A,=(,p,r,),(,q,r,),(,p,q,),(,p,q,),31,求,A,的主析取范式,A,=(,p,r,),(,q,r,),(,p,q,),(,p,q,),(,p,r,),(,q,r,),(,p,q,),(,p,q,), (,(,p,q,),(,p,r,),(,r,q,),(,r,r,),(,p,q,),(,p,q,), (,(,p,q,),(,p,q,),(,(,p,r,),(,p,q,),(,(,r,q,),(,p,q,),(,(,p,q,),(,p,q,),(,(,p,r,),(,p,q,),(,(,r,q,),(,p,q,),(,p,q,r,),(,p,q,r,),成真赋值:101,010,结论: 方案1 派,A,与,C,去, 方案2 派,B,去,32,4,、主合取范式的应用,上述应用，对于主合取范式也都适用，另外，可以根据下列对应关系由主析取范式求主合取范式,没有出现的极小项是,其中,t,=2,n,-s,于是,设,33,例,9,求,A,=,(,p,q,r,)(,p,q,r,)(,p,q,r,),的主合取范式,解,A,m,1,m,3,m,7,M,0,M,2,M,4,M,5,M,6,矛盾式的主合取范式含全部2,n,个极大项,重言式的主合取范式不含任何极大项, 记作1,34,P81-82,：,2.26,（,1,）、（,3,），,2.27,（,1,）、（,2,），,2.28,（,1,），,2.29,（,1,），,2.30,（,2,），,2.31,本节习题,35,