2.2析取范式与合取范式

《2.2析取范式与合取范式》由会员分享，可在线阅读，更多相关《2.2析取范式与合取范式（8页珍藏版）》请在装配图网上搜索。

1、2.2析取范式与合取范式2.2析取范式与合取范式本节给出命题公式的两种规范表示方法，这种规范的表达式能表达真值表所能提供的一切信息定义2.2命题变项及其否定统称作文宇仅由有限个文字构成的析取式称作简单析取式仅由有限个文字构成的合取式称作简单合取式P,rg；pVp,rpVq和rpVqVr,pVpVr都是简单析取式,分别由1个文字,2个文字和3个文字构成np,q;pAp,PAnq和pAqAnr,nPAPAq都是简单合取式,分别由1个文字,2个文字和3个文字构成注意，一个文字既是简单析取式、又是简单合取式设A是含n个文字的简单析取式，若Ai中既含某个命题变项Pj又含它的否定式rPj,由交换律、排中律

2、和零律可知,Ai为重言式反之，若Ai为重言式,则它必同时含某个命题变项及它的否定式否则若将A,中的不带否定符的命题变项都取0值，带否定符的命题变项都取1值，此赋值为Ai的成假赋值，这与Ai是重言式相矛盾.类似地，设Ai是含n个命题变项的简单合取式若Ai中既含某个命题变项Pj又含它的否定式rPj则Ai，为矛盾式反之，若Ai为矛盾式，则Ai中必同时含某个命题变项pj及它的否定式于是，得到下面的定理定理2.1(1)简单析取式是重言式当且仅当它同时含某个命题变项及它的否定式1. 个简单合取式是矛盾式当且仅当它同时含某个命题变项及它的否定式定义2.3由有限个简单合取式的析取构成的命题公式称为析取范式，由

3、有限个简单析取式的合取构成的命题公式称为合取范式，析取范式与合取范式统称为范式析取范式的一般形式为A1VA2V-VAi,其中A,(i=1,2,s)为简单合取式;合取范式的般形式为B1AB2A.ABj,其中B(j=1,2,t)为简单析取式例如,(PJq)VhqArr)Vp为析取范式(pVqVrhpVrqhpVrrVs)为合取范式门戸人4人r既是由一个简单合取式构成的析取范式,又是由3个简单析取式构成的合取范式;类似地，pvnqvr既是由3个简单合取式构成的析取范式,又是由一个简单析取式构成的合取范式。(看定义)析取范式和合取范式具有下述性质定理2.2(1)个析取范式是矛盾式当且仅当它的每个简单合

4、取式都是矛盾式(2)一个合取范式是重言式当且仅当它的每个简单析取式都是重言式到现在为止,我们研究的命题公式中含有5个联结词A,V,r,如何把这样的命题公式化成等值的析取范式和合取范式？首先,可以利用蕴涵等值式与等价等值式ABnAVB|AB(rAVB)A(AVrB)|(2.17)消去任何公式中的联结词-和其次,在范式中不出现如下形式rrA,(qAAB),n(AVB)对其利用双重否定律和德摩根律,可得rrAA|r(AAB)rAVrB|r(AVB)rAArB|(2.18)再次,在析取范式中不出现如下形式:AA(BVC)在合取范式中不出现如下形式利用分配律，可得AA(BVC)(AAB)V(AAC)AV

