离散数学之等值演算.ppt

《离散数学之等值演算.ppt》由会员分享，可在线阅读，更多相关《离散数学之等值演算.ppt（35页珍藏版）》请在三一办公上搜索。

1、1,1.3 命题逻辑等值演算,等值式基本等值式等值演算置换规则,2,等值式,定义 若等价式AB是重言式，则称A与B等值，记作AB，并称AB是等值式说明：定义中，A,B,均为元语言符号,A或B中可能有哑元出现.例如，在(pq)(pq)(rr)中，r为左边公式的哑元.用真值表可验证两个公式是否等值请验证：p(qr)(pq)r p(qr)(pq)r,3,基本等值式,双重否定律:AA等幂律：AAA,AAA交换律:ABBA,ABBA结合律:(AB)CA(BC)(AB)CA(BC)分配律:A(BC)(AB)(AC)A(BC)(AB)(AC),4,基本等值式(续),德摩根律:(AB)AB(AB)AB吸收律:

2、A(AB)A,A(AB)A零律:A11,A00 同一律:A0A,A1A排中律:AA1矛盾律:AA0,5,基本等值式(续),蕴涵等值式:ABAB等价等值式:AB(AB)(BA)假言易位:ABBA等价否定等值式:ABAB归谬论:(AB)(AB)A注意:A,B,C代表任意的命题公式牢记这些等值式是继续学习的基础,6,等值演算与置换规则,等值演算:由已知的等值式推演出新的等值式的过程置换规则：若AB,则(B)(A)等值演算的基础：(1)等值关系的性质：自反、对称、传递(2)基本的等值式(3)置换规则,7,应用举例证明两个公式等值,例1 证明 p(qr)(pq)r证 p(qr)p(qr)（蕴涵等值式，置

