《离散数学》PDF下载

  • 购买积分:11 如何计算积分?
  • 作  者:金聪,郭京蕾编著
  • 出 版 社:北京:清华大学出版社
  • 出版年份:2010
  • ISBN:9787302204046
  • 页数:259 页
图书介绍:本书为离散数学的基础教材。全书分为4篇,分别为数理逻辑、集合论、代数系统和图论。内容包括命题逻辑、谓词逻辑、集合的基本概念和运算、关系、函数、代数系统一般性质、典型的代数系统、图的基本概念、欧拉图和哈密顿图、特殊图。

第1篇 数理逻辑 3

第1章 命题逻辑 3

1.1命题与连接词 3

1.1.1命题的概念 3

1.1.2逻辑连接词 4

1.2命题公式及命题公式的翻译 7

1.2.1命题公式 7

1.2.2命题的翻译 7

1.2.3命题公式的解释 8

1.3等价公式及公式的分类 10

1.3.1等价公式的定义和性质 10

1.3.2基本等价公式 11

1.3.3置换规则 11

1.3.4公式的分类 12

1.4蕴含式与对偶式 14

1.4.1蕴含式 14

1.4.2对偶式 16

1.5其他连接词与最小连接词组 18

1.5.1其他连接词 18

1.5.2最小连接词组 19

1.6范式 20

1.6.1简单合取式与简单析取式 21

1.6.2公式的范式 21

1.7公式的主范式 22

1.7.1主析取范式 23

1.7.2主合取范式 25

1.7.3主析取范式与主合取范式之间的关系 28

1.7.4主范式的应用 29

1.8推理理论 29

1.8.1有效论证 30

1.8.2推理方法 30

习题 34

第2章 谓词逻辑 38

2.1谓词逻辑的基本概念 38

2.1.1个体、谓词 38

2.1.2命题函数 39

2.1.3量词 39

2.2谓词公式与翻译 40

2.2.1谓词公式 40

2.2.2谓词公式的翻译 41

2.3约束变元与自由变元 42

2.4谓词演算的等价式及蕴含式 44

2.4.1量词的转换律 44

2.4.2量词辖域的扩张律与收缩律 45

2.4.3量词的分配律 46

2.4.4多个量词的使用 47

2.5前束范式 48

2.6谓词演算的推理理论 50

2.6.1推理规则 50

2.6.2推理实例 51

习题 55

第2篇 集合论 61

第3章 集合的基本概念和运算 61

3.1集合的基本概念 61

3.2集合的基本运算 63

3.2.1集合的运算 63

3.2.2集合运算算律 65

3.3集合中元素的计数 66

3.3.1容斥原理 66

3.3.2容斥原理实例 69

3.4笛卡儿乘积 70

3.4.1有序对 70

3.4.2笛卡儿积 71

3.4.3 n阶笛卡儿积 73

习题 74

第4章 关系 77

4.1关系的概念 77

4.2关系的表示与性质 79

4.2.1关系的矩阵表示 79

4.2.2关系的图形表示法 79

4.2.3关系的性质 80

4.3关系的运算 81

4.3.1关系的逆运算 81

4.3.2关系的合成运算 83

4.4关系的闭包运算 86

4.5相容关系与覆盖 91

4.5.1关系图法 93

4.5.2关系矩阵法 93

4.6等价关系与划分 94

4.7偏序关系 96

习题 100

第5章 函数 106

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

5.1.1函数的定义 106

5.1.2函数的性质 108

5.2函数的复合与反函数 113

5.2.1函数的复合运算 113

5.2.2函数的逆运算 115

习题 118

第3篇 代数系统 123

第6章 代数系统一般性质 123

6.1二元运算及其性质 123

6.1.1二元运算 123

6.1.2二元运算律 125

6.1.3二元运算特殊元 126

6.1.4二元运算实例 128

6.2代数系统 130

6.3代数系统的同态与同构 132

6.3.1同态与同构 132

6.3.2同态与同构实例 133

6.3.3同态与同构的性质 136

6.4同余关系与商代数 136

6.4.1同余关系 136

6.4.2商代数 137

习题 137

第7章 典型的代数系统 141

7.1半群与群 141

7.1.1半群与独异点 141

7.1.2群的定义与性质 144

7.1.3子群 147

7.1.4陪集与拉格朗日定理 150

7.1.5正规子群与商群 155

7.1.6群的同态与同构 157

7.1.7循环群 158

7.1.8置换群 161

7.2环和域 164

7.2.1环的定义 164

7.2.2整环与域 165

7.2.3环的性质 166

7.2.4子环、理想与商环 168

7.3格与布尔代数 169

7.3.1格的定义与性质 169

7.3.2子格与格同态 172

7.3.3分配格 174

7.3.4有补格 175

7.3.5布尔代数 175

习题 178

第4篇 图论 185

第8章图 185

8.1图的基本概念 185

8.1.1图的定义 185

8.1.2子图 190

8.1.3图的同构 191

8.1.4图的运算 192

8.2图的连通性 193

8.2.1通路和回路 193

8.2.2图的连通性 195

8.2.3图的连通度 198

8.3图的矩阵表示 200

8.3.1图的关联矩阵 200

8.3.2图的邻接矩阵 201

8.3.3图的可达矩阵 204

习题 206

第9章 欧拉图和哈密顿图 209

9.1欧拉图 209

9.1.1欧拉图的引入和定义 209

9.1.2欧拉图的判定 211

9.1.3欧拉图的难点 214

9.1.4欧拉图的应用 215

9.2哈密顿图 219

9.2.1哈密顿图的引入和定义 219

9.2.2哈密顿图的判定 220

9.2.3哈密顿图的难点 226

9.2.4哈密顿图的应用 227

习题 229

第10章 特殊图 233

10.1树 233

10.1.1树的定义与性质 233

10.1.2生成树 236

10.1.3最小生成树 237

10.1.4根树定义与分类 239

10.1.5最优树与哈夫曼算法 242

10.2二分图 243

10.2.1二分图的引入和定义 243

10.2.2二分图的判定 243

10.2.3匹配 245

10.3平面图 249

10.3.1平面图的引入和定义 249

10.3.2平面图的欧拉公式 251

10.3.3平面图判定 253

10.3.4平面图的对偶图 253

10.3.5平面图的可着色性 254

10.3.6平面图的应用 256

习题 256

参考文献 259