范式--离散数学

12.3范式2.3.1析取范式与合取范式简单析取式与简单合取式析取范式与合取范式2.3.2主析取范式与主合取范式极小项与极大项主析取范式与主合取范式主范式的用途22.3.1析取范式与合取范式1、简单析取式与简单合取式（1）文字命题变元及命题变元的否定称为文字，并称命题变元为正文字，命题变元的否定为反文字。如p、q等。3简单析取式（基本和）：由有限个文字构成的析取式。如p,q,pq,pqr,…如p,q,pq,pqr,…简单合取式（基本积）：由有限个文字构成的合取式。（2）简单析取式与简单合取式4简单析取式的一般形式为：其中，为0或1。,mmbibibiPPP2211)(,mjbnijj11简单合取式的一般形式为：其中，为0或1。,mmbibibiPPP2211)(,mjbnijj11在上述表达式中，当bj=1时取Pij的正文字，bj=0时取Pij的反文字。（3）一般形式5（4）简单析取式与简单合取式的性质定理2.3(1)一个简单析取式是重言式当且仅当它同时含某个命题变元和它的否定。(2)一个简单合取式是矛盾式当且仅当它同时含某个命题变元和它的否定。62、析取范式与合取范式（1）定义定义2.16（1）由有限个简单合取式组成的析取式A1A2Ar，称为析取范式，其中A1,A2,,Ar是简单合取式。（2）由有限个简单析取式组成的合取式A1A2Ar称为合取范式，其中A1,A2,,Ar是简单析取式。（3）析取范式与合取范式的统称为范式。7（2）析取范式与合取范式的性质定理2.4(1)一个析取范式是矛盾式当且仅当它的每一个简单合取式都是矛盾式(2)一个合取范式是重言式当且仅当它的每一个简单析取式都是重言式8（3）范式存在定理定理2.5任何命题公式都存在着与之等值的析取范式与合取范式。这个定理意味着：AB且B是范式。9（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)求析取范式10举例例1求(pq)r的析取范式与合取范式解(pq)r(pq)r(pq)r析取范式(pr)(qr)合取范式11例2求的合取范式。[解]原式蕴含等值式等价等值式蕴含等值式双重否定律德.摩根定律分配律)()()()())()(()())()(())()(())()(())()(()()(RPQRQPQPRQRQQPQPRQRQQPQPRQRQQPQPRQRQQPRQQP)()(RQQP求公式的合取范式。12例3范式的表达式不唯一。))()PQPQRRPQRQR（（)()()()()()()(RQRPPQPPRQPPQPRPQPRQP132.3.2主析取范式与主合取范式1、极大项与极小项（1）定义定义2.17在含有n个命题变项的简单合取式(简单析取式)中，若每个命题变项均以文字的形式出现且仅出现一次，而且第i(1in)个文字(按下标或字母顺序排列)出现在左起第i位上，称这样的简单合取式（简单析取式）为极小项（极大项）。14说明:(1)n个命题变项产生2n个极小项和2n个极大项。(2)2n个极小项(极大项)均互不等值。(3)用mi表示第i个极小项，其中i是该极小项成真赋值的十进制表示；用Mi表示第i个极大项，其中i是该极大项成假赋值的十进制表示，mi(Mi)称为极小项(极大项)的名称。15极小项极大项公式成真赋值名称公式成假赋值名称pq00m0pq00M0pq01m1pq01M1pq10m2pq10M2pq11m3pq11M3p,q形成的极小项与极大项2个变元的极大项与极小项16（2）极大项与极小项的关系定理2.6设mi与Mi是由同一组命题变项形成的极小项和极大项，则miMi，Mimi。172、主范式（1）定义主析取范式:由极小项构成的析取范式主合取范式:由极大项构成的合取范式例如，n=3,命题变项为p,q,r时，(pqr)(pqr)m1m3是主析取范式(pqr)(pqr)M1M5是主合取范式18（2）主范式存在定理定理2.7任何命题公式都存在着与之等值的主析取范式和主合取范式，并且是惟一的。19（3）求主析取范式的步骤设公式A含命题变项p1,p2,…,pn(1)求A的析取范式A=B1B2…Bs,其中Bj是简单合取式；(2)若某个Bj既不含pi,又不含pi,则将Bj展开成BjBj(pipi)(Bjpi)(Bjpi)重复这个过程,直到所有简单合取式都是长度为n的极小项为止；(3)消去重复出现的极小项,即用mi代替mimi；(4)将极小项按下标从小到大排列。20解(1)(pq)r(pq)rpq(pq)1同一律(pq)(rr)排中律(pqr)(pqr)分配律m4m5r(pp)(qq)r同一律,排中律(pqr)(pqr)(pqr)(pqr)m0m2m4m6分配律得(pq)rm0m2m4m5m6可记作(0,2,4,5,6)例4求(pq)r的主析取范式。21（4）求主合取范式的步骤设公式A含命题变项p1,p2,…,pn(1)求A的合取范式A=B1B2…Bs,其中Bj是简单析取式；(2)若某个Bj既不含pi,又不含pi,则将Bj展开成BjBj(pipi)(Bjpi)(Bjpi)重复这个过程,直到所有简单析取式都是长度为n的极大项为止；(3)消去重复出现的极大项,即用Mi代替MiMi；(4)将极大项按下标从小到大排列。22例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)分配律M1M3qr(pp)qr同一律,矛盾律(pqr)(pqr)分配律M3M7得(pq)rM1M3M7可记作(1,3,7)23（5）范式的快速求取方法设公式含有n个命题变项,则（1）长度为k的简单合取式可展开成2n-k个极小项的析取。例如公式含p,q,rq(pqr)(pqr)(pqr)(pqr)m2m3m6m7（2）长度为k的简单析取式可展开成2n-k个极大项的合取例如pr(pqr)(pqr)M1M324实例例6(1)求A(pq)(pqr)r的主析取范式解：用快速求法(1)pq(pqr)(pqr)m2m3pqrm1r(pqr)(pqr)(pqr)(pqr)m1m3m5m7得Am1m2m3m5m7(1,2,3,5,7)25实例(续)(2)求Bp(pqr)的主合取范式解p(pqr)(pqr)(pqr)(pqr)M4M5M6M7pqrM1得BM1M4M5M6M7(1,4,5,6,7)263、主析取范式的用途(1)求公式的成真赋值和成假赋值设公式A含n个命题变项,A的主析取范式有s个极小项,则A有s个成真赋值,它们是极小项下标的二进制表示,其余2n-s个赋值都是成假赋值例如(pq)rm0m2m4m5m6成真赋值:000,010,100,101,110;成假赋值:001,011,11127(2)判断公式的类型设A含n个命题变项，则：（1）A为重言式当且仅当A的主析取范式含2n个极小项；（2）A为矛盾式当且仅当A的主析取范式不含任何极小项，记作0；（3）A为可满足式当且仅当A的主析取范式中至少含一个极小项。28例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m0m1m2m3重言式(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)m0m1m3m5m7非重言式的可满足式29(3)判断两个公式是否等值例8用主析取范式判断下面2组公式是否等值:(1)p与(pq)(pq)解pp(qq)(pq)(pq)m2m3(pq)(pq)(pq)(pq)(pq)(pq)m2m3故p(pq)(pq)30解：(pq)r(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)m1m3m5m6m7p(qr)(pq)(pr)(pqr)(pqr)(pqr)(pqr)m5m6m7故(pq)rp(qr)(2)(pq)r与p(qr)31应用题实例例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))32求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去334、主合取范式的应用上述应用，对于主合取范式也都适用，另外，可以根据下列对应关系由主析取范式求主合取范式没有出现的极小项是siiimmmA21,,,,21tjjjmmm其中t=2n-s,tjjjmmmA21tttjjjjjjjjjMMMmmmmmmA212121)(于是设34例9求A=(pqr)(pqr)(pqr)的主合取范式解Am1m3m7M0M2M4M5M6矛盾式的主合取范式含全部2n个极大项重言式的主合取范式不含任何极大项,记作135P81-82：2.26（1）、（3），2.27（1）、（2），2.28（1），2.29（1），2.30（2），2.31本节习题