离散数学基础教程

出版时间：2009-7  出版社：机械工业出版社  作者：徐洁磐  页数：229  

前言

离散数学教学改革探索的体会.离散数学是数学的一大门类,由于它的离散性,使得它在计算机及信息技术应用领域有重要.作用,因此离散数学作为一门课程已在该领域相关专业大量开设,自20世纪70年代开始至今已有30余年历史.随着科学技术不断发展.改革开放不断深入,我们对离散数学课程的改革也不断有新的认识.特别是近年来的变化,促使我们对离散数学课程的教学改革产生一个新的认识,从而能做出新的调整.离散数学课程的变化 1.离散数学课程教学环境的变化近年来离散数学教学环境产生了重大的变化,这主要表现为： (1)离散数学课程设置由计算机专业扩展至信息技术领域的多个专业. (2)离散数学课程内容由少量数学分支领域(数理逻辑.集合论.代数系统及图论等)扩展至多种数学分支领域(如组合数学.数论.有限自动机等). (3)离散数学课程教学课时数出现了由多到少的倾向,据2008年的不完全统计,离散数学课时数由以前的平均90学时下降至平均78学时. (4)由于高等教育由精英化逐渐走向大众化,因此离散数学参学学生人数越来越多但起点逐年降低.以上四点可归结成下面的一句话：“离散数学课程参学人数及专业数越来越多,要求越来越高,但教学课时数越来越少,参学学生起点越来越低.这就形成了当前离散数学教学中的巨大的矛盾与差异,而设法解决这些问题就成为离散数学课程教学改革的当务之急. 2.离散数学课程教学对象的变化由离散数学课程教学环境的变化而引起了教学对象的变化.从广度看,离散数学课程的教学对象已由仅对计算机相关专业学生而扩充到计算机及信息技术领域的各专业(如自动化.通信.电子信息安全等专业)学生.而从所学层次看,离散数学课程的教学对象又可分为研究型本科.工程型本科.应用型本科以及高职高专等多个层次.离散数学课程教学对象的变化反映了对离散数学课程需求的变化是引发课程改革的原进一步的理论需求(如论文撰写及理论研究)提供基础. 3.培养学生离散建模能力,为学生以后在工作中用离散数学作工具应用于本专业的研究与开发提供相应能力.根据以上的目标,离散数学目前已成为计算机及IT相关专业的必修课程及核心课程.根据以上三点变化,我们必须对离散数学课程改革提出新的思想与方案,即下面所介绍的一.二.三原则.离散数学课程教学改革的一,二,三原则 1.离散数学课程的两层结构体系由于离散数学参学人群的专业不一.需求不一以及开设课时不一,因此在教学中存在一定差异,特别是在教学内容要求上并不一致,为此需对其教学内容作分析：首先,离散数学课程有一个基本的.共同的内容要求.它们是离散数学的基本的.必需的部分.一般认为,它们是集合论.代数系统.图论及数理逻辑.(详细原因可参见本书第一篇.)其次,离散数学课程内容允许有差异性,即允许存在不同要求的内容.它们是离散数学的可选择部分,包括组合数学.数论.离散概率.有限自动机理论.递归函数论等.离散数学的必需部分与可选部分构成了一个完整的课程体系,即两层结构体系.它既保证了离散数学的基本要求,同时也满足离散数学的不同要求.根据不同专业与学生的不同层次,可以选取不同的内容以满足不同的要求2.离散数学课程的三种分类教学方法在离散数学课程中的教学内容涉及多个不同方面,它包括对以上三个离散数学教学的不同方面,建议采用三级分类制(它类似于高等数学的四级分类制) (1)分类1：对离散数学分类1,可采用内容深.范围宽但释义少,它的适合范围以研究型学校为主 (2)分类2：对离散数学分类2,可采用内容.范围及释义均适中为宜,它的适合范围以工程型学校为主 (3)分类3：对离散数学分类3,可采用内容浅.范围狭但释义多,它的适合范围以应用型学校为主.三级分类制有助于适应不同专业.不同层次.不同需求以及不同学生的要求,增强离散数学课程教学的灵活性与适应性,避免一刀切的现象. 3.离散数学课程教学的一项新任务——离散建模离散数学是一门工具,它为计算机及汀专业日后研究与开发提供理论支撑.计算机及信息技术领域各专业学生对它的学习与数学专业学生有不同之处,它不是以研究与发展数学本身为目的,而是以研究与开发计算机及IT领域的应用为目的,因此在离散数学课程教学中必须增加离散建模内容,这是科学技术发展对离散数学教学提出的新任务.离散建模一般包括在研究中建立理论模型以及在开发应用中建立应用模型,因此这种建模对三种分类方法都是必需的.上面所给出的一(一项新任务：离散建模).二(二层结构体系).三(三种分类方法)原则为离散数学课程教学改革提供了新的方法与手段.它可以改变目前离散数学课程教学中死板.僵化的格局,促进离散数学课程教学中的多样化与灵活性,以期回归离散数学教学需求的真实面目.离散数学教材的编写 1.教材定位以上面所述的离散数学课程教学改革的一.二.三原则为指导,在离散数学教材的建设方面,也应注重多样化和多品种,以适应不同层次及不同分类的需要,而在多种需要面前,目前最为迫切建设的是以基本必需部分为主的分类3型教材,这主要是由于修读此类的学生人数比例较大,约占所学人数2／3左右,而目前市场上此类教材所占比例又很少.因此,本教材编写定位即以分类3为准.其内容与范围以少而精为原则,而释义则以讲透.讲深为原则.适用对象以应用型本科学生为主. 2.教材编写内容编写内容包括必需的四个部分：集合论.代数系统.图论及数理逻辑,还包括离散建模. 3.教材编写的基本原则在本教材的具体编写中,则坚持以下五项基本原则： (1)内容少而精：在内容选材上坚持少而精,选取具有代表性的核心内容,通过精讲精练达,到单一反三的效果. (2)释义清楚：教材是面向学生的,为使学生接受离散数学抽象思维与离散思维内容.培养相应能力,在教材中必须对离散数学的基本概念与性质作详细的释义,即不但要了解数学的抽象表示,更要注重其形式语义,使学生能掌握它们的精髓并能灵活应用. (3)学以致用：在本教材中增设离散建模内容,介绍离散建模的一般原理,并精选五个著名实例,通过此部分内容学习使学生能初步掌握运用离散数学作工具来解决实际问题的能力. (4)篇幅短小：在本教材中由于内容精练且减少了过于复杂.繁琐的证明环节,因而做到了篇幅短小,一般适合70学时左右的教学需要. (5)适合教学：本教材配有大量习题及思考题,同时每章都有学习小结.每篇都有学习总结,全书还配有电子教案供教师教学之用.同时,本书还会配套相关辅助教材. 4.教材特色 (1)本教材在国内首先系统引入并介绍了离散建模,将离散数学与计算机以及IT领域应用相结合,从而使离散数学这门课程真正融入计算机及信息技术领域中. (2)本教材在突出重点.压缩内容上也取得突破,达到了少而精的目的,同时也能充分适应国内课时减少的需要. (3)本教材的四个核心内容(集合论.代数系统.图论及数理逻辑)坚持其独立性与关联性.所谓独立性,即每部分内容具有各自特色,它们之间不存在依赖关系,每个部分内容不以其他部分内容为先导,所谓关联性,即要强调各部分内容间的共性.教材中的独立性与关联性两者不可缺一,它们的有机结合构成了教材的完整与统一的体系. 5.教材组织结构本教材共五篇12章,内容顺序包括绪言.集合论(共三章).代数系统(共三聿).图论(共二章).数理逻辑(共二章)以及离散建模(共二章)等,其重点为集合论与数理逻辑,书中标有“*”的章节不是必需的,仅供参考选择之用.致谢最后,在本书付梓之际,感谢南京航天航空大学吕义忠教授为审阅本书所作出的辛勤劳动,同时感谢南京大学计算机系及计算机软件新技术国家重点实验室的费翔林教授.徐永森教授.朱怀宏副教授及柏文阳副教授为本书所提供的支持.由于作者水平有限,书中难免存在不足之处,恳请读者不吝赐教. ...徐洁磐南京大学计算机科学与技术系南京大学计算机软件新技术国家重点实验室 2009年3月

