本书包括离散数学课程的标准内容：数理逻辑中的命题逻辑、一阶谓词逻辑、集合论、代数系统、图论等·特别是丰富了集合论的内容，将数学归纳法、计数以及组合论中的一些广泛应用的方法纳入集合论中·另外，书末附录中还讲述了离散数学在关系数据库中的应用·

内容简介

本书力求做到简洁明了、易懂易学，注重理论与实际的结合，注意与后续课程的衔接。适合作为普通高等院校数学、计算机科学与技术等专业的本科生教材，也可供高职高专院校的师生参考使用.

目录

第1章 集合论11.1 集合的概念与运算1

1.1.1 集合的概念1

1.1.2 集合之间的关系2

1.1.3 集合的运算2

1.1.4 集合的运算性质3

1.1.5 序偶与笛卡儿积5

1.2 二元关系6

1.2.1 二元关系及其表示6

1.2.2 二元关系的运算7

1.3 关系的性质10

1.4 关系的闭包运算12

1.5 序关系15

1.6 等价关系18

1.7 映射20

?*1.8 数学归纳法22

?*1.9 计数24

1.9.1 帕斯卡三角形和二项式定理25

1.9.2 鸽巢原理26

1.9.3 乘法法则和加法法则28

1.9.4 排列和组合29

?*1.10 排列组合生成算法31

?*1.11 离散概率简介34

习题137

第2章 命题逻辑41

2.1 命题与联结词41离散数学目录2.1.1 命题与真值41

2.1.2 命题联结词42

2.2 命题公式、指派及真值表46

2.2.1 命题公式46

2.2.2 命题的符号化 47

2.2.3 公式的指派(赋值)及真值表48

2.3 命题公式的等值式，蕴含关系式50

2.3.1 命题公式的等值式50

2.3.2 代入规则与替换规则51

2.3.3 对偶式53

2.3.4 蕴含关系式54

2.4 主析取范式和主合取范式56

2.4.1 合取范式与析取范式57

2.4.2 主范式58

?*2.5 联结词完备集61

2.6 可满足性问题与消解法63

2.7 推理的形式结构68

2.8 自然推理系统?N?中的形式证明70

习题276

第3章 谓词逻辑79

3.1 基本概念79

3.1.1 个体词、谓词79

3.1.2 量词80

3.2 一阶逻辑公式及解释83

3.3 一阶逻辑等值式87

3.4 前束范式与斯科林范式90

3.4.1 前束范式90

3.4.2 斯科林范式92

3.5 谓词演算的推理理论93

??3.6 数理逻辑在计算机科学中的应用99

3.6.1 “钥匙在点火开关中”报警蜂鸣器100

3.6.2 构造自锁控制安全带的电路103

3.6.3 构造一个拿子游戏装置105

3.6.4 构造电路：专用装置和程序化计算机108

习题3109

??第4章 公理系统下的形式证明112

4.1 命题逻辑的公理推理系统112

4.1.1 公理推理系统?P?112

4.1.2 公理推理系统?P?的可靠性、和谐性和完备性117

4.2 谓词逻辑的公理系统120

4.3 定理的机器证明122

第5章 图论124

5.1 图的基本概念124

5.1.1 图及其图形表示125

5.1.2 顶点的度126

5.1.3 完全图和补图128

5.1.4 子图129

5.1.5 图的同构129

5.2 通路、回路与连通性131

5.2.1 通路和回路131

5.2.2 无向图的连通性133

5.2.3 有向图的连通性136

5.2.4 门格定理137

5.3 欧拉图与中国邮递员问题138

5.3.1 哥尼斯堡七桥问题138

5.3.2 欧拉图139

5.3.3 中国邮递员问题142

5.4 哈密尔顿图与旅行售货商问题144

5.4.1 哈密尔顿图144

5.4.2 旅行售货商问题147

5.5 树149

5.5.1 树的定义及其基本性质149

5.5.2 生成树151

5.5.3 最小生成树问题153

5.5.4 根树及其应用154

5.6 图的矩阵表示158

5.6.1 关联矩阵158

5.6.2 邻接矩阵159

5.6.3 可达矩阵164

5.6.4 图的运算165

5.7 平面图与图的着色166

5.7.1 平面图166

5.7.2 对偶图与图着色169

习题5171

第6章 代数系统175

6.1 二元运算与代数系统175

6.1.1 二元运算175

6.1.2 代数系统179

6.2 群和半群180

6.2.1 群和半群的定义 180

6.2.2 关于逆元的性质182

6.2.3 群的几个等价性质182

6.3 子群和元素的阶183

6.3.1 子群183

6.3.2 元素的阶184

6.4 循环群和生成群、群的同构185

6.4.1 循环群和生成群185

6.4.2 群的同构186

6.4.3 循环群的性质186

6.5 变换群和置换群、凯莱定理187

6.5.1 置换群188

6.5.2 凯莱定理190

6.6 子群的陪集和拉格朗日定理192

6.6.1 子群的陪集192

6.6.2 子群的指数和拉格朗日定理193

6.7 正规子群和商群195

6.7.1 正规子群的概念195

6.7.2 正规子群的性质195

6.7.3 商群196

6.8 共轭元和共轭子群198

6.8.1 中心和中心化子198

6.8.2 共轭元和共轭类198

6.8.3 共轭子群与正规化子199

6.9 群的同态200

6.9.1 群的同态定义200

6.9.2 同态基本定理202

6.10 环与域203

?*6.11 代数系统在计算机科学中的应用206

6.11.1 通信模型的基本概念206

6.11.2 纠错编码的基本概念207

6.11.3 线性分组码和汉明码209

习题6212

第7章 格与布尔代数215

7.1 格215

7.2 格同态220

7.3 分配格和有补格223

7.4 布尔代数227

??7.5 布尔函数及其表达式234

习题7238

?*附录A 离散数学在关系数据库中的应用240

A.1 关系数据库简介240

A.2 关系代数与数据子语言242

参考文献251

参考资料