《离散数学》浙大讲义.ppt

《《离散数学》浙大讲义.ppt》由会员分享，可在线阅读，更多相关《《离散数学》浙大讲义.ppt（677页珍藏版）》请在三一办公上搜索。

1、1,漫谈离散数学Swimming in Discrete Mathematics,2,什么叫数学？/数学的研究对象是什么？,数学家语录（1914年）：几百个数学的定义,3,什么叫数学？/数学的研究对象是什么？,本身已如此一目了然，以致于没有任何词汇能够把他解说得更清楚的事物，绝不要试图给他下定义。以免被所使用的含混不清的词汇所欺骗。帕斯卡（法、17世纪）,4,数学：心智的产物 珀拉图,数学是研究数量的科学 亚里士得多,5,数是一种离散的数量、线是一种连续的数量。,研究数及其属性的学科叫做算术研究量及其属性的学科叫做几何,研究数和量的学科叫做数学 亚里士得多,6,数学是研究顺序和度量的科学 笛卡

2、尔,顺序=数度量=量,7,数学=逻辑 罗素,逻辑是数学的少年时代数学是逻辑的成年时代,数学是研究结构的科学 布尔巴基学派（30年代）,8,数学作为人类智慧的一种表达形式，反映生动活泼的意念、深入细致的思考、以及完美和谐的愿望。他的基础是逻辑和直觉、分析和推理、共性和个性。科朗，罗宾斯（美）数学是什么，1941年,9,数学的研究对象是客观世界的和逻辑可能的数量关系和结构关系 丁孙石,数学是研究现实世界中量的关系的科学 关肇直,10,研究离散结构的数学分科。（辞海）,Discrete Math.离散数学 研究离散量的关系的一门科学。,11,离散数学的内容：数理逻辑（Mathematics Logi

3、c)集合论(Sets)组合论（Combination)图论（Graph Theory)代数结构（Algbra Structure)线性代数(Linear Algbra)概率论（Propobility Theory),与高等数学的区别:,12,EXAMPLE 3,离散数学的由来与发展:一、古老 历史:计数:自然数 发展:图论:Konigsberg七桥问题 二、年青 新生:计算机:二进制运算,13,DEFINITION 2.,离散数学课程设置：计算机系核心课程 信息类专业必修课程 其它类专业的重要选修课程,14,离散数学的后继课程：数据结构、编译技术、算法分析与设计、人工智能、数据库、,15,离散

4、数学课程的学习方法:强调：逻辑性、抽象性；注重：概念、方法与应用,16,EXAMPLE 5,教材：Discrete Mathematics and Its Application(Forth Edition:1999)Author:Kenneth H.Reson Publisher:McGraw-Hill 机械工业出版社 http:/,17,参考教材：,1、离散数学（左孝琳、李为槛、刘永才，上海科技文献版）2、离散数学-计算机数学基础学习（陈德人，浙大版）3、Discrete Mathematics（Forth Edition:Richard Johnsonbaugh)4、Discrete M

5、athematics（Revised Edition:Biggs)5、Discrete Math.Elements（Liu Chuang Laung),18,教学内容:,数理逻辑（Mathematics Logic)集合论(Sets)组合论（Combination)图论（Graph Theory)代数结构（Algbra Structure)计算模型(Computing Model),19,教学内容:,1.Foundation:Logic,Sets,Functions2.Foundation:Algorithms,the Integers,Matrices,20,教学内容:,3.Mathemat

6、ical Reasoning4.Counting5.Advanced Counting Techniques6.Relations,21,教学内容:,7.Graphs8.Trees9.Boolean Algebra add other system10.Modeling Computation,22,教学网站:,1.课程介绍 2.网络资源导航3.学习讨论区 4.教学课件5.作业及答案,23,相关网站:,http:/,24,用一组基本的指令来编制一个计算机程序，非常类似于从一组公理来构造一个数学证明。D.E.Knuth,设计方案(一)网站主要内容分为5块:1.课程介绍 2.网络资源导航 3.学习

7、讨论区 4.教学课件 5.作业及答案其中又可分为:需经常更新部分,3,4和5以及不需更新部分,1和2制作原始模版时以此为根据(二)各个块的仔细说明:1.课程介绍已经找了一些离散数学的基本介绍,内容比较简单,即使以后有更新,内容也不会发生很大变化,维护容易2.网络资源导航介绍一些国内外优秀的离散数学网站,以及参考文献等,预计内容无重大变化,维护简单3.学习讨论区参考http:/,25,陈德人 email add.:homepage:http:/张三元 email add.:,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,26,基础部分:逻辑(Logic)

