工科离散数学（第2版）

　　本书共8章，以数理逻辑为基础，介绍命题逻辑、谓词逻辑、集合论基础、关系、函数、运算与代数系统、图和初等数论基础的相关内容，配套微课视频、电子课件、知识导图、部分习题解答等。本书内容不求大求全，根据工程教育的要求，着重介绍有应用价值的理论，避免理论上的缠绕，内容讲解通俗明了，同时还增加了相当数量的工程应用方面的简介，使学习者能够快速了解这些理论的实际工程用途。 本书可作为高等学校计算机科学与技术、软件工程、信息与计算科学以及其他信息领域相关专业离散数学课程的教材，也可供相关领域读者自学使用。

　　牛连强，男，沈阳工业大学软件学院院长、教授二是余年来，长期从事高等学校计算机领域的教学和科研工作，教学经验丰富、科研项目成果丰富，并出版了多部教材和专著，发表论文40余篇。

目 录

第1章 命题逻辑 1
1.1 命题 1
思考与练习1.1 3
1.2 逻辑联结词 3
1.2.1 基本联结词 3
1.2.2 其他联结词 6
思考与练习1.2 6
1.3 命题公式与真值表 7
1.3.1 命题公式 7
1.3.2 真值表 8
思考与练习1.3 8
1.4 命题翻译 9
1.4.1 命题的合取 9
1.4.2 命题的析取 9
1.4.3 条件句复合命题 10
1.4.4 多联结词构成的复合命题 11
思考与练习1.4 12
1.5 命题公式的分类与逻辑等价 13
1.5.1 命题公式的分类 13
1.5.2 命题公式等价 14
1.5.3 联结词的功能完备集 16
1.5.4 对偶原理 17
思考与练习1.5 18
1.6 范式 18
1.6.1 简单的范式 18
1.6.2 小项与大项 19
1.6.3 主析取范式与主合取范式 20
思考与练习1.6 23
1.7 推 理 理 论 24
1.7.1 蕴含与论证 24
1.7.2 自然推理系统 26
思考与练习1.7 33
第2章 谓词逻辑 34
2.1 谓词、个体词与量词 34
2.1.1 个体词和谓词 34
2.1.2 量词与量化 36
思考与练习2.1 37
2.2 谓词逻辑的命题翻译 38
2.2.1 特殊化个体词的命题 38
2.2.2 量词量化的命题 38
思考与练习2.2 41
2.3 量词约束与谓词公式的解释 42
2.3.1 量词对个体词变元的作用 42
2.3.2 谓词公式的解释与求值 42
2.3.3 量词与联结词的搭配 44
思考与练习2.3 44
2.4 谓词公式的等价和蕴含 45
2.4.1 基本等价与蕴含关系 45
2.4.2 利用等价关系计算前束范式 48
思考与练习2.4 49
2.5 谓词逻辑的推理理论 50
2.5.1 推理定律 50
2.5.2 量词的消除与产生规则 50
2.5.3 谓词逻辑的自然推理示例 52
思考与练习2.5 55
2.6 *数学证明初步 56
2.6.1 数学论题的描述 56
2.6.2 证明方法 56
2.6.3 证明策略 58
思考与练习2.6 59
第3章 集合论基础 61
3.1 集合的概念和表示方法 61
3.1.1 集合描述 61
3.1.2 集合的包含与相等 62
3.1.3 空集和全集 63
3.1.4 集合的幂集 65
思考与练习3.1 66
3.2 集合运算 66
3.2.1 基本运算 66
3.2.2 多集合的交与并 68
思考与练习3.2 70
3.3 集合运算的性质 71
3.3.1 集合算律与恒等变换 71
3.3.2 基于定义的运算性质验证 72
思考与练习3.3 74
3.4 集合划分和计数 74
3.4.1 集合的划分与覆盖 75
3.4.2 *集合计数的容斥原理 76
思考与练习3.4 77
3.5 序偶与笛卡儿积 78
3.5.1 序偶和元组 78
3.5.2 笛卡儿积 79
思考与练习3.5 81
第4章 关系 82
4.1 二元关系的含义与表示 82
4.1.1 二元关系 82
4.1.2 关系的矩阵和图表示法 84
思考与练习4.1 85
4.2 关系运算 86
4.2.1 关系的逆与复合 86
4.2.2 关系运算的性质 87
4.2.3 关系运算的图和矩阵实现 88
4.2.4 关系的幂 90
思考与练习4.2 92
4.3 关系的性质 93
4.3.1 自反与反自反关系 93
4.3.2 对称与反对称关系 94
4.3.3 传递关系 95
4.3.4 关系性质的等价描述与判定 95
思考与练习4.3 97
4.4 关系的闭包 98
4.4.1 闭包的概念 98
4.4.2 闭包计算 99
思考与练习4.4 102
4.5 等价关系 102
4.5.1 等价与相容 102
4.5.2 等价类 103
4.5.3 划分与等价关系的对应 104
思考与练习4.5 106
4.6 序关系 107
4.6.1 体现部分序的偏序关系 107
4.6.2 哈斯图 108
4.6.3 链与全序关系 109
4.6.4 偏序集的特殊元素 111
思考与练习4.6 112
第5章 函数 114
5.1 从关系到函数 114
5.1.1 函数的概念 114
5.1.2 函数集 115
5.1.3 函数的性质与特殊函数 116
思考与练习5.1 118
5.2 函数的逆与复合 119
5.2.1 双射的反函数 119
5.2.2 函数复合 119
5.2.3 函数运算的性质 121
思考与练习5.2 122
5.3 集合的基数 122
5.3.1 集合等势 122
5.3.2 有限集与无限集 123
5.3.3 可数集与不可数集 123
5.3.4 基数比较 125
思考与练习5.3 126
第6章 运算与代数系统 127
6.1 运算及其性质 127
6.1.1 运算的概念 127
6.1.2 二元运算的性质 128
思考与练习6.1 129
6.2 二元运算中的特殊元素 130
6.2.1 幺元 130
6.2.2 零元 131
6.2.3 逆元 132
思考与练习6.2 133
6.3 代数系统 133
6.3.1 代数与子代数 133
6.3.2 同态与同构 134
思考与练习6.3 135
6.4 半群与独异点 136
思考与练习6.4 137
6.5 群与子群 138
6.5.1 群的概念 138
6.5.2 群的性质 139
6.5.3 子群 140
思考与练习6.5 141
6.6 循环群与置换群 142
6.6.1 循环群 142
6.6.2 置换群 143
思考与练习6.6 145
6.7 群的陪集分解 145
6.7.1 陪集 146
6.7.2 拉格朗日定理 147
思考与练习6.7 148
6.8 环和域 148
6.8.1 环与整环 148
6.8.2 域 150
思考与练习6.8 150
6.9 格 151
6.9.1 格与其诱导的代数系统 151
6.9.2 子格 153
6.9.3 几种特殊格 153
思考与练习6.9 155
6.10 布尔代数 156
6.10.1 布尔代数的定义 156
6.10.2 二值布尔代数 157
思考与练习6.10 159
第7章 图 160
7.1 图的基本概念 160
7.1.1 图及其组成 160
7.1.2 结点的度与握手定理 161
7.1.3 完全图与正则图 163
7.1.4 子图、补图与图同构 163
思考与练习7.1 165
7.2 图的连通性 165
7.2.1 路与回路 165
7.2.2 无向图的连通性 166
7.2.3 有向图的连通性 167
思考与练习7.2 168




7.3 图的矩阵表示 168
7.3.1 邻接矩阵 168
7.3.2 关联矩阵 170
思考与练习7.3 170
7.4 几种特殊的图 171
7.4.1 二部图 171
7.4.2 欧拉图 173
7.4.3 汉密尔顿图 175
思考与练习7.4 176
7.5 平面图 177
7.5.1 平面图与欧拉定理 177
7.5.2 平面图着色 179
思考与练习7.5 180
7.6 树 180
7.6.1 无向树 180
7.6.2 生成树 182
7.6.3 *单源最短路径 184
7.6.4 根树 186
思考与练习7.6 189
第8章 初等数论基础 190
8.1 整数除法与素数 190
8.1.1 整数除法与整除 190
8.1.2 素数与合数 191
8.1.3 最大公约数与最小公倍数 193
思考与练习8.1 196
8.2 同余与同余方程 196
8.2.1 模算术与同余 196
8.2.2 一次同余方程及方程组 198
思考与练习8.2 200
8.3 费马小定理与欧拉定理 201
8.3.1 费马小定理 201
8.3.2 *欧拉函数与欧拉定理 202
8.3.3 *RSA密码系统原理 202
思考与练习8.3 204
附录 符号索引 205
参考文献 207