《离散数学讲义.ppt》由会员分享，可在线阅读，更多相关《离散数学讲义.ppt（21页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1现在学习的是第1页，共21页鬼谷子问徒鬼谷子问徒 n孙膑，庞涓都是鬼谷子的徒弟。一天鬼谷子出了这道题目：他从2到99中选出两个不同的整数，把积告诉孙，把和告诉庞。n庞说：我虽然不能确定这两个数是什么，但是我肯定你也不知道这两个数是什么。n孙说：我本来的确不知道，但是听你这么一说，我现在能够确定这两个数字了。n庞说：既然你这么说，我现在也知道这两个数字是什么了。n请问这两个数字是什么？为什么？现在学习的是第2页，共21页等值式等值式定义定义 若等价式若等价式AB是重言式，则称是重言式，则称A与与B等值等值，记作记作AB，并称，并称AB是是等值式等值式说明：定义中，说明：定义中，A,B,均为元语
2、言符号均为元语言符号,A或或B中中可能有哑元出现可能有哑元出现.例如，在例如，在(pq)(p q)(r r)中，中，r为左边为左边公式的哑元公式的哑元.用真值表可验证两个公式是否等值用真值表可验证两个公式是否等值请验证：请验证：p(qr)(p q)r p(qr)(pq)r 现在学习的是第3页，共21页基本等值式基本等值式双重否定律双重否定律: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页，共21页基本等值式基
3、本等值式(续续)德德摩根律摩根律 :(A B)AB (A B)AB吸收律吸收律:A(A B)A,A(A B)A零律零律:A 11,A 00 同一律同一律:A 0A,A 1A排中律排中律:AA1矛盾律矛盾律:AA0现在学习的是第5页，共21页基本等值式基本等值式(续续)蕴涵等值式蕴涵等值式:ABA B等价等值式等价等值式:AB(AB)(BA)假言易位假言易位:ABBA等价否定等值式等价否定等值式:ABAB归谬论归谬论:(AB)(AB)A注意注意:A,B,C代表任意的命题公式代表任意的命题公式牢记这些等值式是继续学习的基础牢记这些等值式是继续学习的基础现在学习的是第6页，共21页等值演算与置换规则
4、等值演算与置换规则等值演算等值演算:由已知的等值式推演出新的等值式的过程由已知的等值式推演出新的等值式的过程置换规则置换规则：若：若AB,则则(B)(A)等值演算的基础：等值演算的基础：(1)等值关系的性质：自反、对称、传递等值关系的性质：自反、对称、传递 (2)基本的等值式基本的等值式 (3)置换规则置换规则 现在学习的是第7页，共21页应用举例应用举例证明两个公式等值证明两个公式等值例例1 证明证明 p(qr)(p q)r证证 p(qr)p(q r)（蕴涵等值式，置换规则）（蕴涵等值式，置换规则）(pq)r （结合律，置换规则）（结合律，置换规则）(p q)r （德摩根律，置换规则）（德摩
5、根律，置换规则）(p q)r （蕴涵等值式，置换规则）（蕴涵等值式，置换规则）说明说明:也可以从右边开始演算（请做一遍）也可以从右边开始演算（请做一遍）因为每一步都用置换规则，故可不写出因为每一步都用置换规则，故可不写出 熟练后，基本等值式也可以不写出熟练后，基本等值式也可以不写出现在学习的是第8页，共21页应用举例应用举例证明两个公式不等值证明两个公式不等值例例2 证明证明:p(qr)(pq)r 用等值演算不能直接证明两个公式不等值用等值演算不能直接证明两个公式不等值,证明两证明两个公式不等值的基本思想是找到一个赋值使一个成个公式不等值的基本思想是找到一个赋值使一个成真真,另一个成假另一个成
6、假.方法一方法一 真值表法（自己证）真值表法（自己证）方法二方法二 观察赋值法观察赋值法.容易看出容易看出000,010等是左边的等是左边的成真赋值，是右边的成假赋值成真赋值，是右边的成假赋值.方法三方法三 用等值演算先化简两个公式，再观察用等值演算先化简两个公式，再观察.现在学习的是第9页，共21页应用举例应用举例判断公式类型判断公式类型例例3 3 用等值演算法判断下列公式的类型用等值演算法判断下列公式的类型(1)q(pq)解解 q(pq)q(p q)（蕴涵等值式）（蕴涵等值式）q(pq)（德摩根律）（德摩根律）p(qq)（交换律，结合律）（交换律，结合律）p 0 （矛盾律）（矛盾律）0 （
7、零律）（零律）由最后一步可知，该式为矛盾式由最后一步可知，该式为矛盾式.现在学习的是第10页，共21页例例3(续续)(2)(pq)(qp)解解 (pq)(qp)(p q)(qp)（蕴涵等值式）（蕴涵等值式）(p q)(p q)（交换律）（交换律）1由最后一步可知，该式为重言式由最后一步可知，该式为重言式.问：最后一步为什么等值于问：最后一步为什么等值于1？现在学习的是第11页，共21页例例3(续续)(3)(p q)(pq)r)解解 (p q)(pq)r)(p(qq)r （分配律）（分配律）p 1 r （排中律）（排中律）p r （同一律）（同一律）这不是矛盾式，也不是重言式，而是非重言式的可这
8、不是矛盾式，也不是重言式，而是非重言式的可满足式满足式.如如101是它的成真赋值是它的成真赋值,000是它的成假赋值是它的成假赋值.总结：总结：A为矛盾式当且仅当为矛盾式当且仅当A0 A为重言式当且仅当为重言式当且仅当A1说明：演算步骤不惟一说明：演算步骤不惟一,应尽量使演算短些应尽量使演算短些现在学习的是第12页，共21页几个几个500强面试题强面试题n为什么下水道的井盖是圆的？n一个屋子有一个门（门是关闭的）和3 盏电灯。屋外有3 个开关，分别与这3 盏灯相连。你可以随意操纵这些开关，可一旦你将门打开，就不能变换开关了。确定每个开关具体管哪盏灯。n假设时钟到了12 点。注意时针和分针重叠在
9、一起。在一天之中，时针和分针共重叠多少次？你知道它们重叠时的具体时间吗？现在学习的是第13页，共21页1.4 联结词全功能集联结词全功能集复合联结词复合联结词 排斥或排斥或 与非式与非式 或非式或非式真值函数真值函数联结词全功能集联结词全功能集现在学习的是第14页，共21页复合联结词复合联结词排斥或排斥或:p q(pq)(p q)与非式与非式:p q(p q)或非式或非式:p q(p q)现在学习的是第15页，共21页真值函數真值函數问题：含问题：含n个命题变项的所有公式共产生多少个互个命题变项的所有公式共产生多少个互不相同的真值表？不相同的真值表？答案为答案为 个，为什么？个，为什么？定义定
10、义 称定义域为称定义域为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)=1，则，则F为一个确定的为一个确定的2元真值函数元真值函数.现在学习的是第16页，共21页命题公式与真值函数命题公式与真值函数 对于任何一个含对于任何一个含n个命题变项的命题公式个命题变项的命题公式A，都存在，都存在惟一的一个惟一的一个n元
11、真值函数元真值函数F为为A的真值表的真值表.等值的公式对应的真值函数相同等值的公式对应的真值函数相同.下表给出所有下表给出所有2元真值函数对应的真值表元真值函数对应的真值表,每一个含每一个含2 2个命题变项的公式的真值表都可以在下表中找到个命题变项的公式的真值表都可以在下表中找到.例如：例如：pq,p q,(p q)(pq)q)等等都对应都对应表中的表中的现在学习的是第17页，共21页2元真值函数对应的真值表元真值函数对应的真值表p q0 00 10 11 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1p q0
12、 00 10 11 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1现在学习的是第18页，共21页联结词的全功能集联结词的全功能集定义定义 在一个联结词的集合中，如果一个联结词可在一个联结词的集合中，如果一个联结词可由集合中的其他联结词定义，则称此联结词为由集合中的其他联结词定义，则称此联结词为冗余冗余的联结词的联结词，否则称为，否则称为独立的联结词独立的联结词.例如例如,在联结词集在联结词集,中，由于中，由于 pqp q,所以，所以，为冗余的联结词为冗余的联结词;类似地，类似地，也是冗余的也是冗余的联结词联结词
13、.又在又在,中，由于中，由于 p q(pq)，所以，所以，是冗余的联结词是冗余的联结词.类似地，类似地，也是冗余的联也是冗余的联结词结词.现在学习的是第19页，共21页联结词的全功能集联结词的全功能集(续续)定义定义 设设S是一个联结词集合，如果任何是一个联结词集合，如果任何n(n 1)元元真值函数都可以由仅含真值函数都可以由仅含S中的联结词构成的公式表中的联结词构成的公式表示，则称示，则称S是是联结词全功能集联结词全功能集.说明：说明：若若S是联结词全功能集，则任何命题公式都可用是联结词全功能集，则任何命题公式都可用S中的联结词表示中的联结词表示.若若S1,S2是两个联结词集合，且是两个联结词集合，且S1 S2.若若S1是全是全功能集，则功能集，则S2也是全功能集也是全功能集.现在学习的是第20页，共21页联结词的全功能集实例联结词的全功能集实例 (1)S1=,(2)S2=,(3)S3=,(4)S4=,(5)S5=,(6)S6=(7)S8=,而而,等则不是联结词全功能集等则不是联结词全功能集.现在学习的是第21页，共21页