离散数学讲义ppt课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《离散数学讲义ppt课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 讲义 ppt 课件
- 资源描述:
-
1、12离散数学(第三版),耿素云等编著 清华大学出版社,2004年3月(1) 离散数学(第二版)及其配套参考书离散 数学题解作者:屈婉玲,耿素云,张立昂 清华大学出版社(2) 离散数学焦占亚主编 电子工业出版社 2005年1月3选修课/必修课:周学时:上课周:总学时:4第一篇第一篇 数理逻辑(数理逻辑(14学时)学时)第一章 命题逻辑(8)第二章 谓词逻辑(6)第二篇第二篇 集合论(集合论(12学时)学时)第三章 集合(4)第四章 二元关系与函数(8)第四篇第四篇 图论(图论(14学时)学时)第七章 图论(8)第八章 一些特殊图(4)第九章 树 (2)5考核方式:考核方式:闭卷笔试第四篇第四篇
2、代数系统(代数系统(8学时)学时)第5、6章 图论(8)6(1)上课认真听讲)上课认真听讲(2)课后及时复习)课后及时复习(3)独立、认真地完成作业)独立、认真地完成作业(4)有问题及时提出,不要积累问题)有问题及时提出,不要积累问题7 是研究离散对象和它们之间的关系是研究离散对象和它们之间的关系 的现代数学。的现代数学。 它为计算机科学中的数据结构、编它为计算机科学中的数据结构、编 译理论、操作系统、算法分析、人译理论、操作系统、算法分析、人 工智能等提供了必要的数学知识。工智能等提供了必要的数学知识。其内容较广,主要包括数理逻辑、其内容较广,主要包括数理逻辑、 集合集合论、图论、代数结构等
3、四个基本部分。论、图论、代数结构等四个基本部分。8 离散数学将日常的概念、判断、推理用数学符号来表示,用数学方法进行思维。其目标是掌握严密的思维方法、严格证明的推理能力和演算能力,掌握处理各种具有离散结构的事物的描述工具与方法,适应学习其他专业课程的各种需要,为学习其它计算机课程提供必要的数学工具。9本课程将学习数理逻辑、集合论以及图论、代数系统的部分内容。 数理逻辑的重点是公式演 算与推理证明;集合论的重点是关系理论与映射的描述;图论则着重于讨论结点之间的关系以及图论方法的各种实际应用。10第一篇 数理逻辑数理逻辑11数理逻辑是用数学方法来研究推理过程的科学。主要是指引进一套符号体系的方法,
4、因此数理逻辑一般又叫符号逻辑。基本内容是:命题逻辑(演算)和谓词逻辑(演算)。12命题演算是数理逻辑的基本组成部分,是谓词演算的基础。本章包括以下内容:1-1 命题及其表示法1-2 连结词1-3 命题公式及翻译1-4 真值表与等价公式1-5 其它连结词1-6 对偶与范式1-7 重言式与蕴涵式1-8 推理理论1-9 应用13命题:能够判断真假的陈述语句。8例:中国是一个国家,89为素数。原子命题:不能分解成更简单的陈述语句的命题。复合命题:由连结词、标点符号和原子命题复合构成的命题。一般用字母“T”表示“真”,“F”表示“假”。也经常用“1”表示“真”,“0”表示“假”。1-1 命题及其表示法命
5、题及其表示法148习惯上,命题用小写字母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说谎者悖论(1iarparadoxorEpimenidesparadox)最古老的语义悖论。公元前6世纪古希腊哲学家伊壁孟德所创的四个悖论之一。是关于“我正在撒谎”的悖论。具体为:如果他的确正在撒谎,那么这句话是真的,所以伊壁孟德不在撤谎,如果他不在撒谎,那么这句话是假的,因而伊壁孟德正
9、在撒谎。20NO.2伊勒克特拉悖论(Eletraparadox)逻辑史上最早的内涵悖论。由古希腊斯多亚学派提出。它的基本内容是:伊勒克特拉有位哥哥奥列斯特回家了尽管伊勒支持拉知道奥列斯特是她的哥哥但她并不认识站在她面前的这个男人。写成一个推理即:伊勒克持拉不知道站在她面前的这个人是她的哥哥。伊勒克持拉知道奥列期特是她的哥哥。站在她面前的人是奥列期特。所以,伊勒克持拉既知道并且又不知道这个人是她的哥哥。21NO.3M:著名的理发师悖论是伯特纳德罗素提出的。一个理发师的招牌上写着:告示:城里所有不自己刮脸的男人都由我给他们刮脸,我也只给这些人刮脸。M:谁给这位理发师刮脸呢?M:如果他自己刮脸,那他
10、就属于自己刮脸的那类人。但是,他的招牌说明他不给这类人刮脸,因此他不能自己来刮。M:如果另外一个人来给他刮脸,那他就是不自己刮脸的人。但是,他的招牌说他要给所有这类人刮脸。因此其他任何人也不能给他刮脸。看来,没有任何人能给这位理发师刮脸了!22NO.4唐吉诃德悖论M:小说唐吉诃德里描写过一个国家它有一条奇怪的法律:每一个旅游者都要回答一个问题。问,你来这里做什么?M:如果旅游者回答对了。一切都好办。如果回答错了,他就要被绞死。M:一天,有个旅游者回答旅游者:我来这里是要被绞死。M:这时,卫兵也和鳄鱼一样慌了神,如果他们不把这人绞死,他就说错了,就得受绞刑。可是,如果他们绞死他,他就说对了,就不
11、应该绞死他。23下一句话是真的;上一句话是假的。命题常项(常元):具有唯一真值的命题;命题变项(变元):泛指任意一个命题或者类似x+y5根据条件不同真值不同的命题。注意:命题变项不是命题,它不具有唯一真值241-2 联结词联结词1、否定设P为一命题,则新命题“P是不对的”称为P的否定。记作: P如:P:2是常数。 P:2不是常数。Q:今天是星期四。 Q:今天不是星期四。 P与 P的真值关系: 10 P0 1 P 251-2 联结词联结词(续)(续)2、合取设P,Q是两命题,新命题“P并且Q”称为命题P,Q的合取。记作:PQ如:P:北京是中国的首都。 Q:北京是一个古都。 PQ:北京是中国的首都
12、并且是一个古都。 0 0 0 0 0 1 0 1 P Q 1 0 1 1 P Q P Q的真值关系:261-2 联结词联结词(续)(续)3、析取设P,Q为两个命题,则新命题“P或者Q”称为命题P,Q的析取。记作:PQ如:P:北京是中国的首都。 Q:北京是一个故都。 PQ:北京是中国的首都或者是一个故都。规定:PQ的真值为1当且仅当P,Q中至少有一个真值为1。 PQ的真值关系: 0 0 0 1 0 1 1 1 P Q 1 0 1 1 P Q271-2 联结词联结词(续)(续)注意:析取联结词与汉语中的“或”的意义不完全相同。 汉语中的“或”既可以表示“排斥或”,也可以表示 “可兼或”。例如:P:
13、今天晚上我在家看电视或去剧场看戏。Q:他可能是100米或400米赛跑的冠军。“排斥或排斥或”“可兼或可兼或”281-2 联结词联结词(续)(续)4、条件设P,Q是两命题,其条件命题是一个复合命题,记做PQ,读做“如果P,则Q”。 1 1 0 1P Q 0 0 0 1 1 0 1 1 P Q真值关系:“善意的推定善意的推定”291-2 联结词联结词(续)(续)5、双条件设P,Q是两命题,其双条件命题是一个复合命题,记做PQ,读做“如果P,则Q”。真值关系: 1 0 0 1 0 0 0 1 1 0 1 1 P QPQ301-2 联结词联结词(续)(续)在命题演算中,五个联结词的含义由真值表唯一确定
14、。 T T F TP Q F F F T T F T T P Q F T T TP Q F F F T T F T T P Q F F F F F T F T P Q T F T T P Q T F PF T P T F F T F F F T T F T T P QPQ311-3 命题公式及其赋值命题公式及其赋值定义:合式公式(1)单个命题变元本身是一个合式公式。(2)如果A是一个合式公式,那么A是合式公式。(3)如果A、B是合式公式,那么(AB)、 (AB)、(AB)、 (AB)都是合式公 式。(4)当且仅当能够有限次地应用上面(1)、(2)、 (3)所得到的包含命题变元、联结词合括号的
15、符号串是合式公式。 递归定义递归定义基础归纳界限321-3 命题公式及其赋值命题公式及其赋值(续)(续)例如:合式公式:(PQ),(PQ)(P(PQ)(PQ)(QR)(ST)非合式公式:(PQ)(Q)(PQ (PQ)Q)括号不匹配括号不匹配应是双目运算符331-3 命题公式及翻译命题公式及翻译联结词的运算优先级:高低 命题公式的层(描述公式的复杂程度)命题公式的赋值(解释、翻译)真值表341-3 命题公式及翻译命题公式及翻译(续)(续)请看教材请看教材Page 10-11。例题例题1:我们要做到身体好、学习好、工作好,为祖 国的四化建设而奋斗。解解 找出原子命题: A:我们要做到身体好。 B:
16、我们要做到学习好。 C:我们要做到工作好。 P;我们要为祖国的四化建设而奋斗。命题的形式化描述: (A B C) P。351-3 命题公式及翻译命题公式及翻译(续)(续)例题例题2:上海到北京的14次列车是下午五点半或六点 开。解解 找出原子命题: P:上海到北京的14次列车是下午五点半开。 Q:上海到北京的14次列车是下午六点开。排斥或: ( PQ)(P Q)PQ原命题P QPQ (PQ)TTFTTFTFTTFTFTTTFTFFFFTF命题的形式化描述:(PQ)。361-3 命题公式及翻译命题公式及翻译(续)(续)例题3: (自学)例题4: (自学)例题5: (自学)例题6: (自学)37习
17、题:习题:* 各章节后习题中的双号大题中的双各章节后习题中的双号大题中的双号小题。号小题。381-4 真值表与等价公式真值表与等价公式定义:定义:在命题公式中,对于分量指派真值的各种可能组合,就确定了这个命题公式的各种真值情况,把它们汇列成表,就是命题公式的真值表。含含n个命题变元的命题公式,共有个命题变元的命题公式,共有2n组赋值。组赋值。例题1:PQ的真值表。PQ P P Q0011011110001101391-4 真值表与等价公式真值表与等价公式(续)(续)例题2:(PQ) P的真值表。PQP Q P(P Q) P00010010101000011100例题3: (PQ) v(PQ)的
18、真值表。PQ P QP Q PQ(P Q)v( PQ)0011011011000010010001100111永假永假公式公式401-4 真值表与等价公式真值表与等价公式(续)(续)例题4:(PQ)(PQ)的真值表。PQP Q (P Q) P Q Pv Q(P Q)( Pv Q)00011111010110111001011111100001永真永真公式公式411-4 真值表与等价公式真值表与等价公式(续)(续)定义:定义:给定两个命题公式A和B,设P1, P2, Pn,为所有出现在A和B中的原子变元。若给P1, P2, Pn任意一组真值指派,A和B的真值都相同,则称A和B是等价(或逻辑相等)
19、,记做AB。 例题5:证明PQ (PQ)(QP) 。PQPQPQQP(PQ) (QP)001111010100100010111111421-4 真值表与等价公式真值表与等价公式(续)(续)两个公式(1) P Q PQPQ P P QPQ00111011111000011011(2) (P Q) ( P Q) PQPQ P QP Q P Q(P Q) ( P Q)PQ00110111011000001001000011001011431-4 真值表与等价公式真值表与等价公式(续)(续)10个命题定律:序号定律表达式1双重否定律P P2幂等律PP PPP P3结合律(P Q) R P (Q R)
20、(P Q) R P (Q R)4交换律P Q Q PP Q Q P5分配律P (Q R) (P Q) (P R)P (Q R) (P Q) (P R)441-4 真值表与等价公式真值表与等价公式(续)(续)10个命题定律:序号定律表达式6吸收律P (P Q) PP (P Q) P7德.摩根律(P Q) P Q(P Q) P Q8同一律P 0 PP 1 P9零律P 1 1P 0 010排中律矛盾律P P 1P P 04511蕴涵等值式A B A B12等价等值式A B (A B) (B A)13假言易位A B B A14等价否定等值式A B A B15归谬论(A B) (A B) A1-4 真值
21、表与等价公式真值表与等价公式(续)(续)461-4 真值表与等价公式真值表与等价公式(续)(续)例题6 验证吸收律:P (P Q) PP (P Q) PPQ(P Q)P (P Q)(P Q)P (P Q)TTTTTTTFFTTTFTFFTFFFTFFF验证:列出真值表471-4 真值表与等价公式真值表与等价公式定义:定义:如果X是合式公式A的一部分,且X本身也是一个合式公式,则称X为公式A的一个子公式。例题7:证明Q (P (P Q) Q P 。证明:证明:由吸收律, (P (P Q) P 因此,根据上面的定理,有Q (P (P Q) Q P 。证毕。证毕。 此定理也称为置换定理此定理也称为置
22、换定理定理:定理:设X是合式公式A的子公式,若X Y,如果将A中的X用Y来置换,则所得到的公式B与公式A等价,即A B。481-4 真值表与等价公式真值表与等价公式例题8 证明:(P Q) (P Q) P 证: (P Q) (P Q) P (Q Q) 分配律 P 1 否定律 P同一律491-4 真值表与等价公式真值表与等价公式例题9 证明:P (Q R) Q (P R) R (Q P)证: P (Q R) P (Q R) 蕴涵等值式 Q (P R) 结合律 Q (P R) 蕴涵等值式(第二个等价公式类似可证。)501-5 其它连结词其它连结词定义:定义:设P和Q是两个命题公式,复合命题P 、Q
23、恰有一个成立称为P与Q的排斥或或异或。 P Q的真值为T,当且仅当P与Q的真值不相同时为T,否则为F。PQP QTTFTFTFTTFFF定理:定理:设P,Q,R为任意命题公式。如果P Q R,则P R Q,Q R P,且P Q R为一矛盾式。511-5 其它连结词其它连结词定义:定义:设P和Q是两个命题公式,复合命题P Q称为P和Q的条件否定, P Q的真值为T,当且仅当P的真值为T,Q的真值为F;否则,P Q的真值为为F。PQP QTTFTFTFTFFFF521-5 其它连结词其它连结词定义:定义:设P和Q是两个命题公式,复合命题PQ称为P和Q的“与非”,当且仅当P和Q的真值都为T时, PQ
24、 的真值为F;否则, PQ的真值为为T。PQPQTTFTFTFTTFFT531-5 其它连结词其它连结词定义:定义:设P和Q是两个命题公式,复合命题PQ称为P和Q的“或非”,当且仅当P和Q的真值都为T时, PQ 的真值为F;否则, PQ的真值为为T。PQPQTTFTFFFTFFFT541-5 其它连结词其它连结词命题公式:12345678PQTFPQ P QP QPQTTTFTTFFTFTFTFTFFTFTFTTFFTTFFTFFTFFFTTFT910111213141516PQP QPQPQP QPQP QQPQ PTTTFTFTFTFTFTFFTFTTFFTTFTFFTFTFFFTTFTF
25、TF551-5 其它连结词其它连结词等价公式:等价公式:1. PQ (PQ) (QP) 2. (PQ) P Q3. P Q ( P Q),P Q ( P Q)4. P Q (P Q)5. P Q ( PQ)6. PQ (P Q)7. PQ (P Q)最小联结词组:最小联结词组: , 或或 , 或或或或56回顾表1-4.8的10个命题定律:序号定律表达式1对合律P P2幂等律PP PPP P3集合律(P Q) R P (Q R)(P Q) R P (Q R)4交换律P Q Q PP Q Q P5分配律P (Q R) (P Q) (P R)P (Q R) (P Q) (P R)1-6 对偶与范式对
展开阅读全文