目录

第1 章集合............................................ 1

1.1 集合的概念........................................ 1

1.1.1 集合的定义与表示............................... 1

1.1.2 集合的性质................................... 2

1.1.3 特殊集合.................................... 3

1.2 集合运算......................................... 4

1.2.1 集合基本运算.................................. 4

1.2.2 维恩图...................................... 5

1.2.3 集合公式与恒等式............................... 7

1.2.4 集合恒等式的证明............................... 9

1.3 集合的基数........................................ 13

1.4 计数原理......................................... 19

1.4.1 加法原理与乘法原理............................. 19

1.4.2 容斥原理.................................... 21

1.4.3 鸽巢原理.................................... 22

1.5 习题............................................ 23

第2 章关系............................................ 29

2.1 关系的概念........................................ 29

2.1.1 序偶与关系................................... 29

2.1.2 关系矩阵与关系图............................... 33

2.2 关系的运算........................................ 36

2.2.1 复合运算.................................... 36

2.2.2 逆运算...................................... 41

2.2.3 幂运算...................................... 45

2.3 关系的性质........................................ 46

2.3.1 自反性...................................... 46

2.3.2 对称性...................................... 48

2.3.3 传递性...................................... 50

2.4 闭包............................................ 53

2.5 特殊关系......................................... 55

2.5.1 等价关系.................................... 55

2.5.2 相容关系.................................... 60

2.5.3 偏序关系.................................... 63

2.6 习题............................................ 71

第3 章函数............................................ 78

3.1 函数的概念........................................ 78

3.1.1 函数的定义与表示............................... 78

3.1.2 特殊函数.................................... 80

3.2 函数的运算........................................ 81

3.2.1 复合函数.................................... 81

3.2.2 逆函数...................................... 84

3.3 习题............................................ 85

第4 章命题逻辑......................................... 90

4.1 命题逻辑的基本概念.................................. 90

4.1.1 命题....................................... 90

4.1.2 逻辑联结词................................... 92

4.2 命题公式......................................... 93

4.2.1 命题逻辑符号化................................ 93

4.2.2 真值表...................................... 95

4.2.3 等价式...................................... 97

4.2.4 蕴涵式...................................... 102

4.3 综合应用......................................... 106

4.4 联结词的完备集..................................... 108

4.5 对偶式........................................... 111

4.6 范式............................................ 114

4.7 命题逻辑推理...................................... 127

4.7.1 逻辑推理的基本概念............................. 127

4.7.2 逻辑推理方法.................................. 127

4.8 习题............................................ 133

第5 章谓词逻辑......................................... 142

5.1 谓词逻辑的基本概念.................................. 142

5.1.1 个体和谓词................................... 143

5.1.2 量词....................................... 144

5.2 谓词公式......................................... 146

5.2.1 谓词逻辑符号化................................ 146

5.2.2 谓词公式的解释................................ 149

5.2.3 等价式和蕴涵式................................ 151

5.3 前束范式......................................... 155

5.4 谓词逻辑推理...................................... 158

5.5 习题............................................ 164

第6 章代数系统的引入、半群与群.............................. 170

6.1 代数系统......................................... 170

6.2 半群............................................ 178

6.3 群与子群......................................... 182

6.4 几类特殊群........................................ 188

6.4.1 阿贝尔群.................................... 188

6.4.2 循环群...................................... 189

6.4.3 置换群...................................... 192

6.5 群论在量子信息中的应用............................... 194

6.6 习题............................................ 195

第7 章环和域........................................... 199

7.1 环.............................................. 199

7.2 子环与环的同态..................................... 203

7.3 域.............................................. 206

7.4 一元方程的求解..................................... 207

7.5 习题............................................ 208

第8 章格.............................................. 212

8.1 格与子格......................................... 212

8.2 分配格........................................... 222

8.3 有补格........................................... 226

8.4 布尔代数在信息科学中的应用............................ 235

8.5 习题............................................ 236

第9 章图论基础......................................... 242

9.1 图论简介......................................... 242

9.2 图的基本概念...................................... 243

9.2.1 图的定义.................................... 243

9.2.2 图的相关术语.................................. 244

9.2.3 伪图、多重图和简单图............................ 247

9.2.4 完全图...................................... 248

9.2.5 子图....................................... 248

9.2.6 补图....................................... 250

9.2.7 图的同构.................................... 251

9.3 图的连通性........................................ 253

9.3.1 通路与回路................................... 253

9.3.2 图的连通性简介................................ 254

9.3.3 连通度...................................... 257

9.4 图的矩阵表示...................................... 260

9.4.1 任意图...................................... 260

9.4.2 简单图...................................... 261

9.5 图在交通规划与物流管理中的应用......................... 270

9.6 习题............................................ 271

第10 章特殊图........................................... 275

10.1 欧拉图........................................... 275

10.2 哈密尔顿图........................................ 279

10.2.1 中国邮递员问题............................... 283

10.2.2 最短通路问题................................. 285

10.3 二分图........................................... 286

10.3.1 平面图的基本概念.............................. 291

10.3.2 平面图的面.................................. 293

10.3.3 平面图的判别................................. 296

10.3.4 对偶图..................................... 299

10.3.5 平面图的着色................................. 300

10.4 树.............................................. 302

10.4.1 无向树及其性质............................... 302

10.4.2 生成树..................................... 302

10.4.3 最小生成树.................................. 303

10.4.4 根树及其应用................................. 305

10.5 树在信息科学中的应用................................. 312

10.6 习题............................................ 313

附录A 数学家简介........................................ 318

附录B 中英文对照........................................ 321