离散数学-第2章-命题逻辑等值演算

本章的主要内容：等值式与基本的等值式等值演算与置换规则析取范式与合取范式，主析取范式与主合取范式联结词完备集本章与其他各章的联系是第一章的抽象与延伸是后续各章的先行准备第二章命题逻辑等值演算一、等值式与基本的等值式1．等值式定义2.1若等价式AB是重言式，则称A与B等值，记作AB，并称AB是等值式几点说明：定义中，A,B,均为元语言符号A或B中可能有哑元出现.例如，在(pq)((pq)(rr))中，r为左边公式的哑元.判断等值式有如下方法：1.真值表2.等值演算3.范式第一节等值式二、用真值表判断公式的等值例2.1判断下面两个公式是否等值：┐(p∨q)与┐p∧┐q解用真值表法判断┐(p∨q)(┐p∧┐q)是否为重言式。此等价式的真值表:1．基本的等值式双重否定律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)A零律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组等值式包含了24个重要等值式。由于A,B,C可以代表任意的命题公式，因而以上各等值式都是用元语言符号书写的，称这样的等值式为等值式模式，每个等值式模式都给出了无穷多个同类型的具体的等值式。例如，在蕴涵等值式（2.12）中，取A=p，B=q时，得等值式:p→q┐p∨q当取A=p∨q∨r，B=p∧q时，得等值式:(p∨q∨r)→(p∧q)┐(p∨q∨r)∨(p∧q)这些具体的等值式都被称为原来的等值式模式的代入实例。二、等值演算与置换规则1．等值演算——由已知的等值式推演出新的等值式的过程2．等值演算的基础：（1）等值关系的性质：自反、对称、传递性（2）基本的等值式（3）置换规则（见3）3．置换规则设(A)是含公式A的命题公式，(B)是用公式B置换了(A)中的所有的A后得到的命题公式，若BA，则(B)(A)三、等值演算的应用举例（以后章节待续）1．证明两个公式等值例证明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证方法一真值表法（自己证）方法二观察赋值法.易知000,010等是左边的成真赋值，是右边的成假赋值方法三用等值演算先化简两个公式，再观察.2.判断公式类型例用等值演算法判断下列公式的类型（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）为矛盾式.（2）(pq)(qp)(pq)(qp)（蕴涵等值式）(pq)(pq)（交换律）1由最后一步可知，（2）为重言式.问：最后一步为什么等值于1？说明：（2）的演算步骤可长可短，以上演算最省.（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.6例2.6在某次研讨会的中间休息时间，3名与会者根据王教授的口音对他是哪个省市的人进行了判断：甲说王教授不是苏州人，是上海人。乙说王教授不是上海人，是苏州人。丙说王教授既不是上海人，也不是杭州人。听完以上3人的判断后，王教授笑着说，他们3人中有一人说的全对，有一人说对了一半，另一人说的全不对。试用逻辑演算法分析王教授到底是哪里人？解设命题p：王教授是苏州人。q：王教授是上海人。r：王教授是杭州人。p,q,r中必有一个真命题，两个假命题，要通过逻辑演算将真命题找出来。设甲的判断为A1=┐p∧q乙的判断为A2=p∧┐q丙的判断为A3=┐q∧┐r一、析取范式与合取范式定义2.2命题变项及其否定统称作文字。仅有有限个文字构成的析取式称作简单析取式。仅有有限个文字构成的合取式称作简单合取式。p,┐q等为一个文字构成简单析取式，p∨┐p，┐p∨q等为2个文字构成的简单析取式，┐p∨┐q∨r,p∨┐q∨r等为3个文字构成的简单析取式。┐p,q等为一个文字构成的简单合取式，┐p∧p，p∧┐q等为2个文字构成的简单合取式，p∧q∧┐r,┐p∧p∧q等为3个文字构成的简单合取式。应该注意，一个文字既是简单析取式，又是简单合取式。为方便起见，有时用A1,A2,…,As表示s个简单析取式或s个简单合取式。定理2.1（1）一个简单析取式是重言式当且仅当它同时含某个命题变项及它的否定式。（2）一个简单合取式是矛盾式当且仅当它同时含有某个命题变项及它的否定式。第二节析取范式与合取范式证明：设Ai是含n个文字的简单析取式，若Ai中既含有某个命题变项pj，又含有它的否定式┐pj，由交换律、排中律和零律可知，Ai为重言式。反之，若Ai为重言式，则它必同时含某个命题变项及它的否定式，否则，若将Ai中的不带否定号的命题变项都取0，带否定号的命题变项都取1，此赋值为Ai的成假赋值，这与Ai是重言式相矛盾。类似的讨论可知，若Ai是含n个命题变项的简单合取式，且Ai为矛盾式，则Ai中必同时含有某个命题变项及它的否定式，反之亦然。如：p∨┐p，p∨┐p∨r都是重言式。┐p∨q，┐p∨┐q∨r都不是重言式。定义2.3（1）由有限个简单合取式构成的析取式称为析取范式。（2）由有限个简单析取式构成的合取式称为合取范式。（3）析取范式与合取范式统称为范式。设Ai(i=1,2,…,s)为简单合取式，则A=A1∨A2∨…∨As为析取范式。例如，A1=p∧┐q，A2=┐q∧┐r，A3=p，则由A1,A2,A3构造的析取范式为A=A1∨A2∨A3=(p∧┐q)∨(┐q∧┐r)∨p类似地，设Ai(i=1,2,…,s)为简单的析取式，则A=A1∧A2∧…∧As为合取范式。例如，取A1=p∨q∨r，A2=┐p∨┐q，A3=r，则由A1,A2,A3组成的合取范式为A=A1∧A2∧A3=(p∨q∨r)∧(┐p∨┐q)∧r形如┐p∧q∧r的公式既是一个简单合取式构成的析取范式，又是由三个简单析取式构成的合取范式。类似地，形如p∨┐q∨r的公式既是含三个简单合取式的析取范式，又是含一个简单析取式的合取范式。3.求公式的范式举例例求下列公式的析取范式与合取范式（1）A=(pq)r（2）B=(pq)r解（1）(pq)r(pq)r（消去）pqr（结合律）注意：最后结果既是A的析取范式（由3个简单合取式组成的析取式），又是A的合取范式（由一个简单析取式组成的合取式）（2）(pq)r(pq)r（消去第一个）(pq)r（消去第二个）(pq)r（否定号内移——德摩根律）最后一步已为析取范式（两个简单合取式构成）继续：B(pq)r(pr)(qr)（对分配律）最后一步已为合取范式（由两个简单析取式构成）二、主析取范式与主合取范式1．极小项与极大项定义2.4在含有n个命题变项的简单合取式（简单析取式）中，若每个命题变项均以文字的形式在其中出现且仅出现一次，而且第i（1in）个文字出现在左起第i位上，称这样的简单合取式（简单析取式）为极小项（极大项）.几点说明：n个命题变项产生2n个极小项和2n个极大项2n个极小项（极大项）均互不等值，有且只有一个成真赋值用mi表示第i个极小项，其中i是该极小项成真赋值的十进制表示.Mi表示第i个极大项，其中i是该极大项成假赋值的十进制表示,mi（Mi）称为极小项（极大项）的名称.由p,q两个命题变项形成的极小项与极大项由下表给出极小项极大项公式成真赋值名称公式成假赋值名称pqpqpqpq00011011m0m1m2m3pqpqpqpq00011011M0M1M2M3由p,q,r三个命题变项形成的极小项与极大项由下表给出.极小项极大项公式成真赋值名称公式成假赋值名称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r000001010011100101110111M0M1M2M3M4M5M6M7mi与Mi的关系由书上定理2.4给出，即miMi,Mimi2.主析取范式与主合取范式定义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——主合取范式3.命题公式A的主析取范式与主合取范式（1）与A等值的主析取范式称为A的主析取范式；与A等值的主合取范式称为A的主合取范式.（2）主析取范式的存在惟一定理定理2.5任何命题公式都存在着与之等值的主析取范式和主合取范式,并且是惟一的4．用等值演算法求公式的主范式的步骤：（1）先求析取范式（合取范式）（2）将不是极小项（极大项）的简单合取式（简单析取式）化成与之等值的若干个极小项之析取（极大项之合取），利用的等值式为同一律（零律）、排中律（矛盾律）、分配律、幂等律等.（3）极小项（极大项）用名称mi（Mi）表示，并按角标从小到大顺序排序.例求公式A=(pq)r的主析取范式与主合取范式.（1）求主析取范式(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（主析取范式）（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（主合取范式）3.主范式的用途——与真值表相同.（1）求公式的成真成假赋值(pq)rm1m3m5m6m7，其成真赋值为001,011,101,110,111，当然成假赋值为000,010,100.类似地，由主合取范式也立即求出成假或成真赋值.（2）判断公式的类型设A含n个命题变项.A为重言式A的主析取范式含2n个极小项A的主合取范式为1.A为矛盾式A的主析取范式为0A的主合析取范式含2n个极大项A为非重言式的可满足式A的主析取范式中至少含一个（但不是全部）极小项A的主合取范式中