《离散数学前言》PPT课件.ppt

《《离散数学前言》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《离散数学前言》PPT课件.ppt（21页珍藏版）》请在三一办公上搜索。

1、离 散 数 学Discrete Mathematics,陕西科技大学镐学院,2013年9月,联系方法:,教学要求:,1.准备作业本（32开）：要求作业写清日期并且不抄题做解答。2.课堂上带好练习纸，做好课堂练习。3.做好复习、预习。4.做好出勤。5.课程成绩=作业成绩+考试成绩+出勤成绩,一、课程简介1.离散数学课程设置：计算机专业核心课程 信息类专业必修课程 其它类专业的重要选修课程,2.离散数学的后继课程：数据结构、编译技术、算法分析与设计、人工智能、数据库、,3.离散数学课程的学习方法:强调：逻辑性、抽象性；注重：概念、方法与应用,教学内容：数理逻辑（Mathematics Logic)

2、集合论(Sets)代数系统（Algbra Structure)图论（Graph Theory),教学目的：通过该课程的学习，培养和锻炼抽象思维和缜密概括的能力，为专业基础课和专业课的学习打下坚实的理论基础。总学时：80学时二、适用范围、对象本课程教学大纲适用于以下专业：软件工程本科；测绘工程本科；地理信息系统本科；4 遥感工程本科,三、教材及主要参考书教材：屈婉玲、耿素云、张立昂编著，离散数学（普通高等教育“十一五”国家级规划教材），高等教育出版社，2008年3月参考书：屈婉玲、耿素云、张立昂编著，离散数学（21世纪大学本科计算机专业系列教材），清华大学出版社，2005年6月第1版左孝凌等编著

3、，离散数学，上海科学技术出版社，1982年9月 王元元，张桂芸编著，离散数学导论，科学出版社，2002年2月美Richard Johnsonbaugh 著，王孝喜等译，离散数学，第5版，电子工业出版社 美Kenneth H,Rosen 著，袁崇义，屈婉玲等译，离散数学及其应用，第5版，机械工业出版社四、执行时间软件工程专业、地理信息系统专业2008及以后各年级学生,五、学习要领概念（正确）：必须掌握好离散数学中大量的概念 判断（准确）：根据概念对事物的属性进行判断 推理（可靠）：根据多个判断推出一个新的判断 六、离散数学与计算机的关系 第一部分 数理逻辑 计算机是数理逻辑和电子学相结合的产物,

4、第二部分 集合论 集合：一种重要的数据结构 关系：关系数据库的理论基础 函数：所有计算机语言中不可缺少的一部分第三部分 代数系统 计算机编码和纠错码理论 数字逻辑设计基础 计算机使用的各种运算第四部分 图论 数据结构、操作系统、编译原理、计算机网络原理的基础 第五部分 概率论,数理逻辑简介,逻辑学是一门研究思维形式及思维规律的科学，也就是研究推理过程的规律的科学。逻辑规律就是客观事物在人的主观意识中的反映。逻辑学分为辩证逻辑与形式逻辑两种，辩证逻辑是以辩证法认识论的世界观为基础的逻辑学，形式逻辑主要是对思维的形式结构和规律进行研究的类似于语法的一门工具性学科。思维的形式结构包括了概念、判断和推

5、理之间的结构和联系，其中概念是思维的基本单位，通过概念对事物是否具有某种属性进行肯定或否定的回答，这就是判断；由一个或几个判断推出另一判断的思维形式，就是推理。用数学方法来研究推理的规律称为数理逻辑。这里所指的数学方法，就是引进一套符号体系的方法，在其中表达和研究推理的规律。,数理逻辑简介,通常认为数理逻辑是由莱布尼兹(Leibniz)创立的。数理逻辑的内容包括：证明论、模型论、递归论、公理化集合论。数理逻辑的应用在形式语义学、程序设计方法学和软件工程领域。在逻辑程序设计方面。在数据库理论方面。在程序自动生成、自动转换等的理论和技术研究中。在形式语言理论、自动机理论、可计算理论、计算复杂性理论

