离散数学的概念.ppt

离散数学的概念离散数学(Discrete mathematics) 是数学的几个分支的总称,以研究离散量的结构和相互间的关系为主要目标,其研究对象一般地是有限个或可数无穷个元素; 是我们计算机学科的基础。序言?由于数字电子计算机是一个离散结构,它只能处理离散的或离散化了的数量关系, 因此,无论计算机科学本身, 还是与计算机科学及其应用密切相关的现代科学研究领域,都面临着如何对离散结构建立相应的数学模型;又如何将已用连续数量关系建立起来的数学模型离散化, 从而可由计算机加以处理。?离散数学课程主要介绍离散数学的各个分支的基本概念、基本理论和基本方法。这些概念、理论以及方法大量地应用在数字电路、编译原理、数据结构、操作系统、数据库系统、算法的分析与设计、人工智能、计算机网络等专业课程中;同时,该课程所提供的训练十分有益于学生概括抽象能力、逻辑思维能力、归纳构造能力的提高, 十分有益于学生严谨、完整、规范的科学态度的培养。简而论之,一般认为,离散数学包括了以下几个子学科: 数理逻辑、集合论、关系论、函数论、代数系统与图论。集合论的学科起源与发展?第一次数学危机的经过:公元前一世纪,,古希腊数学走到了世界的前列,起很多研究成果甚至领先世界近千年,其中最有代表意义的莫过于“毕达哥拉斯”学派。该学派是一个很专制很严密的组织,它要求成员严守纪律,对宗师毕达哥拉斯绝对服从,不允许有任何人跟任何组织冒犯学派在数学上的权威。毕达哥拉斯在数论上曾有过“万物皆数”,且“数”只能是整数跟分数。但是,毕达哥拉斯的学生希帕苏斯发现了以下命题:“边长为 1的正方形对角线长度应该是多少? ”,当时勾股定理已经得到严格证明,命题于是演变成“什么数的平方是 2?”显然按照毕达哥拉斯的理论,这个数是找不到的,但边长为 1的正方形又确实存在!毕达哥拉斯感到了恐惧,为了防止泄密,他让人将希帕苏斯投入了爱琴海。亚里士多德后来证明了这个正方形的长度并非有理数,毕达哥拉斯的绝对权威受到了严重的挑战。一方面已经证明单位正方形对角线的长不是整数与分数,按毕达哥拉斯学派的观点, 这并不是一个“数”,这令人难以接受;另一方面,当时占统治地位的毕达哥拉斯学派对数的根深蒂固的人数又使他们不肯承认并打压这种“怪异的数字”的存在,一时间数学界陷入极大的矛盾之中,这就是第一次数学危机的由来。?十八世纪,才华横溢的牛顿跟莱布尼茨几乎同时发现了微积分方法, 这对于数学界来说,有着划时代的意义。但由于牛莱二人对于微积分这种方法内含的原理本身不是很清楚,他们对“流数”(即我们现在的增量)的表述十分含糊,整个推导过程并不清晰,于是被英国哲学家, 神职人员伯克莱抓到了空子,提出了著名的伯克莱悖论: “因为如果让增量变为零,或者说没有任何增量,那么原来关于增量存在的假设也就不能成立,而由这一假设引出的结果,即借助于增量而得到的表达式却必须保留。”按照逻辑上讲,伯克莱的悖论是有道理的,牛莱二人的对于微积分方法的推导过程确实存在着逻辑上的致命漏洞! ?但是对于微积分的实际应用却是摆在那里的,它的实用性不言自明。这样,伯克莱的批评与讽刺指出了当时微积分在理论上的漏洞跟推导过程中的粗糙, 一时间,牛莱二人的“微积学说”跟伯克莱等人的“反微积学说”争持激烈,这就是第二次数学危机的由来。要说清楚这个问题, 我觉得很有必要先跟大家说清楚一个大家都已经闻名遐迩但又可能知之不详的一个相当著名的概念——数学发展史上出现的三次危机第三次数学危机先介绍康托尔 Cantor 这个伟大的数学家集合论的创始人离散数学的奠基者康托尔 1845 年岀生于俄国圣彼得堡后随父移居法兰克福先后在格丁根大学和法兰克福大学里是从外尔斯特拉斯库默尔和克罗内克后任哈类大学教授或西尔威斯特奖章专攻纯粹数学康托尔是数学史上第一个给出集合定义且引入点集的极限点闭集开集交集并集等概念的人 1874 年康托尔证明了代数数集与有理数集的可数性和实数集的不可数性同年构造了“ Cantor ”尘集 1878 年他又引入集合“势”的概念且证明了 Cantor 尘集与实数集等势而不可数但其测度为零 1883 年康托尔证明了著名的“ Cantor 定理”一个集合与它的幂集间不可能建立一一对应幂集的势大于原集合的势幂集的概念是我们的课堂内容 1877 年康托尔证明了一条直线上的点与平面上的点乃至 n 维空间上的点一一对应 1878 年康托尔提出了连续统假设代号 CH continuum hypothesis 在自然数的势与实数集的势之间不存在其他的势这个假设是否成立至今无人证真或证伪 1883 年康托尔提出良序集和序数的概念一个集合他的元素按确定的顺序排列存在该集合的第一个元素而且对于每个元素都存在一个确定的后继这样的集合称为良序集举个例子自然数集合 12…n n+1 就是一