第1部分 集合论 3
相关历史背景 3
第1章 集合 5
1.1集合的基本概念 5
1.1.1集合与元素 5
1.1.2集合的表示 5
1.1.3集合间的关系 6
1.2集合的运算 7
1.2.1并运算 7
1.2.2交运算 9
1.2.3补运算 9
1.2.4差运算 10
1.2.5对称差运算 10
1.2.6有限集合基数的运算 11
1.3集合恒等式的证明 13
1.3.1从定义出发证明集合恒等 13
1.3.2利用集合运算律证明恒等式 14
1.4笛卡儿积 15
1.4.1笛卡儿积的概念 15
1.4.2笛卡儿积的运算性质 15
1.4.3 n阶笛卡儿积 17
习题一 17
第2章 关系 20
2.1关系的基本概念 20
2.1.1二元关系 20
2.1.2关系的表示法 21
2.2关系的运算 23
2.2.1逆关系 24
2.2.2关系的合成 26
2.2.3关系的幂 28
2.3关系的性质 29
2.3.1关系的基本性质 29
2.3.2关系性质的定理 32
2.4关系的闭包 33
2.5等价关系 35
2.5.1等价关系与等价类 35
2.5.2商集与划分 37
2.6偏序关系与层次结构 38
习题二 41
第3章 映射 45
3.1映射的基本概念 45
3.1.1映射的定义 45
3.1.2单射、满射和双射 47
3.1.3有关映射的定理 47
3.2逆映射与复合映射 49
3.2.1逆映射 49
3.2.2映射的合成 50
3.2.3有关映射合成的定理 51
3.3变换与置换 52
3.3.1变换 52
3.3.2置换 54
习题三 54
第2部分 数理逻辑 59
相关历史背景 59
第4章 命题逻辑 64
4.1基本概念和基本运算 64
例题分析4.1 67
4.2命题公式和真值表 69
例题分析4.2 71
4.3等值演算 73
例题分析4.3 76
4.4推理理论 77
例题分析4.4 83
4.5范式 88
习题四 90
第5章 谓词逻辑 93
5.1基本概念 93
例题分析5.1 96
5.2谓词公式及解释 98
例题分析5.2 103
5.3谓词公式的等值式 105
例题分析5.3 109
5.4谓词逻辑的推理理论 110
例题分析5.4 112
习题五 115
第3部分 代数系统 119
相关历史背景 119
第6章 代数系统的基本概念 121
6.1代数运算和代数系统的定义 121
6.2代数系统的性质 122
6.2.1常见的运算性质 122
6.2.2常见的特殊元素 123
6.2.3可逆元素与幂等元素 124
6.3同态与同构 125
6.3.1同态映射与同构映射 125
6.3.2同态象 126
6.3.3同构象 129
6.3.4同构的应用 129
习题六 132
第7章 几个典型的代数系统 135
7.1群 135
7.1.1群的定义 135
7.1.2群的基本性质 136
7.2环与域 137
7.3格与布尔代数 139
7.3.1布尔代数的基本性质 140
7.3.2几个布尔代数系统 142
7.4关系代数 143
习题七 144
第4部分 图论 149
相关历史背景 149
第8章 图的基本概念 151
8.1基本概念 151
例题分析8.1 155
8.2图的连通性 158
例题分析8.2 160
8.3图的矩阵表示 161
例题分析8.3 164
8.4一些特殊的图 166
8.4.1欧拉图 166
8.4.2汉密尔顿图 168
8.4.3二部图 169
8.4.4平面图 170
例题分析8.4 171
8.5最短路径 172
8.5.1有向图的最短路径问题 172
8.5.2 Dijkstra的标号法 172
8.5.3 Dijkstra标号法需要改进之处 174
8.5.4改进的Dijkstra标号法 174
例题分析8.5 177
8.6关键路径 179
8.6.1 PERT图 179
8.6.2最早完成时间 180
8.6.3最晚完成时间 180
8.6.4缓冲时间 180
习题八 181
第9章 树 184
9.1树的基本概念 184
9.2有向树 187
习题九 193
第5部分 组合计数基础 197
第10章 组合计数基础 197
10.1基本计数规则 197
10.1.1加法法则 197
10.1.2乘法法则 197
10.2排列与组合 198
10.3二项式定理与组合恒等式 200
10.4多项式定理 202
习题十 203
第6部分 离散数学在各领域中的应用 207
第11章 离散数学在各领域中的应用 207
11.1集合的应用 207
11.1.1集合在关系数据库中的应用 207
11.1.2集合特征代码与代码的运算 208
11.1.3有限集合的基数 209
11.1.4序关系在项目管理中的应用 210
11.2命题逻辑的应用 210
11.2.1推理问题 210
11.2.2红楼梦中的命题逻辑 212
11.2.3分工 212
11.2.4逻辑学家的推理 213
11.2.5程序下载 214
11.2.6自动调动电路 215
11.2.7发问 215
11.2.8人员录取方案 216
11.2.9排课方案 216
11.2.10人员选派 218
11.2.11在科技管理中的应用 219
11.2.12在排队论中的应用 221
11.2.13密码锁问题 221
11.2.14假言推理的应用 222
11.2.15电路设计 223
11.3代数系统的应用 224
11.3.1开关电路的技术问题 225
11.3.2开关电路函数 225
11.3.3逻辑门 225
11.4图论的应用 226
11.4.1购物场所的选址 226
11.4.2最优匹配问题 227
11.4.3旅游路线的选择 227
11.4.4公交网络路径的确定 230
11.4.5消防选址 231
11.4.6中国邮递员问题 233
11.4.7人员分配 233
11.4.8着色问题 235
11.4.9 PERT图简介 235
11.4.10最小成本生成树 236
11.4.11列车运行模型 237
11.4.12排座位 237
11.4.13关键路径问题 238
11.4.14电网建设 241
11.4.15城市交通 242
11.4.16铁路危险货物配放 243
11.4.17树状河流空间关系 246
11.4.18风险管理中的决策树 247
模拟试题一 249
模拟试题二 251
参考文献 253