离散数学PDF电子书下载

第1篇　数理逻辑 3

第1章　数理逻辑 3

1.1　命题及命题联结词 3

1.1.1　命题 3

1.1.2　命题联结词 4

1.1.3　命题的符号化 5

1.2　命题公式及命题公式之间的逻辑关系 6

1.2.1　命题公式的定义 7

1.2.2　公式的解释 7

1.2.3　真值表 8

1.2.4　公式的分类 9

1.2.5　公式之间的逻辑关系 9

1.3　谓词与量词 14

1.3.1　个体 14

1.3.2　谓词 14

1.3.3　量词 15

1.3.4　命题的符号化 16

1.4　谓词公式及谓词公式之间的逻辑关系 18

1.4.1　谓词逻辑中的合法符号 18

1.4.2　项 18

1.4.3　谓词公式 19

1.4.4　有关谓词公式的概念 19

1.4.5　谓词公式的解释 20

1.4.6　谓词公式的分类 21

1.4.7　谓词公式之间的逻辑关系 22

1.5　范式 25

1.5.1　主析（合）取范式 25

1.5.2　前束范式 32

1.6　数理逻辑推理理论 33

1.6.1　命题逻辑推理理论 33

1.6.2　谓词逻辑推理理论 38

1.7　命题逻辑推理系统N 43

1.7.1　什么是形式系统 43

1.7.2　命题逻辑推理系统N 43

1.7.3　N中的一些基本定理 45

1.8　谓词逻辑推理系统NL 47

1.8.1　NL的构造 47

1.8.2　NL中的形式证明 48

1.8.3　NL中的一些基本定理 49

小结 51

习题一 51

习题二 54

第2章　非经典逻辑介绍 57

2.1　模态逻辑 57

2.1.1　模态 57

2.1.2　模态命题的形式化 58

2.1.3　模态命题形式之间的逻辑关系 59

2.2　多值逻辑 60

2.2.1　卢卡西维茨的多值逻辑系统 61

2.2.2　另外一些多值逻辑系统 63

2.3　非单调逻辑 64

2.4　模糊逻辑 65

2.5　道义逻辑 67

2.5.1　道义逻辑系统 67

2.5.2　道义逻辑的等值式与蕴含式 69

小结 69

习题一 69

第2篇　关系 75

第3章　集合基础 75

3.1　集合的概念和表示法 75

3.1.1　集合与元素 75

3.1.2　集合的表示 76

3.2　集合的关系 77

3.2.1　元素的属于关系 77

3.2.2　集合的包含关系 78

3.2.3　集合的相等关系 78

3.2.4　空集 79

3.2.5　全集 79

3.2.6　幂集 80

3.3　集合的基本运算 80

3.3.1　集合的并（∪）、交（∩） 80

3.3.2　集合的差集（—）和绝对补集（～） 81

3.3.3　集合的对称差集（？） 82

3.3.4　集合运算的基本性质 82

3.4　包含排斥原理 84

小结 86

习题一 86

习题二 88

第4章 关系 90

4.1　笛卡儿积与序偶 90

4.2　二元关系的定义和表示 91

4.2.1　二元关系的定义 91

4.2.2　几种特殊关系 92

4.2.3　几种常用的关系 92

4.2.4　关系的表示法 93

4.3　关系的运算 94

4.3.1　定义域、值域、域 94

4.3.2　关系的交、并、补、差运算 95

4.3.3　关系逆运算 96

4.3.4　关系的复合运算 96

4.3.5　关系运算的性质 96

4.3.6　关系的幂运算 97

4.3.7　特殊关系运算 98

4.4　关系的性质 99

4.5　关系的闭包 103

4.5.1　关系闭包的定义 104

4.5.2　关系闭包的构造 104

4.5.3　关系闭包的性质 106

4.6　等价关系与集合的划分 107

4.6.1　集合的覆盖和划分 107

4.6.2　等价关系 107

4.6.3　等价类和商集 108

4.7　偏序关系与偏序集 110

4.7.1　偏序关系的定义 110

4.7.2　序关系 111

4.7.3　偏序关系的哈斯图 112

4.7.4　偏序集中的特殊元素 113

小结 114

习题一 115

习题二 117

第5章 函数 120

5.1　函数的概念 120

5.2　函数的性质 121

5.3　函数的运算 124

小结 126

习题一 127

习题二 127

第3篇　图论 131

第6章　图论中的基本概念 131

6.1 图与图形 131

6.2　图论中的术语 132

6.2.1　一些图的基本概念和常用术语 132

6.2.2　子图 134

6.2.3　补图 135

6.3　同构 135

6.4　图的连通性 138

6.4.1　通路和回路 138

6.4.2　无向图的连通性 139

6.4.3　有向图的连通性 142

6.5　图的矩阵表示 143

6.5.1　有向图的邻接矩阵 143

6.5.2　有向图的可达矩阵 145

6.5.3　无向图的关联矩阵 145

小结 147

习题一 147

习题二 149

第7章　特殊图 151

7.1　欧拉图 151

7.2　哈密尔顿图 153

7.3　二部图 155

7.4　平面图 159

7.4.1　平面图的基本概念 159

7.4.2　欧拉公式 160

7.4.3　图的可平面性 161

7.5　无向树 162

7.5.1　无向树的概念及性质 163

7.5.2　最小生成树 164

7.6　根树 167

7.7　图的应用 172

7.7.1　计算机鼓轮设计 172

7.7.2　巡回售货员问题 173

7.7.3　关键路径问题 174

7.7.4　通信网络 176

7.7.5　前缀码问题 177

小结 179

习题一 179

习题二 183

第4篇　代数系统 187

第8章　代数系统 187

8.1　代数运算及性质 187

8.1.1　代数运算 187

8.1.2　代数系统的定义 188

8.1.3　几个特殊的代数系统 189

8.2　二元运算的性质 190

8.3　代数系统中的特殊元素 190

8.3.1　幂等元和消去元 190

8.3.2　幺元 191

8.3.3　零元 192

8.3.4　逆元 193

8.4　同态与同构 195

小结 199

习题一 199

习题二 201

第9章　几个特殊的代数系统 203

9.1　群论 203

9.1.1　群的定义 203

9.1.2　群的性质 207

9.1.3　特殊群 209

9.1.4　群的同态 213

9.2　环与域 214

9.2.1　环的定义 214

9.2.2　交换律、单位元、零因子、整环 215

9.2.3　除环与域 217

9.3　格与布尔代数 219

9.3.1　格的概念 219

9.3.2　同构格 221

9.3.3　格的性质 221

9.3.4　特殊的格 223

9.3.5　布尔代数 224

小结 226

习题一 227

习题二 229

第5篇　组合分析初步 233

第10章　排列与组合 233

10.1　加法原理与乘法原理 233

10.1.1　加法原理 233

10.1.2　乘法原理 234

10.1.3　加法原理与乘法原理的应用 235

10.2　排列与组合 236

10.2.1　集合的排列 236

10.2.2　集合的组合 239

10.2.3　多重集的排列 242

10.2.4　多重集的组合 244

小结 246

习题一 246

习题二 248

第11章　鸽巢原理 249

11.1　鸽巢原理 249

11.1.1 问题的引入 249

11.1.2　鸽巢原理的基本形式 249

11.1.3　鸽巢原理的推广 251

11.2　鸽巢原理的应用 253

11.2.1　制造鸽巢是应用鸽巢原理的关键 253

11.2.2　较复杂问题举例 254

小结 256

习题一 257

习题二 257

附录　各章习题二答案 258

参考文献 265