[数学]离散数学.ppt

离 散 数 学 Discrete Mathematics,主讲教师：欧阳丹彤 ouyd@ 助课教师：刘杰 liu_jie@ 计算机学院智能信息处理研究室,离散数学是现代数学的一个重要分支，也是计算机科学与技术一级学科及其相关专业必修的基础理论的核心课程是学习后续专业课程不可缺少的数学工具《中国计算机科学与技术学科教程》中将其列为计算机科学与技术专业14个知识领域之一 形成于七十年代初期，是随着计算机科学的发展而逐步建立的1、课程的性质,研究对象：离散量结构及相互关系离散量:逻辑量、图、树、整数、布尔代数连续量:温度、压力、体积、电压—— 计算机中离散处理 可见，离散数学充分描述了计算机学科离散性的 特点 离散数学是一门理论性较强，应用性较广的课程1、课程的性质,掌握离散数学的基本概念和基本原理离散数学所涉及的概念、方法和理论，大量地出现在“编译原理”、“数据结构”、“操作系统”、“数据库系统”、“算法分析”、“定理机器证明”、“人工智能”等众多领域，为学习这些课程做了必要的知识准备 如：谓词逻辑成为程序的语义理论和程序的正确性证明的重要研究工具；平面图的理论被用于印刷电路板的设计；图论的概念和理论广泛用于AI、DS等；布尔代数为开关理论的研究提供了分析工具，并导致了数字逻辑理论的建立；代数系统的理论被用于对数据结构的研究，产生了抽象数据类型的理论；代数系统的理论成为编码理论的数学基础。

2、课程的目的,,离散数学、数据结构、算法设计与分析、组合数学和程序设计等课程紧密相关,以问题的求解步骤来具体说明5门课程的紧密相关性： 运用离散数学,组合数学等知识完成待解问题数学建模 运用数据结构和算法设计的知识选择、构造恰当数据结构，编写较好的计算机算法 对算法的关键点，运用离散数学、组合数学知识进行正确性证明（此步骤是可选择的） 运用算法分析、离散数学、组合数学等知识对算法进行时空复杂性分析 运用离散数学、算法设计、组合数学和运筹学等知识对算法进行优化（此步骤是可选择的） (在算法基础上)使用程序设计技巧编写程序，使用程序测试技术测试程序，在计算机上完成问题求解数据结构、离散数学、算法设计与分析、组合数学和程序设计等课程紧密相关,数据结构、离散数学、算法、组合数学和汇编语言程序是图灵奖获得者、著名计算机科学家、数学家D.E.Knuth教授的旷世之作《计算机程序设计艺术》的主要内容2、课程的目的,提供良好的数学训练 （1）提高逻辑思维、抽象思维能力（2）提高严密的推理能力（3）提高数学语言描述能力 （4）提高判断对错能力—独立工作能力,,分析问题与 解决问题 的能力,定义与定理多离散数学是建立在大量定义之上的逻辑推理学科，因此对概念的理解是我们学习这门课程的核心。

在学习这些概念的基础上，要特别注意概念之间的联系，而描述这些联系的实体则是大量的定理与性质 方法性强离散数学的许多证明题中，方法性是非常强的，如果掌握了题的证明方法，很容易就可以证出来，反之则事倍功半所以在学习该课程中要善于总结，勤于思考，这也是培养分析问题、解决问题能力与抽象思维能力的一个过程3、课程的特点,,4、如何学好离散数学？,掌握概念：在模棱两可的地方多下功夫，弄懂、弄透认真完成作业一道题做完，还要提出如下几个问题： （1）是否肯定一定对 （2）是否有更简洁的方法 （3）推理是否严密 （4）语言是否流畅5、离散数学教学内容,第一章 集合论基础（集合论） 第二章 命题逻辑 第三章 谓词逻辑 第四章 图与网络 （图论） 第五章 数论基础 （数论） 六--八章 抽象代数 ----离散Ⅱ,,数理逻辑,,离散Ⅰ,第一章 集合论基础,§1.1 集合的基本概念§1.2 关 系 §1.3 映 射,集合论发展史,集合论(Set Theory)是现代数学的基础．它的起源可追溯到16世纪末，主要是对数集进行卓有成效的研究． 集合论实际发展是由 19世纪 70年代德国数学家康托尔(G Cantor) 在无穷序列和分析的有关课题的理论研究中创立的．Cantor对具有任意特性的无穷集合进行了深入的探讨，提出了关于基数、序数、超穷数和良序集等理论，奠定了集合论的深厚基础．因此， Cantor被誉为集合论的创始人．他创立的集合论是实数理论，以至整个微积分理论体系的基础。