5、(BAC)(AVB)A(AVC)上述3步，可将任一公式化成与之等值的析取范式和合取范式于是，得到下述定理定理2.3(范式存在定理)任一命题公式都存在与之等值的析取范式与合取范式求给定公式范式的步骤1. 为消去联结词-,2. 用双重否定律消去双重否定符,用德摩根律内移否定符3.3使用分配律:求析取范式时使用人对V的分配律，求合取范式时使用V对人的分配律例2.7求下面公式的析取范式与合取范式：(p-q)r解为了清晰和无误，利用交换律使每个简单析取式和简单合取式中命题变项都按字典顺出现。1. 先求合取范式(p-q)r(npVq)r(消去)(hpVq)ir)A(rhpVq)(消去)(n(npVq)Vr

6、)A(rrVrpVq)(消去)(PAq)Vr)A(pVqVr)(否定符内移)台(PVr)A(qVr)A(pVqr)(v对A的分配律)含3个简单析取式的合取范式1. 求析取范式求析取范式与求合取范式的前两步是相同的，只是在利用分配律时有所不同,因而前4步与(1)相同，接着使用A对V的分配律(p-q)r(pAnq)VrnpVqVnr)(pAnqAnp)V(pAnqAq)V(pAnqAV(rAq)V(rAq)(人对V的分配律)(pAnqAnr)VpAr)V(qAr)(矛盾律和同一律)最后两步的结果都是析取范式,一般地,命题公式的析取范式是不惟一的同样,合取范式也是不惟一的为了使命题公式的范式惟一,进

7、一步将简单合取式和简单析取式规范化,定义如下定义2.4在含有n个命题变项的简单合取式(简单析取式)中，若每个命题变项和它的否定式恰好出现一个且仅出现一次，而且命题变项或它的否定式按下标从小到大或按字典顺序排列,称这样的简单合取式简单析取式为极小项(极大项)由于每个命题变项在极小项中以原形或否定形式出现且仅出现一次，因而n个命题变项共可产生2个不同的极小项.每个极小项都有且仅有一个成真赋值若极小项的成真赋值所对应内二进制数等于十进制数i,就将这个极小项记作mi类似地,n个命题变项共可产生2个不同的极大项，每个极大项只有一个成假赋值，将其对应的十进制数做极大项的角标，记作Mi表2.3和表2.4分别

8、列出含p,q与p,q,啲全部极小项和极大项根据表2.3和表2.4可以直接验证极小项与极大项之间有下述关系定理2.4设mi与Mi是命题变项含P1,P2,.,P3的极小项和极大项，则nmi=MinMimi定义2.5所有简单合取式(简单析取式)都是极小项(极大项)的析取范式(合取范式)为主析取范式(主合取范式)下面讨论如何求出与给定公式等值的主析取范式和主合取范式，首先证明它的存在性和惟一性，再给出它的求法定理2.5任何命题公式都存在与之等值的主析取范式和主合取范式,并且是惟一的证这里只证主析取范式的存在性和惟一性首先证明存在性设A是任一含n个命题变项的公式由定理2.3可知,存在与A等值的析取范式A

9、：即AA若A的某个简单合取式A,中既不含命题变项Pj,也不含它的否定式nPj,则将Ai展成如下等值的形式A1A(PjVnpj)(AiAPj)V(AiAnPj)继续这个过程，直到所有的简单合取式都含有所有的命题变项或它的否定式若在演算过程中出现重复出现的命题变项以及极小项和矛盾式时,都应“消去”：如用p代替pAp,m代替miVmi,0代替矛盾式等最后就将A化成与之等值的主析取范式A下面再证明惟一性假设命题公式A等值于两个不同的主析取范式B和C,那么必有BC由于B和C是不同的主析取范式，不妨设极小项mi只出现在B中而不出现在C中于是，角标i的二进制表示为B的成真赋值，而为C的成假赋值，这与BC矛盾

10、主合取范式的存在惟一性可类似证明在证明定理2.5的过程中，已经给出了求主析取范式的步骤为了醒目和便于记忆，求出某公式的主析取范式(主合取范式)后，将极小项(极大项)都用名称写出,并且按极小项(极大项)名称的角标由小到大顺序排列例2.8求例2.7中公式的主析取范式和主合取范式解(1)求主析取范式在例2.7中已给出公式的析取范式,即(p-q)r(pAnqAnr)V(nPr)V(qr)在此析取范式中,第一项pAnqAnr是极小项m4o,另外两个简单合取式npAr,qAr都不是极小项下面先分别求出它们派生的极小项，注意，因为公式含有3个命题变项，所以极小项均由3个文字组成npArnpA(nqVq)Ar

