离散数学

"本书特别适合计算类本科专业使用，开设本课程时（第三、第四学期），学生已经有了基本的程序设计能力，相关问题分析和解决方案融合了程序算法，引导学生上机编程验证。 在传统的离散数学内容基础上，本书增加了预备知识一章，包括矩阵和组合数学基础。相关章节增加了算法和程序实例，便于学生深入理解。 "

离散数学是计算机类专业的重要专业基础课程，研究离散结构和相互关系的理论和方法，在专业教学的课程体系中具有重要的理论支撑作用。离散数学的综合、分析、推理等方法，在计算机科学的理论研究和技术开发中有着广泛的应用。本书系统介绍了离散数学的内容，全书共分11章，包括预备知识（矩阵和组合数学基础）、集合论、命题逻辑、谓词逻辑、关系、特殊关系、图论基础、特殊图、代数系统、群和环域格。本书内容简洁清晰，相关内容融合了算法和程序，问题分析和推理的注释使用了程序员熟悉的格式。本书特别适合作为应用研究型和应用型高等学校计算机类相关专业“离散数学”课程的教材（48学时），也可作为相关工程技术人员的参考书。

第1章预备知识
1.1矩阵知识
1.1.1矩阵概念
1.1.2矩阵运算
1.1.3布尔矩阵
1.2组合数学基础
1.2.1整除与优选公约数、素数
1.2.2基本计数原则
1.2.3排列组合
1.2.4鸽笼原理
本章习题
第2章集合
2.1集合的基本概念
2.2集合间的相互关系
2.3集合的运算
2.4序偶与笛卡儿积
2.5容斥原理
本章习题
第3章命题逻辑
3.1命题概念
3.2命题联结词
3.2.1否定联结词“□（特殊字符）”
3.2.2合取联结词“∧”
3.2.3析取联结词“∨”
3.2.4蕴涵联结词“→”
3.2.5等价联结词“□（特殊字符）”
3.2.6其他联结词
3.3命题公式
3.4命题逻辑等值演算
3.4.1等值式与等值演算
3.4.2联结词完备集
3.5对偶与范式
3.5.1公式的对偶
3.5.2析取范式与合取范式
3.5.3主析取范式与主合取范式
3.6命题逻辑推理
3.6.1推理的基本概念
3.6.2推理的基本方法
本章习题
第4章谓词逻辑
4.1谓词逻辑基本概念
4.1.1个体
4.1.2谓词
4.1.3量词
4.2谓词公式
4.2.1谓词公式
4.2.2谓词公式的解释与类型
4.3谓词公式等值演算
4.4前束范式
4.5谓词逻辑推理
本章习题
第5章关系
5.1关系的定义
5.2关系的表示
5.2.1关系的矩阵表示
5.2.2关系的关系图表示
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关系的闭包
本章习题
第6章特殊关系
6.1等价关系
6.1.1等价关系的概念
6.1.2等价类与商集
6.1.3划分
6.2偏序关系
6.2.1偏序关系的概念
6.2.2哈斯图
6.2.3拓扑排序
6.3函数
6.3.1函数的定义
6.3.2函数的性质
6.3.3复合函数
6.3.4逆函数
本章习题
第7章图论基础
7.1图论三个经典问题
7.2图的基本概念
7.2.1图的定义
7.2.2握手定理
7.2.3图的表示
7.2.4子图与补图
7.2.5图的同构
7.3图的连通性
7.3.1通路与回路
7.3.2无向图的连通性
7.3.3有向图的连通性
本章习题
第8章特殊图
8.1欧拉图
8.2哈密尔顿图
8.3平面图
8.4无向树
8.4.1无向树定义及性质
8.4.2生成树与最小生成树
8.5根树
8.5.1有向树与根树
8.5.2根树的遍历
8.5.3很优树
本章习题
第9章代数系统
9.1代数系统概述
9.2运算的性质和特殊元素
9.2.1运算的性质
9.2.2特殊元素
9.3代数系统的同态
9.3.1代数系统的同态定义
9.3.2子代数与积代数
本章习题
第10章特殊代数系统
10.1半群与独异点
10.2群
10.2.1群的定义及基本性质
10.2.2交换群
10.3循环群
10.3.1元素的周期
10.3.2循环群的定义
10.3.3子群
10.3.4群同态
10.4置换群
10.5陪集与拉格朗日定理
10.5.1陪集
10.5.2拉格朗日定理
10.6正规子群与商群
10.6.1正规子群
10.6.2商群
本章习题
第11章环、域、格和布尔代数
11.1环
11.2域
11.3格
11.3.1格
11.3.2分配格、有界格、有补格
11.4布尔代数
本章习题
参考文献