离散数学讲义.ppt

《离散数学讲义.ppt》由会员分享，可在线阅读，更多相关《离散数学讲义.ppt（212页珍藏版）》请在金锄头文库上搜索。

1、Discrete Mathematics,离散数学讲义（电子版）,2,课程概况,教材： 离散数学（第三版），耿素云等编著 清华大学出版社，2004年3月,参考书： （1） 离散数学(第二版)及其配套参考书离散 数学题解作者：屈婉玲，耿素云，张立昂 清华大学出版社 （2） 离散数学焦占亚主编 电子工业出版社 2005年1月,3,课程概况,选修课/必修课：选修 周学时：3（学时） 上课周：116周 总学时：48（学时）,4,课程内容及学时安排,第一篇 数理逻辑（14学时） 第一章 命题逻辑（8） 第二章 谓词逻辑（6） 第二篇 集合论（12学时） 第三章 集合（4） 第四章 二元关系与函数（8）

2、第四篇 图论（14学时） 第七章 图论（8） 第八章 一些特殊图（4） 第九章 树 （2）,5,课程考核,考核方式： 闭卷笔试,第四篇 代数系统（8学时） 第5、6章 图论（8）,6,课程要求,（1）上课认真听讲 （2）课后及时复习 （3）独立、认真地完成作业 （4）有问题及时提出，不要积累问题,7,什么是离散数学？,是研究离散对象和它们之间的关系 的现代数学。,它为计算机科学中的数据结构、编 译理论、操作系统、算法分析、人 工智能等提供了必要的数学知识。,其内容较广，主要包括数理逻辑、 集合论、图论、代数结构等四个基本部分。,8,什么是离散数学？,离散数学将日常的概念、判断、推理用数学符号来

3、表示，用数学方法进行思维。其目标是掌握严密的思维方法、严格证明的推理能力和演算能力，掌握处理各种具有离散结构的事物的描述工具与方法，适应学习其他专业课程的各种需要，为学习其它计算机课程提供必要的数学工具。,9,什么是离散数学？,本课程将学习数理逻辑、集合论以及图论、代数系统的部分内容。 数理逻辑的重点是公式演 算与推理证明；集合论的重点是关系理论与映射的描述；图论则着重于讨论结点之间的关系以及图论方法的各种实际应用。,10,课程内容,第一篇 数理逻辑,11,第一篇 数理逻辑,数理逻辑是用数学方法来研究推理过程的科学。主要是指引进一套符号体系的方法，因此数理逻辑一般又叫符号逻辑。 基本内容是：命

4、题逻辑（演算）和谓词逻辑（演算）。,12,第一章 命题逻辑,命题演算是数理逻辑的基本组成部分，是谓词演算的基础。 本章包括以下内容：,1-1 命题及其表示法 1-2 连结词 1-3 命题公式及翻译 1-4 真值表与等价公式 1-5 其它连结词 1-6 对偶与范式 1-7 重言式与蕴涵式 1-8 推理理论 1-9 应用,13,命题：能够判断真假的陈述语句。 例：中国是一个国家， 9为素数。 原子命题：不能分解成更简单的陈述语句的命题。 复合命题：由连结词、标点符号和原子命题复合构成的命题。 一般用字母“T”表示“真”，“F”表示“假”。也经常用“1”表示“真”，“0”表示“假”。,1-1 命题及

5、其表示法,14,习惯上，命题用小写字母p，q，r，或用带下标小写字母表示。 例如： 命题p：中国人们是伟大的。 命题q：别的星球上有生物。 命题p1：1+101=102（在十进制或二进制数范围内）。 命题P2：今天下雨。 命题r：我去看电影。,1-1 命题及其表示法（续）,15,判断下列句子哪些是命题？,地球是圆的。,2+3=5,2+3=6,你会讲英语吗？,3-x=5,是命题，真值为T,是命题，真值为T,是命题，真值为F,不是命题（疑问句不是命题）。,不是命题，它的真值不确定。,1-1 命题及其表示法（续）,16,判断下列句子哪些是命题（续）？,请关上门！,除地球外的星球 有生物。,太阳明天会

