离散数学的概念PPT课件

离散数学的概念离散数学(Discretemathematics)是数学的几个分支的总称，以研究离散量的结构和相互间的关系为主要目标，其研究对象一般地是有限个或可数无穷个元素；是我们计算机学科的基础。序言由于数字电子计算机是一个离散结构，它只能处理离散的或离散化了的数量关系，因此，无论计算机科学本身，还是与计算机科学及其应用密切相关的现代科学研究领域，都面临着如何对离散结构建立相应的数学模型；又如何将已用连续数量关系建立起来的数学模型离散化，从而可由计算机加以处理。离散数学课程主要介绍离散数学的各个分支的基本概念、基本理论和基本方法。这些概念、理论以及方法大量地应用在数字电路、编译原理、数据结构、操作系统、数据库系统、算法的分析与设计、人工智能、计算机网络等专业课程中；同时，该课程所提供的训练十分有益于学生概括抽象能力、逻辑思维能力、归纳构造能力的提高，十分有益于学生严谨、完整、 规范 编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载 的科学态度的培养。简而论之，一般认为，离散数学包括了以下几个子学科：数理逻辑、集合论、关系论、函数论、代数系统与图论。集合论的学科起源与发展第一次数学危机的经过：公元前一世纪，，古希腊数学走到了世界的前列，起很多研究成果甚至领先世界近千年，其中最有代表意义的莫过于“毕达哥拉斯”学派。该学派是一个很专制很严密的组织，它要求成员严守纪律，对宗师毕达哥拉斯绝对服从，不允许有任何人跟任何组织冒犯学派在数学上的权威。毕达哥拉斯在数论上曾有过“万物皆数”，且“数”只能是整数跟分数。但是，毕达哥拉斯的学生希帕苏斯发现了以下命题:“边长为1的正方形对角线长度应该是多少？”，当时勾股定理已经得到严格证明，命题于是演变成“什么数的平方是2？”显然按照毕达哥拉斯的理论，这个数是找不到的，但边长为1的正方形又确实存在！毕达哥拉斯感到了恐惧，为了防止泄密，他让人将希帕苏斯投入了爱琴海。亚里士多德后来证明了这个正方形的长度并非有理数，毕达哥拉斯的绝对权威受到了严重的挑战。一方面已经证明单位正方形对角线的长不是整数与分数，按毕达哥拉斯学派的观点，这并不是一个“数”，这令人难以接受；另一方面，当时占统治地位的毕达哥拉斯学派对数的根深蒂固的人数又使他们不肯承认并打压这种“怪异的数字”的存在，一时间数学界陷入极大的矛盾之中，这就是第一次数学危机的由来。十八世纪，才华横溢的牛顿跟莱布尼茨几乎同时发现了微积分方法，这对于数学界来说，有着划时代的意义。但由于牛莱二人对于微积分这种方法内含的原理本身不是很清楚，他们对“流数”（即我们现在的增量）的表述十分含糊，整个推导过程并不清晰，于是被英国哲学家，神职人员伯克莱抓到了空子，提出了著名的伯克莱悖论：“因为如果让增量变为零，或者说没有任何增量，那么原来关于增量存在的假设也就不能成立，而由这一假设引出的结果，即借助于增量而得到的表达式却必须保留。”按照逻辑上讲，伯克莱的悖论是有道理的，牛莱二人的对于微积分方法的推导过程确实存在着逻辑上的致命漏洞！但是对于微积分的实际应用却是摆在那里的，它的实用性不言自明。这样，伯克莱的批评与讽刺指出了当时微积分在理论上的漏洞跟推导过程中的粗糙，一时间，牛莱二人的“微积学说”跟伯克莱等人的“反微积学说”争持激烈，这就是第二次数学危机的由来。要说清楚这个问题，我觉得很有必要先跟大家说清楚一个大家都已经闻名遐迩但又可能知之不详的一个相当著名的概念——数学发展史上出现的三次危机第三次数学危机先介绍康托尔（Cantor）这个伟大的数学家，集合论的创始人，离散数学的奠基者。康托尔1845年岀生于俄国圣彼得堡，后随父移居法兰克福，先后在格丁根大学和法兰克福大学里是从外尔斯特拉斯、库默尔和克罗内克，后任哈类大学教授，或西尔威斯特奖章，专攻纯粹数学康托尔是数学史上第一个给出集合定义，且引入点集的极限点、闭集、开集、交集、并集等概念的人1874年，康托尔证明了代数数集与有理数集的可数性和实数集的不可数性，同年构造了“Cantor”尘集1878年他又引入集合“势”的概念，且证明了Cantor尘集与实数集等势而不可数，但其测度为零1883年，康托尔证明了著名的“Cantor定理”：一个集合与它的幂集间不可能建立一一对应，幂集的势大于原集合的势。（幂集的概念是我们的课堂内容）1877年，康托尔证明了一条直线上的点与平面上的点（乃至n维空间上的点）一一对应1878年，康托尔提出了连续统假设（代号CH，continuumhypothesis）：在自然数的势与实数集的势之间不存在其他的势。这个假设是否成立，至今无人证真或证伪！1883年，康托尔提出良序集和序数的概念：一个集合，他的元素按确定的顺序排列，存在该集合的第一个元素，而且对于每个元素，都存在一个确定的后继，这样的集合称为良序集。举个例子：自然数集合1，2…n，n+1就是一个良序集，1为第一个元素，n+1是n的后继。康托尔用w表示自然数这个良序集的自然顺序，而把w写在紧跟自然数序列之后，且称w也是一个“数”，或称w为第一个“超穷序数”，它比所有自然数都大，是自然数序列永远达不到的极限康托尔以他那大胆而又浪漫的构想，巧夺天工的证明技巧，对数学那份执着的敏感和新奇的思路，成为了后世数学家学习跟敬仰的模范，但是在他所处的那个时代，他是一个彻头彻尾的争议人物在当时，他的理论，尤其是上面说到的“实无穷理论”，更是成为了当时主流数学界的靶子，为此，他跟他的业师克罗内克翻了脸，用康托尔自身的话说：我已经意识到，我必须要跟我的前辈们彻底决裂！事实上，他自己也困于自己的推理世界中不能自拔，当他在1877年推出“一一对应”理论时，他曾郁闷地向好友戴德金表示：“我看到了这个事实，但连我自己都不敢相信它。”当然，他还是相信自己严格证明出的东西是真的，这种自信与质疑，缠绕了这个天才的一生。康托尔（Cantor）康托尔的朴素集合论：把一定的并且彼此可以明确识别的事物——这种事物，可以是直观的对象，也可以是思维的对象——放在一起，称为一个集合，这些事物的每一个称为该集合的每一个元素。其实，作为第三次数学危机的主角之一，康托尔已经很敏感地认识到这种朴素的集合论在逻辑上可能要出事，他向戴德金说过要“禁谈一切集合组成的集合”十分可惜的是，这位天才没有来得及建立一套公理系统给出的集合论以及明确无暇的概念与理论便与世长辞了。果然出事了1902年，罗素提出了著名的“理发师悖论”：一位乡村理发师，宣称他不给村子里任何自己刮脸的人刮脸，但给所有不自己刮脸的人刮脸。人们问：“那您自己给不给自己刮脸？”理发师无言以对。的确如果理发师自己刮脸，那么违背了他自己原则的前半部分，但如果他不自己刮脸，那么按照原则的后一部分，他又必须给自己刮脸，理发师则陷入深深地矛盾中不能自圆其说。事实上，“理发师悖论”只是“罗素悖论”的通俗版本，下面我们看一下罗素制造的“仿理发师悖论”：事实上，有的集合，比如26个字母的集合：Ą={a,b,c,…,x,y,z}显然有Ą不属于Ą中的元素但有的集合，比如“集合β是以10个以上元素的集合为元素组成的集合”。则{1，2，3…，10，11}，{1，2，3…，10，11，12}，…{1，2，3…，10，…,n，n+1}这些集合皆有10个以上的元素，而β的元素个数也超过10个，故而β∈β。则可见，若根据康托尔的“朴素集合论”，则会发生集合不是自己的元素，又会发生集合是自己元素的现象。那么，罗素构造了以下集合：B={A|A不属于A}罗素问：“B∈B吗？”我们惊奇地发现，我们居然无法回答这个问题！若B∈B，按照B的定义，则B不属于B，矛盾；若B不属于B，按照B的定义，则B∈B，又矛盾！罗素认为解决理发师悖论的根本办法是宣布世界上根本不存在这种理发师，或者把理发师排除在“他给刮脸跟他不给刮脸的人群”之外，也就是说，排除罗素悖论的根本途径是不承认B={A|A不属于A}是一个集合，禁谈一个集合是自己本身的元素，即不可以讨论B∈B。就是这样，第三次数学危机爆发了，突破口是天才数学家康托尔的朴素集合论。自此之后，一大群数学精英为了推进数论的发展，先后为剔除“罗素悖论”前赴后继…….其中，以法国数学家策墨罗提出的 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 最为彻底，他跟弗伦克尔合作提出一套ZF公理，策墨罗是这样 评价 LEC评价法下载LEC评价法下载评价量规免费下载学院评价表文档下载学院评价表文档下载 这个方案的：从现有的集合论成果出发，建立这一数学分支的原则，这些原则必须足够狭窄，以保证排除一切矛盾；另一方面，又必须充分广阔，使得康托尔集合论中一切有价值的东西得以保留。在ZF公理出现以前，人们可以自由地构造集合{x|ф(x)}，其中ф(x)}是对该集合中的元素性质的一种描述，正是这样的限制不够严格地随意制集合才导致了罗素悖论。对此，ZF公理的办法是：必须先有一个集合A，在A中选择满足性质ф(x)的元素来构造另一个集合（A的子集），包含一切集的集合不存在。这也叫公理集合论ZF公理较好的解决了第三次数学危机，到目前为止，还没有人发现任何悖论或者矛盾。在这个历史背景下去评论它，无疑是成功的。在一大群数学家的不懈努力下，消除悖论的努力成为了集合论发展的巨大推动力，比如说外延公理、空集公理、分离公理、幂集公理、并集公理、选择公理和无穷公理共七个公理的集合论体系，这个就是策墨罗所提出的ZF系统的理论基础。但是我们也应该清楚，其实严格来讲，罗素悖论不是被剔除了，只不过是被避开了。虽然集合论公理化运动是假定了数学运用的逻辑本身不成问题，但数学家们对于这一前提陆续提出了不同的观点，并形成了关于数学基础的三大学派，即：以罗素为代表的逻辑主义，以布劳威尔为代表的直觉主义和以希尔伯特为代表的形式主义。在集合论上出现的歧见也懂很多个侧面推动了数理逻辑的发展，现代数理逻辑的四大分支——公理化集合论，证明论，模型论，递归论的提出，也都源于20世纪早期关于离散数学基础问题的探讨。在这些坚实的基础上，集合论，甚至推广到整个离散数学，都在发现悖论跟解决悖论中曲折前进。ENDMADEBY王渝鑫2008.10.09