离散数学及应用
2010-7
中国电力出版社
郭键 等编著
307
离散数学是计算机及相关专业的一门重要核心、基础课，是计算机科学与技术的基础理论之一。它隶属于现代数学的范畴，研究的对象是离散数据结构及相互关系。它在数据结构、数据库、程序设计、形式语言、自动机、人工智能、操作系统、编译原理、语言学等领域都有着重要的应用。通过离散数学课程的学习，可以培养学生的数学抽象思维和严格的推理能力，使学生掌握信息技术领域中的一些基本数学工具和方法，为将来从事软、硬件开发打下坚实基础。 全书共分为5篇16章，内容安排如下。 第1篇为集合论部分，包括第1～3章。第1章为集合的总体概述，介绍了有关集合的运算、有限集合的计算以及集合的各种运算定律；第2章为关系，由笛卡尔积引入关系的概念，介绍了关系的表示方法、关系的各种运算、关系的性质、关系的闭包、等价关系、相容关系以及偏序关系等；第3章为函数，主要介绍了函数的基本概念、一些特殊的函数、函数的运算以及集合的基数等。 第2篇为图论部分，包括第4～7章。第4章介绍了图的基本概念以及图的操作和运算；第5章介绍了几类特殊的图形，主要有欧拉图、汉密尔顿图、二部图、平面图等；第6章和第7章分别介绍了无向树和有向树，主要有无向树和有向树涉及的基本概念、最小生成树、最优二叉树及其遍历等。第3篇为数理逻辑部分，包括第8和第9章。第8章介绍了命题逻辑，包括命题、命题公式与赋值、命题公式类型、命题的等价、命题的范式以及在命题逻辑中的推理理论；第9章为谓词逻辑部分，包括谓词公式与解释、谓词公式类型、谓词公式的等价、谓词公式的范式以及在谓词逻辑中的推理理论等。 第4篇为代数结构部分，包括第10～12章。第10章介绍了群的基本定义、交换群、置换群、循环群、子群、商群等，并介绍了群的同态与同构等；第11章介绍了环和理想，包括环的基本概念、多项式环、欧几里德环、商环等：第12章介绍了域，包括扩域、代数元、超越元以及有限域、本原元、本原多项式等。 第5篇为离散数学的应用部分，包括第13～16章。第13章介绍了数理逻辑的应用，介绍了命题逻辑在简化电路、简化计算机程序、简化逻辑网络图以及在继电器控制开关中的应用，并介绍了谓词逻辑在人工智能领域、在逻辑程序设计语言等方面的应用；第14章介绍了关系的应用，主要有关系及运算在关系型数据库中的应用、关系的闭包、等价关系、序关系等的应用实例；第15章介绍了图论的应用，主要包括平面图与着色的应用、图的通路的应用、欧拉图和汉密尔顿图的应用、树的应用以及网络流等问题；第16章介绍了文法、有限自动机、语言等内容。 全书内容深入浅出，图文并茂，各篇章之间既有联系，又相对独立，读者可根据需要选择阅读。每章后面都附有作者精心挑选的思考题，可帮助读者进一步巩固所学的知识。 本书由北京物资学院信息学院郭键、李俊韬、谭加博编写。
本书共分为5篇：集合论、图论、数理逻辑、代数结构及综合应用。集合论部分介绍了集合、关系、函数等；图论部分介绍了图的基本概念及特殊图；数理逻辑包括命题逻辑和谓词逻辑；代数系统介绍了群、环、域等；最后详细介绍了这四部分在计算机中的实际应用。本书在编写过程中，尽量将离散数学的各个部分有机地结合起来，力求条理清楚、深入浅出，通过该课程的学习，可使读者掌握必备的离散数学知识，并提高其利用离散数学知识分析和解决实际问题的能力。 本书可作为高等院校计算机科学技术等相关专业的本科生和研究生的教学用书，也可作为计算机工程技术和研究人员学习离散数学的参考用书。
前言第1篇 集合论 第1章 集合 1.1 集合的基本概念及性质 1.1.1 集合的基本概念 1.1.2 集合的表示形式 1.1.3 集合的基本性质 1.1.4 集合之间的关系 1.2 集合的运算 1.2.1 集合的交运算 1.2.2 集合的并运算 1.2.3 集合的补运算 1.2.4 集合的对称差运算 1.2.5 集合的广义交和广义并运算 1.3 有限集合的计数 1.3.1 鸽巢原理 1.3.2 包容排斥原理 1.4 集合的运算定律 思考与练习题 第2章 关系 2.1 笛卡尔积概念 2.1.1 序偶 2.1.2 笛卡尔积 2.2 二元关系及其表示方法 2.2.1 二元关系的定义 2.2.2 二元关系的表示方法 2.3 二元关系的运算 2.3.1 关系的基本运算 2.3.2 关系的复合运算 2.3.3 关系的幂运算 2.3.4 关系的逆运算 2.3.5 关系的限制和像 2.4 二元关系的性质 2.4.1 自反性与反自反性 2.4.2 对称性、反对称性、非对称性 2.4.3 传递性 2.4.4 关系性质的保持性 2.5 二元关系的闭包 2.5.1 关系闭包定义 2.5.2 关系闭包涉及的定理 2.5.3 关系闭包的求解方法总结 2.6 等价关系 2.6.1 等价关系定义 2.6.2 等价类与商集 2.6.3 等价类与划分 2.7 相容关系与覆盖 2.7.1 相容关系与覆盖的定义 2.7.2 最大相容类 2.8 序关系 2.8.1 偏序关系 2.8.2 全序关系与良序关系 2.8.3 拟序关系 思考与练习题 第3章 函数 3.1 函数的基本概念 3.1.1 函数的引入 3.1.2 函数的定义及特点 3.2 特殊函数 3.2.1 单射、满射与双射 3.2.2 常用函数 3.3 函数的运算 3.3.1 函数的复合运算 3.3.2 函数的逆运算 3.4 集合的基数 3.4.1 基数的定义 3.4.2 丁数集的定义及性质 3.4.3 集合基数的比较 思考与练习题第2篇 图论 第4章 图的基本概念 第5章 特殊图 第6章 无向树 第7章 有向树第3篇 数理逻辑 第8章 命题逻辑 第9章 谓词逻辑第4篇 代数结构 第10章 群 第11章 环与理想 第12章 域第5篇 综合应用 第13章 数理逻辑的应用实例 第14章 关系的应用实例 第15章 图论的应用实例 第16章 有限自动机与语言参考文献
在有限集A中，A的基数lAl就是集合A中元素的个数。在计算和证明中，常常会遇到从有限集A中取若干元素的问题，或者给定有限集A与B，求AUB和AnB等。 1.3.1 鸽巢原理 有一种抢位子的游戏，当座位少人多时，就会发生几个人同时挤在同一个位子上的情况。同样的道理，只要一年里出生的人数超过366个，那么必可得出这样的结论：至少有两人是同年同月同日出生的。 鸽巢原理（Pigeonhole Principle，又称抽屉原理、鸽舍原理）：若有n+1只鸽子住进n个鸽巢，则至少有1个鸽巢住进2只鸽子。 证明（反证法）假设每个鸽巢至多住进1只鸽子，则n个鸽巢至多住进n只鸽子，这与有，z+1只鸽子矛盾。故至少有1只鸽巢至少住进2只鸽子。 【例1-9】月黑风高穿袜子。某晚你房间的电灯忽然间坏了，伸手不见五指，而你又要出去，于是就摸床底下的袜子。你有三双分别为红、白、蓝颜色的袜子，可是你平时做事随便，一脱袜就乱扔，在黑暗中不能知道哪一双是颜色相同的。你想拿最少数目的袜子出去，在外面借街灯配成同颜色的一双。问需要拿的最少数目应该是多少？ 解如果懂得鸽巢原理，就会知道只需拿出去四只袜子就行了。因为如果我们将这三双袜子分别放人三个盒子中，则要抽出4只袜子，至少有一个盒子的袜子全被拿出来，则这个盒子的袜子必然是同色的，可以拿来穿。 1.3.2 包容排斥原理 我们可以利用有限集合中元素的个数来进行计数。在做这类计数运算时，被包含的公共子集常被重复计数，需要排除掉这部分的重复计数，而在排除时，由于包含关系又发生重复排除，需要再加回被重复排除的部分，如此容、斥、容、斥……，直至不再容或斥。这就是计数中的包容排斥原理（又称容斥原理）。
很好，非常好的，质量很好很好，非常好的，质量很好很好，非常好的，质量很好很好，非常好的，质量很好 很好，非常好的，质量很好很好，非常好的书，质量很好很好，非常好的，质量很好很好，非常好的，质量很好 很好，非常好的，质量很好很好，非常好的，质量很好很好，非常好的，质量很好很好，非常好的，质量很好 很好，非常好的，质量很好很好，非常好的书，质量很好很好，非常好的，质量很好很好，非常好的，质量很好