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

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,*,离散数学第三讲范式与主范式,离散数学第三讲范式与主范式,2,讲授重点：范式与主范式的求法,讲授难点：主范式的求法,讲授内容：,1.,范式,析取范式,合取范式,2.,主范式,主析取范式,主合取范式,3.,主析取范式的个数,第三讲 范式与主范式,2讲授重点：范式与主范式的求法讲授内容：第三讲,3,1.,文字,：命题变元或命题变元否定，,P,Q,；,2.,质合取式,：若干个文字的合取,P,Q R;,3.,质析取式,：若干个文字的析取,P Q,R;,4.,析取范式,:,若干质合取式的析取,若与公式,A,等价，,则称它为,A,的析取范式。,5.,合取范式,:,若干质析取式的合取,，若与公式,A,等价，,则称它为,A,的合取范式。,1,、范式,-,析取范式与合取范式,合取式,-,称为积,析取式,-,称为和,31.文字：命题变元或命题变元否定，P,Q；1、范式-,4,析取范式,:,合取范式,:,1,、范式,-,析取范式与合取范式,4析取范式:合取范式:1、范式-析取范式与合取范式,5,范式存在定理,定理,1,：,任意,一个命题公式,A,都存在,与之等价的,析取范式,和,合取范式,。,1,、范式,-,析取范式与合取范式,5定理1：任意一个命题公式A都存在与之等价的,6,1),、化成限定性公式；,A,中，,化成,，；,析取范式,合取范式,对的分配律 （合取范式）,E11:,(PQ),P,Q;,E10:,(PQ),P,Q,P,P,1,、范式,-,析取范式与合取范式,2),、将否定联结词,移到命题变量的前面,摩根律,E10,E11,；,3),、消除多余的否定联结词，,双否定律,4),、用对的,分配律,化成，析取范式。,常用公式,6 1)、化成限定性公式；A中，化成 ，,7,任给一个命题公式,A,经过以上四步演算,即得到一个与,A,等值的,析取范式,或,合取范式,.,任何命题公式的析取范式和合取范式都,不是唯一,的,1,、范式,-,析取范式与合取范式,7 任给一个命题公式A,经过以上四步演算,即得到一个与A等值,8,2,、主范式,-,主析取范式与主合取范式,特殊的质合取式,1.,小项,极小项定义：,82、主范式-主析取范式与主合取范式特殊的质合取式1.小项,9,例如：,2,个变元,P,Q,可构造,4,个极小项,2,、主范式,极小项的个数：,n,个命题变元可以构成 个极小项。,我们把对应的十进制数当作足标,用,m,i,表示这一项,即,9 例如：2 个变元P,Q 可构造 4 个极小项2、,10,2,、主范式,一般，,n,个变元的极小项是,:,102、主范式一般，n个变元的极小项是:,11,2,、主范式,2.,主析取范式,:,若干个极小项的析取,若与公式,A,等价，则称它为,A,的主析取范式。,求命题公式,A,的主析取范式的步骤：,1),求公式,A,的析取范式,A,2),展开：若,A,的某简单,质合取式,B,中不含命题变项,p,i,或其否定,p,i,则将,B,展成如下形式：,B,BT,B(P,i,P,i,),(BP,i,)(B,P,i,),3),消去：将重复出现的命题变项、,矛盾式,及重复出现的极小项都,“,消去,”,如,PP,用,P,代,P,P,用,F,代,m,i,m,i,用,m,i,代。,4),排序：小项的序号从小到大。,例,2.,求命题公式,(PQ)R,的,主析取范式。,112、主范式2.主析取范式:若干个极小项的析取,若与公式,12,例,2.,求命题公式,(PQ)R,的主析取范式。,A,(,P,Q),R,P,Q,(,R,R,),(,P,P,)(,Q,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,P,Q,R,P,Q,R,P,Q,R,m,1,m,3,m,5,m,6,m,7,(1,3,5,6,7),2,、主范式,12例2.求命题公式(PQ)R的主析取范式。A(P,13,2,、主范式,极小项的性质：,1).,极小项之间彼此不等价；,2).,极小项与使其为真的指派之间建立了一一对应关系,3).,主析取范式中，极小项与真值表中相应指派处公式真值为,1,的相对应。,主析取范式与真值表的关系,例如：,极小项 足标 指 派,m,5,-101 1,，,0,，,1,132、主范式极小项的性质：主析取范式与真值表的关系例如：,14,2,、主范式,3.,大项,极大项：,142、主范式3.大项极大项：,15,4.,主合取范式,若干个大项的合取,若与公式,A,等价，则称它为,A,的主合取范式。,2,、主范式,例,4,求,(PQ)R,的主合取范式,.,求命题公式,A,的主合取范式的步骤：,（,1,）先求出合取范式,A,.,（,2,）若,A,的某简单析取式,B,中不含命题变项,P,i,或其否定,P,i,则将,B,展成如下形式：,B,BF,B(P,i,P,i,),(BP,i,)(B,P,i,).,154.主合取范式2、主范式例4 求(PQ)R的主合取,16,例,4,求,(PQ)R,的主合取范式,.,2,、主范式,解：,(PQ)R,(PR)(QR)(,合取范式,),(P(Q,Q,)R)(P,P,)QR),(PQR)(P,Q,R),(PQR)(,P,QR),(PQR)(P,Q,R)(,P,QR),M0M2M4,(0,2,4),其中,表示合取,.,16例4 求(PQ)R的主合取范式.2、主范式解：(P,17,极小项与极大项的关系,一个命题公式的主析取范式和主合取范式紧密相关,在它们的简记式中,代表极小项和极大项的足标是互补的,m,i,M,i,M,i,m,i,.,原命题,A,与其否命题,A,的关系,设命题公式,A,中含,n,个命题变元，且设,A,的,主析取范式中,含,k,个,极小项,m,i,l,m,i,2,m,i,k,则,A,的主析取范式中必含,2,n,-k,个极小项,设为,m,j,l,m,j,2,即,A,m,j,l,m,j,2,A,A,(m,j,l,m,j,2,),m,j,l,m,j,2,M,j,l,M,j,2,极小项与极大项之间的关系,17极小项与极大项的关系极小项与极大项之间的关系,18,(1),求出,A,的主析取范式中,没包含,的极小项,m,j1,m,j2,.,(2),求出与,(1),中极小项下标相同的极大项,M,j1,M,j2,.,(3),由以上极大项构成的合取式为,A,的主合取范式,.,主析取范式与主合取范式的关系,极小项与极大项之间的关系,18(1)求出A的主析取范式中没包含的极小项mj1,mj2,19,一个命题公式的真值表是唯一的,因此一个命题公式的,主析取范式,(,主合取范式,),也是唯一的。,2,、主范式,两个命题公式如果有相同的,主析取范式,(,主合取范式,),那么两个命题公式是逻辑等价的。,定理,2,：在真值表中使一个命题公式,A,的真值为真,(,假,),的指派所对应的小项,(,大项,),的析取,(,合取,),，即为,A,的主析取范式,(,主合取范式,),。,19 一个命题公式的真值表是唯一的,因此一个命题公式,20,A,：,(PQ)R,B,：,m,001,m,011,m,101,m,110,m111,(1),对使,A,的真值为真的指派，由于它所对应的小项在,B,中，所以此类指派也使,B,的真值为真。,(2),对使,A,的真值为假的指派，由于它所对应的小项不在,B,中，所以此类指派也使,B,的真值为假。,故,A,与,B,同真假，从而逻辑等价,例：,2,、主范式,(PQ)R,的,主析取范式,(PQ)R,m,001,m,011,m,101,m,110,m111,(1,3,5,6,7),20A：(PQ)R例：2、主范式(PQ)R的主析取范,21,主范式的应用,利用主范式可以求解判问题或者证明等价式成立。,2,、主范式,(1),判定命题公式的类型,根据主范式的定义和定理，也可以判定含,n,个命题变元的公式，其关键是先求出给定公式的主范式,；其次按下列条件判定之：,(,a,),若,A,，或,A,可化为与其等价的、含,2,n,个小项的主析取范式，则,A,为永真式。,(,b,),若,A,，或,A,可化为与其等价的、含,2,n,个大项的主合取范式，则,A,为永假式。,(,c,),若,A,不与,或者,等价，且又不含,2,n,个小项或者大项，则,A,为可满足的。,21主范式的应用2、主范式(1)判定命题公式的类型,22,（,2,）证明命题公式是否等价,由于任一公式的主范式是唯一的，所以将给定的公式求出其主范式，若主范式相同，则给定两公式是等价的。,2,、主范式,222、主范式,23,当,n,=1,时,极小项有,2,1,=2,个，即,P,P,。主析取范式有,:,没有极小项,全部极小项,3,、主析取范式的个数,23当n=1时,极小项有21=2个，即P,P。主析取范式,24,当,n,=2,时，极小项有,2,2,=4,个，即,P,Q,，,P,Q,，,P,Q,，,P,Q,。主析取范式有,3,、主析取范式的个数,24 当n=2 时，极小项有 22=4 个，即PQ,25,共,2,2,2,=16,个。以此类推,n,个命题变元,可构造,2,2,n,个不同的主析取范式,(,包括,F,),。这个数字增长非常快,如,n,=3,时,2,2,3,=256,n,=4,时,2,2,4,=65 536,。,主合取范式和主析取范式是一一对应的,因此,n,个命题变元,也可构造,2,2,n,个不同的主合取范式,(,包括,T,),。,3,、主析取范式的个数,25 共222=16 个。以此类推,n个命题变元,