8、集合(Sets)算法(Algorithms)数论(Number Theory),2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,27,1.1 逻辑 Logic,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,28,逻辑学：研究推理的一门学科数理逻辑：用数学方法研究推理的一门数学学科,-一套符号体系+一组规则,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,29,数理逻辑的内容：古典数理逻辑：命题逻辑、谓词逻辑 现代数理逻辑：公理化集合论、递归论、模型论、证明论,2/10/20

9、23 3:13 AM,Discrete Math.,DeRen Chen,30,命题 Proposition:一个有确定真或假意义的语句.,命题逻辑 Proposition Logic,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,31,EXAMPLE 1,All the following statements are propositions.1.Washington,D.C.,is the capital of the United States of America.2.Toronto is the capital of Canada.3.1+

10、1=2.4.2+2=3.,Propositions 1 and 3 are true,whereas 2 and 4 are false.,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,32,EXAMPLE 2,Consider the following sentences.1.What time is it?2.Read this carefully.3.x+1=2.4.x+y=z.,Sentences 1 and 2 are not propositions because they are not statements.Sentences 3

11、and 4 are not propositions because they are neither true nor false,since the variables in these sentences have not been assigned values.Various ways to form propositions from sentences of this type will be discussed in Section 1.3.,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,33,命题的语句形式 陈述句非命题语句：疑问句

12、命令句 感态句 非命题陈述句：悖论语句,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,34,命题的符号表示：大小写英文字母：P、Q、R、p、q、r、命题真值（Truth Values）的表示：真：T、1 假：F、0,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,35,命题语句真值确定的几点说明：1、时间性 2、区域性 3、标准性命题真值间的关系表示：真值表（Truth Table),2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,36,DEFINITION 1.,Let

13、p be a proposition.The statement It is not the case that p.is another proposition,called the negation of p.The negation of p is denoted by p.The proposition p is read not p.,p的否定,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,37,EXAMPLE 3,Find the negation of the proposition Today is Friday and express

14、 this in simple English.,The negation is It is not the case that today is Friday.This negation can be more simply expressed by Today is not Friday.,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,38,Table 1,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,39,DEFINITION 2.,Let p and q be propositions.The prop

15、osition p and q,denoted by pq,is the proposition that is true when both p and q are true and is false otherwise.The proposition pq is called the conjunction of p and q.The truth table for pq is shown in Table 2.,p和q的合取,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,40,Table 2,2/10/2023 3:13 AM,Discrete

16、 Math.,DeRen Chen,41,EXAMPLE 4,Find the conjunction of the propositions p and q where p is the proposition Today is Friday and q is the proposition It is raining today.,Solution:The conjunction of these propositions,pq,is the proposition Today is Friday and it is raining today.This proposition is tr

17、ue on rainy Fridays and is false on any day that is not a Friday and on Fridays when it does not rain.,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,42,DEFINITION 3.,Let p and q be propositions.The proposition p or q,denoted by pq,is the proposition that is false when p and q are both false and true o

18、therwise.The proposition pq is called the disjunction of p and q.The truth table for pq is shown in Table 3.,p和q的析取,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,43,Table 3,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,44,EXAMPLE 5,What is the disjunction of the propositions p and q where p and q are th

19、e same propositions as in Example 4?,Solution:The disjunction ofp and q,pq,is the proposition Today is Friday or it is raining today.This proposition is true on any day that is either a Friday or a rainy day(including rainy Fridays).It is only false on days that are not Fridays when it also does not

20、 rain.,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,45,DEFINITION 4.,Let p and q be propositions.The exclusive or of p and q,denoted by p q,is the proposition that is true when exactly one of p and q is true and is false otherwise.The truth table for the exclusive or of two propositions is displayed

21、in Table 4.,p和q的对称差,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,46,Table 4,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,47,DEFINITION 5.,Let p and q be propositions.The implication pq is the proposition that is false when p is true and q is false and true otherwise.In this implication p is called the

22、 hypothesis(or antecedent or premise)and q is called the conclusion(or consequence).,如果p,则q,单条件,蕴涵P:前提Q:结论,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,48,Table 5,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,49,EXAMPLE 6,What is the value of the variable x after the statement if 2+2=4 then x:=x+1 if x

23、=0 before this statement is encountered?(The symbol:=stands for assignment.The statement x:=x+1 means the assignment of the value of x+1 to x.),Solution:Since 2+2=4 is true,the assignment statement x:=x+1 is executed.Hence,x has the value 0+1=1 after this statement is encountered.,2/10/2023 3:13 AM,