6、出来。,不是命题，祈使句不是命题。,是命题，它的真值是唯一确定的，只是目前人们不知道,是命题，它的真值是唯一确定的，到明天就知道了。,再次注意：命题是具有唯一真值的陈述句。,1-1 命题及其表示法（续）,17,我正在说谎 悖论(paradox)是一种矛盾命题。悖论是自相矛盾的命题。即如果承认这个命题成立，就可推出它的否定命题成立；反之，如果承认这个命题的否定命题成立，又可推出这个命题成立。 paradox来自希腊语“para+dokein”，意思是“多想一想”。 悖论是属于领域广阔、定义严格的数学分支的一个组成部分，这一分支以“趣味数学”知名于世。这就是说它带有强烈的游戏色彩。然而，切莫以为大

7、数学家都看不起“趣味数学”问题。欧拉就是通过对bridge-crossing之谜的分析打下了拓扑学的基础。莱布尼茨也写到过他在独自玩插棍游戏（一种在小方格中插小木条的游戏）时分析问题的乐趣。,18,希尔伯特证明了切割几何图形中的许多重要定理。冯纽曼奠基了博弈论。最受大众欢迎的计算机游戏生命是英国著名数学家康威发明的。爱因斯坦也收藏了整整一书架关于数学游戏和数学谜的书。 古今中外有不少著名的悖论，它们震撼了逻辑和数学的基础，激发了人们求知和精密的思考，吸引了古往今来许多思想家和爱好者的注意力。解决悖论难题需要创造性的思考，悖论的解决又往往可以给人带来全新的观念。,19,例如比较有名的理发师悖论：

8、某乡村有一位理发师，一天他宣布：只给不自己刮胡子的人刮胡子。这里就产生了问题：理发师给不给自己刮胡子？如果他给自己刮胡子，他就是自己刮胡子的人，按照他的原则，他不能给自己刮胡子；如果他不给自己刮胡子，他就是不自己刮胡子的人，按照他的原则，他就应该给自己刮胡子。这就产生了矛盾 历史上著名的悖论NO.1 说谎者悖论(1iar paradox or Epimenides paradox) 最古老的语义悖论。公元前6世纪古希腊哲学家伊壁孟德 所创的四个悖论之一。是关于“我正在撒谎”的悖论。具体为：如果他的确正在撒谎，那么这句话是真的，所以伊壁孟德不在撤谎，如果他不在撒谎，那么这句话是假的，因而伊壁孟德

9、正在撒谎。,20,NO.2 伊勒克特拉悖论(Eletra paradox) 逻辑史上最早的内涵悖论。由古希腊斯多亚学派提出。它的基本内容是：伊勒克特拉有位哥哥奥列斯特回家了尽管伊勒支持拉知道奥列斯特是她的哥哥但她并不认识站在她面前的这个男人。 写成一个推理即： 伊勒克持拉不知道站在她面前的这个人是她的哥哥。 伊勒克持拉知道奥列期特是她的哥哥。 站在她面前的人是奥列期特。 所以，伊勒克持拉既知道并且又不知道这个人是她的 哥哥。,21,NO.3 M：著名的理发师悖论是伯特纳德罗素提出的。一个理发师的招牌上写着： 告示：城里所有不自己刮脸的男人都由我给他们刮脸，我也只给这些人刮脸。 M：谁给这位理发

10、师刮脸呢？ M：如果他自己刮脸，那他就属于自己刮脸的那类人。但是，他的招牌说明他不给这类人刮脸，因此他不能自己来刮。 M：如果另外一个人来给他刮脸，那他就是不自己刮脸的人。但是，他的招牌说他要给所有这类人刮脸。因此其他任何人也不能给他刮脸。看来，没有任何人能给这位理发师刮脸了！,22,NO.4 唐吉诃德悖论 M：小说唐吉诃德里描写过一个国家它有一条奇怪的法律：每一个旅游者都要回答一个问题。 问，你来这里做什么？ M：如果旅游者回答对了。一切都好办。如果回答错了，他就要被绞死。 M：一天，有个旅游者回答 旅游者：我来这里是要被绞死。 M：这时，卫兵也和鳄鱼一样慌了神，如果他们不把这人绞死，他就说

11、错了，就得受绞刑。可是，如果他们绞死他，他就说对了，就不应该绞死他。,23,下一句话是真的； 上一句话是假的。 命题常项（常元）：具有唯一真值的命题； 命题变项（变元）：泛指任意一个命题或者类似x+y5根据条件不同真值不同的命题。 注意：命题变项不是命题，它不具有唯一真值,24,1-2 联结词,1、否定,设P为一命题，则新命题“P是不对的”称为P的否定。记作： P,如：P：2是常数。, P：2不是常数。,Q：今天是星期四。, Q：今天不是星期四。,P与 P的真值关系：,25,1-2 联结词（续）,2、合取,设P，Q是两命题，新命题“P并且Q”称为命题P，Q的合取。记作：PQ,如：P：北京是中国

