[数学]离散数学.ppt

离 散 数 学Discrete Mathematics 主讲教师：欧阳丹彤 ouyd@jlu.edu.cn 助课教师：刘杰 liu_jie@jlu.edu.cn 计算机学院智能信息处理研究室 数据结构、离散数学、算法设计与分析、组合数学和程序设计等课程紧密相关 数据结构、离散数学、算法、组合数学和汇编语言程序是图灵奖获得者、著名计算机科学家、数学家D.E.Knuth教授的旷世之作《计算机程序设计艺术》的主要内容。 2、课程的目的 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) Cantor 生平 1879年 任哈雷大学教授。 1891年 组建德国数学家联合会，被选为第一任主席。 1904年 被伦敦皇家学会授予当时数学界最高荣誉——西尔威斯特（Sylvester）奖章。 1884年春天起 患了严重的忧郁症，极度沮丧，神态不安，精神病时时发作，不得不经常住到精神病院的疗养所去。变得很自卑，甚至怀疑自己的工作是否可靠。他请求哈雷大学当局把他的数学教授职位改为哲学教授职位。 1918年 在哈雷大学附属精神病院去世，享年73岁。 对Cantor的不同评价 法国数学家庞加莱 （H.Poincare 1854－1912）： 我个人，而且还不只我一人，认为重要之点在于，切勿引进一些不能用有限个文字去完全定义好的东西。集合论是一个有趣的“病理学的情形”，后一代将把（Cantor）集合论当作一种疾病，而人们已经从中恢复过来了。 Cantor的主要研究成果 通过一一对应关系建立了集合之间等势的概念，奠定了无限集分类的基础。 最著名的著作--《超穷理论基础》:数学理论必须肯定实无穷，因为很多最基本的数学性质，例如一切正整数，圆周上的一切点等，事实上都是实无穷性的概念。而且不能把有穷所具有的性质强加于无穷。他的“一一对应”的原理突破了传统的“整体大于部分”的旧观念，例如全体正整数与（其部分）全体正偶数一一对应，正整数集与正偶数集等势。 Cantor的主要研究成果 引进了可数集的概念，证明了有理数全体及代数数（有理多项式的根）全体都是可数集合。 运用对角线方法证明了实数集是不可数集，从而间接推导出超越数（非代数数的实数）比代数数多，同时也说明了无限集可按大小区分为不同的类。 Cantor的主要研究成果 证明了n维空间与一维直线之间存在一一对应。 系统研究了序数理论，提出了良序原理。 证明了集的幂集比原集有更大的基数。 提出了连续统假设。 集合论发展史（继续） 随着集合论的发展，以及它与数学哲学密切联系所作的讨论，1900年前后，出现了许多悖论，有力冲击了或者说动摇了集合论的发展． （数学史上的三次危机?无理数的发现──第一次数学危机　　 无穷小是零吗？──第二次数学危机 悖论的产生——第三次数学危机） 著名的罗素悖论：1902年，受到“理发师悖论”的启发而提出。理发师悖论：“一个理发师宣称，他不给自己刮脸的人刮脸，但给所有不自己刮脸的人刮脸。”人们问：“理发师先生，您自己的脸谁刮？” （悖论不是谬论，悖论中充满着令人惊奇的内容——悖论可以推导出自相矛盾的结论，人们却难以指出悖论非法的理由。公元前6世纪，希腊人伊比孟德说： “我说这句话时正在说谎。” 伊翁问听众，他上面说的那句话是真话还是假话？该怎么 回答伊翁呢？ “下面的句子是错的， 上面的句子是对的。”问“下面的句子是错的”为真还是为假？)