离散数学讲义.ppt

1、1.3命题逻辑等值演算命题逻辑等值演算 等值式等值式基本等值式基本等值式等值演算等值演算置换规则置换规则1鬼谷子问徒鬼谷子问徒 n孙膑，庞涓都是鬼谷子的徒弟。一天鬼谷子出了这道题目：他从2到99中选出两个不同的整数，把积告诉孙，把和告诉庞。n庞说：我虽然不能确定这两个数是什么，但是我肯定你也不知道这两个数是什么。n孙说：我本来的确不知道，但是听你这么一说，我现在能够确定这两个数字了。n庞说：既然你这么说，我现在也知道这两个数字是什么了。n请问这两个数字是什么？为什么？2等值式等值式 定义定义若等价式若等价式AB是重言式，则称是重言式，则称A与与B等值等值，记作记作AB，并称并称AB是是等值式等

2、值式说明：定义中，说明：定义中，A,B,均为元语言符号均为元语言符号,A或或B中中可能有哑元出现可能有哑元出现.例如，在例如，在(pq)(p q)(r r)中，中，r为左边为左边公式的哑元公式的哑元.用真值表可验证两个公式是否等值用真值表可验证两个公式是否等值请验证：请验证：p(qr)(p q)r p(qr)(pq)r3基本等值式基本等值式 双重否定律双重否定律:AA等幂律等幂律：A AA,A AA交换律交换律:A BB A,A BB A结合律结合律:(A B)CA(B C)(A B)CA(B C)分配律分配律:A(B C)(A B)(A C)A(B C)(A B)(A C)4基本等值式基本等

3、值式(续续)德德摩根律摩根律 :(A B)AB(A B)AB吸收律吸收律:A(A B)A,A(A B)A零律零律:A 11,A 00同一律同一律:A 0A,A 1A排中律排中律:AA1矛盾律矛盾律:AA05基本等值式基本等值式(续续)蕴涵等值式蕴涵等值式:ABA B等价等值式等价等值式:AB(AB)(BA)假言易位假言易位:ABBA等价否定等值式等价否定等值式:ABAB归谬论归谬论:(AB)(AB)A注意注意:A,B,C代表任意的命题公式代表任意的命题公式牢记这些等值式是继续学习的基础牢记这些等值式是继续学习的基础6等值演算与置换规则等值演算与置换规则 等值演算等值演算:由已知的等值式推演出新

4、的等值式的过程由已知的等值式推演出新的等值式的过程置换规则置换规则：若：若AB,则则(B)(A)等值演算的基础：等值演算的基础：(1)等值关系的性质：自反、对称、传递等值关系的性质：自反、对称、传递(2)基本的等值式基本的等值式(3)置换规则置换规则7应用举例应用举例证明两个公式等值证明两个公式等值 例例1证明证明p(qr)(p q)r证证p(qr)p(q r)（蕴涵等值式，置换规则）蕴涵等值式，置换规则）(pq)r（结合律，置换规则）结合律，置换规则）(p q)r（德摩根律，置换规则）德摩根律，置换规则）(p q)r（蕴涵等值式，置换规则）蕴涵等值式，置换规则）说明说明:也可以从右边开始演算

5、（请做一遍）也可以从右边开始演算（请做一遍）因为每一步都用置换规则，故可不写出因为每一步都用置换规则，故可不写出 熟练后，基本等值式也可以不写出熟练后，基本等值式也可以不写出 8应用举例应用举例证明两个公式不等值证明两个公式不等值例例2证明证明:p(qr)(pq)r用等值演算不能直接证明两个公式不等值用等值演算不能直接证明两个公式不等值,证明两证明两个公式不等值的基本思想是找到一个赋值使一个成个公式不等值的基本思想是找到一个赋值使一个成真真,另一个成假另一个成假.方法一方法一真值表法（自己证）真值表法（自己证）方法二方法二观察赋值法观察赋值法.容易看出容易看出000,010等是左边的等是左边的