12、的首都。 Q：北京是一个古都。 PQ：北京是中国的首都并且是一个古都。,P Q的真值关系：,26,1-2 联结词（续）,3、析取,设P，Q为两个命题，则新命题“P或者Q”称为命题P，Q的析取。记作：PQ,如：P：北京是中国的首都。 Q：北京是一个故都。 PQ：北京是中国的首都或者是一个故都。,规定：PQ的真值为1当且仅当P，Q中至少有一个真值为1。,PQ的真值关系：,27,1-2 联结词（续）,注意：析取联结词与汉语中的“或”的意义不完全相同。 汉语中的“或”既可以表示“排斥或”，也可以表示 “可兼或”。,例如： P：今天晚上我在家看电视或去剧场看戏。 Q：他可能是100米或400米赛跑的冠军

13、。,“排斥或”,“可兼或”,28,1-2 联结词（续）,4、条件,设P，Q是两命题，其条件命题是一个复合命题，记做PQ，读做“如果P，则Q”。,真值关系：,“善意的推定”,29,1-2 联结词（续）,5、双条件,设P，Q是两命题，其双条件命题是一个复合命题， 记做PQ，读做“如果P，则Q”。,真值关系：,30,1-2 联结词（续）,在命题演算中，五个联结词的含义由真值表唯一确定。,31,1-3 命题公式及其赋值,定义：合式公式 （1）单个命题变元本身是一个合式公式。 （2）如果A是一个合式公式，那么A是合式公式。 （3）如果A、B是合式公式，那么（AB）、 （AB）、（AB）、 （AB）都是合

14、式公 式。 （4）当且仅当能够有限次地应用上面（1）、（2）、 （3）所得到的包含命题变元、联结词合括号的 符号串是合式公式。 递归定义,基础,归纳,界限,32,1-3 命题公式及其赋值（续）,例如： 合式公式： (PQ), (PQ) (P(PQ) (PQ)(QR)(ST) 非合式公式： (PQ)(Q) (PQ (PQ)Q),括号不匹配,括号不匹配,应是双目运算符,33,1-3 命题公式及翻译,联结词的运算优先级：,高,低, ,命题公式的层（描述公式的复杂程度） 命题公式的赋值（解释、翻译） 真值表,34,1-3 命题公式及翻译（续）,请看教材Page 10-11。,例题1：我们要做到身体好、

15、学习好、工作好，为祖 国的四化建设而奋斗。 解 找出原子命题： A：我们要做到身体好。 B：我们要做到学习好。 C：我们要做到工作好。 P；我们要为祖国的四化建设而奋斗。 命题的形式化描述： (A B C) P。,35,1-3 命题公式及翻译（续）,例题2：上海到北京的14次列车是下午五点半或六点 开。 解 找出原子命题： P：上海到北京的14次列车是下午五点半开。 Q：上海到北京的14次列车是下午六点开。 排斥或： （ PQ）（P Q）,命题的形式化描述：(PQ)。,36,1-3 命题公式及翻译（续）,例题3： （自学） 例题4： （自学） 例题5： （自学） 例题6： （自学）,37,习题

16、：,*各章节后习题中的双号大题中的双 号小题。,38,1-4 真值表与等价公式,定义：在命题公式中，对于分量指派真值的各种可能组合，就确定了这个命题公式的各种真值情况，把它们汇列成表，就是命题公式的真值表。,含n个命题变元的命题公式，共有2n组赋值。,例题1：PQ的真值表。,39,1-4 真值表与等价公式（续）,例题2：(PQ) P的真值表。,例题3： (PQ) v(PQ)的真值表。,永假公式,40,1-4 真值表与等价公式（续）,例题4：(PQ)(PQ)的真值表。,永真公式,41,1-4 真值表与等价公式（续）,定义：给定两个命题公式A和B，设P1， P2， Pn，为所有出现在A和B中的原子变元。若给P1， P2， Pn任意一组真值指派，A和B的真值都相同，则称A和B是等价（或逻辑相等），记做AB。,例题5：证明PQ (PQ)(QP) 。,42,1-4 真值表与等价公式（续）,两个公式 （1） P Q PQ,（2） (P Q) (P Q) PQ,43,1-4 真值表与等价公