离散数学chapter01-2014

离散数学龙宇上海交通大学计算机科学与工程系[e-mail]:342055392离散数学研究对象：离散个体及其结构离散数学是：现代数学的一个重要分支计算机科学与技术的理论基础是计算机应用必不可少的工具，所以又称为计算机数学离散数学应用举例在数字电路中的应用交通信号灯控制有红、黄、绿三灯，由3个开关分别控制(1)每次仅一种颜色灯亮(2)红灯及绿灯不会连续出现，即二者之间必须有黄灯(3)可加上延时：如红灯20秒，黄灯10秒，绿灯13秒(4)更复杂的情形：十字路口多信号灯、信号灯闪断等本质上是数理逻辑理发师悖论及解决在某个城市中有一位理发师，他的广告词是这样写的：“本人的理发技艺十分高超，誉满全城。我将为本城所有不给自己刮脸的人刮脸，我也只给这些人刮脸。我对各位表示热诚欢迎！”来找他刮脸的人络绎不绝，自然都是那些不给自己刮脸的人。可是，有一天，这位理发师从镜子里看见自己的胡子长了，他本能地抓起了剃刀，你们看他能不能给他自己刮脸呢？如果他不给自己刮脸，他就属于“不给自己刮脸的人”，他就要给自己刮脸，而如果他给自己刮脸呢？他又属于“给自己刮脸的人”，他就不该给自己刮脸。本质上是集合论一笔画及社交网络一笔画：给定一个由顶点和边所组成的图。能否无重复的遍历该图的边？社交网络：在社交网络环境中，依据后台数据库，自动得到一个成员之间彼此直接/间接认识的最大群体本质上是图论6离散数学事实上，从计算机产生到其发展每一步都离不开数学1936年，英国数学家图灵(A.M.Turing)发表了著名论文“理想计算机”，从而给出了计算机的理论模型1946年在著名数学家冯·诺依曼(J.VonNeumann)的领导下，制造了世界上第一台现代意义的通用计算机EDVAC(ElectronicDiscreteVariableAutomaticComputer)．．．为什么离散数学对计算机科学来说如此重要？数字电子计算机是一个离散结构，它只能处理离散的或离散化了的数量关系无论计算机科学本身，还是与计算机科学及其应用密切相关的现代科学研究领域，都面临着如何对离散结构建立相应的数学模型；又如何将已用连续数量关系建立起来的数学模型离散化，从而可由计算机加以处理7离散数学与计算机科学的关系数理逻辑：人工智能、程序正确性证明、程序验证等集合论：关系数据库模型等图论：数据结构、数据库模型、网络模型等代数结构：软件规范、形式语义、编译系统、编码理论、密码学、数据仓库等组合数学：算法分析设计、编码、容错等8离散数学课程说明研究对象----离散个体及其结构研究思想----以集合和映射为工具、体现公理化和结构的思想研究内容----包含不同的数学分支，模块化结构数理逻辑：推理、形式化方法集合论：离散结构的表示、描述工具图论：离散结构的关系模型代数结构：离散结构的代数模型组合数学：离散结构的存在性、计数、枚举、优化、设计离散概率（概率统计课程）9课程内容数理逻辑图论PPT下载地址课程中心=view&courseType=0&courseId=7548教材和辅导书参考教材：数理逻辑与集合论（第二版）：石纯一，清华大学出版社图论与代数结构：戴一奇，清华大学出版社辅导书：1.数理逻辑：莫绍揆，科学文献出版社2.数理逻辑教程：莫绍揆，华中工学院出版社3.集论与逻辑：沈恩绍，科学出版社4.AMathematicalIntroductiontoLogic,2nd.Ed,H.Enderton,AcademicPress5.LogicforApplications,2nded.,A.Nerode,Springer6.离散数学（第4版），RichardJohnsonbaugh，电子工业出版社11第一部分数理逻辑逻辑学研究人的思维形式和规律的科学数理逻辑用数学方法研究推理，是研究推理中前提和结论之间的形式关系的科学所谓推理就是由一个或几个判断推出一个新判断的思维形式这里所说的数学方法就是建立一套表意符号体系，对具体事物进行抽象的形式研究的方法.因此,数理逻辑又称符号逻辑什么是逻辑直观的说，逻辑是研究说话的『道理』的学科，从而增强人的“说话”（推理过程）与思考的能力“说话”：日常对话、数学证明、科学定律、各种预测…例子：判断下面两个说法是否有『道理』所有的人都会死；所有的人都会死；苏格拉底是人。苏格拉底会死。所以，苏格拉底会死。所以，苏格拉底是人。会死的人苏会死的人苏数理逻辑前史时期－古典形式逻辑时期代表人物：亚里士多德数理逻辑初创时期－逻辑代数时期代表人物：莱布尼茨数理逻辑的奠定时期代表人物：康托尔、希尔伯特、罗素数理逻辑发展初期代表人物：哥德尔数理逻辑现代发展时期这一时期从20世纪40年代开始。主要内容是各种非经典逻辑和四论－模型论、集合论、递归论和证明论的突飞猛进的发展数理逻辑的发展历程14第一章命题逻辑的基本概念命题逻辑(Logic)研究命题的推理演算命题逻辑的应用数学上定理的推导在计算机科学上，验证程序的正确性主要内容命题的基本概念命题联结词命题合式公式、重言式自然语句的形式化151.1命题（Proposition）命题是一个非真即假(不可兼)的陈述句命题是一个陈述句，命令句、疑问句和感叹句都不是命题命题只有两个取值：真或假。这个陈述句所表达的内容可决定是真还是假，而且不是真的就是假的，不能不真又不假，也不能又真又假真假命题凡与事实相符的陈述句为真语句，而与事实不符的陈述句为假语句．这就是说，一个命题具有两种可能的取值(又称真值)，为真或为假，并且只能取其一通常用大写字母“T”(1)表示真值为真，用“F”(0)表示真值为假．因为只有两种取值，所以这样的命题逻辑称为二值逻辑16命题举例“雪是白的.”是命题,真值为1.“雪是黑的.”是命题,真值为0.“好大的雪啊!”非陈述句，不是命题“大于2的偶数可表示成两个素数之和.”(Goldbach猜想)是命题,目前不知其真假.“1+10l＝110.”此数学式相当于命题“1加101等于110”.在十进制中真值为0,在二进制中真值为1.并非说同一命题有两个真值!在不同数制中是不同的命题“xy”17命题变项为了对命题作逻辑演算，采用数学手法将命题符号化(形式化)是十分重要的命题的表示：大写符号P表示“雪是白的”Q表示“北京是中国的首都”命题变项：P表示任一命题时，P就称为命题变项(变元)．命题与命题变项含义是不同的：命题指具体的陈述句，是有确定的真值命题变项的真值不定，只当将某个具体命题代入命题变项时，命题变项化为命题，方可确定其真值命题与命题变项像初等数学中常量与变量的关系一样．如5是一个常量，是一个确定的数字，而x是一个变量，赋给它一个什么值它就代表什么值，即x的值是不定的18简单命题和复合命题简单命题又称原子命题(Primitiveproposition)简单命题是不包含任何的与、或、非一类联结词的命题简单命题不可再分割，如“雪是白的”再分割就不是命题了．命题“雪是白的而且1+1＝2”不是简单命题，它可以分割为“雪是白的”以及“1+1＝2”两个简单命题，联结词是“而且”在简单命题中，尽管常有主语和谓语，但我们不去加以分割，是将简单命题作为一个不可分的整体来看待，进而作命题演算．在谓词逻辑里，才对命题中的主谓结构进行深入分析19复合命题(Compoundproposition)复合命题：把一个或几个简单命题用联结词(如与、或、非等)联结所构成的新的命题“张三学英语和李四学日语”就是一个复合命题由简单命题“张三学英语”“李四学日语”经联结词“和”联结而成复合命题的真值：依赖于构成该复合命题的各个简单命题的真值以及联结词上例中，当以上两个简单命题真值均为真时，该复合命题方为真命题逻辑所讨论的是多个命题联结而成的复合命题的规律性20内容/形式命题是一个可取真或可取假的陈述句数理逻辑不关心内容这些具体的陈述句的真值究竟为什么或在什么环境下是真还是假数理逻辑只关心形式命题可以被赋予真或假这样的可能性，以及规定了真值后怎样与其他命题发生联系211.2命题联结词及真值表联结词可将命题联结起来构成复杂的命题命题逻辑联结词的引入是十分重要的，其作用相当于初等数学里在实数集上定义的+、、、÷等运算符通过联结词便可定义新的命题，从而使命题逻辑的内容变得丰富起来我们要讨论的仅只是复合命题的真值，此值可由组成它的简单命题的真值所确定值得注意的是逻辑联结词与日常自然用语中的有关联结词的共同点和不同点22常用的逻辑联结词(五个)否定词（negation）“”是个一元联结词，亦称否定符号．一个命题P加上否定词就形成了一个新的命题，记作P，这个新命题是命题的否定，读作非P。否定词“”的真值规定如下：若命题P的真值为真，那么P的真值就为假；若P的真值为假，那么P的真值就为真．P与P间的真值关系，常常使用称作真值表的一种表格来表示.23P的定义真值表真值表表明了P的真值如何依赖于P的真值真值表描述了命题之间的真值关系，很直观真值表是命题逻辑里研究真值关系的重要工具PPTFFT24例1“昨天张三去看球赛了”．该命题以P表示；“昨天张三没有去看球赛”，该新命题便可用P表示．若昨天张三去看球赛了，命题P是真的，那么新命题P必然是假的．反之，若命题P是假的，那么P就是真的．25例2Q：今天是星期三Q：今天不是星期三Q不能理解为“今天是星期四”，因为“今天是星期三”的否定，并不一定必是星期四，还可能是星期五、星期六……Q：这些都是男同学。Q：这些不都是男同学。(翻译成“这些都不是男同学”是错的。)26合取词合取词(Conjunction)是个二元命题联结词，亦称合取符号将两个命题P,Q联结起来，构成一个新的命题PQ，读作P,Q的合取，也可读作P与Q这个新命题PQ的真值与构成它的命题P,Q的真值间的关系，由合取词真值表来规定。27合取词真值表PQPQFFFFTFTFFTTT只有当两个命题变项P＝T，Q=T时方有P^Q＝T。而P，Q只要有一为F，则P^Q=F。28例4A：今天下雨了．B：教室里有100张桌子。命题AB是：“今天下雨了并且教室里有100张桌子”．29合取词与日常自然用语中的联结词逻辑联结词是自然用语中联结词的抽象，与“合取词”并不等同，这是需注意的．日常自然用语里的联结词“和”、“与”、“并且”，一般是表示两种同类有关事物的并列关系。而在逻辑语言中仅考虑命题与命题之间的形式关系并不顾及日常自然用语中是否有此说法。这样，“”同“与”、“并且”又不能等同视之。日常自然用语中说，“这台机器质量很好，但是很贵”，这句话的含义是说同一台机器质量很好而且很贵。若用P表示“这台机器质量很好”，用Q表示“这台机器很贵”，那么这句话的逻辑表示就是PQ，尽管这句话里出现的联结词是“但是”。“张和李是同学”中的“和”不是联结词总之，合取词有“与”、“并且”的含义。30析取词∨析取词(disjunction)“∨”是个二元命题联结词将两个命题P,Q联结起来，构成一个新的命题P∨Q，读作P,Q的析取，也读作P或Q这个新命题的真值与构成它的命题P,Q的真值间的关系，由析取词真值表来规定31析取词真值表PQPQFFFFTTTFTTTT当P、Q有一取值为T时,P∨Q便为T。仅当P、Q均取F值时,P∨Q方为F。32例5P:今天刮风Q:今天下雨命题“今天刮风或者下雨”便可由P∨Q来描述了例6A:2小于3B:雪是黑的A∨B就是命题“2小于3或者雪是黑的”由于2小于3是真的，所以A∨B必取值为真，尽管“雪是黑的”