《离散数学》

第一章基本形式和运算1

1 引言1

2 元素与集合1

3 子集2

4 文氏图和补集7

5 集合的计算机表示法8

6 集运算11

7 集代数12

8 集合的计算机运算14

9 积集18

10 关系 映射 函数19

11 等价关系与序关系27

12 子集格33

13 矢量和矩阵34

第二章无向图40

1 图论40

2 基本定义41

3 几类特殊的图45

4 图的矩阵表示法52

5 图的各种矩阵之间的关系56

6 不变量和图同构62

7 圈基71

8 最大完全子图76

9 矩阵存储的最小化85

10 三次图的带宽90

11 双图的带宽100

12 平面图和四色猜想105

第三章戈恩树110

1 引言110

2 树域113

3 树118

4 前置表示法和树形123

5 显定义128

6 检索、子程序和定理证明136

第四章有向图139

1 引言139

2 基本定义139

3 几类特殊的图142

4 有向图的矩阵表示法143

5 流程图145

6 网络148

7 最小成本流156

8 剪枝法求最短道路159

9 关键道路165

10 多处理系统图169

11 信息网络169

第五章形式语言和自然语言177

1 引言177

2 半群177

3 形式语言179

4 巴科斯范式和 ALGOL 类语言188

6 自然语言193

5 形式语言的语义学193

第六章有限群与计算196

1 群和子群的定义196

2 图的群199

3 群的图202

4 生成元素和关系204

5 排列和置换群211

6 排列发生器219

第七章偏序和格225

1 引言225

2 偏序225

3 格227

4 一些特殊的格234

5 原子格240

第八章布尔代数244

1 引言244

2 布尔代数的性质244

3 布尔代数与集合代数246

4 布尔函数248

5 开关电路253

6 布尔函数化简258

7 计算机的运算268

第九章命题演算270

1 引言270

2 基本定义270

3 真值表273

4 合式公式280

5 算符的最小集合282

6 波兰表示法286

7 逻辑证明293

8 集合与字集300

第十章组合论302

1 引言302

2 事物的排列302

3 事物的组合308

4 组合的枚举母函数312

5 排列的枚举母函数319

6 斯特林数323

7 排列的圈类326

8 分割和有序划分329

第十一章不同代表系统335

1 引言和历史335

2 第三类问题、一般情况343

3 第三类问题、划分情况347

4 总结351

第十二章离散概率353

1 离散集合的概率353

2 条件概率与独立性359

3 二项式系数的计算364

4 分布368

5 随机数380

部分习题解答和提示384

英汉术语对照表402