6、等方面。在人工智能方面。,数理逻辑简介,一个土耳其商人想找一个十分聪明的助手协助他经商，有两人前来应聘，这个商人为了试试哪个更聪明些，就把两个人带进一间漆黑的屋子里，他打开灯后说：“这张桌子上有五顶帽子，两顶是红色的，三顶是黑色的，现在，我把灯关掉，而且把帽子摆的位置弄乱，然后我们三个人每人摸一顶帽子戴在自己头上，在我开灯后，请你们尽快说出自己头上戴的帽子是什么颜色的。”说完后，商人将电灯关掉，然后三人都摸了一顶帽子戴在头上，同时商人将余下的两顶帽子藏了起来，接着把灯打开。这时，那两个应试者看到商人头上戴的是一顶红帽子，其中一个人便喊道：“我戴的是黑帽子。”请问这个人说得对吗？他是怎么推导出来

7、的呢？,数理逻辑简介,前提,结论,推理（规则）,数理逻辑的知识体系,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世纪数学中最为深刻的活动，是关于数学基础的探讨。这不仅涉及到数学的本性，也涉及到演绎数学的正确性。数学中若干悖论的发现，引发了数学史上的第三次危机，这种悖论在集合论中尤为突出。集合论最初是一门研究数学基础的学科

8、，它从一个比“数”更简单的概念-集合出发，定义数及其运算，进而发展到整个数学领域，在这方面它取得了极大的成功。集合论的起源可以追溯到19世纪末期。1874年，29岁的德国数学家康托尔(Georg Cantor)在“数学杂志”发表了关于无穷集合论的第一篇革命性文章，从1874年至1884年间，Cantor的系列有关集合的文章，奠定了集合论的基础。,集合论概述,康托尔开创的集合论被称为朴素集合论，因为他没有对集合论作完整的形式的刻画，从而导致了理论的不一致(产生了悖论)。在集合论的若干悖论中，最通俗易懂的是Russell(罗素)的理发师悖论：一个乡村理发师，自夸本村无人可与相比，宣称他当然不给自己

9、刮脸的人刮脸，但却给本村所有自己不刮脸的人刮脸。一天他发生了疑问，他是否应当给自己刮脸。,集合论概述,集合不仅可以用来表示数即其运算，更可以用于非数值信息的表示和处理，如数据的增加、删除、修改、排序，以及数据间关系的描述，有些很难用传统的数值计算来处理，但可以用集合运算来处理。因此，集合论在程序语言、数据结构、编译原理、数据库与知识库、形式语言和人工智能等领域中都得到了广泛的应用，并且还得到了发展，如Zadeh(扎德)的模糊集理论和Pawlak的粗糙集理论。,代数系统,近世代数，是关于运算的学说，是关于运算规则的学说，但它不把自己局限在研究数的运算性质上，而是企图研究一般性元素的运算性质。.K

10、lein数学之所以重要，其中心原因在于它所提供的数学系统的丰富多彩；此外的原因是，数学给出了一个系统，以便于使用这些模型对物理现实和技术领域提出问题，回答问题，并且也就探索了模型的行为。代数系统-具有运算的集合-是抽象代数研究的主要对象。,代数结构的知识体系,半群与群,半群,独异点,群,交换半群,交换独异点,Abel群,有限群,循环群,n元置换群,Klein群,图论,图论是离散数学的重要组成部分，是近代应用数学的重要分支。1736年是图论历史元年，因为在这一年瑞士数学家欧拉(Euler)发表了图论的首篇论文哥尼斯堡七桥问题无解，所以人们普遍认为欧拉是图论的创始人。1936年，匈牙利数学家寇尼格（Konig）出版了图论的第一部专著有限图与无限图理论，这是图论发展史上的重要的里程碑，它标志着图论将进入突飞猛进发展的新阶段。计算机科学的发展为图论的发展提供了计算工具。现代科学技术的发展需要借助图论来描述和解决各类课题中的各种关系，从而推动科学技术不断地攀登新的高峰。作为描述事务之间关系的手段或称工具，图论在许多领域，诸如，计算机科学、物理学、化学、运筹学、信息论、控制论、网络通讯、社会科学以及经济管理、军事、国防、工农业生产等方面都得到广泛的应用，也正是因为在众多方面的应用中，图论自身才得到了非常迅速的发展。,