第1章 命题逻辑 1
1.1 引言 1
数理逻辑的发展 1
1.2 命题与命题联结词 1
1.2.1 命题的概念 2
1.2.2 命题标识符和命题分类 4
1.2.3 命题联结词 4
1.3 翻译、命题公式和真值表 10
13.1 翻译 10
1.3.2 命题公式 12
1.3.3 真值情况和真值表 13
1.4 等价式和蕴涵式 15
1.4.1 等价公式 15
1.4.2 等价定律公式 16
1.4.3 子公式 17
1.4.4 证明两个公式等价的方法 19
1.4.5 蕴涵式 21
1.4.6 两个命题公式间的永真蕴涵关系的判断 22
1.5 永真式、永假式 25
永真式、永假式 25
1.6.1 其他联结词的定义 27
1.6 其他联结词 27
1.6.2 “与非”↑的性质 28
1.6.3 “或非”↓的性质 28
1.6.4 “异或”性质 29
1.6.5 最小联结词 31
1.7 对偶与范式 32
1.7.1 对偶 32
1.7.2 范式 35
1.7.3 主析取范式 37
1.7.4 主合取范式 41
1.7.5 主范式的应用 44
1.8 命题演算的推理理论 46
1.8.1 推理的基本概念 47
1.8.2 判断有效结论的方法和规则 49
1.9 本章习题 57
第2章 谓词逻辑 62
2.1 谓词基本概念 62
2.2 个体、谓词及其表达式 63
2.3 命题函数 66
2.4 量词 69
2.5.1 谓词公式 72
2.5 谓词公式与翻译 72
2.5.2 谓词逻辑的翻译 73
2.6 变元的约束 77
2.7 谓词公式的永真式、永假式、等价式和蕴涵式 80
2.7.1 判定方法和基本公式 80
2.7.2 谓词等价式和蕴涵式 81
2.7.3 谓词公式的范式 84
2.7.4 多个量词的使用 87
2.8 谓词演算的推理理论 89
2.8.1 4个与量词有关的推理规则 89
2.8.2 谓词逻辑中推理的论证 91
2.8.3 谓词逻辑演算中常见的错误 97
2.9 本章习题 100
第3章 集合及其运算 103
3.1 集合的概念与表示 103
3.1.1 集合的概念 103
3.1.2 集合的表示 104
3.1.3 集合的相等或包含关系 105
3.2 集合的运算 107
3.3 基本的集合恒等式 111
3.4 包含排斥原理 116
3.5 本章习题 121
4.1 序偶和笛卡尔乘积 123
第4章 二元关系 123
4.2 关系及其表示 126
4.3 复合关系和逆关系 130
4.4 关系的性质 133
4.5 关系的闭包 137
4.6 等价关系 143
4.7 序关系 146
4.8 本章习题 150
5.1 函数的概念 153
第5章 函数 153
5.2 函数的类型 154
5.3 复合函数 156
5.4 逆函数 158
5.5 本章习题 161
第6章 代数结构 162
6.1 代数系统的一般概念 162
6.2 代数系统的运算性质 165
6.3 代数系统的同态和同构 169
6.4 同余关系和商代数 173
6.5 半群和独异点 178
6.6 群和子群 181
6.7 交换群和循环群 184
6.8 子群的陪集及拉格朗日定理 186
6.9 置换群 189
6.10 环和域 192
6.11 本章习题 195
第7章 格和布尔代数 198
7.1 格的基本概念 198
7.2 格的基本性质 200
7.3 模格和分配格 203
7.4 有界格和有补格 207
7.5 布尔代数 209
7.6 布尔表达式和布尔函数 213
7.7 本章习题 218
第8章 图论 221
8.1 图的基本定义及相关术语 221
8.1.1 图的概念 221
8.1.2 图G的结点与边之间的关系 223
8.1.3 图的分类 224
8.2 结点的度数及其计算 226
8.3 子图、补图和图的同构 230
8.3.1 子图的概念 230
8.3.2 补图的概念 231
8.3.3 图的同构概念 233
8.4 通路、回路和连通性 235
8.4.1 通路和回路的概念 235
8.4.2 简单有向图的连通性 239
8.4.3 无向图的连通性 242
8.5.1 无向图与有向图的关联矩阵 244
8.5 图的矩阵表示 244
8.5.2 图的邻接矩阵 246
8.5.3 有向图的可达矩阵 248
8.6 欧拉图与哈密尔顿图 249
8.6.1 欧拉图 249
8.6.2 哈密尔顿图 256
8.7 最优路径和关键路径 262
8.7.1 最优路径的概念 262
8.7.2 最优路径在实际中的应用 264
8.7.3 欧拉图的应用——中国邮路问题 265
8.7.4 哈密尔顿回路和货郎担问题 265
8.8.1 平面图的概念 267
8.8 平面图 267
8.8.2 平面图的面 268
8.8.3 平面图的判定 270
8.9 对偶与着色 275
8.9.1 对偶的基本概念 275
8.9.2 面图的对偶图的做法 276
8.9.3 对偶图性质 276
8.9.4 图的着色 277
8.9.5 地图的着色与平面图的点着色 279
8.10 二分图 280
8.11 本章习题 282
第9章 树 288
9.1 无向树及其性质 288
9.1.1 树的基本概念 288
9.1.2 无向树的性质 288
9.2 无向图的生成树和最小生成树 291
9.3 有向树、根树和二叉树 296
9.3.1 有向树和根树的概念 296
9.3.2 m叉树和二叉树 298
9.4 树的遍历 302
9.5 最优树与Huffman算法 303
9.6 最佳前缀码 304
9.7 本章习题 306
第10章 Petri网和运输网络 309
10.1 Petri网的基本概念 309
10.2 Petri网的执行规则 310
10.3 Petri网的活性和安全性 312
10.4 Petri网在工作流建模中的应用 314
10.5 运输网络 318
10.5.1 运输网络的基本概念 318
10.5.2 求最大流的标记法 320
10.6 本章习题 322
11.1 基本原理 323
第11章 计数方法和分类原理 323
11.2 排列与组合 324
11.3 可重复的排列与组合 327
11.4 二项式系数和组合恒等式 330
11.5 多项式定理 333
11.6 tirling公式 335
11.7 鸽巢原理 337
11.8 本章习题 339
《离散数学》模拟试卷1 342
《离散数学》模拟试卷2 345