内容概要

本书共五篇12章，将离散数学按总论、主要内容及应用的顺序进行讲解，其中主要内容部分讲述离散数学中的四个核心内容（集合论、代数系统、图论与数理逻辑），应用部分在国内首先系统引入和介绍了离散建模的相关内容，并将离散数学与计算机以及IT领域应用相结合，从而使离散数学这门课程真正融入计算机及信息技术领域中。　　全书在内容选材上上坚持少而精，选取具有代表性的核心内容，通过精讲精练达到举一反三的效果；释义则以讲透、讲深为原则，不但要使学生了解数学的抽象表示，更要注重其形式语义，掌握它们的精髓并能灵活应用；增设离散建模内容，介绍离散建模的一般原理，并精选五个著名实例，使学生能初步掌握运用离散数学解决实际问题的能力。　　本书可作为普通高等院校计算机及相关专业的本科离散数学课程教材，也可供计算机应用开发人员参考。

作者简介

徐洁磐，南京大学计算机科学与技术系教授，长期从事计算机理论和离散数学的教学与研究，曾任中国离散数学学会理事长，主持制订我国第一部离散数学教学大纲，编写了我国第一部原创离散数学教材《离散数学导论》（国家级规划教材），还著有《离散数学及其在计算机科学中的应用

书籍目录

