本书介绍计算机专业必需的离散数学基础知识,包括离散数学四大分支的基础理论,它们是数理逻辑、集合论、代数系统和图论,共8章,依次为命题逻辑、谓词逻辑、集合、关系、函数、代数结构、格与布尔代数、图论及其应用。本书包含较多的与计算机科学和工程有关的例题和习题。
本书适合作为高等理工科院校计算机科学与技术、软件工程等相关专业教材,也可供教师、研究生、有关工程技术人员作为参考书。

目 录

第1章 命题逻辑 1
1-1 命题 1
1-1-1 命题与真值 1
1-1-2 原子命题与复合命题 2
1-2 逻辑联结词 3
1-2-1 否定联结词 3
1-2-2 合取联结词 3
1-2-3 析取联结词 4
1-2-4 蕴含联结词 4
1-2-5 等价联结词 5
1-3 命题公式 5
1-3-1 命题公式的概念 5
1-3-2 命题符号化 6 目 录

第1章 命题逻辑 1
1-1 命题 1
1-1-1 命题与真值 1
1-1-2 原子命题与复合命题 2
1-2 逻辑联结词 3
1-2-1 否定联结词 3
1-2-2 合取联结词 3
1-2-3 析取联结词 4
1-2-4 蕴含联结词 4
1-2-5 等价联结词 5
1-3 命题公式 5
1-3-1 命题公式的概念 5
1-3-2 命题符号化 6
1-3-3 命题公式真值表 7
1-3-4 命题公式的类型 9
1-3-5 重言式的性质 9
1-4 命题逻辑的等价关系 9
1-4-1 等价 9
1-4-2 基本等价式 10
1-4-3 置换规则 11
1-5 命题公式的标准化 13
1-5-1 析取范式与合取范式 13
1-5-2 主析取范式与主合取范式 14
1-5-3 主范式的应用 16
1-6 命题逻辑的蕴含关系 17
1-6-1 蕴含 17
1-6-2 证明蕴含关系的方法 17
1-6-3 基本蕴含式 17
1-7 命题逻辑的推理理论 18
1-7-1 论证的有效性 18
1-7-2 有效论证的判断方法 18
1-7-3 自然推理系统 19
1-7-4 自然推理系统中构造有效论证的方法 20
本章总结 23
习题 23

第2章 谓词逻辑 25
2-1 谓词逻辑命题符号化 25
2-1-1 命题逻辑的局限性 25
2-1-2 谓词逻辑三要素 25
2-1-3 谓词逻辑命题符号化 27
2-2 谓词公式 28
2-2-1 谓词逻辑的合式公式 28
2-2-2 闭式 28
2-2-3 谓词公式的解释 29
2-2-4 谓词逻辑的公式类型 30
2-3 谓词逻辑的等价关系 31
2-3-1 等价关系 31
2-3-2 基本等价式 31
2-4 谓词公式的标准化 32
2-5 谓词逻辑的蕴含关系 32
2-5-1 蕴含关系 32
2-5-2 基本蕴含式 33
2-6 谓词逻辑的推理理论 33
本章总结 35
习题 35

第3章 集合 37
3-1 集合的概念与表示 37
3-1-1 集合的定义 37
3-1-2 集合的表示方法 38
3-2 集合之间的关系 39
3-2-1 集合之间的关系 39
3-2-2 特殊集合 39
3-3 集合的运算 40
3-3-1 集合的基本运算 40
3-3-2 集合关系的证明方法 41
3-3-3 笛卡儿积 42
本章总结 42
习题 42

第4章 关系 45
4-1 关系的概念及表示 45
4-1-1 关系的概念 45
4-1-2 关系的表示方法 46
4-2 关系的性质 47
4-2-1 自反性与反自反性 47
4-2-2 对称性与反对称性 48
4-2-3 传递性 49
4-3 关系的运算 50
4-3-1 关系的复合运算 50
4-3-2 关系的逆运算 53
4-3-3 关系的闭包运算 54
4-4 等价关系与划分 55
4-4-1 等价关系的概念 55
4-4-2 等价类 56
4-4-3 划分 57
4-5 次序关系 57
4-5-1 偏序关系 58
4-5-2 其他次序关系 59
本章总结 60
习题 60

第5章 函数 63
5-1 函数的概念与性质 63
5-1-1 函数的概念 63
5-1-2 函数的性质 64
5-2 函数的运算 65
5-2-1 函数的复合运算 65
5-2-2 函数的逆运算 65
5-3 基数 66
5-3-1 基数的概念 66
5-3-2 基数的比较 67
本章总结 68
习题 68

第6章 代数结构 70
6-1 代数系统的概念 70
6-2 代数系统的运算及其性质 71
6-2-1 二元运算的性质 72
6-2-2 小结 75
6-3 半群与含幺半群 75
6-3-1 半群和子半群 76
6-3-2 含幺半群和子含幺半群 77
6-4 群与子群 79
6-4-1 群 79
6-4-2 子群 82
6-5 交换群、循环群与置换群 83
6-5-1 交换群 83
6-5-2 循环群 84
6-5-3 置换群 85
6-6 陪集与拉格朗日定理 86
6-6-1 陪集 86
6-6-2 拉格朗日定理 88
6-7 同态与同构 89
6-7-1 同态 89
6-7-2 同构 90
6-7-3 同余关系 92
6-8 环与域 94
6-8-1 环 94
6-8-2 域 96
本章总结 98
习题 99

第7章 格与布尔代数 102
7-1 格 102
7-1-1 格的概念 102
7-1-2 格的性质 104
7-2 分配格 108
7-3 有补格 109
7-4 布尔代数 111
本章总结 113
习题 113

第8章 图论及其应用 116
8-1 图的基本概念 116
8-1-1 图 116
8-1-2 结点的度 118
8-1-3 图的同构 118
8-1-4 子图和补图 119
8-2 图的连通性 121
8-2-1 路径与回路 121
8-2-2 连通图 121
8-3 图的矩阵表示 123
8-3-1 图的邻接矩阵 123
8-3-2 图的可达矩阵 125
8-4 *短路径与关键路径 127
8-4-1 *短路径 127
8-4-2 评审图与关键路径 128
8-5 树 129
8-5-1 无向树 129
8-5-2 有向树 132
本章总结 136
习题 136

附录 习题答案及提示 139
第1章 习题参考答案 139
第2章 习题参考答案 144
第3章 习题参考答案 150
第4章 习题参考答案 153
第5章 习题参考答案 158
第6章 习题参考答案 161
第7章 习题参考答案 164
第8章 习题参考答案 166

参考文献 167

1.注重实践
2.突破经典
3.明确关系,理清脉络