《离散数学、算法及CAI》

第一篇 计算机科学中的离散结构1

第一章 命题逻辑1

1.1 引言1

1.2 命题及命题逻辑联结词1

习题1-16

1.3 命题变元和合式的公式7

1.4 重言式（或永真式）和永真蕴含式8

1.4-1 有关重言式的讨论8

1.4-2 重言式与恒等式（或叫等价式）9

1.4-3 永真蕴含式的定义和常用永真蕴含式10

1.4-4 代入规则和替换规则11

1.5 对偶原理12

习题1-214

1.6 范式和判定问题15

1.6-1 析取范式和合取范式15

1.6-2 主析取范武和主合取范式17

习题1-320

1.7 命题演算的推论理论21

习题1-424

小结25

第二章 谓词逻辑25

2.1 谓词演算26

2.2 谓词逻辑中的推论理论32

习题2-133

2.3 谓词公式的范式34

习题2-235

小结36

第三章 集合论36

3.1集合的概念及其表示36

习题3-139

3.2 集合的运算40

习题3-246

3.3 集合定律47

3.4 包含排斥原理48

习题3-350

3.5 多重序元与笛卡尔乘积50

习题3-453

小结53

第四章 二元关系53

4.1 关系的基本概念54

4.2 关系的性质55

习题4-156

4.3 关系的表示及其运算56

习题4-262

习题4-367

习题4-471

4.4 特种关系71

习题4-576

习题4-680

习题4-786

小结86

第五章 函数87

5.1 函数的基本概念和性质87

习题5-190

5.2 函数的合成和合成函数的性质90

习题5-293

5.3 特种函数93

习题5-395

5.4 反函数96

习题5-498

5.5 特征函数98

习题5-5100

5.6 基数100

习题 5-6102

5.7 二元运算103

习题5-7106

小结106

第六章 代数系统107

6.1 代数系统的一般概念107

6.2 同态与同构108

习题6-1111

6.3 同余关系111

习题6-2112

6.4 商代数和积代数113

习题6-3115

6.5 典型代数系统115

习题6-4119

小结120

第七章 图论120

7.1 图的基本概念120

习题7-1123

7.2 子图和图的运算124

习题7-2126

7.3 路径、回路和连通性128

习题7-3132

7.4 图的矩阵表示133

习题7-4141

7.5 欧拉图142

习题7-5144

7.6 特殊图144

习题7-6146

习题7-7151

7.7 树151

习题7-8163

7.8 网络164

习题7-9176

小结177

第二篇 离散数学中的算法178

第一章 数理逻辑中的算法178

1.1 逻辑联结词的定义方法178

1.2 合式公式的表示方法180

1.3 构造任意合式公式的真值表181

第二章 集合论中的算法182

2.1 求并集182

2.2 求交集184

2.3 求差集185

2.4 求笛卡尔乘积187

第三章 关系中的算法189

3.1 判关系R是否为自反关系及对称关系189

3.2 判关系R是否为可传递关系190

3.3 判关系R是否为等价关系191

3.4 求等价类193

3.5 求极大相容类195

3.6 关系的合成运算196

3.7 关系的闭包运算（1）197

3.8 关系的闭包运算（2）199

3.9 m个字符串按字典顺序分类算法200

第四章 函数中的算法202

4.1 求满射函数202

4.2 插入算法203

第五章 代数系统中的算法205

5.1 判是否为代数系统的算法205

5.2 判是否为同余关系206

5.3 判是否为群的算法208

第六章 图论中的算法210

6.1 道路矩阵的Warshall算法210

6.2 二叉树的遍历211

6.3 构造最优二叉树算法215

6.4 最小生成树的Kruskal算法217

6.5 求最短距离的Dijkstra算法221

6.6 判别连通性的算法224

第三篇 离散数学计算机辅助教学227

1.1 计算机辅助教学简介227

1.2 离散数学CAI目录菜单227

参考文献273