离散数学的概念.ppt

《离散数学的概念.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学的概念离散数学(Discretemathematics)是数学的几个分支的总称，以研究离散量的结构和相互间的关系为主要目标，其研究对象一般地是有限个或可数无穷个元素；是我们计算机学科的基础。序言由于数字电子计算机是一个离散结构，它只能处理离散的或离散化了的数量关系，因此，无论计算机科学本身，还是与计算机科学及其应用密切相关的现代科学研究领域，都面临着如何对离散结构建立相应的数学模型；又如何将已用连续数量关系建立起来的数学模型离散化，从而可由计算机加以处理。离散数学课程主要介绍离散数学的各个分支的基本概念、基本理论和基本方法。这些概

2、念、理论以及方法大量地应用在数字电路、编译原理、数据结构、操作系统、数据库系统、算法的分析与设计、人工智能、计算机网络等专业课程中；同时，该课程所提供的训练十分有益于学生概括抽象能力、逻辑思维能力、归纳构造能力的提高，十分有益于学生严谨、完整、规范的科学态度的培养。简而论之，一般认为，离散数学包括了以下几个子学科：数理逻辑、集合论、关系论、函数论、代数系统与图论。集合论的学科起源与发展第一次数学危机的经过：公元前一世纪，，古希腊数学走到了世界的前列，起很多研究成果甚至领先世界近千年，其中最有代表意义的莫过于“毕达哥拉斯”学派。该学派是一个

3、很专制很严密的组织，它要求成员严守纪律，对宗师毕达哥拉斯绝对服从，不允许有任何人跟任何组织冒犯学派在数学上的权威。毕达哥拉斯在数论上曾有过“万物皆数”，且“数”只能是整数跟分数。但是，毕达哥拉斯的学生希帕苏斯发现了以下命题:“边长为1的正方形对角线长度应该是多少？”，当时勾股定理已经得到严格证明，命题于是演变成“什么数的平方是2？”显然按照毕达哥拉斯的理论，这个数是找不到的，但边长为1的正方形又确实存在！毕达哥拉斯感到了恐惧，为了防止泄密，他让人将希帕苏斯投入了爱琴海。亚里士多德后来证明了这个正方形的长度并非有理数，毕达哥拉斯的绝对权威受

4、到了严重的挑战。一方面已经证明单位正方形对角线的长不是整数与分数，按毕达哥拉斯学派的观点，这并不是一个“数”，这令人难以接受；另一方面，当时占统治地位的毕达哥拉斯学派对数的根深蒂固的人数又使他们不肯承认并打压这种“怪异的数字”的存在，一时间数学界陷入极大的矛盾之中，这就是第一次数学危机的由来。十八世纪，才华横溢的牛顿跟莱布尼茨几乎同时发现了微积分方法，这对于数学界来说，有着划时代的意义。但由于牛莱二人对于微积分这种方法内含的原理本身不是很清楚，他们对“流数”（即我们现在的增量）的表述十分含糊，整个推导过程并不清晰，于是被英国哲学家，神职人

5、员伯克莱抓到了空子，提出了著名的伯克莱悖论：“因为如果让增量变为零，或者说没有任何增量，那么原来关于增量存在的假设也就不能成立，而由这一假设引出的结果，即借助于增量而得到的表达式却必须保留。”按照逻辑上讲，伯克莱的悖论是有道理的，牛莱二人的对于微积分方法的推导过程确实存在着逻辑上的致命漏洞！但是对于微积分的实际应用却是摆在那里的，它的实用性不言自明。这样，伯克莱的批评与讽刺指出了当时微积分在理论上的漏洞跟推导过程中的粗糙，一时间，牛莱二人的“微积学说”跟伯克莱等人的“反微积学说”争持激烈，这就是第二次数学危机的由来。要说清楚这个问题，我觉

6、得很有必要先跟大家说清楚一个大家都已经闻名遐迩但又可能知之不详的一个相当著名的概念——数学发展史上出现的三次危机第三次数学危机先介绍康托尔（Cantor）这个伟大的数学家，集合论的创始人，离散数学的奠基者。康托尔1845年岀生于俄国圣彼得堡，后随父移居法兰克福，先后在格丁根大学和法兰克福大学里是从外尔斯特拉斯、库默尔和克罗内克，后任哈类大学教授，或西尔威斯特奖章，专攻纯粹数学康托尔是数学史上第一个给出集合定义，且引入点集的极限点、闭集、开集、交集、并集等概念的人1874年，康托尔证明了代数数集与有理数集的可数性和实数集的不可数性，同年构造

7、了“Cantor”尘集1878年他又引入集合“势”的概念，且证明了Cantor尘集与实数集等势而不可数，但其测度为零1883年，康托尔证明了著名的“Cantor定理”：一个集合与它的幂集间不可能建立一一对应，幂集的势大于原集合的势。（幂集的概念是我们的课堂内容）1877年，康托尔证明了一条直线上的点与平面上的点（乃至n维空间上的点）一一对应1878年，康托尔提出了连续统假设（代号CH，continuumhypothesis）：在自然数的势与实数集的势之间不存在其他的势。这个假设是否成立，至今无人证真或证伪！1883年，康托尔提出良序集和序

8、数的概念：一个集合，他的元素按确定的顺序排列，存在该集合的第一个元素，而且对于每个元素，都存在一个确定的后继，这样的集合称为良序集。举个例子：自然数集合1，2…n，n+1就是一个良序集，1为第