24、Discrete Math.,DeRen Chen,50,implication pq The converse of pq:qp The contrapositive of pq:q p,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,51,EXAMPLE 7,Find the converse and the contrapositive of the implication If today is Thursday,then I have a test today.,Solution:The converse is If I have a test

25、 today,then today is Thursday.And the contrapositive of this implication is If I do not have a test today,then today is not Thursday.,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,52,DEFINITION 6.,Let p and q be propositions,The biconditional p q is the proposition that is true when p and q have the s

26、ame truth values and is false otherwise.The truth table for p q is shown in Table 6.,P当且仅当q,双条件，等价,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,53,Table 6,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,54,EXAMPLE 8,How can the following English sentence be translated into a logical expression?You can ac

27、cess the Internet from campus only if you are a computer science major or you are not a freshman,Solution:a(c f).,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,55,EXAMPLE 9,How can the following English sentence be translated into a logical expression?You cannot ride the roller coaster if you are unde

28、r 4 feet tall unless you are older than 16 years old.,Solution:(r s)q.,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,56,EXAMPLE 10,说离散数学是枯燥无味的或毫无价值的，那是不对的。P：离散数学是有味道的；Q：离散数学是有价值的；,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,57,APPLICATION 1,Web Page Searching.Most Web search engines support Boolean se

29、arching techniques,which usually can help find Web pages about particular subjects.For instance,using Boolean searching to find Web pages about universities in New Mexico,we can look for pages matching NEW AND MEXICO AND UNIVERSITIES.The results of this search will include those pages that contain t

30、he three words NEW,MEXICO,and UNIVERSITIES.,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,58,APPLICATION 2,A bit string is a sequence of zero or more bits.The length of this string is the number of bits in the string.,The bitwise of two strings of the same length:Bitwise OR Bitwise AND Bitwise XOR,2/1

31、0/2023 3:13 AM,Discrete Math.,DeRen Chen,59,Table 7,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,60,EXAMPLE 12,Find the bitwise OR,bitwise AND,and bitwise XOR of the bit strings 01 1011 0110 and 11 0001 1101.(Here,and throughout this book,bit strings will be split into blocks of four bits to make the

32、m easier to read.),Solution:The bitwise OR,bitwise AND,and bitwise XOR of these strings are obtained by taking the OR,AND,and XOR of the corresponding bits,respectively.This gives us01 1011 011011 0001 1101 11 1011 1111 bitwise OR 01 0001 0100 bitwise AND 10 1010 1011 bitwise XOR,2/10/2023 3:13 AM,D

33、iscrete Math.,DeRen Chen,61,P、Q、R 称为原子命题（Atomic Proposition）。原子命题或加上逻辑联结词组成的表达式成为复合命题（Compositional Proposition）。从命题常量 到 命题变量(Propositional Variable),命题公式：1、原子命题是命题公式；2、设P是命题公式，则P也是命题公式；3、设P、Q是命题公式，则（P Q）、（P Q）、（P Q）、（P Q）也是命题公式；4、有限次地使用1、2、3所得到的也是命题公式。Proposition Formulas,Well-Formed Formulas(wff),

34、2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,62,命题公式的运算规则：逻辑联接词的优先级：、命题公式的表达式的运算规律：同代数表达式命题公式的运算方法：所有公式中的命题变量用指定命题（真值）代入（或指派），得到一个公式对应的真值。,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,63,性质1：如果一个命题公式有N个互异的命题变量，则命题公式对应的真值有2的N次幂种可能分布。,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,64,永真命题公式（Tautology）公式中的命

35、题变量无论怎样代入，公式对应的真值恒为T。永假命题公式（Contradiction)公式中的命题变量无论怎样代入，公式对应的真值恒为F。可满足命题公式（Satisfaction）公式中的命题变量无论怎样代入，公式对应的真值总有一种情况为T。一般命题公式（Contingency）既不是永真公式也不是永假公式。,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,65,性质2：（1）设P是永真命题公式，则P的否定公式是永假命题公式；（2）设P是永假命题公式，则P的否定公式是永真命题公式；（3）设P、Q是永真命题公式，则（P Q）、（P Q）、（P Q）、（P Q

