离散数学PDF电子书下载

第1章　命题逻辑 1

1.1　命题及其表示法 1

1.1.1　命题与命题判别 1

1.1.2　命题的表示 2

练习 2

1.2　复合命题与联结词 2

1.2.1　原子命题与复合命题 2

1.2.2　命题联结词与其运算定义 3

练习 5

1.3　命题公式与真值表 6

1.3.1　命题公式 6

1.3.2　真值表 7

1.3.3　命题公式的类型 8

练习 9

1.4　等价与蕴含 9

1.4.1　等价及基本等价定律 9

1.4.2　等值演算 10

练习 13

1.5　最小联结词组与范式 14

1.5.1　最小联结词组 14

1.5.2　对偶 14

1.5.3　合取范式与析取范式 14

1.5.4　小项与主析取范式 15

1.5.5　大项与主合取范式 18

1.5.6 由范式判定公式性质 20

练习 20

1.6　推理理论 20

1.6.1　推理 20

1.6.2　有效结论及其证明 21

1.6.3　构造论证法 22

练习 25

本章小结 26

习题 27

第2章　谓词逻辑 29

2.1　谓词的概念与表示 29

练习 31

2.2　量词与谓词公式 31

2.2.1　量词与特性谓词 31

2.2.2　谓词公式 33

练习 34

2.3　谓词演算 35

2.3.1　谓词公式的赋值 35

2.3.2　谓词演算的等价式和蕴含式 35

练习 37

2.4　前束范式 37

练习 38

2.5　谓词演算的推理理论 38

练习 40

本章小结 41

习题 41

第3章　集合论基础 44

3.1　集合的基本概念和表示法 44

3.1.1　集合与元素 44

3.1.2　集合的相关概念及其表示 45

3.1.3　集合间的关系 46

3.1.4　幂集 47

练习 48

3.2　集合的运算 48

练习 51

3.3　集合计数 51

练习 53

本章小结 54

习题 55

第4章　计数理论 56

4.1　整数与除法 56

4.1.1 引言 56

4.1.2　除法与除法算法 56

4.1.3　素数 57

4.1.4　最大公约数和最小公倍数 58

4.1.5　欧几里德算法 60

4.1.6　模运算 61

4.1.7　同余应用 62

练习 64

4.2　矩阵 64

4.2.1 引言 64

4.2.2　矩阵运算 65

4.2.3　矩阵乘法算法 66

4.2.4　矩阵的转置和幂 66

4.2.5　0—1矩阵 67

练习 69

4.3　数学归纳法 70

4.3.1　数学归纳法的应用 70

4.3.2　数学归纳法的第二原理 71

练习 72

4.4　递归与递推 72

4.4.1　函数的递归定义 72

4.4.2　递归算法 73

4.4.3　递归与迭代 74

4.4.4　递推关系 75

4.4.5　求解递推关系 75

练习 80

4.5　基本的计数原则 81

4.5.1　加法规则和乘法规则 81

4.5.2　树图 83

4.5.3　鸽巢原理 83

练习 84

4.6　一般性的排列与组合 85

4.6.1　排列与组合 85

4.6.2　特殊的排列与组合 86

4.6.3　生成排列和组合 88

练习 91

本章小结 92

习题 94

第5章　关系与函数 96

5.1　关系 96

5.1.1　序偶与笛卡儿积 96

5.1.2　关系的定义 97

5.1.3　关系的表示 98

5.1.4　关系的运算 99

5.1.5　关系的性质 102

5.1.6　关系的闭包 106

5.1.7　沃舍尔算法（Warshall算法） 108

练习 110

5.2 函数 113

5.2.1　函数的概念 113

5.2.2　复合函数与逆函数 115

5.2.3　函数增长 116

练习 118

本章小结 119

习题 119

第6章　特殊关系 122

6.1　相容关系与覆盖 122

6.1.1　相容关系 122

6.1.2　覆盖 123

6.1.3　相容与覆盖的关系 123

练习 124

6.2　等价关系与划分 124

6.2.1　等价关系 124

6.2.2　划分与等价类 125

6.2.3　二者关系 126

练习 127

6.3　序关系 128

6.3.1　偏序 128

6.3.2　拟序 129

6.3.3　全序 129

6.3.4 良序 130

练习 130

6.4　格 130

6.4.1　偏序格 130

6.4.2　分配格 132

6.4.3　有补格 133

练习 134

本章小结 135

习题 136

第7章　代数系统 137

7.1　一般代数系统 137

7.1.1　集合上的运算 137

7.1.2　运算及其性质 138

练习 140

7.2　同构与同态 141

7.2.1　同构 141

7.2.2　同构系统的性质保持 142

7.2.3　同构关系 144

7.2.4 同态 144

7.2.5　同态系统的性质保持 146

练习 146

7.3　半群与独异点 146

练习 147

7.4　群与子群 148

7.4.1　群 148

7.4.2　子群 150

7.4.3　子群的陪集与拉格朗日定理 151

练习 152

7.5　格与布尔代数 152

7.5.1　格的基本定律 153

7.5.2　分配格、有界格与有补格 153

7.5.3　布尔代数 154

练习 156

本章小结 157

习题 159

第8章　图论 161

8.1　图的基本概念 161

练习 166

8.2　连通性 167

练习 171

8.3　图的矩阵表示 172

8.3.1　邻接矩阵 172

8.3.2　统计顶点之间的通路 173

8.3.3　可达性矩阵 175

8.3.4　关联矩阵 178

练习 179

8.4　欧拉图与汉密尔顿图 180

8.4.1　欧拉图 180

8.4.2　汉密尔顿图 182

练习 183

8.5 平面图 183

练习 186

8.6　树及应用 186

8.6.1 无向树 186

8.6.2　根树及其应用 188

练习 191

本章小结 192

习题 194

参考文献 196