离散数学(微课版)(第2版)

本书是在国家精品课程、国家精品资源共享课程和国家级一流本科课程“离散数学”的基础上，结合卓越工程师教育培养计划和新工科建设编写而成的。全书共10章，系统介绍了数理逻辑、集合与关系、图论，以及代数系统与布尔代数中的基本概念、算法、定理及其证明方法。本书不仅注重基本概念的描述，还特别注重阐述有关离散数学的证明方法及离散数学问题求解的算法，并且举出大量的应用实例，充分展示了离散数学在软件工程和计算机科学与技术中的基础作用和强大应用。

王庆先 王庆先 电子科技大学信息与软件工程学院教授/博士生导师，电子科技大学计算机应用技术专业博士，先后到美国明尼苏达大学大学、美国罗切斯特大学交流访问。长期从事《离散数学》，《组合数学》，《算法分析与设计》课程的教学。目前主要从事人工智能、大数据应用等方面的研究，在Neurocomputing，Physicas等高水平刊物和国际会议上发表学术论文数十篇，主持和参与多项国家级项目、省部级项目和企业横向合作项目。 至2004年以来，长期从事离散数学课程的教学研究，融合科研成果，利用现代信息技术探索新的教学方法和教学模式，取得了较好的教学研究成果。主持教育部产学研协同育人项目《离散数学在线学习系统》（项目编号：201802111012,2018-2020）1项，作为第二负责人完成教育部《离散数学》精品资源共享课程建设项目（2012-2013），参与完成（排名第二）《离散数学》MOOC建设》（项目编号：201701049023,2017-2019），参与完成（排名第三）教育部《离散数学》国家双语示范课程建设（2008-2012），参与完成（排名第二）《离散数学》省级教学团队项目（2009-2013），参与完成（排名第三）国家级精品课程《离散数学》建设项目（2006-2010），参与编写（工作量1/4）国家“十一五”规划教材《离散数学及应用（2019年第3版，2013年第2版，2007年第1版）》，撰写的教研论文“离散数学课堂签到研究与实践”，“离散数学实时判卷系统”在《大学数学》期刊上发表；自主研发的“离散数学学习系统”目前已在所教学班级试用，取得了较好的效果。

