离散数学教程
2009-3
东北大学出版社有限公司
孙晶
162
离散数学作为计算机科学的基础学科的一个标志，是现代数学中的一门重要学科，主要以研究离散量为主，是研究离散量的结构及相互关系的学科。随着计算机的发明和发展，离散数学变得越来越重要，它在可计算性与计算复杂性理论、算法与数据结构、程序设计语言、数值与符号计算、操作系统、软件工程、数据库与信息检索系统、人工智能与机器人、网络、计算机图形学以及人机通信、管理、金融、工程等各个领域，都有着广泛的应用。 作为一门重要的专业基础课，通过离散数学的教学，不仅能为学生的专业课学习及将来所从事的软、硬件开发和应用研究打下坚实的基础，同时也能培养他们抽象思维和严格的逻辑推理能力。 本书包括集合论、数理逻辑、代数系统和图论四部分内容。 集合论是数学的基础，现代集合论以公理为基础，讨论集合的理论和性质。主要介绍集合的公理体系、关系的概念、序关系、函数等内容。 数理逻辑是逻辑学的一部分，它是用数学的方法研究数学推理和数学性质以及数学基础，也就是引进一些符号，用符号的方法来演绎推理规律，所以也称为符号逻辑。 代数系统也称代数结构或近世代数，是代数学中研究的重要对象，是抽象的代数学，所以也称为抽象代数。它是对“不相关的代数”抽象出共同的性质，即它们是由一些元素组成的集合，它们满足一个或几个运算，运算的结果仍然在此集合中。在研究时，不考虑元素具体是什么，只考虑元素和结构的性质。 图论从18世纪产生到现在，一直被其他应用科学所重视，有很多脍炙人口的典型数学模型和数学应用。随着计算机的发展，这个学科有了更大的应用空间。
离散数学是计算机科学相关专业重要的专业基础课程，是计算机专业，信息相关专业，计算机系统软、硬件开发专业以及数学与应用数学专业，数学建模。工程，管理，金融等专业不可缺少的基础知识。本书适合高等院校相关各专业作为离散数学课程的基本教材和参考书。 全书共分四章。分别介绍集合论、数理逻辑、代数系统和图论四部分内容，并附有教学大纲和模拟试题。本书内容叙述严谨，推演详尽，深入浅出，通俗易懂，大部分概念都用详细的实例说明并配有习题。
第1章 集合论 1.1 集合的概念与运算 1.1.1 集合的概念和表示法 1.1.2 集合论的公理系统 1.1.3 集合相等与包含 1.1.4 空集与基础集 1.1.5 无限集与幂集 1.1.6 集合的并集 1.1.7 集合的交集 1.1.8 集合的补集 1.1.9 集合的对称差集 1.2 关系的概念 1.2.1 笛卡儿积 1.2.2 关系 1.2.3 恒同关系 1.2.4 关系图与关系矩阵 1.3 关系的性质与运算 1.3.1 关系的性质 1.3.2 关系的运算 1.3.3 复合关系 1.3.4 逆关系 1.3.5 关系的相关运算 1.4 关系的闭包 1.4.1 闭包的概念 1.4.2 闭包的计算 1.4.3 传递闭包的warshau计算方法 1.5 等价关系 1.5.1 集合的覆盖与划分 1.5.2 等价关系 1.5.3 相容关系 1.6 序关系 1.6.1 偏序关系 1.6.2 盖住关系 1.6.3 哈斯图 1.6.4 最（极）大（小）元 1.6.5 上（下）（确）界 1.6.6 全序集与良序集 1.7 函数 1.7.1 函数的概念 1.7.2 特殊的函数 1.7.3 逆函数 1.7.4 复合函数 1.8 基数 1.8.1 基数的概念 1.8.2 可数集 集合论习题第2章 数理逻辑 2.1 命题与联结词 2.1.1 命题的概念 2.1.2 命题符号 2.1.3 复合命题 2.1.4 常用的五个命题联结词 2.2 命题公式与真值表 2.2.1 命题变元 2.2.2 命题公式 2.2.3 真值表 2.3 等价及等价公式 2.3.1 等价或逻辑相等 2.3.2 等价公式表 2.4 重言式与蕴含式 2.4.1 重言式 2.4.2 蕴含 2.4.3 蕴含式的证明方法 2.4.4 蕴含公式表 2.4.5 其他联结词 2.5 范式 2.5.1 合取范式与析取范式 2.5.2 小项与主析取范式 2.5.3 大项与主合取范式 2.5.4 用真值表表示主范式 2.6 推理理论 2.6.1 推理规则 2.6.2 直接证法 2.6.3 反证法 2.6.4 CP规则法 2.7 谓词与谓词公式 2.7.1 谓词的概念 2.7.2 命题函数与论域 ……第3章 代数系统第4章 图论附录参考文献
第1章 集合论 集合论的创立到公理化系统集合论的过程，使集合论在数学发展史中产生了巨大的作用。集合论的产生与完备过程，集合论的思维方式对传统思维模式的超越，集合论中悖论的出现及解决，这些开辟了现代数学发展的道路，成为现代数学大厦的基础。 我们原本生活在一个无穷的世界里，但我们的认识往往要从有限开始。无穷的世界里有着我们在有限的思维方式下认为不可思议的问题。例如：“从地球到月球的线段和一厘米长线段上的点一样多。”您会相信吗？发现它并揭示其中奥秘的是20世纪初伟大的数学家、集合论的创始人——奥格尔·康托尔。他的理论把人们从有限带进了无穷，把近代数学推向了现代数学。到了19世纪末，德国数学家康托尔（1845—1909）才开始揭示其中的奥秘：自然数的集合与正整数的集合一样大，而实数的集合不与正整数的集合一样大。在1874年至1909年的30多年间，他系统地建立了关于无穷集合的理论，创立了超穷序数、基数新概念，并把近代的超穷基数赋予可数集，给连续系统更高的超穷数，还建立了一整套有关的基本定理。1901年勒贝格以测度论充实了集合论，康托尔的集合论到了20世纪初为人们所接受。 集合论中的矛盾由数学家借一个乡村理发师的典故揭示出来。一个乡村只有一名理发师，乡村规定称：“凡是自己不能给自己理发的人，必须由理发师来理。”但问题出来了，理发师的头发由谁来理？要是他自己不给自己理发，那么按照乡村规定，他必须到理发师那里让理发师给他理发，同样因为他自己就是理发师；要是他自己给自己理发，那么按照乡村规定，他就不应该到理发师处理发，而他自己就是理发师；于是这个理发师陷入了逻辑的矛盾中。这个逻辑矛盾涉及了集合的概念、元素、属于，在当时产生了极大的震动。这就是著名的罗素悖论。 在集合论产生与发展的整个过程中，许多数学家与哲学家从事了集合论的研究工作，并取得了令人振奋的成就，策墨罗和弗郎克尔通过对康托尔朴素集合论的研究，提出了zF公理系统，把集合论建立在一系列公理系统上，使朴素集合论完善为公理化集合论。它克服了康托尔朴素集合论引起的一些矛盾，推动了集合论的发展。后来在1937年至1954年间，建立了集合论的另一个公理系统，简称VNB系统。在1940年的专著《选择公理、广义连续系统假设与集合公理的协调性》中使用了VNB系统，将集合建立在一系列公理系统上，使朴素集合论发展为公理的集合论，克服了康托尔在集合论上引起的矛盾，推动了集合论的发展。
《离散数学教程》包括集合论、数理逻辑、代数系统和图论四部分内容。集合论是数学的基础，现代集合论以公理为基础，讨论集合的理论和性质。主要介绍集合的公理体系、关系的概念、序关系、函数等内容。数理逻辑是逻辑学的一部分，它是用数学的方法研究数学推理和数学性质以及数学基础，也就是引进一些符号，用符号的方法来演绎推理规律，所以也称为符号逻辑。
