离散数学概述.ppt

Click to edit Master text styles,Second level,Third level,Fourth level,Click to edit Master title style,离散数学概述,离 散 数 学,课程名称,离散数学,Discrete Mathematics,离散数学结构,Discrete Mathematical Structures,课程简介,离散数学，是现代数学的一个重要分支，计算机科学与技术一级学科的核心课程，是整个计算机学科的专业基础课。,离散数学是以研究离散量的结构和相互间的关系为主要目标，其研究对象一般地是有限个或可数个元素，因此它充分描述了计算机科学离散性的特点。,离散数学是随着计算机科学的发展而逐步建立的，它形成于七十年代初期，是一门新兴的工具性学科。,后续课程,数据结构操作系统,编译理论算法分析,系统结构容错判断,机器定理证明数据库原理,人工智能,离散数学的发展,18世纪以前,数学基本上是研究离散对象的数量和空间关系的科学,。,之后,因天文学,物理学的发展,如行星轨道,牛顿三大力学定律等研究,极大地推动了连续数学(以微积分,数学物理方程,实、复变函数论为代表)的发展。,离散对象的研究则处于停滞状态,。,20世纪30年代,图灵提出计算机的理论模型,图灵机,。,这种模型早于实际制造计算机十多年,现实的计算机的计算能力,本质上和图灵机的计算能力一样。,由于在计算机内,机器字长总是有限的,它代表离散的数或其它离散对象，因此随着计算机科学和技术的迅猛发展,离散数学就显得重要。,离散数学的内容,数理逻辑,：“证明”在计算科学的某些领域至关重要，构造一个证明和写一个程序的思维过程在本质上是一样的。,组合分析,：解决问题的一个重要方面就是计数或枚举对象。,离散结构,：用来表示离散对象以及它们之间关系的抽象数学结构，包括：集合、排列、关系、树、图。,算法化思维,：许多问题都可以通过构造一个可以被程序实现的算法来解决。它的三个步骤是：,构造,（选择合适的离散模型和操作步骤）、,验证,（算法的正确性）、,评估,（时间和空间的复杂性）。,应用和建模,：在可以想到的任何研究领域都有离散数学的应用。计算科学、化学、植物学、动物学、语言学、地理、经济学等，构造离散模型都是极其有用的解决问题的方法。,教学内容,集合论,数理逻辑,图论,代数结构,为什么要学离散数学,计算机求解的基本模式是：,实际问题,数学建模,算法设计,编程实现,离散数学为数学建模打下知识基础、为算法设计提供具体指导,离散数学结构实际上就是通用的抽象的模式的集合。告诉你各种模式的本质特征和它们之间的关系，以及选用它们的策略；告诉你哪些问题是可解的，哪些是当前在图灵机模型上无（最优）解的，哪些是可以得到近似,/,较优解的。,简而言之，离散数学的作用就在于训练运用离散结构作为问题的抽象模型、构造算法、解决问题的能力。,离散数学的应用举例,关系型数据库的设计（关系代数）,表达式解析（树）,优化编译器的构造（闭包）,编译技术、程序设计语言（代数结构）,Lisp,和,Prolog,、人工智能、自动推理、机器证明（数理逻辑）,网络路由算法（图论）,游戏中的人工智能算法（图论、树、博弈论）,专家系统（集合论、数理逻辑,知识和推理规则的计算机表达）,软件工程,团队开发,时间和分工的优化（图论,网络、划分）,(,各种,),算法的构造、正确性的证明和效率的评估（离散数学的各分支）,学习要求,本课程特点定义+定理+例题,多做习题，完成作业想的清楚，说的明白，写的工整,教材,耿素云，,屈婉玲,编著,离散数学(修订版,),北京：高等教育出版社,2004,耿素云，,屈婉玲,编著,离散数学学习指导与习题解析,北京：高等教育出版社,2005,,necweb,.,neu,.,edu,.,cn,/,ncourse,/,lssx,/index.,htm,参考教材,左孝凌，李为鉴，刘永才编著离散数学上海：上海科学技术文献出版社,1982,孙吉贵，杨凤杰，欧阳丹彤，李占山编著离散数学高等教育出版社，2002,美,Kenneth H.Rosen,著,袁崇义，,屈婉玲,，,王捍贫，刘田译,离散数学及其应用北京：机械工业出版社，2002,数理逻辑简介,逻辑学,是一门研究思维形式及思维规律的科学，也就是研究推理过程的规律的科学。逻辑规律就是客观事物在人的主观意识中的反映。,逻辑学分为辩证逻辑与形式逻辑两种，,辩证逻辑,是以辩证法认识论的世界观为基础的逻辑学，,形式逻辑,主要是对思维的形式结构和规律进行研究的类似于语法的一门工具性学科。,思维的形式结构包括了概念、判断和推理之间的结构和联系，其中概念是思维的基本单位，通过概念对事物是否具有某种属性进行肯定或否定的回答，这就是,判断,；由一个或几个判断推出另一判断的思维形式，就是,推理,。,用数学方法来研究推理的规律称为,数理逻辑,。这里所指的数学方法，就是引进一套符号体系的方法，在其中表达和研究推理的规律。,数理逻辑简介,通常认为数理逻辑是由,莱布尼兹(,Leibniz,),创立的。,数理逻辑的内容包括：证明论、模型论、递归论、公理化集合论。,数理逻辑的应用,在形式语义学、程序设计方法学和软件工程领域。,在逻辑程序设计方面。,在数据库理论方面。,在程序自动生成、自动转换等的理论和技术研究中。,在形式语言理论、自动机理论、可计算理论、计算复杂性理论等方面。,在人工智能方面。,数理逻辑简介,一个土耳其商人想找一个十分聪明的助手协助他经商，有两人前来应聘，这个商人为了试试哪个更聪明些，就把两个人带进一间漆黑的屋子里，他打开灯后说：“这张桌子上有五顶帽子，两顶是红色的，三顶是黑色的，现在，我把灯关掉，而且把帽子摆的位置弄乱然后我们三个人每人摸一顶帽子戴在自己头上，在我开灯后，请你们尽快说出自己头上戴的帽子是什么颜色的。”说完后，商人将电灯关掉，然后三人都摸了一顶帽子戴在头上，同时商人将余下的两顶帽子藏了起来，接着把灯打开。这时，那两个应试者看到商人头上戴的是一顶红帽子，其中一个人便喊道：“我戴的是黑帽子。”,请问这个人说得对吗？他是怎么推导出来的呢？,数理逻辑简介,前提,结论,推理（规则）,数理逻辑的知识体系,1.1 命题与联结词,1.2 命题公式及其赋值,2.1 等值式,2.2 析取范式与合取范式,3.1 推理的形式结构,3.2 自然推理系统,4.1 一阶逻辑命题符号化,4.2 一阶逻辑公式及解释,5.1 一阶逻辑等值式与置换规则,5.2 一阶逻辑前束范式,5.3 一阶逻辑的推理理论,集合论(,set,theroy,),概述,20世纪数学中最为深刻的活动，是关于数学基础的探讨。这不仅涉及到数学的本性，也涉及到演绎数学的正确性。数学中若干悖论的发现，引发了数学史上的第三次危机，这种悖论在集合论中尤为突出。,集合论最初是一门研究数学基础的学科，它从一个比“数”更简单的概念-集合出发，定义数及其运算，进而发展到整个数学领域，在这方面它取得了极大的成功。,集合论的起源可以追溯到19世纪末期。1874年，29岁的德国数学家康托尔(,Georg,Cantor),在“数学杂志”发表了关于无穷集合论的第一篇革命性文章，从1874年至1884年间，,Cantor,的系列有关集合的文章，奠定了集合论的基础。,集合论概述,康托尔开创的集合论被称为朴素集合论，因为他没有对集合论作完整的形式的刻画，从而导致了理论的不一致(产生了悖论)。,在集合论的若干悖论中，最通俗易懂的是,Russell(,罗素)的理发师悖论：,一个乡村理发师，自夸本村无人可与相比，宣称他当然不给自己刮脸的人刮脸，但却给本村所有自己不刮脸的人刮脸。一天他发生了疑问，他是否应当给自己刮脸,。,集合论概述,集合不仅可以用来表示数即其运算，更可以用于非数值信息的表示和处理，如数据的增加、删除、修改、排序，以及数据间关系的描述，有些很难用传统的数值计算来处理，但可以用集合运算来处理。,因此，集合论在程序语言、数据结构、编译原理、数据库与知识库、形式语言和人工智能等领域中都得到了广泛的应用，并且还得到了发展，如,Zadeh,(,扎德)的模糊集理论和,Pawlak,的粗糙集理论。,代数系统,近世代数，是关于运算的学说，是关于运算规则的学说，但它不把自己局限在研究数的运算性质上，而是企图研究一般性元素的运算性质。,.,Klein,数学之所以重要，其中心原因在于它所提供的数学系统的丰富多彩；此外的原因是，数学给出了一个系统，以便于使用这些模型对物理现实和技术领域提出问题，回答问题，并且也就探索了模型的行为。,R.C.Buck&E.F.Buck,代数系统-具有运算的集合-是抽象代数研究的主要对象。,代数结构的知识体系,半群与群,环与域,格与布尔代数,分类,代数,推广,成分：载体及运算,公理：运算性质,代数系统的构成,代数系统的,同态与同构,代数系统间的关系,映射,子代数,积代数,商代数,等价关系,笛卡儿积,子集,新代数系统,同种的,同类型的,产生,半群与群,广群,二元运算的封闭性,结合律,半群,单位元,独异点,每个元素可逆,群,交换律,交换半群,交换律,交换独异点,交换律,Abel,群,有限个元素,有限群,生成元,循环群,实例,n,元置换群,实例,Klein,群,图论,图论是离散数学的重要组成部分，是近代应用数学的重要分支。,1736年是图论历史元年，因为在这一年瑞士数学家欧拉(,Euler,),发表了图论的首篇论文哥尼斯堡七桥问题无解，所以人们普遍认为欧拉是图论的创始人。,1936年，匈牙利数学家寇尼格（,Konig,）,出版了图论的第一部专著有限图与无限图理论，这是图论发展史上的重要的里程碑，它标志着图论将进入突飞猛进发展的新阶段。,计算机科学的发展为图论的发展提供了计算工具。,现代科学技术的发展需要借助图论来描述和解决各类课题中的各种关系，从而推动科学技术不断地攀登新的高峰。,作为描述事务之间关系的手段或称工具，图论在许多领域，诸如，计算机科学、物理学、化学、运筹学、信息论、控制论、网络通讯、社会科学以及经济管理、军事、国防、工农业生产等方面都得到广泛的应用，也正是因为在众多方面的应用中，图论自身才得到了非常迅速的发展。,