离散数学命题逻辑等值演算

1第二章命题逻辑等值演算本章的主要内容：等值式与基本的等值式等值演算与置换规则析取范式与合取范式，主析取范式与主合取范式联结词完备集本章与其他各章的联系是第一章的抽象与延伸是后续各章的先行准备2第一节等值式一、等值式与基本的等值式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)r,p(qr)⇎(pq)r32、基本的等值式双重否定律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)A4零律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注意：要牢记各个等值式，这是继续学习的基础.5二、等值演算与置换规则１.等值演算——由已知的等值式推演出新的等值式的过程２.等值演算的基础：（1）等值关系的性质：自反、对称、传递性（2）基本的等值式（3）置换规则（见3）３.置换规则设(A)是含公式A的命题公式，(B)是用公式B置换了(A)中的所有的A后得到的命题公式，若BA，则(B)(A)6三、等值演算的应用举例（以后章节待续）1．证明两个公式等值例证明p(qr)(pq)r证p(qr)p(qr)（蕴涵等值式，置换规则）(pq)r（结合律，置换规则）(pq)r（德摩根律，置换规则）(pq)r（蕴涵等值式，置换规则）7几点说明：也可以从右边开始演算（请做一遍）因为每一步都用置换规则，故可不写出熟练后，基本等值式也可以不写出用等值演算不能直接证明两个公式不等值8例证明p(qr)⇎(pq)r证方法一真值表法（自己证）方法二观察赋值法.易知000,010等是左边的成真赋值，是右边的成假赋值方法三用等值演算先化简两个公式，再观察.92.判断公式类型例用等值演算法判断下列公式的类型（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（零律）由最后一步可知，（1）为矛盾式.10（2）(pq)(qp)(pq)(qp)（蕴涵等值式）(pq)(pq)（交换律）1由最后一步可知，（2）为重言式.问：最后一步为什么等值于1？说明：（2）的演算步骤可长可短，以上演算最省.11（3）((pq)(pq))r)(p(qq))r（分配律）p1r（排中律）pr（同一律）由最后一步可知，（3）不是矛盾式，也不是重言式，它是可满足式，其实101,111是成真赋值，000,010等是成假赋值.总结：从此例可看出A为矛盾式当且仅当A0A为重言式当且仅当A13．解判定问题：见书上例2.612第二节析取范式与合取范式一、析取范式与合取范式1．基本概念（1）文字——命题变项及其否定的总称（2）简单析取式——有限个文字构成的析取式p,q,pq,pqr,…（3）简单合取式——有限个文字构成的合取式p,q,pq,pqr,…（4）析取范式——由有限个简单合取式组成的析取式A1A2Ar(r1)（5）合取范式——由有限个简单析取式组成的合取式A1A2Ar(r1)（6）范式——析取范式与合取范式的总称13说明：单个文字既是简单析取式，又是简单合取式形如pqr,pqr的公式既是析取范式，又是合取范式主要性质：简单析取式与简单合取式的性质见定理2.1析取范式与合取范式的性质见定理2.2142.命题公式的范式（1）公式A的析取范式（2）公式A的合取范式（3）公式范式存在定理定理2.3任何命题公式都存在着与之等值的析取范式与合取范式（4）求公式A的范式的步骤：消去A中的,（若存在）否定联结词的内移或消去使用分配律：对分配（析取范式）对分配（合取范式）（5）公式的范式存在，但不惟一，这是它的局限性153.求公式的范式举例例求下列公式的析取范式与合取范式（1）A=(pq)r（2）B=(pq)r解（1）(pq)r(pq)r（消去）pqr（结合律）注意：最后结果既是A的析取范式（由3个简单合取式组成的析取式），又是A的合取范式（由一个简单析取式组成的合取式）16（2）(pq)r(pq)r（消去第一个）(pq)r（消去第二个）(pq)r（否定号内移——德摩根律）最后一步已为析取范式（两个简单合取式构成）继续：B(pq)r(pr)(qr)（对分配律）最后一步已为合取范式（由两个简单析取式构成）171．极小项与极大项定义2.4在含有n个命题变项的简单合取式（简单析取式）中，若每个命题变项均以文字的形式在其中出现且仅出现一次，而且第i（1in）个文字出现在左起第i位上，称这样的简单合取式（简单析取式）为极小项（极大项）.二、主析取范式与主合取范式几点说明：n个命题变项产生2n个极小项和2n个极大项2n个极小项（极大项）均互不等值用mi表示第i个极小项，其中i是该极小项成真赋值的十进制表示.Mi表示第i个极大项，其中i是该极大项成假赋值的十进制表示,mi（Mi）称为极小项（极大项）的名称.18由p,q两个命题变项形成的极小项与极大项由下表给出极小项公式成真赋值名称pqpqpqpq00011011m0m1m2m3极大项公式成假赋值名称pqpqpqpq00011011M0M1M2M319由p,q,r三个命题变项形成的极小项与极大项由下表给出.极小项公式成真赋值名称pqrpqrpqrpqrpqrpqrpqrpqr000001010011100101110111m0m1m2m3m4m5m6m720极大项公式成假赋值名称pqrpqrpqrpqrpqrpqrpqrpqr000001010011100101110111M0M1M2M3M4M5M6M7mi与Mi的关系由书上定理2.4给出，即miMi,Mimi212.主析取范式与主合取范式定义2.5（1）主析取范式——由极小项构成的析取范式（2）主合取范式——由极大项构成的合取范式例如，n=3,命题变项为p,q,r时，(pqr)(pqr)m1m3——主析取范式(pqr)(pqr)M7M1——主合取范式223.命题公式A的主析取范式与主合取范式（1）与A等值的主析取范式称为A的主析取范式；与A等值的主合取范式称为A的主合取范式.（2）主析取范式的存在惟一定理定理2.5任何命题公式都存在着与之等值的主析取范式和主合取范式,并且是惟一的234.用等值演算法求公式的主范式的步骤：（1）先求析取范式（合取范式）（2）将不是极小项（极大项）的简单合取式（简单析取式）化成与之等值的若干个极小项之析取（极大项之合取），利用的等值式为同一律（零律）、排中律（矛盾律）、分配律、幂等律等.（3）极小项（极大项）用名称mi（Mi）表示，并按角标从小到大顺序排序.例求公式A=(pq)r的主析取范式与主合取范式.24（1）求主析取范式(pq)r(pq)r（析取范式）①(pq)(pq)(rr)(pqr)(pqr)m6m7r(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（主析取范式）25（2）求A的主合取范式(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（主合取范式）263.主范式的用途——与真值表相同.（1）求公式的成真成假赋值(pq)rm1m3m5m6m7，其成真赋值为001,011,101,110,111，当然成假赋值为000,010,100.类似地，由主合取范式也立即求出成假或成真赋值.272）判断公式的类型设A含n个命题变项.A为重言式A的主析取范式含2n个极小项A的主合取范式为1.A为矛盾式A的主析取范式为0A的主合析取范式含2n个极大项A为非重言式的可满足式A的主析取范式中至少含一个（但不是全部）极小项A的主合取范式中至少含一个（但不是全部）极大项28（3）判断两个公式是否等值例用主析取范式判两个公式是否等值⑴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显见，⑴中的两公式等值，而⑵的不等值.（4）解实际问题（见书上例2.12）6.最后说明两点：由公式A的主析取范式确定它的主合取范式，反之亦然.用公式A的真值表求A的主范式.291．定义定义2.7设S是一个联结词集合，如果任何n(n1)元真值函数都可以由仅含S中的联结词构成的公式表示，则称S是联结词完备集说明：若S是联结词完备集，则任何命题公式都可由S中的联结词所表示二、联结词的完备集1．一些联结词完备集定理2.6S={,,}是联结词完备集证明的关键：主析取（主合取）范式存在惟一性定理30第二章习题课一、本章的主要内容及要求1．基本内容等值式与等值演算基本的等值式（16组，24个公式）主析取与主合取范式联结词完备集31二、练习题1．设A与B均为含n个命题变项的公式，判断下列命题是否为真？（1）AB当且仅当A与B有相同的主析取范式（2）若A为重言式，则A的主合取范式为0（3）若A为矛盾式，则A的主析取范式为1（4）任何公式都能等值地化成{,}中的公式（5）任何公式都能等值地化成{,,}中的公式32（1）为真，这是显然的（2）为假.注意,任何公式与它的主范式是等值的，显然重言式不能与0等值。重言式的主合取范式不含极大项，因而主合取范式为1.（3）的分析类似于（2），矛盾式的主合取范式为0.（4）为假，因为{,}不是完备集，比如矛盾式(pq)q不能化成{,}中的公式.（5）为真，注意{,,}的子集{,}为完备集.332．通过求主范式判公式类型（1）(pq)(qp)（2）(pq)q（3）(pq)p（1）重言式，（2）矛盾式，（3）可满足式344.某公司要从赵、钱、孙、李、周五名新毕业的大学生中选派一些人出国学习.选派必须满足以下条件：（1）若赵去，钱也去.（2）李、周两人中必至少有一人去（3）钱、孙两人中去仅去一人.（4）孙、李两人同去或同不去.（5）若周去，则赵、钱也去.用等值演算法分析该公司如何选派他们出国？35解此类问题的步骤应为：○1将简单命题符号化○2写出各复合命题○3写出由②中复合命