集合论创始人 康托尔 德国数学家 (Georg Cantor 1845－1918),1845年3月3日出生于俄国的一个丹麦—犹太血统的家庭1856年与父母一起迁到德国的法兰克福1863年进入柏林大学，转到纯粹的数学1866年获得博士学位1874年在《数学杂志》上发表了关于无穷集合理论的第一篇革命性文章数学史上一般认为这篇文章的发表标志着集合论的诞生Cantor 生平,1879年任哈雷大学教授1891年组建德国数学家联合会，被选为第一任主席1904年被伦敦皇家学会授予当时数学界最高荣誉——西尔威斯特（Sylvester）奖章1884年春天起患了严重的忧郁症，极度沮丧，神态不安，精神病时时发作，不得不经常住到精神病院的疗养所去变得很自卑，甚至怀疑自己的工作是否可靠他请求哈雷大学当局把他的数学教授职位改为哲学教授职位1918年在哈雷大学附属精神病院去世，享年73岁克罗内克（L.Kronecker 1823－1891）Cantor的老师，对Cantor表现出了无微不至的关怀他用各种用得上的尖刻语言，粗暴地、连续不断地攻击Cantor达十年之久他甚至在柏林大学的学生面前公开攻击Cantor 。

横加阻挠Cantor在柏林得到一个薪金较高、声望更大的教授职位使得Cantor想在柏林得到职位而改善其地位的任何努力都遭到挫折对Cantor的不同评价,法国数学家庞加莱（H.Poincare 1854－1912）：我个人，而且还不只我一人，认为重要之点在于，切勿引进一些不能用有限个文字去完全定义好的东西集合论是一个有趣的“病理学的情形”，后一代将把（Cantor）集合论当作一种疾病，而人们已经从中恢复过来了德国数学家魏尔（C.H.Hermann Weyl，1885－1955）: 关于基数的等级观点是雾上之雾菲利克斯.克莱因（F.Klein，1849－1925）:不赞成集合论的思想数学家H．A．施瓦兹—Cantor的好友由于反对集合论而同Cantor断交Cantor的主要研究成果,通过一一对应关系建立了集合之间等势的概念，奠定了无限集分类的基础最著名的著作--《超穷理论基础》:数学理论必须肯定实无穷，因为很多最基本的数学性质，例如一切正整数，圆周上的一切点等，事实上都是实无穷性的概念而且不能把有穷所具有的性质强加于无穷他的“一一对应”的原理突破了传统的“整体大于部分”的旧观念，例如全体正整数与（其部分）全体正偶数一一对应，正整数集与正偶数集等势。

引进了可数集的概念，证明了有理数全体及代数数（有理多项式的根）全体都是可数集合 运用对角线方法证明了实数集是不可数集，从而间接推导出超越数（非代数数的实数）比代数数多，同时也说明了无限集可按大小区分为不同的类Cantor的主要研究成果,Cantor的主要研究成果,证明了n维空间与一维直线之间存在一一对应 系统研究了序数理论，提出了良序原理 证明了集的幂集比原集有更大的基数 提出了连续统假设集合论发展史（继续）,随着集合论的发展，以及它与数学哲学密切联系所作的讨论，1900年前后，出现了许多悖论，有力冲击了或者说动摇了集合论的发展．（数学史上的三次危机 无理数的发现──第一次数学危机 无穷小是零吗？──第二次数学危机 悖论的产生——第三次数学危机）,著名的罗素悖论：1902年，受到“理发师悖论”的启发而提出 理发师悖论：“一个理发师宣称，他不给自己刮脸的人刮脸，但给所有不自己刮脸的人刮脸人们问：“理发师先生，您自己的脸谁刮？” （悖论不是谬论，悖论中充满着令人惊奇的内容——悖论可以推导出自相矛盾的结论，人们却难以指出悖论非法的理由公元前6世纪，希腊人伊比孟德说： “我说这句话时正在说谎。

