2离散数学第2章-高等教育-屈婉玲-耿素云-张立昂-课件-

1主要内容等值式与基本的等值式等值演算与置换规则析取范式与合取范式，主析取范式与主合取范式联结词完备集可满足性问题与消解法第二章命题逻辑等值演算22.1等值式定义2.1若等价式AB是重言式，则称A与B等值，记作AB，并称AB是等值式几点说明：定义中，A,B,均为元语言符号A或B中可能有哑元出现.例如(pq)((pq)(rr))r为左边公式的哑元.用真值表可检查两个公式是否等值请验证：p(qr)(pq)rp(qr)不与(pq)r等值3等值式例题例1判断下列各组公式是否等值:(1)p(qr)与(pq)r111111011111110111011101000001010011100101110111(pq)rp(qr)qrpqrpq00000011结论:p(qr)(pq)r4等值式例题(2)p(qr)与(pq)r010111011111110111011101000001010011100101110111(pq)rp(qr)qrpqrpq11110011结论:p(qr)与(pq)r不等值5基本等值式双重否定律AA幂等律AAA,AAA交换律ABBA,ABBA结合律(AB)CA(BC),(AB)CA(BC)分配律A(BC)(AB)(AC),A(BC)(AB)(AC)德摩根律(AB)AB(AB)AB吸收律A(AB)A,A(AB)A6基本等值式零律A11,A00同一律A0A.A1A排中律AA1矛盾律AA0蕴涵等值式ABAB等价等值式AB(AB)(BA)假言易位ABBA等价否定等值式ABAB归谬论(AB)(AB)A特别提示：必须牢记这16组等值式，这是继续学习的基础7等值演算与置换规则1.等值演算——由已知的等值式推演出新的等值式的过程2.等值演算的基础：(1)等值关系的性质：自反性、对称性、传递性(2)基本的等值式(3)置换规则（见3）3.置换规则设(A)是含公式A的命题公式，(B)是用公式B置换(A)中所有的A后得到的命题公式若BA，则(B)(A)8等值演算的应用举例证明两个公式等值例2证明p(qr)(pq)r证p(qr)p(qr)（蕴涵等值式，置换规则）(pq)r（结合律，置换规则）(pq)r（德摩根律，置换规则）(pq)r（蕴涵等值式，置换规则）今后在注明中省去置换规则注意：用等值演算不能直接证明两个公式不等值9证明两个公式不等值例3证明p(qr)与(pq)r不等值证方法一真值表法,见例1(2)方法二观察法.观察到000,010是左边的成真赋值，是右边的成假赋值方法三先用等值演算化简公式，然后再观察p(qr)pqr(pq)r(pq)r(pq)r更容易看出前面的两个赋值分别是左边的成真赋值和右边的成假赋值等值演算的应用举例10判断公式类型:A为矛盾式当且仅当A0A为重言式当且仅当A1例4用等值演算法判断下列公式的类型(1)q(pq)(2)(pq)(qp)(3)((pq)(pq))r)等值演算的应用举例解(1)q(pq)q(pq)（蕴涵等值式）q(pq)（德摩根律）p(qq)（交换律，结合律）p0（矛盾律）0（零律）矛盾式11判断公式类型(2)(pq)(qp)(pq)(qp)（蕴涵等值式）(pq)(pq)（交换律）1重言式(3)((pq)(pq))r)(p(qq))r（分配律）p1r（排中律）pr（同一律）可满足式，101和111是成真赋值，000和010等是成假赋值.122.2析取范式与合取范式基本概念(1)文字——命题变项及其否定的总称(2)简单析取式——有限个文字构成的析取式p,q,pq,pqr,…(3)简单合取式——有限个文字构成的合取式p,q,pq,pqr,…(4)析取范式——由有限个简单合取式组成的析取式p,pq,pq,(pq)(pqr)(qr)(5)合取范式——由有限个简单析取式组成的合取式p,pq,pq,(pqp(pqr)(6)范式——析取范式与合取范式的总称13范式概念说明：单个文字既是简单析取式，又是简单合取式14范式的性质定理2.1(1)一个简单析取式是重言式当且仅当它同时含有某个命题变项和它的否定式.(2)一个简单合取式是矛盾式当且仅当它同时含有某个命题变项和它的否定式.定理2.2(1)一个析取范式是矛盾式当且仅当它每个简单合取式都是矛盾式.(2)一个合取范式是重言式当且仅当它的每个简单析取式都是重言式.15命题公式的范式定理2.3（范式存在定理）任何命题公式都存在与之等值的析取范式与合取范式公式A的析取(合取)范式与A等值的析取(合取)范式求公式A的范式的步骤：(1)消去A中的,（若存在）ABABAB(AB)(AB)(2)否定联结词的内移或消去AA(AB)AB(AB)AB16命题公式的范式(3)使用分配律A(BC)(AB)(AC)求合取范式A(BC)(AB)(AC)求析取范式公式范式的不足不惟一17求公式的范式例5求下列公式的析取范式与合取范式(1)(pq)r(2)(pq)r解(1)(pq)r(pq)r（消去）pqr（结合律）18(2)(pq)r(pq)r（消去第一个）(pq)r（消去第二个）(pq)r（否定号内移——德摩根律)析取范式(pr)(qr)（对分配律）合取范式求公式的范式19极小项与极大项定义2.4在含有n个命题变项的简单合取式（简单析取式）中，若每个命题变项均以文字的形式在其中出现且仅出现一次，而且第i个文字出现在左起第i位上（1in），称这样的简单合取式（简单析取式）为极小项（极大项）.几点说明：n个命题变项有2n个极小项和2n个极大项2n个极小项（极大项）均互不等值用mi表示第i个极小项，其中i是该极小项成真赋值的十进制表示.用Mi表示第i个极大项，其中i是该极大项成假赋值的十进制表示.mi（Mi）称为极小项（极大项）的名称.20实例由两个命题变项p,q形成的极小项与极大项极小项极大项公式成真赋值名称公式成假赋值名称pqpqpqpq00011011m0m1m2m3pqpqpqpq00011011M0M1M2M321实例极小项极大项公式成真赋值名称公式成假赋值名称pqrpqrpqrpqrpqrpqrpqrpqr000001010011100101110111m0m1m2m3m4m5m6m7pqrpqrpqrpqrpqrpqrpqrpqr000001010011100101110111M0M1M2M3M4M5M6M7由三个命题变项p,q,r形成的极小项与极大项.mi与Mi的关系：miMi,Mimi22主析取范式与主合取范式主析取范式——由极小项构成的析取范式主合取范式——由极大项构成的合取范式例如，n=3,命题变项为p,q,r时，(pqr)(pqr)m1m3——主析取范式(pqr)(pqr)M1M7——主合取范式公式A的主析取(合取)范式——与A等值的主析取(合取)范式定理2.5(主范式的存在惟一定理)任何命题公式都存在与之等值的主析取范式和主合取范式,并且是惟一的23求公式主范式的步骤求公式主析取范式的步骤:设公式A含命题变项p1,p2,…,pn(1)求A的析取范式A=B1B2…Bs,其中Bj是简单合取式j=1,2,…,s(2)若某个Bj既不含pi,又不含pi,则将Bj展开成BjBj(pipi)(Bjpi)(Bjpi)重复这个过程,直到所有简单合取式都是长度为n的极小项为止(3)消去重复出现的极小项,即用mi代替mimi(4)将极小项按下标从小到大排列24求公式主范式的步骤求公式的主合取范式的步骤:设公式A含命题变项p1,p2,…,pn(1)求A的合取范式A=B1B2…Bs,其中Bj是简单析取式j=1,2,…,s(2)若某个Bj既不含pi,又不含pi,则将Bj展开成BjBj(pipi)(Bjpi)(Bjpi)重复这个过程,直到所有简单析取式都是长度为n的极大项为止(3)消去重复出现的极大项,即用Mi代替MiMi(4)将极大项按下标从小到大排列25实例例6(1)求公式A=(pq)r的主析取范式和主合取范式解(pq)r(pq)r（析取范式）①(pq)(pq)(rr)(pqr)(pqr)m6m7②r(pp)(qq)r(pqr)(pqr)(pqr)(pqr)m1m3m5m7③②,③代入①并排序，得(pq)rm1m3m5m6m7（主析取范式）26实例(pq)r(pr)(qr)（合取范式）④prp(qq)r(pqr)(pqr)M0M2⑤qr(pp)qr(pqr)(pqr)M0M4⑥⑤,⑥代入④并排序，得(pq)rM0M2M4（主合取范式）27主范式的应用1.求公式的成真成假赋值设公式A含n个命题变项,A的主析取范式有s个极小项,则A有s个成真赋值,它们是极小项下标的二进制表示,其余2n-s个赋值都是成假赋值例如(pq)rm1m3m5m6m7成真赋值为001,011,101,110,111，成假赋值为000,010,100.类似地，由主合取范式也立即求出成假赋值和成真赋值.282.判断公式的类型设A含n个命题变项.A为重言式A的主析取范式含全部2n个极小项A的主合取范式不含任何极大项,记为1.A为矛盾式A的主合析取范式含全部2n个极大项A的主析取范式不含任何极小项,记为0.A为非重言式的可满足式A的主析取范式中至少含一个、但不是全部极小项A的主合取范式中至少含一个、但不是全部极大项.主范式的应用29例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非重言式的可满足式主范式的应用303.判断两个公式是否等值例8用主析取范式判以下每一组公式是否等值⑴p(qr)与(pq)r⑵p(qr)与(pq)r解p(qr)=m0m1m2m3m4m5m7(pq)r=m0m1m2m3m4m5m7(pq)r=m1m3m4m5m7显见，⑴中的两公式等值，而⑵的不等值.主范式的应用314.解实际问题例9某单位要从A,B,C三人中选派若干人出国考察,需满足下述条件:(1)若A去,则C必须去;(2)若B去,则C不能去;(3)A和B必须去一人且只能去一人.问有几种可能的选派方案?解记p:派A去,q:派B去,r:派C去(1)pr,(2)q