序绪言第一篇　集合论　第1章　集合论基础 　　1.1　集合的基本概念 　　1.2　集合的表示方法 　　　1.2.1　枚举法 　　　1.2.2　特性刻划法 　　1.3　集合概念间的关系 　　　1.3.1　集合与元素间的关系 　　　1.3.2　集合与集合间的关系 　　　1.3.3　集合相交中的两个特殊关系 　　1.4　集合概念的基本性质 　　1.5　集合运算 　　1.6　集合运算的应用 　　1.7　扩充的集合运算之一——差运算与对称差运算 　　1.8　扩充的集合运算之二——幂运算 　　1.9　扩充的集合运算之三——笛卡儿乘 　　　1.9.1　序偶 　　　1.9.2　笛卡儿乘 　　　1.9.3　n元有序组与n阶笛卡儿乘积　　本章小结　　习题一　第2章　关系 　　2.1　关系的基本概念 　　2.2　关系的表示 　　　2.2.1　枚举法 　　　2.2.2　特性刻划法 　　　2.2.3　矩阵表示法 　　　2.2.4　图示法　　2.3　关系的性质 　　2.4　关系运算 　　　2.4.1　关系的并、交、补运算 　　　2.4.2　关系的复合运算与逆运算 　　　2.4.3　关系上的闭包运算 　　2.5　两种常用的关系 　　　2.5.1　次序关系 　　　2.5.2　等价关系 　　2.6　n元关系　　本章小结　　习题二　第3章　函数与无限集 　　3.1　函数的基本概念 　　3.2　函数的表示 　　3.3　函数的分类 　　3.4　函数运算 　　　3.4.1　函数的复合运算 　　　3.4.2　函数的逆运算 　　3.5　几种常用函数 　　3.6　多元函数 　　3.7　有限集与无限集　　本章小结　　习题三　第一篇总结　第一篇附录第二篇　代数系统　第4章　代数系统概论 　　4.1　代数系统介绍 　　4.2　代数运算中的常见性质 　　4.3　代数系统的同态与同构 　　4.4　代数系统的分类　　本章小结　　习题四　第5章　群论 　　5.1　半群 　　5.2　群　　　5.2.1　群及其性质 　　　5.2.2　群同态与变换群 　　　5.2.3　有限群 　　　5.2.4　循环群 　　　5.2.5　子群与正规子群　　本章小结　　习题五　第6章　环论与格论 第三篇　图论　第7章　图论原理　第8章　树 第四篇　数理逻辑　第9章　命题逻辑 　第10章　谓词逻辑 第五篇　离散建模　第11章　离散建模概念与方法 　第12章　离散建模应用实例附录　中英文名词对照表参考文献

章节摘录

插图：2.5两种常用的关系在关系中有两种关系是我们经常需要用到的，它们是次序关系与等价关系，它们都是满足某些性质（自反性、对称性及传递性）的特殊关系。2.5.1  次序关系“次序”是我们经常碰到的一种关系，在日常生活中所遇到的“次序”关系是很多的，如体育竞赛中的排名、姓氏笔划排序、字典次序排序以及多项指标综合排序等。在这节中我们将这些次序关系分为三种类型并用关系理论加以定义与研究，它们是：·偏序关系·线性次序关系·拟序关系在次序关系中我们将用关系的三个性质去刻划。一般讲，次序关系必满足反对称性与传递性。这两个性质是构成次序关系的必要条件。以此为基本准则再加上满足自反性的条件将次序关系分为两种：·偏序关系——满足自反性的次序关系，即满足自反性、反对称性及传递性。·拟序关系——满足反自反性的次序关系，即满足反自反性、反对称性及传递性。进一步，我们可对偏序关系作分解，在偏序关系中有两种排列次序，一种是所有元素均能顺序排序而另一种则不能。我们将重点讨论前面的一种，它称为线性次序关系或全序关系。·线性次序关系——所有元素均能顺序排列的偏序关系。下面我们分别讨论这三种关系。

编辑推荐

《离散数学基础教程》是由机械工业出版社出版的。