第 1 章 集合论 历史人物 本章思维导图 1.1　集合的基本概念 1.1.1　集合的表示 1.1.2　集合与集合的关系 1.2　几个特殊集合 1.3　集合的运算 1.4　无限集 1.4.1　可数集 1.4.2　不可数集 1.5　集合的应用 1.5.1　集合的计算机表示 1.5.2　计数问题 1.6　习题 第　2 章 命题逻辑 历史人物 本章思维导图 2.1　命题与命题联结词 2.1.1　命题 2.1.2　命题联结词 2.1.3　自然语言的命题符号化 2.2　命题公式、解释与真值表 2.2.1　命题公式 2.2.2　命题公式的解释与真值表 2.2.3　命题公式的基本等价定律 2.3　公式的标准型——范式 2.3.1　命题联结词的完备集 2.3.2　析取范式和合取范式 2.3.3　主合取范式和主析取范式 2.4　命题逻辑的推理理论 2.4.1　推理的基本概念 2.4.2　推理有效性的判别方法 2.5　命题逻辑的应用 2.5.1　命题联结词的应用 2.5.2　命题公式的应用 2.5.3　范式的应用 2.5.4　命题逻辑推理的应用 2.6　习题 第　3 章 谓词逻辑 历史人物 本章思维导图 3.1　自然语言的谓词符号化 3.1.1　谓词 3.1.2　量词 3.2　谓词公式与解释 3.2.1　谓词公式 3.2.2　自由变元和约束变元 3.2.3　谓词公式的解释 3.2.4　谓词公式的基本等价定律 3.3　谓词公式的标准型——前束范式* 3.3.1　前束范式 3.3.2　Skolem 范式 3.4　谓词逻辑的推理理论 3.4.1　推理规则与推理定律 3.4.2　推理有效性的判别方法 3.5　谓词逻辑的应用 3.5.1　谓词符号化的应用 3.5.2　谓词逻辑推理的应用 3.6　习题 第　4 章 二元关系 历史人物 本章思维导图 4.1　二元关系及其表示 4.1.1　序偶和笛卡儿积 4.1.2　关系的定义 4.1.3　关系的表示法 4.2　关系的运算 4.2.1　关系的复合运算 4.2.2　关系的逆运算 4.2.3　关系的幂运算 4.3　关系的性质 4.3.1　关系性质的定义 4.3.2　关系性质的判定定理 4.3.3　关系性质的保守性 4.4　关系的闭包 4.5　关系的应用 4.5.1　二元关系及表示的应用 4.5.2　关系运算的应用 4.6　习题 第　5 章 特殊关系 历史人物 本章思维导图 5.1　相容关系 5.1.1　相容关系的定义 5.1.2　集合的覆盖 5.2　等价关系 5.2.1　等价关系的定义 5.2.2　集合的划分 5.2.3　等价类与商集 5.2.4　等价关系与划分 5.3　次序关系 5.3.1　拟序关系 5.3.2　偏序关系 5.3.3　全序关系 5.3.4　良序关系 5.4　函数 5.4.1　函数的基本概念 5.4.2　函数的运算 5.4.3　置换函数 5.5　特殊关系的应用 5.5.1　等价关系的应用 5.5.2　次序关系的应用 5.5.3　函数的应用 5.5.4　置换函数的应用 5.6　习题 第　6 章 图 历史人物 本章思维导图 6.1　图的基本概念 6.1.1　图的定义 6.1.2　图的表示 6.1.3　图的操作 6.1.4　邻接点与邻接边 6.1.4　图的分类 6.1.5　子图与补图 6.2　握手定理 6.3　图的同构 6.4　通路与回路 6.4.1　通路与回路 6.4.2　无向赋权图的最短通路 6.5　图的连通性 6.5.1　无向图的连通性 6.5.2　有向图的连通性 6.6　图的应用 6.6.1　网络的结构 6.6.2　渡河问题 6.6.3　均分问题 6.7　习题 第　7 章 特殊图 历史人物 思维导图 7.1　树 7.1.1　树的基本概念及性质 7.1.2　生成树及算法 7.2　根树 7.1.3　根树的定义与分类 7.1.4　根树的遍历 7.1.5　最优树与哈夫曼算法 7.2　欧拉图 7.2.1　欧拉图的引入与定义 7.2.2　欧拉图的判定 7.3　哈密顿图 7.3.1　哈密顿图的引入与定义 7.3.2　哈密顿图的判定 7.4　偶图 7.4.1　偶图的定义 7.4.2　偶图的判定 7.4.3　匹配 7.5　平面图 7.5.1　平面图的定义 7.5.2　平面图的简单判定方法——观察法 7.5.3　欧拉公式 7.5.4　库拉托夫斯基定理 7.6　特殊图的应用 7.6.1　无向树的应用 7.6.2　根树的应用 7.6.3　欧拉图的应用 7.6.4　哈密顿图的应用 7.6.5　偶图的应用 7.6.6　平面图的应用 7.7　习题 第　8 章 代数系统 历史人物 本章思维导图 8.1　代数系统 8.1.1　代数运算 8.1.2　代数系统与子代数 8.2　运算律和特殊元 8.2.1　二元运算律 8.2.2　二元运算的特殊元 8.3　同态与同构 8.3.1　同态与同构的定义 8.3.2　同态的性质 8.4　代数系统的应用 8.4.1　代数系统的计算机表示 8.4.2　数据库与关系代数 8.5　习题 第　9 章 群 环 域 历史人物 本章思维导图 9.1　群的基本概念 9.1.1　群的定义 9.1.2　元素的阶 9.1.3　子群 9.1.4　群的同态和同构 9.2　特殊群 9.2.1　循环群 9.2.2　置换群 9.3　陪集与拉格朗日定理 9.3.1　陪集 9.3.2　拉格朗日定理 9.4　正规子群与商群 9.4.1　正规子群 9.4.2　商群 9.5　环和域 9.5.1　环和域的定义 9.5.2　子环、理想和商环 9.5.3　环的同态和同构 9.6　群环域的应用 9.6.1　计数问题 9.6.2　多项式编码 9.7　习题 第　10 章 格与布尔代数 历史人物 思维导图 10.1　格的定义和性质 10.1.1　格的定义 10.1.2　格的性质 10.2　子格与格同态 10.2.1　子格和理想 10.2.2　格同态 10.3　特殊格 10.3.1　分配格与模格 10.3.2　有界格与有补格 10.4　布尔代数 10.5　格与布尔代数的应用 10.5.1　格与树形图结构 10.5.2　布尔函数及其表示 10.6　习题