伊翁问听众，他上面说的那句话是真话还是假话？该怎么 回答伊翁呢？ “下面的句子是错的，上面的句子是对的问“下面的句子是错的”为真还是为假？),伯特兰·罗素（1872-1970） 英国著名哲学家、数学家、逻辑学家、 散文作家、社会活动家,1872年5月，生于英国曼摩兹郡的特雷克，幼年时父母双亡，是祖母将他抚育成人 1890年进剑桥大学三一学院学习 1893年获数学荣誉学士学位一级接着改学哲学 1894年获道德哲学荣誉学士学位一级 毕业后曾游学德国学经济，受马克思主义影响，回国后，在伦敦大学政治和经济学院任讲师 l903年发表《数学原理》一书，并以论文《几何学基础》获三一学院研究员职位 1908年当选为皇家学会会员罗素生平,1910年发表《哲学文集》;1917年发表《哲学的问题》 1914年加入工党 第一次世界大战期间，因参加和平主义者的活动，被处罚金，革职入狱在狱中，撰写了《数学哲学导论》（1919） 1920年访问中国和苏联，著有《布尔什维主义的实践和理论》1920年到北大担任客座教授，一年后离开，隔年写成《中国问题》这本书他看见：“中国文化正在发生急遽的变化”，提出建议：“假如中国人能自由地吸收我们文明中他们所需要的东西，而排斥那些他们觉得不好的东西，那么他们将能够在其自身传统中获得一种有机发展，并产生将我们的优点同他们自己的优点相结合起来的辉煌成就。

1927年，罗素和夫人布拉克在英国彼得斯费尔德市附近创办一所私立学校，实验他的教育理论，是当时英国的进步主义学校之一1935年离婚后，布拉克独自办到1939年他一直主张“自由教育”和“爱的教育”认为教育的基本目的是品格的发展，而“活力、勇气、敏感和智慧”是形成“理想品格”的基础；并深信通过对儿童的身体、感情和智力上的“恰当的处理”，可以使这些品质得到普遍的培养1931年他继承为第三世罗素勋爵 1949年获荣誉勋章 1950年由于他“多产而重要的哲学著作，并以此成为人道主义与自由思想的代言人”而获得了该年度的诺贝尔文学奖50年代因积极参加世界和平运动，反对核战争而获得世界和平奖1955年2月，爱因斯坦收到了英国著名哲学家罗素的信，告诉他由于制造核武器的竞赛，人类的前途实在令人担心，希望以爱因斯坦为首团结几个著名的科学家发表宣言避免毁灭人类战争发生爱因斯坦在收到信后马上回信表示：“你熟悉这些组织的工作你是将军我是小兵你只要发出命令，我就随后跟从于是出现了著名的《罗素―爱因斯坦宣言》除了爱因斯坦在临终前签字外，约里奥·居里、汤川秀树和李诺·鲍林等多位科学家都在宣言上签字 1961年，89岁高龄的罗素参与一个核裁军的游行后被拘禁了7天。

他反对越南战争，和萨特一起于1967年5月成立了一个民间法庭（后被称为“罗素法庭”），揭露美国的战争罪行1959年，罗素发表了《西方智慧》后，开始了《罗素自传》的创作，并在1967年95岁高龄之际完成了一生最优秀的著作之一《罗素自传》 1970年2月2日去世，一生曾四次结婚，三次离婚《罗素自传》序言 我为什么而活着对爱情的渴望，对知识的追求，对人类苦难不可遏制的同情心，这三种纯洁但无比强烈的激情支配着我的一生这三种激情就像飓风一样，在深深的苦海上，肆意地把我吹来吹大，吹到濒临绝望的边缘 我寻求爱情，首先因为爱情给我带来狂喜，它如此强烈以致我经常愿意为了几小时的欢愉而牺牲生命中的其它一切我寻求爱情，其次是因为爱情解除孤寂——那是一颗震颤的心，在世界的边缘，俯瞰那冰冷死寂、深不可测的深渊我寻求爱情，最后是因为在爱情的结合中，我看到圣徒和诗人们所想象的天堂景象的神秘缩影这就是我所寻求的，虽然它对人生似乎过于美好，然而最终我还是得到了它我以同样的热情寻求知识，我希望了解人的心灵我希望知道星星为什么闪闪发光，我试图理解毕达哥拉斯的思想威力，即数字支配着万物流转这方面我获得一些成就，然而并不多。

爱情和知识，尽其可能地把我引上天堂，但是同情心总把我带回尘世痛苦的呼号的回声在我心中回荡，饥饿的儿童，被压迫者折磨的受害者，被儿女视为可厌负担的无助的老人以及充满孤寂、贫穷和痛苦的整个世界，都是对人类应有生活的嘲讽我渴望减轻这些不幸，但是我无能为力，而且我自己也深受其害 这就是我的一生，我觉得它值得活如果有机会的话，我还乐意再活—次。