6、成真赋值，是右边的成假赋值成真赋值，是右边的成假赋值.方法三方法三用等值演算先化简两个公式，再观察用等值演算先化简两个公式，再观察.9应用举例应用举例判断公式类型判断公式类型 例例3 3用等值演算法判断下列公式的类型用等值演算法判断下列公式的类型(1)q(pq)解解 q(pq)q(p q)（蕴涵等值式）蕴涵等值式）q(pq)（德摩根律）德摩根律）p(qq)（交换律，结合律）交换律，结合律）p 0（矛盾律）矛盾律）0（零律）（零律）由最后一步可知，该式为矛盾式由最后一步可知，该式为矛盾式.10例例3(续续)(2)(pq)(qp)解解(pq)(qp)(p q)(qp)（蕴涵等值式）蕴涵等值式）(p

7、 q)(p q)（交换律）交换律）1由最后一步可知，该式为重言式由最后一步可知，该式为重言式.问：最后一步为什么等值于问：最后一步为什么等值于1？11例例3(续续)(3)(p q)(pq)r)解解(p q)(pq)r)(p(qq)r（分配律）分配律）p 1 r（排中律）排中律）p r（同一律）同一律）这不是矛盾式，也不是重言式，而是非重言式的可这不是矛盾式，也不是重言式，而是非重言式的可满足式满足式.如如101是它的成真赋值是它的成真赋值,000是它的成假赋值是它的成假赋值.总结：总结：A为矛盾式当且仅当为矛盾式当且仅当A0 A为重言式当且仅当为重言式当且仅当A1说明：演算步骤不惟一说明：演算

8、步骤不惟一,应尽量使演算短些应尽量使演算短些12几个几个500强面试题强面试题n为什么下水道的井盖是圆的？n一个屋子有一个门（门是关闭的）和3 盏电灯。屋外有3 个开关，分别与这3 盏灯相连。你可以随意操纵这些开关，可一旦你将门打开，就不能变换开关了。确定每个开关具体管哪盏灯。n假设时钟到了12 点。注意时针和分针重叠在一起。在一天之中，时针和分针共重叠多少次？你知道它们重叠时的具体时间吗？131.4联结词全功能集联结词全功能集 复合联结词复合联结词 排斥或排斥或 与非式与非式 或非式或非式真值函数真值函数联结词全功能集联结词全功能集14复合联结词复合联结词 排斥或排斥或:p q(pq)(p

9、q)与非式与非式:p q(p q)或非式或非式:p q(p q)15真值函數真值函數 问题：含问题：含n个命题变项的所有公式共产生多少个互个命题变项的所有公式共产生多少个互不相同的真值表？不相同的真值表？答案为答案为 个，为什么？个，为什么？定义定义称定义域为称定义域为000,001,111，值域，值域为为0,1的函数是的函数是n元真值函数元真值函数，定义域中的元素是，定义域中的元素是长为长为n的的0,1串串.常用常用F:0,1n0,1表示表示F是是n元真值元真值函数函数.共有共有 个个n元真值函数元真值函数.例如例如 F:0,120,1，且，且F(00)=F(01)=F(11)=0，F(01

10、)=1，则，则F为一个确定的为一个确定的2元真值函数元真值函数.16命题公式与真值函数命题公式与真值函数对于任何一个含对于任何一个含n个命题变项的命题公式个命题变项的命题公式A，都存在都存在惟一的一个惟一的一个n元真值函数元真值函数F为为A的真值表的真值表.等值的公式对应的真值函数相同等值的公式对应的真值函数相同.下表给出所有下表给出所有2元真值函数对应的真值表元真值函数对应的真值表,每一个含每一个含2 2个命题变项的公式的真值表都可以在下表中找到个命题变项的公式的真值表都可以在下表中找到.例如：例如：pq,p q,(p q)(pq)q)等等都对应都对应表中的表中的172元真值函数对应的真值表

11、元真值函数对应的真值表p q0001011100000000000011110011001101010101 p q0001011111111111000011110011001101010101 18联结词的全功能集联结词的全功能集 定义定义在一个联结词的集合中，如果一个联结词可在一个联结词的集合中，如果一个联结词可由集合中的其他联结词定义，则称此联结词为由集合中的其他联结词定义，则称此联结词为冗余冗余的联结词的联结词，否则称为，否则称为独立的联结词独立的联结词.例如例如,在联结词集在联结词集,中，由于中，由于pqp q,所以，所以，为冗余的联结词为冗余的联结词;类似地，类似地，也是冗余的也

12、是冗余的联结词联结词.又在又在,中，由于中，由于p q(pq)，所以，所以，是冗余的联结词是冗余的联结词.类似地，类似地，也是冗余的联也是冗余的联结词结词.19联结词的全功能集联结词的全功能集(续续)定义定义设设S是一个联结词集合，如果任何是一个联结词集合，如果任何n(n 1)元元真值函数都可以由仅含真值函数都可以由仅含S中的联结词构成的公式表中的联结词构成的公式表示，则称示，则称S是是联结词全功能集联结词全功能集.说明：说明：若若S是联结词全功能集，则任何命题公式都可用是联结词全功能集，则任何命题公式都可用S中的联结词表示中的联结词表示.若若S1,S2是两个联结词集合，且是两个联结词集合，且S1 S2.若若S1是全是全功能集，则功能集，则S2也是全功能集也是全功能集.20联结词的全功能集实例联结词的全功能集实例(1)S1=,(2)S2=,(3)S3=,(4)S4=,(5)S5=,(6)S6=(7)S8=,而而,等则不是联结词全功能集等则不是联结词全功能集.21