离散数学资料

《离散数学资料》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、离散数学吕锡亮lu_xiliang@hotmail.com离散数学，是现代数学的一个重要分支，计算机科学与技术一级学科的核心课程，是整个计算机学科的专业基础课。离散数学是以研究离散量的结构和相互间的关系为主要目标，其研究对象一般地是有限个或可数个元素，因此它充分描述了计算机科学离散性的特点。离散数学是随着计算机科学的发展而逐步建立的，它形成于七十年代初期，是一门新兴的工具性学科。数理逻辑：“证明”在计算科学的某些领域至关重要，构造一个证明和写一个程序的思维过程在本质上是一样的。组合分析：解决问题的一个重要方面就是计数或枚举对象。离散结构：用来表示离散

2、对象以及它们之间关系的抽象数学结构，包括：集合、排列、关系、树、图。算法化思维：许多问题都可以通过构造一个可以被程序实现的算法来解决。它的三个步骤是：构造（选择合适的离散模型和操作步骤）、验证（算法的正确性）、评估（时间和空间的复杂性）。应用和建模：在可以想到的任何研究领域都有离散数学的应用。计算科学、化学、植物学、动物学、语言学、地理、经济学等，构造离散模型都是极其有用的解决问题的方法。教学内容集合论数理逻辑图论代数结构本课程特点定义+定理+例题多做习题，完成作业想的清楚，说的明白，写的工整教材耿素云，屈婉玲编著．离散数学(修订版)．北京：高等

3、教育出版社,2004耿素云，屈婉玲编著．离散数学学习指导与习题解析．北京：高等教育出版社,2005逻辑学是一门研究思维形式及思维规律的科学，也就是研究推理过程的规律的科学。逻辑规律就是客观事物在人的主观意识中的反映。逻辑学分为辩证逻辑与形式逻辑两种，辩证逻辑是以辩证法认识论的世界观为基础的逻辑学，形式逻辑主要是对思维的形式结构和规律进行研究的类似于语法的一门工具性学科。思维的形式结构包括了概念、判断和推理之间的结构和联系，其中概念是思维的基本单位，通过概念对事物是否具有某种属性进行肯定或否定的回答，这就是判断；由一个或几个判断推出另一判断的思维形式，

4、就是推理。用数学方法来研究推理的规律称为数理逻辑。这里所指的数学方法，就是引进一套符号体系的方法，在其中表达和研究推理的规律。数理逻辑20世纪数学中最为深刻的活动，是关于数学基础的探讨。这不仅涉及到数学的本性，也涉及到演绎数学的正确性。数学中若干悖论的发现，引发了数学史上的第三次危机，这种悖论在集合论中尤为突出。集合论最初是一门研究数学基础的学科，它从一个比“数”更简单的概念----集合出发，定义数及其运算，进而发展到整个数学领域，在这方面它取得了极大的成功。集合论的起源可以追溯到19世纪末期。1874年，29岁的德国数学家康托尔(GeorgCant

5、or)在“数学杂志”发表了关于无穷集合论的第一篇革命性文章，从1874年至1884年间，Cantor的系列有关集合的文章，奠定了集合论的基础。集合论康托尔开创的集合论被称为朴素集合论，因为他没有对集合论作完整的形式的刻画，从而导致了理论的不一致(产生了悖论)。在集合论的若干悖论中，最通俗易懂的是Russell(罗素)的理发师悖论：一个乡村理发师，自夸本村无人可与相比，宣称他当然不给自己刮脸的人刮脸，但却给本村所有自己不刮脸的人刮脸。一天他发生了疑问，他是否应当给自己刮脸。集合不仅可以用来表示数及其运算，更可以用于非数值信息的表示和处理，如数据的增加、

6、删除、修改、排序，以及数据间关系的描述，有些很难用传统的数值计算来处理，但可以用集合运算来处理。因此，集合论在程序语言、数据结构、编译原理、数据库与知识库、形式语言和人工智能等领域中都得到了广泛的应用，并且还得到了发展，如Zadeh(扎德)的模糊集理论和Pawlak的粗糙集理论。图论是离散数学的重要组成部分，是近代应用数学的重要分支。1736年是图论历史元年，因为在这一年瑞士数学家欧拉(Euler)发表了图论的首篇论文——《哥尼斯堡七桥问题无解》，所以人们普遍认为欧拉是图论的创始人。1936年，匈牙利数学家寇尼格（Konig）出版了图论的第一部专著《

7、有限图与无限图理论》，这是图论发展史上的重要的里程碑，它标志着图论将进入突飞猛进发展的新阶段。计算机科学的发展为图论的发展提供了计算工具。现代科学技术的发展需要借助图论来描述和解决各类课题中的各种关系，从而推动科学技术不断地攀登新的高峰。作为描述事务之间关系的手段或称工具，图论在许多领域，诸如，计算机科学、物理学、化学、运筹学、信息论、控制论、网络通讯、社会科学以及经济管理、军事、国防、工农业生产等方面都得到广泛的应用，也正是因为在众多方面的应用中，图论自身才得到了非常迅速的发展。图论数理逻辑简介通常认为数理逻辑是由莱布尼兹(Leibniz)创立的。

8、数理逻辑的内容包括：证明论、模型论、递归论、公理化集合论。数理逻辑的应用在形式语义学、程序设计方法学和软件