36、）也是永真命题公式,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,66,小 结 1、命题的概念：定义、逻辑值、符号化表示2、从简单命题到复合命题：逻辑联接词：运算方法、运算优先级3、从命题常量到命题变量，从复合命题到命题公式：命题公式的真值描述：真值表4、命题公式的分类：永真公式、永假公式、可满足公式、一般公式,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,67,进一步的思考：1、从二值逻辑到多值逻辑 2、从确定值到模糊值 模糊逻辑（Fuzzy Logic),练习题：1、2、7、9、25（d）、30（b）,2/

37、10/2023 3:13 AM,Discrete Math.,DeRen Chen,68,基础部分:逻辑(Logic)集合(Sets)算法(Algorithms)数论(Number Theory),2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,69,1.1.1 命题逻辑 Proposition Logic,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,70,逻辑学：研究推理的一门学科数理逻辑：用数学方法研究推理的一门数学学科,-一套符号体系+一组规则,2/10/2023 3:13 AM,Discrete Mat

38、h.,DeRen Chen,71,数理逻辑的内容：古典数理逻辑：命题逻辑、谓词逻辑 现代数理逻辑：公理化集合论、递归论、模型论、证明论,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,72,Proposition:一个有确定真或假意义的语句.,命题逻辑 Proposition Logic,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,73,EXAMPLE 1,All the following statements are propositions.1.Washington,D.C.,is the capital

39、 of the United States of America.2.Toronto is the capital of Canada.3.1+1=2.4.2+2=3.,Propositions 1 and 3 are true,whereas 2 and 4 are false.,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,74,EXAMPLE 2,Consider the following sentences.1.What time is it?2.Read this carefully.3.x+1=2.4.x+y=z.,Sentences 1

40、 and 2 are not propositions because they are not statements.Sentences 3 and 4 are not propositions because they are neither tree nor false,since the variables in these sentences have not been assigned values.Various ways to form propositions from sentences of this type will be discussed in Section 1

41、.3.,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,75,命题的语句形式 陈述句非命题语句：疑问句 命令句 感态句 非命题陈述句：悖论语句,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,76,命题的符号表示：大小写英文字母：P、Q、R、p、q、r、。命题真值（Truth Values）的表示：真：T、1 假：F、0,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,77,命题语句真值确定的几点说明：1、时间性 2、区域性 3、标准性命题真值间的关系表示：真值表（Truth

42、 Table),2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,78,DEFINITION 1.,Let p be a proposition.The statement It is not the case that p.is another proposition,called the negation of p.The negation of p is denoted by p.The proposition p is read not p.,p的否定,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,79,E

43、XAMPLE 3,Find the negation of the proposition Today is Friday and express this in simple English.,The negation is It is not the case that today is Friday.This negation can be more simply expressed by Today is not Friday.,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,80,Table 1,2/10/2023 3:13 AM,Discre

44、te Math.,DeRen Chen,81,DEFINITION 2.,Let p and q be propositions.The proposition p and q,denoted by pq,is the proposition that is true when both p and q are true and is false otherwise.The proposition pq is called the conjunction of p and q.The truth table for pq is shown in Table 2.,p和q的合取,2/10/202

45、3 3:13 AM,Discrete Math.,DeRen Chen,82,Table 2,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,83,EXAMPLE 4,Find the conjunction of the propositions p and q where p is the proposition Today is Friday and q is the proposition It is raining today.,Solution:The conjunction of these propositions,pq,is the p

46、roposition Today is Friday and it is raining today.This proposition is true on rainy Fridays and is false on any day that is not a Friday and on Fridays when it does not rain.,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,84,DEFINITION 3.,Let p and q be propositions.The proposition p or q,denoted by p

47、q,is the proposition that is false when p and q are both false and true otherwise.The proposition pq is called the disjunction of p and q.The truth table for pq is shown in Table 3.,p和q的析取,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,85,Table 3,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,86,EXAMPLE 5

48、,What is the disjunction of the propositions p and q where p and q are the same propositions as in Example 4?,Solution:The disjunction ofp and q,pq,is the proposition Today is Friday or it is raining today.This proposition is true on any day that is either a Friday or a rainy day(including rainy Fri

49、days).It is only false on days that are not Fridays when it also does not rain.,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,87,DEFINITION 4.,Let p and q be propositions.The exclusive or of p and q,denoted by p q,is the proposition that is true when exactly one of p and q is true and is false otherwi

50、se.The truth table for the exclusive or of two propositions is displayed in Table 4.,p和q的对称差,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,88,Table 4,2/10/2023 3:13 AM,Discrete Math.,DeRen Chen,89,DEFINITION 5.,Let p and q be propositions.The implication pq is the proposition that is false when p is t