离散数学第三讲-范式与主范式.pptx

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第三讲 范式与主范式,1.为何引入范式？,命题公式千变万化，不易于研究其性质和应用。,2.处理方法：,将,命题公式,转化为,逻辑等价标准形。,范式-逻辑等价标准形式,1,第1页,讲授重点：范式与主范式求法,讲授难点：主范式求法,讲授内容：,1.范式,析取范式,合取范式,2.主范式,主析取范式,主合取范式,3.主析取范式个数,第三讲 范式与主范式,2,第2页,1.文字,：命题变元或命题变元否定，P,Q；,2.质合取式,：若干个文字合取,P,Q R;,3.质析取式,：若干个文字析取,P Q,R;,4.析取范式,:,若干质合取式析取,若与公式A等价，,则称它为A 析取范式。,5.合取范式:,若干质析取式合取,，若与公式A等价，,则称它为A 合取范式。,1、范式-析取范式与合取范式,合取式-称为积,析取式-称为和,3,第3页,析取范式:,合取范式:,1、范式-析取范式与合取范式,4,第4页,范式存在定理,定理1：,任意,一个命题公式A,都存在,与之等价,析取范式,和,合取范式,。,1、范式-析取范式与合取范式,5,第5页,1)、化成限定性公式；A中，,化成,，；,析取范式,合取范式,对分配律 （合取范式）,E11:,(PQ),P,Q;,E10:,(PQ),P,Q,P,P,1、范式-析取范式与合取范式,2)、将否定联结词移到命题变量前面,摩根律E10,E11,；,3)、消除多出否定联结词，,双否定律,4)、用对,分配律,化成，析取范式。,惯用公式,6,第6页,任给一个命题公式A,经过以上四步演算,即得到一个与A等值,析取范式,或,合取范式,.,任何命题公式析取范式和合取范式都,不是唯一,1、范式-析取范式与合取范式,7,第7页,2、主范式-主析取范式与主合取范式,特殊质合取式,1.小项,极小项定义：,8,第8页,比如：2 个变元,P,Q,可结构 4 个极小项,2、主范式,极小项个数：,n个命题变元能够组成 个极小项。,我们把对应十进制数看成足标,用m,i,表示这一项,即,9,第9页,2、主范式,普通，n个变元极小项是:,10,第10页,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,主析取范式。,11,第11页,例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,第12页,2、主范式,极小项性质：,1).极小项之间彼此不等价；,2).极小项与使其为真指派之间建立了一一对应关系,3).主析取范式中，极小项与真值表中对应指派处公式真值为1相对应。,主析取范式与真值表关系,比如：,极小项 足标 指 派,m,5,-101 1，0，1,13,第13页,2、主范式,3.大项,极大项：,14,第14页,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,).,15,第15页,例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,第16页,极小项与极大项关系,一个命题公式主析取范式和主合取范式紧密相关,在它们简记式中,代表极小项和极大项足标是互补,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,第17页,(1)求出A主析取范式中,没包含,极小项m,j1,m,j2,.,(2)求出与(1)中极小项下标相同极大项M,j1,M,j2,.,(3)由以上极大项组成合取式为A主合取范式.,主析取范式与主合取范式关系,极小项与极大项之间关系,18,第18页,一个命题公式真值表是唯一,所以一个命题公式,主析取范式(,主合取范式)也是唯一。,2、主范式,两个命题公式假如有相同,主析取范式(,主合取范式),那么两个命题公式是逻辑等价。,定理2,：在真值表中使一个命题公式A真值为真,(假),指派所对应小项,(大项),析取,(合取),，即为A主析取范式,(主合取范式),。,19,第19页,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),20,第20页,主范式应用,利用主范式能够求解判问题或者证实等价式成立。,2、主范式,(1)判定命题公式类型,依据主范式定义和定理，也能够判定含,n,个命题变元公式，其关键是先求出给定公式主范式,；其次按以下条件判定之：,(,a,)若,A,，或,A,可化为与其等价、含2,n,个小项主析取范式，则,A,为永真式。,(,b,)若,A,，或,A,可化为与其等价、含2,n,个大项主合取范式，则,A,为永假式。,(,c,)若,A,不与,或者,等价，且又不含2,n,个小项或者大项，则,A,为可满足。,21,第21页,（2）证实命题公式是否等价,因为任一公式主范式是唯一，所以将给定公式求出其主范式，若主范式相同，则给定两公式是等价。,2、主范式,22,第22页,当,n,=1时,极小项有2,1,=2个，即,P,P,。主析取范式有 :,没有极小项,全部极小项,3、主析取范式个数,23,第23页,当,n,=2 时，极小项有 2,2,=4 个，即,P,Q,，,P,Q,，,P,Q,，,P,Q,。主析取范式有,3、主析取范式个数,24,第24页,共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,第25页,作业：P21 习题1.3,2(2)、3(2)、,26,第26页,