第二章析取范式与合取范式

§2.2析取范式与合取范式1.简单析取式(简单合取式)命题变项及其否定称为文字。如p,p仅有有限个文字构成的析取式称作简单析取式。如p,┐q;p∨┐p，┐p∨q;┐p∨┐q∨r,p∨┐q∨r。仅有有限个文字构成的合取式称作简单合取式。如p,┐q;┐p∧p，p∧┐q;p∧q∧┐r,┐p∧p∧q。注意：•一个文字既是简单析取式，又是简单合取式。•一般用A1,A2,…,As表示s个简单析取式或s个简单合取式。2.定理2.1一个简单析取式是重言式当且仅当它同时含某个命题变项及它的否定式。如：p∨┐p，p∨┐p∨r都是重言式；┐p∨q，┐p∨┐q∨r都不是重言式。一个简单合取式是矛盾式当且仅当它同时含有某个命题变项及它的否定式。如：p∧┐p，p∧┐p∧r都是矛盾式；p∧┐q，┐p∧q∧┐r都不是矛盾式。3.范式的定义由有限个简单合取式构成的析取式称为析取范式。由有限个简单析取式构成的合取式称为合取范式。析取范式与合取范式统称为范式。•设Ai(i=1,2,…,s)为简单合取式,则析取范式的形式:A=A1∨A2∨…∨As例如A=(p∧┐q)∨(┐q∧┐r)∨p•设Ai(i=1,2,…,s)为简单析取式,则合取范式的形式:A=A1∧A2∧…∧As例如A=(p∨q∨r)∧(┐p∨┐q)∧r•思考：┐p∧q∧r与p∨┐q∨r属于什么范式？4.定理2.2一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式。一个合取范式是重言式当且仅当它的每个简单析取式都是重言式。5.定理2.3（范式存在定理）任一命题公式都存在着与之等值的析取范式与合取范式。•研究范式的目的是将给定公式化成与之等值的析取范式或合取范式，进而将公式化成与之等值的主析取范式或主合取范式。思考：怎样将公式转化为范式？例2.7求下面公式的析取范式与合取范式：(p→q)r先求合取范式(p→q)r(┐p∨q)r（消去→）((┐p∨q)→r)∧(r→(┐p∨q))（消去）(┐(┐p∨q)∨r)∧(┐r∨┐p∨q)（消去→）((p∧┐q)∨r)∧(┐p∨q∨┐r)（否定号内移）(p∨r)∧(┐q∨r)∧(┐p∨q∨┐r)（∨对∧分配律）6.将公式转化为范式的步骤①消除联结词，A→B┐A∨BAB(AB)∧(BA)(┐A∨B)∧(A∨┐B②缩小┐的作用范围┐┐AA┐(A∧B)┐A∨┐B┐(A∨B)┐A∧┐B③利用分配率，转化为析取（合取）范式A∧(B∨C)(A∧B)∨(A∧C)A∨(B∧C)(A∨B)∧(A∨C)例2.7求下面公式的析取范式与合取范式：(p→q)r求析取范式(p→q)r(┐p∨q)r（消去→）((┐p∨q)→r)∧(r→(┐p∨q))（消去）(┐(┐p∨q)∨r)∧(┐r∨┐p∨q)（消去→）((p∧┐q)∨r)∧(┐p∨q∨┐r)（否定号内移）(p∧┐q∧┐p)∨(p∧┐q∧q)∨(p∧┐q∧┐r）∨(r∧┐p)∨(r∧q)∨(r∧┐r)（∨对∧分配律）(p∧┐q∧┐r)∨(┐p∧r)∨(q∧r)7.极小项与极大项的定义极小项：在含有n个命题变项的简单合取式中，若每个命题变项和它的否定式不同时出现，而二者之一必出现且仅出现一次，且第i个命题变项或它的否定式出现在从左算起的第i位上（若命题变项无角标，就按字典顺序排列），称这样的简单合取式为极小项。例：p∧r∧q;p∧┐p∧r;p∧┐q∧p;p∧q∧r;p∧┐q∧r;┐p∧┐q∧┐r思考:(1)n个命题变项共可产生多少个不同的极小项?(2)每个极小项有多少个成真赋值?2n一个规定:成真赋值所对应的二进制数转换为十进制数i，就将所对应极小项记作mi7.极小项与极大项的定义极大项：在含有n个命题变项的简单析取式中，若每个命题变项和它的否定式不同时出现，而二者之一必出现且仅出现一次，且第i个命题变项或它的否定式出现在从左算起的第i位上（若命题变项无角标，就按字典顺序排列），称这样的简单析取式为极大项。例：p∨r∨q;p∨┐p∨r;p∨┐q∨p;p∨q∨r;p∨┐q∨r;┐p∨┐q∨┐r思考:(1)n个命题变项共可产生多少个不同的极大项?(2)每个极大项有多少个成假赋值?2n一个规定:成假赋值所对应的二进制数转换为十进制数i，就将所对应极大项记作Mi极小项解释记法极大项解释记法pqr000m0pqr000M0pqr001m1pqr001M1pqr010m2pqr010M2pqr011m3pqr011M3pqr100m4pqr100M4pqr101m5pqr101M5pqr110m6pqr110M6pqr111m7pqr111M7p,q,r形成的极小项与极大项8.定理2.4设mi与Mi是命题变项p1,p2,……,pn形成的极小项和极大项，则┐miMi，┐Mimi9.主析取范式(主合取范式)设由n个命题变项构成的析取范式中所有的简单合取式都是极小项，则称该析取范式为主析取范式。设由n个命题变项构成的合取范式中所有的简单析取式都是极大项，则称该合取范式主合取范式。例如：(p→q)r(p∧┐q∧┐r)∨(┐p∧r)∨(q∧r)(p∧┐q∧┐r)∨(┐p∧┐q∧r)∨(┐p∧q∧r)∨(┐p∧q∧r）∨(p∧q∧r)例如：(p→q)r(p∨r)∧(┐q∨r)∧(┐p∨q∨┐r)10.定理2.5任何命题公式都存在着与之等值的主析取范式和主合取范式,并且是唯一的。如何求主析取范式（主合取范式）？•首先求等价的析取范式（合取范式）•然后对非极小项（或者非极大项）进行扩展。AA∨(P∧┐P)（A∨P）∧（A∨┐P）AA∧(P∨┐P)（A∧P）∨（A∧┐P）•最后，求出某公式的主析取范式（主合取范式）后，将极小项（极大项）都用名称写出，并且按极小项（极大项）名称的角标由小到大顺序排列。求A=(rp)(q(pr))的主析取范式例1：解：(rp)(q(pr))(rp)(qp)(qr)(pr)(qp)(qr)[(pr)(qq)][(qp)(rr)][(qr)(pp)](pqr)(pqr)(pqr)(pqr)m1m3m6m7AA∧(P∨┐P)（A∧P）∨（A∧┐P）结论:公式的所有成真赋值对应主析取范式的所有极小项.(rp)(q(pr))的主合取范式(rp)(qp)(qr)(pr)(qp)(qr)[(pr)q][(pr)p](qr)[(pq)(qr)(pp)(pr)](qr)(pqq)(qrq)(prq)(pqr)(qrr)(prr)(pq)(qr)(prq)(pqr)(qr)(pr)(pq)(qr)(prq)(pqr)(pr)(pqr)(pqr)(pqr)(pqr)M4M5M0M2结论:公式的所有成假赋值对应主合取范式的所有极大项.例2：求A=(p→q)r的主析取范式(p→q)r(p∧┐q∧┐r)∨(┐p∧r)∨(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)m4∨m1∨m3∨m7求A=(p→q)r的主合取范式(p→q)r(p∨r)∧(┐q∨r)∧(┐p∨q∨┐r)(p∨q∨r)∧(p∨┐q∨r)∧(┐p∨┐q∨r)∧(┐p∨q∨┐r)M0M2M6M5如何求一个公式的主析取范式？（1）利用等值转化法（2）利用真值表（3）通过主合取范式求逆例3：求命题公式p→q的主析取范式和主合取范式。方法1：真值表法pqp→q001011100111p→qm0m1m4(pq)(pq)(pq)方法2：公式法p→qpq[p(qq)][q(pp)](pq)(pq)(pq)M2pqm0m1m4练习:求(p→q)(qr)的主析取范式公式法：(p→q)(qr)(pq)(qr)(pqr)(qr)(pqr)(qrp)(qrp)(pqr)(pqr)m3m7练习:求(p→q)(qr)的主析取范式真值表法：pqrpp→qqr(p→q)(qr)00010000011000010110001111111000100101010011001001110111(p→q)(qr)m3m7练习:求(p→q)(qr)的主析取范式求合取范式：(p→q)(qr)(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)M0M1M4M5M2M6因此主析取范式为：m3m7历史遗留问题:(1)我只给村里所有那些不给自己理发的人理发(2)只要别人有困难,他就帮忙,除非困难解决.a:别人有困难,b:他帮忙ab作业Ｐ385题（1、3）注意总结规律6题（2)作业问题:•整体较好,都交了.•个别书写不认真,应付私事。•注意“”的书写P1414题(10)除非天下大雨，否则他不乘车上班。p:天下大雨q:他乘车上班q→p(14)2和4是素数，这是不对的。p:2是素数q:4是素数(pq)P384题(4)(pq)(pq)(pq)(pq)(pq)(pq)[(pq)p][(pq)q](pp)(qp)(pq)(qq)(qp)(pq)(pq)(pq)11.主析取范式的用途求公式的成真与成假赋值判断公式的类型判断两个命题公式是否等值应用主析取范式分析和解决实际问题例1:求(p→q)→(q∨p)的成真赋值Am1∨m2∨…∨ms(p→q)→(qp)(pq)(qp)(pq)(qp)(pq)(pq)(pq)m0m2m3即成真赋值为：00,10，11pqpp→qqqp(p→q)→(qp)0010111011100010011111101011Am1∨m2∨…∨ms(1)A为重言式当且仅当其主析取范式包含2n个极小项(2)A为矛盾式当且仅当其主析取范式包不含极小项(3)A为可满足式当且仅当其主析取范式包至少含一个极小项例2：判断下列公式的类型(1)p→(pq)p(pq)(pq)(pq)(pq)(pq)(pq)(pq)m1m0m3m2重言式(2)(pq)→r(pq)r(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)m1m0m7m3m5pqrpq(pq)→r0000100101010100111110010101111101011111若公式A、B含有相同的命题变项，A与B等值的充要条件是它们有相同的主析取范式。例：问(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)m5m4m7m3m1p→(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)(pqr)(pqr)m3m1m2m0m5m4m7M6例:某科研所要从