3、换规则）(pq)r（结合律，置换规则）(pq)r（德摩根律，置换规则）(pq)r（蕴涵等值式，置换规则）,说明:也可以从右边开始演算（请做一遍）因为每一步都用置换规则，故可不写出 熟练后，基本等值式也可以不写出,8,应用举例证明两个公式不等值,例2 证明:p(qr)(pq)r 用等值演算不能直接证明两个公式不等值,证明两个公式不等值的基本思想是找到一个赋值使一个成真,另一个成假.方法一 真值表法（自己证）方法二 观察赋值法.容易看出000,010等是左边的的成真赋值，是右边的成假赋值.方法三 用等值演算先化简两个公式，再观察.,9,应用举例判断公式类型,例3 用等值演算法判断下列公式的类型(1

4、)q(pq)解 q(pq)q(pq)（蕴涵等值式）q(pq)（德摩根律）p(qq)（交换律，结合律）p0（矛盾律）0（零律）由最后一步可知，该式为矛盾式.,10,例3(续),(2)(pq)(qp)解(pq)(qp)(pq)(qp)（蕴涵等值式）(pq)(pq)（交换律）1由最后一步可知，该式为重言式.问：最后一步为什么等值于1？,11,例3(续),(3)(pq)(pq)r)解(pq)(pq)r)(p(qq)r（分配律）p1r（排中律）pr（同一律）这不是矛盾式，也不是重言式，而是非重言式的可满足式.如101是它的成真赋值,000是它的成假赋值.,总结：A为矛盾式当且仅当A0 A为重言式当且仅当

5、A1说明：演算步骤不惟一,应尽量使演算短些,12,1.4 范式,析取范式与合取范式 主析取范式与主合取范式,13,析取范式与合取范式,文字:命题变项及其否定的总称简单析取式:有限个文字构成的析取式如 p,q,pq,pqr,简单合取式:有限个文字构成的合取式如 p,q,pq,pqr,析取范式:由有限个简单合取式组成的析取式 A1A2Ar,其中A1,A2,Ar是简单合取式合取范式:由有限个简单析取式组成的合取式 A1A2Ar,其中A1,A2,Ar是简单析取式,14,析取范式与合取范式(续),范式:析取范式与合取范式的总称公式A的析取范式:与A等值的析取范式公式A的合取范式:与A等值的合取范式说明：

6、单个文字既是简单析取式，又是简单合取式pqr,pqr既是析取范式，又是合取范式(为什么?),15,命题公式的范式,定理 任何命题公式都存在着与之等值的析取范式与合取范式.求公式A的范式的步骤：(1)消去A中的,（若存在）(2)否定联结词的内移或消去(3)使用分配律 对分配（析取范式）对分配（合取范式）公式的范式存在，但不惟一,16,求公式的范式举例,例 求下列公式的析取范式与合取范式(1)A=(pq)r解(pq)r(pq)r（消去）pqr（结合律）这既是A的析取范式（由3个简单合取式组成的析取式），又是A的合取范式（由一个简单析取式组成的合取式）,17,求公式的范式举例(续),(2)B=(pq

7、)r解(pq)r(pq)r（消去第一个）(pq)r（消去第二个）(pq)r（否定号内移德摩根律）这一步已为析取范式（两个简单合取式构成）继续：(pq)r(pr)(qr)（对分配律）这一步得到合取范式（由两个简单析取式构成）,18,2元真值函数对应的真值表,19,极小项与极大项,定义 在含有n个命题变项的简单合取式(简单析取式)中，若每个命题变项均以文字的形式出现且仅出现一次，称这样的简单合取式(简单析取式)为极小项(极大项）.说明：n个命题变项产生2n个极小项和2n个极大项 2n个极小项（极大项）均互不等值 在极小项和极大项中文字均按下标或字母顺序排列 用mi表示第i个极小项，其中i是该极小项

8、成真赋值的十 进制表示.用Mi表示第i个极大项，其中i是该极大项成 假赋值的十进制表示,mi(Mi)称为极小项(极大项)的名称.mi与Mi的关系:mi Mi,Mi mi,20,极小项与极大项(续),由p,q两个命题变项形成的极小项与极大项,21,由p,q,r三个命题变项形成的极小项与极大项,22,主析取范式与主合取范式,主析取范式:由极小项构成的析取范式主合取范式:由极大项构成的合取范式例如，n=3,命题变项为p,q,r时，(pqr)(pqr)m1m3 是主析取范式(pqr)(pqr)M1M5 是主合取范式 A的主析取范式:与A等值的主析取范式 A的主合取范式:与A等值的主合取范式.,23,主

9、析取范式与主合取范式(续),定理 任何命题公式都存在着与之等值的主析取范式和主合取范式,并且是唯一的.用等值演算法求公式的主范式的步骤：(1)先求析取范式（合取范式）(2)将不是极小项（极大项）的简单合取式（简 单析取式）化成与之等值的若干个极小项的析 取（极大项的合取），需要利用同一律（零 律）、排中律（矛盾律）、分配律、幂等律等.(3)极小项（极大项）用名称mi（Mi）表示，并按角标从小到大顺序排序.,24,求公式的主范式,例 求公式 A=(pq)r的主析取范式与主合 取范式.(1)求主析取范式(pq)r(pq)r,（析取范式）(pq)(pq)(rr)(pqr)(pqr)m6m7,25,求

10、公式的主范式(续),r(pp)(qq)r(pqr)(pqr)(pqr)(pqr)m1m3m5m7,代入并排序，得(pq)r m1m3m5 m6m7（主析取范式）,26,求公式的主范式(续),(2)求A的主合取范式(pq)r(pr)(qr),（合取范式）pr p(qq)r(pqr)(pqr)M0M2,27,求公式的主范式(续),qr(pp)qr(pqr)(pqr)M0M4,代入并排序，得(pq)r M0M2M4（主合取范式）,28,主范式的用途与真值表相同,(1)求公式的成真赋值和成假赋值 例如(pq)r m1m3m5 m6m7，其成真赋值为001,011,101,110,111，其余的赋值 0

11、00,010,100为成假赋值.类似地，由主合取范式也可立即求出成 假赋值和成真赋值.,29,主范式的用途(续),(2)判断公式的类型 设A含n个命题变项，则 A为重言式A的主析取范式含2n个极小项 A的主合取范式为1.A为矛盾式 A的主析取范式为0 A的主合取范式含2n个极大项A为非重言式的可满足式A的主析取范式中至少含一个且不含全部极小项A的主合取范式中至少含一个且不含全部极大项,30,主范式的用途(续),例 用主析取范式判断下述两个公式是否等值：p(qr)与(pq)r p(qr)与(pq)r解 p(qr)=m0m1m2m3 m4m5 m7(pq)r=m0m1m2m3 m4m5 m7(pq

12、)r=m1m3 m4m5 m7故中的两公式等值，而的不等值.,(3)判断两个公式是否等值,说明：由公式A的主析取范式确定它的主合取范式，反之亦然.用公式A的真值表求A的主范式.,31,主范式的用途(续),例 某公司要从赵、钱、孙、李、周五名新毕业的大学生中选派一些人出国学习.选派必须满足以下条件：(1)若赵去，钱也去；(2)李、周两人中至少有一人去；(3)钱、孙两人中有一人去且仅去一人；(4)孙、李两人同去或同不去；(5)若周去，则赵、钱也去.试用主析取范式法分析该公司如何选派他们出国？,32,例(续),解此类问题的步骤为：将简单命题符号化 写出各复合命题 写出由中复合命题组成的合取式 求中所

13、得公式的主析取范式,33,例(续),解 设p：派赵去，q：派钱去，r：派孙去，s：派李去，u：派周去.(1)(pq)(2)(su)(3)(qr)(qr)(4)(rs)(rs)(5)(u(pq)(1)(5)构成的合取式为 A=(pq)(su)(qr)(qr)(rs)(rs)(u(pq),34,例(续),A的演算过程如下:A(pq)(qr)(qr)(su)(u(pq)(rs)(rs)（交换律)B1=(pq)(qr)(qr)(pqr)(pqr)(qr)（分配律）B2=(su)(u(pq)(su)(pqs)(pqu)（分配律）B1B2(pqrsu)(pqrsu)(qrsu)(pqrs)(pqru)再令 B3=(rs)(rs),35,例(续),得 A B1B2B3(pqrsu)(pqrsu)注意：在以上演算中多次用矛盾律要求：自己演算一遍 A(pqrsu)(pqrsu)结论：由可知，A的成真赋值为00110与11001，因而派孙、李去（赵、钱、周不去）或派赵、钱、周去（孙、李不去）.,