离散数学 第2版

目录 3

第一篇　数理逻辑 3

第1章　命题逻辑 3

1.1　命题与联结词 3

1.2　命题公式、翻译和真值表 8

1.3　公式分类与等价式 11

1.4　对偶式与蕴涵式 15

1.5　联结词的扩充与功能完全组 19

1.6　逻辑运算应用举例 22

1.7　公式标准型——范式 26

1.8　公式的主范式 28

1.9　命题逻辑的推理理论 33

1.10　命题逻辑的归结推理 39

习题 42

2.1 谓词逻辑中基本概念与表示 45

第2章　谓词逻辑 45

2.2　谓词公式与翻译 48

2.3　约束变元与自由变元 49

2.4　谓词逻辑的解释与其赋值 52

2.5　真与逻辑有效 55

2.6　谓词逻辑中的等价式 58

2.7　变换规则 60

2.8　谓词逻辑的蕴涵式 61

2.9　谓词逻辑中公式范式 63

2.10　谓词逻辑的推理理论 66

2.11　谓词逻辑的归结推理 70

习题 74

第二篇　集合论 81

第3章　集合论的公理系统 81

3.1 公理导出和基本概念 81

3.2　外延公理与子集公理 83

9.1 因数和倍数 1 83

9.2　素数和合数 1 84

3.3　集合的表示法 86

3.4　偶集公理与联集公理 87

9.4　整数分解惟一性定理 1 89

3.5　极小元与正则公理 91

3.6 无穷公理 92

3.7　幂集公理 93

习题 96

第4章　关系与函数 98

4.1 有序对 98

4.2　笛卡儿积 99

4.3　二元关系及其矩阵表示 100

4.4　关系的性质 106

4.5　等价关系与划分 112

4.6　函数 114

4.7　递归定义函数 117

4.8　序关系 118

4.9　代换公理 123

习题 125

第5章　序数与基数 128

5.1 序数 128

5.2　基数 133

习题 138

6.1 选择公理 139

第6章　选择公理与无穷集合 139

6.2 良序定理 140

6.3　无穷集合 142

习题 145

7.1　基本计数原理 149

第7章　计数原理与技术 149

第三篇　计数 149

7.2　鸽洞原理 151

7.3　容斥原理 152

7.4　排列与组合 154

7.5 递推关系 158

习题 161

第8章　离散概率 163

8.1　随机事件及事件的关系 163

8.2　离散集合上的概率 165

8.3　事件组合的概率 167

8.4　条件概率 169

8.5　伯努利试验与二项分布 172

8.6　随机变量及其数字特征 173

习题 178

第9章　整数与整除 183

第四篇　数论与算法 183

9.3　最大公因数和最小公倍数 186

9.5　模运算与同余 190

9.6　剩余类和剩余系 193

习题 196

第10章　整数与算法 198

10.1　算法的基本概念 198

10.2　欧几里得算法 201

10.3　整数的基底b展开算法 202

10.4　整数的计算机算术运算算法 203

习题 204

第11章　数论应用 206

11.1　一次同余式 206

11.2　一次同余式组 208

11.3　二次同余式和勒让德符号 211

11.4　雅可比符号 218

11.5　数论在计算机科学中的应用 220

习题 223

第五篇　代数结构 227

第12章　代数结构基本概念及性质 227

12.1　代数结构的定义与例 227

12.2　代数结构的基本性质 228

12.3 同态与同构 234

12.4 同余关系 241

12.5　商代数 243

12.6　积代数 245

习题 246

第13章　半群与群 248

13.1　半群和独异点的定义及性质 248

13.2　半群和独异点的同态与同构 251

13.3　积半群 254

13.4　群的基本定义与性质 254

13.5　置换群和循环群 257

13.6　子群与陪集 263

13.7　群的同态与同构 270

习题 274

第14　章环和域 277

14.1 环 277

14.2　子环与理想 279

14.3　环同态与环同构 283

14.4　域 285

14.5　有限域 286

习题 288

第15章　布尔代数 290

15.1　布尔代数的基本定义与性质 290

15.2　格 295

15.3　子布尔代数、积布尔代数和布尔代数同态 298

15.4　布尔代数的原子表示 299

15.5　布尔代数B2r 302

15.6　布尔表达式及其范式定理 304

习题 307

第六篇　图论 313

第16章　图的基本概念及其矩阵表示 313

16.1　图的基本概念 313

16.2　链（或路）与圈（或回路） 319

16.3　最短链与关键路 325

16.4　图的矩阵表示 328

习题 341

17.1 欧拉图与哈密尔顿图 345

第17章　几类重要的图 345

17.2　二部图 353

17.3　树 357

17.4　图的生成树 370

17.5　平面图 374

17.6　图的色数问题 381

习题 385

参考文献 388