12命题逻辑等值演算.ppt

离散数学,等值演算联结词全功能集,本节的主要内容等值式与基本的等值式等值演算与置换规则联结词全功能集,若A与B有相同的真值表，则说明在2n个赋值下，A与B的真值都相同,于是等价式AB应为重言式。,2.1等值式,两公式什么时候代表了同一个命题呢？抽象地看，它们的真假取值完全相同时即代表了相同的命题。,定义1.10设A,B是两个命题公式，若等价式AB为重言式，则称A与B是等值的，记作AB。,1.等值的定义及说明,用真值表可以验证两个公式是否等值。判断A,B是否等值(AB)判断AB为重言式AB的真值表最后一列全为1在各种赋值下，A，B取值完全相同A,B的真值表完全相同,说明,例2.1判断下面两个公式是否等值(pq)与pq,例题,相等,解答,例题2.2判断下列各组公式是否等值(1)p(qr)与(pq)r(2)(pq)r与(pq)r,例题,相等,不相等,解答,（1）双重否定律AA（2）幂等律AAA，AAA（3）交换律ABBA，ABBA（4）结合律(AB)CA(BC)(AB)CA(BC)（5）分配律A(BC)(AB)(AC)（对的分配律）A(BC)(AB)(AC)（对的分配律）（6）德摩根律(AB)AB(AB)AB（7）吸收律A(AB)A，A(AB)A,2.基本等值式,（8）零律A11，A00（9）同一律A0A。A1A（10）排中律AA1（11）矛盾律AA0（12）蕴涵等值式ABAB（13）等价等值式AB(AB)(BA)（14）假言易位ABBA（15）等价否定等值式ABAB（16）归谬论(AB)(AB)A,其中A,B,C可以代表任意的公式，称这样的等值式为等值式模式。每个等值式模式都给出了无穷多个同类型的具体的等值式。例如，在蕴涵等值式ABAB中，取A=p，B=q时，得等值式pqpq取A=pqr，B=pq时，得等值式(pqr)(pq)(pqr)(pq)这些具体的等值式都被称为原来的等值式模式的一个实例。,说明,由已知的等值式推演出另外一些等值式的过程为等值演算。置换规则:设(A)是含公式A的命题公式，(B)是用公式B置换了(A)中所有的A后得到的命题公式，若BA，则(B)(A)。,3.等值演算与置换规则,等值演算的基础等值关系的性质：自反性：AA。对称性：若AB，则BA。传递性：若AB且BC，则AC。基本的等值式置换规则等值演算的应用证明两个公式等值判断公式类型解判定问题,关于等值演算的说明,证明两个公式等值(pq)r(pr)(qr),例题,(pq)r(pq)r（蕴含等值式、置换规则）(pq)r（蕴含等值式、置换规则）(pq)r（德摩根律、置换规则）(pr)(qr)（分配律、置换规则）,也可以从右边开始演算因为每一步都用置换规则，故可不写出熟练后，基本等值式也可以不写出通常不用等值演算直接证明两个公式不等值,解答,说明,例2.3用等值演算法验证等值式(pq)r(pr)(qr),(pr)(qr)(pr)(qr)(蕴含等值式)(pq)r(分配律)(pq)r(德摩根律)(pq)r(蕴含等值式),例题,解答,方法一、真值表法。,方法二、观察法。易知，010是(pq)r的成假赋值，而010是p(qr)的成真赋值，所以原不等值式成立。,例2.4证明：(pq)r与p(qr)不等值,方法三、通过等值演算化成容易观察真值的情况，再进行判断。A=(pq)r(pq)r（蕴涵等值式）(pq)r（蕴涵等值式）(pq)r（德摩根律）B=p(qr)p(qr)（蕴涵等值式）pqr（结合律）000，010是A的成假赋值，而它们是B的成真赋值。,例题2.5用等值演算判断下列公式的类型：（1）(pq)pq（2）(p(pq)r（3）p(pq)p)q),(1)(pq)pq(pq)pq（蕴涵等值式）(pq)p)q（蕴涵等值式）(pq)p)q（德摩根律）(pq)p)q（德摩根律）(pp)(qp)q（分配律）(1(qp)q（排中律）(qq)p（同一律）1p（排中律）1（零律）（重言式）,解答,(2)(p(pq)r(ppq)r(ppq)r0r0（2）为矛盾式,(3)p(pq)p)q)p(pq)p)q)p(pp)(qp)q)p(0(qp)q)p(qpq)p1p易知10，11为（3）的成真赋值，00，01为成假赋值，因而（3）为可满足式,例题2.6在某次研讨会的中间休息时间，3名与会者根据王教授的口音对他是哪个省市的人进行了判断：甲说王教授不是苏州人，是上海人。乙说王教授不是上海人，是苏州人。丙说王教授既不是上海人，也不是杭州人。听完以上3人的判断后，王教授笑着说，他们3人中有一人说的全对，有一人说对了一半，另一人说的全不对。试用逻辑演算法分析王教授到底是哪里人？,设命题p：王教授是苏州人。q：王教授是上海人。r：王教授是杭州人。p,q,r中必有一个真命题，两个假命题，要通过逻辑演算将真命题找出来。设甲的判断为A1=pq乙的判断为A2=pq丙的判断为A3=qr,解答,甲的判断全对：B1=A1=pq甲的判断对一半：B2=(pq)(pq)甲的判断全错：B3=pq乙的判断全对：C1=A2=pq乙的判断对一半：C2=(pq)(pq)乙的判断全错：C3=pq丙的判断全对：D1=A3=qr丙的判断对一半：D2=(qr)(qr)丙的判断全错：D3=qr,由王教授所说E=(B1C2D3)(B1C3D2)(B2C1D3)(B2C3D1)(B3C1D2)(B3C2D1)为真命题。经过等值演算后,可得E(pqr)(pqr)由题设，王教授不能既是上海人，又是杭州人，因而p,r中必有一个假命题，即pqr0，于是Epqr为真命题，因而必有p,r为假命题，q为真命题，即王教授是上海人。甲说的全对，丙说对了一半，而乙全说错了。,例1.1A,B,C,D四人做百米竞赛。观众甲、乙、丙预报比赛的名次为：甲：C第一，B第二；乙：C第二，D第三；丙：A第二，D第四。比赛结束后发现甲、乙、丙每人报告的情况都是各对一半，试问实际的名次？,解：设pi，qi，ri，si表示A第i名，B第i名，C第i名，D第i名，显然pi，qi，ri，si中均有一个真命题。要寻找下列3个成立的真命题(1)（r1q2)(r1q2)1(2)（r2s3)(r2s3)1(3)（p2s4)(p2s4)1,因为真命题的合取仍为真命题，故：1（1）（2）（r1q2r2s3)(r1q2r2s3)(r1q2r2s3)(r1q2r2s3)其中C不能即是第一又是第二，B和C不能都是第二，所以r1q2r2s30r1q2r2s30得出(4)（r1q2r2s3)(r1q2r2s3)(3)和（4）产生新的公式1（3)（4)（p2s4r1q2r2s3)(p2s4r1q2r2s3)(p2s4r1q2r2s3)（p2s4r1q2r2s3)由于A,B不能同时第二，D不能第三又第四。所以(5)1p2s4r1q2r2s3p2q2r1r2s3s4C第一，A第二，D第三，B第四。,排斥或：与非联结词或非联结词,2.3连结词的完备集,定义1.14称F:0，1n0,1为n元真值函数F的自变量为n个命题变量，定义域:0，1n=000,001,111,值域为0，1。n个命题变量共可22n个不同的真值函数。1元真值函数共可4个,2.3连结词的完备集,2个命题变项共有16个,每个真值函数对应无群多个与之等值的命题公式所以每一个命题公式对应唯一的与之等值的真值函数。,2.定义1.15在一个联结词的集合中，如果一个联结词可由集合中的其他联结词定义，则称此联接词为冗余的联结词，否则称为独立的联结词。,在联结词集,中，(pq)pqpq(pq)(qp)(pq)(qp)所以,冗余在,中，由于Pq（Pq）（Pq）所以冗余，但在,中无冗余。,2.定义1.16在任一真值函数都可以用仅含有某一联结词集中的联结词的命题公式表示，则称该联结词集为全功能集。若一个联结词集的全功能中不含冗余的联结词，则称它是极小全功能集。,3.，,，,，,都是全功能集，其中，,是最小功能集。,例1.13若已