11、(npAnqAr)V(npAqVr)m1Vm3QAr(npVp)AqAr(npAqAr)V(pAqAr)m3Vm7于是(p-q)rm1Vm3Vm4Vm7(2)求主合取范式由例2.7已求出公式的合取范式，(p-q)r(pVr)A(rqVr)人hpVqVr)其中rpVqVr已是极大项M5,利用矛盾律和同一律将另两人个简单析取式化成极大项PvrpV(qAnq)Vr(pVqVr)A(pVqVr)M0Vm2iqVr(pAp)VnqVr)(pVqqVr)人(pVqqVr)M2Vm6于是(p-q)rM0VM2VM3VM6例2.9求命题公式p-q的主析取范式与主合取范式。解本公式中含两人个命题变项，所心权小项

12、和极大项均含两个文字。1. P-qnpVqM2(主合取范式)1. P-qnpVq(npA(nqVq)V(npVp)Aq)(npAnq)V(npAq)V(npAq)V(pAq)(npAnq)V(npAq)V(pAq)m0Vm1Vm3(主析取范式)由例2.8与2.9可知,在求给定公式的主析取范式(主合取范式)时,一定要根据公式中命题变项的个数决定极小项(极大项)中文字的个数.下面讨论主析取范式的用途(主合取范式可类似讨论)主析取范式像真值表一样，可以表达出公式以及公式之间关系的一切信息1.求公式的成真赋值与成假赋值若公式A中含n个命题变项,A的主析取范式含s(0WsW2n)个极小项，则A有s个成真

13、赋值，它们是所含极小项角标的二进制表示，其余2n-s个赋值都是成假赋值例如，例2.8中(pq)rm1Vm3Vm4Vm7.这里有3个命题变项，将主析取范式中各极小项的角标1,3,4,7写成长为3的二进制数，它们分别为001,011,100,111这4个赋值即为该公式的成真赋值而主析取范式中未出现的极小项m0,m2,m3,m6。的角标的二进制表示000,010,101,110为该公式的成假赋值又如例2.9中,p-qm0Vm,Vm3,含两个命题变项,极小项的角标的二进制表示00,01,11为该公式的成真赋值,而10是它的成假赋值1.判断公式的类型设公式A中含n个命题变项，容易看出1.A为重言式当且仅

