离散数学结构/普通高等院校计算机专业(本科)使用教程系列

本书特别关注与计算机科学密切相关的数学知识，既注重各部分内容之间的紧密联系，又注重理论、算法的实际应用。它首先介绍了基础知识，包括集合、序列、整数除法、矩阵、逻辑和计数等概念。接着描述了离散数学的主要知识体系，内容涉及集合论、数学结构、图论、关系、函数、格和布尔代数、树结构、图结构、半群和群等知识，包括整个体系的基础和多个分支。最后介绍了离散数学的应用，涉及形式语言和有限状态机、群和编码。 本书内容丰富、具体，结构清晰，注重实用。它既适用于高等院校计算机及相关专业的本科生和研究生的学习，又可作为工程技术人员的参考书。

第1章 基础知识 1.1 集合与子集 1.1.1 集合的概念和表示 1.1.2 集合之间的关系 1.1.3 集合的运算 1.1.4 集合运算的代数性质 练习1.1 1.2 序列 1.2.1 序列 1.2.2 特征函数 1.2.3 串和正则表达式 练习1.2 1.3 整数的除法 1.3.1 素数 1.3.2 最大公约数 1.3.3 最小公倍数 练习1.3 1.4 矩阵 1.4.1 矩阵和运算 1.4.2 布尔矩阵的运算 练习1.4 1.5 数学结构 练习1.5 要点回顾1 自测题1 第2章 逻辑 2.1 命题和逻辑运算 2.1.1 命题 2.1.2 逻辑联结词与复合命题 2.1.3 谓词和量词 练习2.1 2.2 条件命题 2.2.1 蕴涵联结词和等价联结词 2.2.2 三类命题 2.2.3 命题运算的性质 2.2.4 逻辑的应用 练习2.2 2.3 证明方法 2.3.1 直接证明法 2.3.2 间接证明法 2.3.3 反证法 2.3.4 证明过程 练习2.3 2.4 数学归纳法 2.4.1 数学归纳法 2.4.2 强归纳法 练习2.4 要点回顾2 自测题2 第3章 计数 3.1 叠加原理 练习3.1 3.2 排列 练习3.2 3.3 组合 练习3.3 3.4 鸽巢原理 练习3.4 3.5 概率基础 3.5.1 样本空间 3.5.2 事件 3.5.3 给事件赋概率 3.5.4 等可能结果 练习3.5 3.6 递归关系 练习3.6 要点回顾3 自测题3 第4章 关系 4.1 乘积集合 练习4.1 4.2 关系和有向图 4.2.1 关系 4.2.2 由关系得到的集合 4.2.3 关系的矩阵 4.2.4 关系的有向图 练习4.2 4.3 关系和有向图中的路径 练习4.3 4.4 关系的性质 4.4.1 自反的关系和反自反的关系 4.4.2 对称的、不对称的、反对称的关系 4.4.3 传递关系 练习4.4 4.5 等价关系 4.5.1 等价关系 4.5.2 等价关系和划分 练习4.5 4.6 关系的计算机表示 4.6.1 线性表的表示 4.6.2 关系的表示 4.6.3 关系的矩阵表示方法的计算量 4.6.4 关系的链表表示方法的计算量 4.6.5 检查传递性的计算量对比 练习4.6 4.7 关系的运算 4.7.1 关系的运算 4.7.2 关系的运算的性质 4.7.3 合成 练习4.7 4.8 闭包 4.8.1 闭包 4.8.2 传递闭包的WARSHALL算法 练习4.8 要点回顾4 自测题4 第5章 函数 5.1 函数 5.1.1 函数定义 5.1.2 特殊的函数 5.1.3 反函数 练习5.1 5.2 计算机科学中的函数 练习5.2 5.3 函数的增长 练习5.3 5.4 排列函数 5.4.1 排列和循环 5.4.2 奇排列和偶排列 练习5.4 要点回顾5 自测题5 第6章 序关系和结构 6.1 偏序集合 6.1.1 偏序集合 6.1.2 哈斯图 6.1.3 拓扑排序 6.1.4 同构 练习6.1 6.2 偏序集合的极值元素 练习6.2 6.3 格 6.3.1 格 6.3.2 同构格 6.3.3 格的性质 6.3.4 特殊和格 练习6.3 6.4 有限布尔代数 6.4.1 一类特殊的格 6.4.2 布尔代数 6.4.3 布尔代数的性质 练习6.4 6.5 布尔代数上的函数 练习6.5 6.6 电路设计 练习6.6 要点回顾6 自测题6 第7章 树 7.1 树 练习7.1 7.2 标记树 7.2.1 标记树 7.2.2 定位二元树的计算机表示 练习7.2 7.3 树搜索 7.3.1 搜索二元树 7.3.2 搜索一般的树 练习7.3 7.4 无向树 7.4.1 无向树 7.4.2 连通关系的生成树 练习7.4 7.5 最小生成树 练习7.5 要点回顾7 自测题7 第8章 图论 8.1 图 8.1.1 图 8.1.2 子图和商图 练习8.1 8.2 欧拉路径及回路 练习8.2 8.3 哈密尔顿路径及回路 练习8.3 8.4 运输网 8.4.1 运输网 8.4.2 流 8.4.3 最大流 8.4.4 最大流算法 8.4.5 扩展的运输网 8.4.6 匹配问题 练习8.4 8.5 图着色 8.5.1 图着色 8.5.2 颜色多项式 练习8.5 要点回顾8 自测题8 第9章 半群和群 9.1 二元运算回顾 9.1.1 二元运算 9.1.2 二元运算的表格 9.1.3 二元运算的性质 练习9.1 9.2 半群 9.2.1 半群 9.2.2 子半群 9.2.3 同构映射和同态 练习9.2 9.3 半群的积和商 练习9.3 9.4 群 练习9.4 9.5 群的积和商 练习9.5 要点回顾9 自测题9 第10章 语言和有限状态机 10.1 语言 10.1.1 语言 10.1.2 语法 练习10.1 10.2 语法和语言的表示 10.2.1 BNF符号 10.2.2 句法图 10.2.3 正则语法和正则表达式 练习10.2 10.3 有限状态机 10.3.1 有限状态机 10.3.2 摩尔机器 10.3.3 机器一致和商机器 练习10.3 10.4 半群、机器和语言 练习10.4 10.5 机器和正则语言 练习10.5 10.6 机器简化 练习10.6 要点回顾10 自测题10 第11章 群和编码 11.1 二进制编码和错误检测 11.1.1 编码函数 11.1.2 群码 练习11.1 11.2 解码和纠错 练习11.2 要点回顾11 自测题11 附录A 符号表 附录B 术语表