14、当A的主析取范式含全部2个极小项2. A为矛盾式当且仅当A的主析取范式不含任何极小项此时，记A的主式为03. A为可满足式当且仅当A的主析取范式中至少含一个极小项例2.10用公式的主析取范式判断下述公式的类型11(p-q)y2. p-(PVq)3. (pVg)r解注意,(1),(2)中公式含两个命题变项，极小项含两个文字，而(3)中公式含3个命题变项，因而极小项中应含3个文字1.1(p-q)Aqi(ipVq)Aq(pA1q)Aq0这说明该公式是矛盾式。1.P-(pVq)1pVpVq(1pA(1qVq)V(pA(1qVq)V(1pVp)Aq)(1pA1q)V(1pAq)V(pA1q)V(pAq)

15、V(1pAq)V(pAq)(1pA1q)V(1pAq)V(pA1q)V(pAq)m0Vm1Vm2Vm3由于主析取范式含两个命题变项的全部22=4个极小项，故该公式为重言式。其实,以上演算到第就已知该公式等值于1,因而它为重言式,如果要写出它的主析取范式，由1可直接写出全部极小项:1.(pVq)1pVpVq1m0Vm1Vm2Vm31.(pVq)-r1(pVq)Vr(1pA1q)Vr(1pAiq)Vr(下为凑式子)(1pA1qA(1rVr)V(1pVp)A(1qVq)Ar)(1pA1qA1r)V(1pA1qAr)V(1pAqAr)v(pA1(1pA1qA1r)V(1pA1qAr)V(1pAqAr)

16、V(pA1qAr)V(pAqAr)m0Vm1Vm3Vm5Vm7该公式是可满足的，但不是重言式，因为它的主析取范式没含全部8个极小项。1.判断两个命题公式是否等值1.设公式A,B共含有n个命题变项，按n个命题变项求出A与B=B，则AB,否则Ar解(1)这里有2个命题变项,因而极小项含2个文字PpA(nqVq)(PAnq)V(pAq)m2Vm3(pAq)V(pAnq)m2,Vm3所以P(pAnq)V(pAq)这里有3个命题变项,因而极小项含3个文字.经过演算得到(p-q)-rm1Vm3Vm4Vm5Vm7(pAq)-rm0Vm1Vm2Vm3Vm4Vm5Vm7两者的主析取范式不同，所以(p-q)-r(

17、pAq)-r最后举一个应用主析取范式分析和解决实际问题的例子例2.12某科研所要从3名科研骨干A,B,C中挑选12名出国进修由于工作需要，选派时要满足以下条件:1. 若A去，则C同去.2. 若B去，则C不能去3. 若C不去，则A或B可以去问所里有哪些选派方案？解设p：派A去q：派B去R:派C去由已知条件可得公式(p-r)A(q-)人仙r-(pvq)该公式的成真赋值即为可行的选派方案经过演算得到(p-r)A(q-)人(r-(pvq)hpVr)A(rqVrr)人(rV(pVq)(npVr)Aq)V(hpVr)Jr)A(pVqVr)（hp5q）V（rJqlMhpJr）V（rjr）人（pVqVr）（n

18、PAnqAP）V（pAnqAr）V.（此处展开大量计算略）（npAnqAr）V（pAqAnr）V（pJqAr）m1,Vm2,Vm3故有3种选派方案1. C去,A,B都不去2. B去,A,C都不去3. A,C同去,B不去以上讨论了主析取范式的求法与用途，也可对主合取范式做类似的讨论关于主合取范式还要说明以下两点1.由主析取范式求主合取范式设公式A含n个命题变项,A的主析取范式含s（0s2n）个极小项，即A=mi1Vmi2.Vmin,0ij2n-1,j=1,2,.s.没出现的极小项为mj1,mj2,.,mj2n-1它们的角标的二进制表示为的成真赋值，因而的主析取范式为nA=mj1Vmj2V.Vmj

19、2n-1这就由公式的主析取范式直接求出它的主合取范式例2.13利用公式的主析取范式,求主合取范式:1. Am1Vm2（A中含2个命题变项p,q）2. Bm1Vm2Vm3（B中含3个命题变项p,q,r）解由题可知,没出现在主析取范式中的极小项为mO和m3,所以A的主合取范式中含两个极大项MO与M3,故AM0AM3（2）B的主析取范式中没出现的极小项为mo,m4,m5,m6,m7因而BMOAM4AM5AM6AM7反之,也可由公式的主合取范式给出主析取范式1.重言式与矛盾式的主合取范式矛盾式无成真赋值，因而矛盾式的主合取范式含全部2n（n为公式中命题变项个数）个极大项而重言式无成假赋值，主合取范式不含任何极大项，规定重言式的主合取范式为1.至于可满足式，它的主合取范式中极大项的个数一定小于2n最后,要问:n个命题变项的主析取范式（主合取范式）共有多少个？n个命题变项共可产生个极小项（极大项）,因而共可产生22n个不同的主析取范式（主合取范式）这与在1.2节中对真值表个数的讨论情况是一样的事实上,AB当且仅当A与B有相同的真值表，又当且仅当A与B有相同的主析取范式（主合取范式）因而可以说，真值表与主析取范式（主合取范式）是描述命题公式的两种等价的不同标准形式，两者可以相互确定，由A的主析取范式（主合取范式）可以立刻确定A的真值表由A的真值表也可以立刻确定A的主析取范式（主合取范式）.