离散数学教程PDF电子书下载

第1章　数理逻辑 1

1.1　命题逻辑的基本概念 1

1.1.1　命题的形式表示与逻辑连接词 1

1.1.2　逻辑表达式和等价式 6

1.1.3　命题常元、命题变元和命题公式 7

1.1.4　真值函数与真值表 7

1.1.5　等价式和永真隐含式 8

1.1.6　其他逻辑连接词 12

1.1.7　逻辑连接词及其完备功能集 14

1.1.8　对偶原理 15

1.1.9　范式 17

1.2　命题逻辑中的推理规则和证明方法 22

1.2.1 自然推理 22

1.2.2　证明方法 24

1.2.3　形式逻辑中的一些主要定律在数理逻辑中的表示 26

1.3　命题演算与公理系统 28

1.3.1　公理系统的基本概念 28

1.3.2　形式系统的基本概念 29

1.3.3　公理系统的基本要求 30

1.3.4　公理系统L 31

1.3.5 自然推理与公理系统推理 35

1.3.6　公理系统L的性质 37

1.3.7　其他命题逻辑公理系统 39

1.4　一阶谓词逻辑的基本概念 41

1.4.1　谓词及其符号化表示 42

1.4.2　量词与量化 43

1.4.3 一阶语言∮和谓词演算 44

1.4.4　变元的约束与辖域 46

1.4.5　谓词公式的解释 48

1.4.6　谓词演算中的等价式和永真隐含式 50

1.4.7　前束范式 53

1.5　谓词演算的推理规则与证明方法 54

1.5.1 自然推理 54

1.5.2　公理系统推理 57

1.5.3　公理系统K 58

1.5.4 K的合理性、一致性和完备性 59

1.6 自动定理证明与消解原理 61

1.6.1　概述 62

1.6.2 Herbrand理论 63

1.7 Robinson消解原理 73

1.7.1　命题逻辑中的消解原理 74

1.7.2　代换与合一算法 76

1.7.3　合一算法在谓词逻辑消解原理中的应用 78

1.7.4　删除策略 79

1.7.5　消解方法 80

1.8 Horn子句问题求解逻辑 84

第2章　集合 85

2.1　集合的基本概念和表示方法 85

2.1.1　元素与集合之间的“属于”关系 85

2.1.2　“概括性公理”与集合的描述法表示 87

2.1.3　“外延性公理”与集合的相等 87

2.1.4　集合之间的“包含”关系（？） 88

2.1.5　集合的幂集 89

2.2　集合的运算 91

2.2.1　集合的“并”、“交”、“差”、“补”运算 91

2.2.2　集合的环和、环积运算 92

2.2.3　集合运算的Venn氏图表示 93

2.2.4　集合的笛卡儿乘积和序偶 93

2.2.5　基数的概念与包含排斥原理 94

2.3　归纳定义与归纳证明 97

2.3.1 自然数域上函数的递归定义 98

2.3.2　构造性表达式的归纳定义 99

2.3.3 自然数的归纳定义 100

2.3.4 Peano公设 101

2.4　归纳证明 102

2.4.1　构造性表达式性质的证明 102

2.4.2 自然数集合上表达式性质的证明 103

2.4.3　数学归纳法第1推理规则 104

2.4.4　数学归纳法第1推理规则的变形 105

2.4.5　数学归纳法第2推理规则 105

2.5 语言的“并置”运算、“幂”运算和“闭包”运算 107

第3章　关系 111

3.1　关系的基本概念 111

3.1.1　关系及其数学定义 111

3.1.2　二元关系 112

3.1.3　关系矩阵和关系图 114

3.2　关系的性质 115

3.2.1　关系的性质 116

3.2.2　有关关系性质的总结 118

3.3　关系的复合运算 121

3.3.1　复合运算的定义 121

3.3.2　复合运算的图形表示 121

3.3.3　用关系矩阵实现关系复合 122

3.3.4　复合运算的性质 124

3.4　关系的幂运算 125

3.4.1　关系的幂运算 125

3.4.2　用关系图实现幂运算 125

3.5　逆关系及其性质 126

3.5.1　逆关系 126

3.5.2　逆关系的性质 127

3.6　关系的闭包运算 128

3.6.1　关系闭包的定义 129

3.6.2　关系闭包的求法 129

3.7　次序关系 132

3.7.1　偏序集合的哈斯图表示 133

3.7.2　偏序集合的特异元素 134

3.7.3　偏序集合特异元素的一些定理 135

3.7.4　线序集合和良序集合 136

3.7.5　词典序和标准序 137

3.7.6　拟序集合 138

3.8　等价关系与划分 138

3.8.1　等价关系 138

3.8.2　等价类及其性质 140

3.8.3　集合的覆盖与划分 141

3.8.4　划分与等价关系 142

3.9　相容关系 143

第4章　函数 145

4.1　基本概念 145

4.1.1 函数的定义与相等 146

4.1.2　函数诱导出的函数 147

4.1.3 f:X→Y表达的是一类函数 148

4.1.4　多元函数的表达 149

4.1.5 函数的归纳定义与递归定义 150

4.1.6　偏函数和函数的扩大与缩小 153

4.1.7　函数的复合 154

4.2　特殊函数类 155

4.2.1　映射的基本概念 155

4.2.2 几个常用的函数类 157

4.3　逆函数 161

4.4　置换 163

4.5　运算 164

第5章　无限集和基数 169

5.1　无限集的基本概念 169

5.2　可数集与不可数集 172

5.3　不可数无限集及其基数 175

5.4　基数的比较 178

5.4.1　基数的相等与次序关系 178

5.4.2　有关基数的一些定理 180

5.5　无限集合的特性 183

第6章　代数系统 187

6.1　代数系统的组成与分类 188

6.2　代数系统的公理 189

6.3　代数运算的规则和特异元素 190

6.4　子代数 194

6.5　常见代数系统的实例 194

6.6　代数系统的同构与同态 197

6.6.1　同构的定义 197

6.6.2　同构的例子 200

6.6.3　同构的性质 202

6.6.4　同态的定义 204

6.6.5　同态的实例 205

6.6.6　同态的性质 206

6.7　同余关系 211

6.8　商代数和积代数 215

第7章　群、环和域 221

7.1　半群和独异点 221

7.1.1　半群和独异点的概念 221

7.1.2　循环含幺半群和生成元 223

7.1.3　半群和独异点的同态与同构 226

7.2　群 228

7.2.1　群的定义 229

7.2.2　群的基本性质 230

7.2.3　群的同态与同构 233

7.2.4　置换群 237

7.2.5　循环群 240

7.2.6　子群的定义与判定 242

7.2.7　子群的陪集与拉格朗日定理 244

7.2.8　正规子群和商群 248

7.3　环和域 249

7.3.1　环的基本概念 249

7.3.2　整环、体和域的基本概念 252

7.3.3　子环与理想的基本概念 255

第8章　格与布尔代数 259

8.1　格是满足一定条件的偏序集合 259

8.1.1 基本定义 259

8.1.2　格的对偶性原理和基本性质 262

8.1.3　“保交”、“保联”运算的性质 263

8.2　格是满足一定公理的代数系统 268

8.3　子格与格的积代数 270

8.4　格的同态与同构 272

8.5　特殊格 274

8.5.1 有补格 275

8.5.2　分配格 276

8.5.3　有补分配格的性质 278

8.6　布尔代数 279

8.6.1　布尔代数的基本定义与性质 279

8.6.2　子布尔代数 281

8.6.3　布尔同态 282

8.6.4　有限布尔代数的原子表示 282

8.6.5　布尔代数的积代数 286

8.6.6　布尔函数 286

第9章 图论 289

9.1　图的基本概念 289

9.1.1 图的定义 289

9.1.2　图论中的名词汇集及其解释 290

9.1.3　结点的次数 292

9.1.4　子图与图的同构 293

9.2　路径和回路 295

9.2.1　基本概念 295

9.2.2　可达性与连通性的概念 297

9.2.3　欧拉路径与欧拉循环 299

9.2.4　哈密屯路径与哈密屯循环 300

9.3　图的矩阵表示 302

9.3.1　邻接矩阵 302

9.3.2　矩阵运算 303

9.3.3　可达性的矩阵运算 305

9.4　平面图 306

9.4.1　库拉托夫斯基定理 306

9.4.2　欧拉公式 307

9.5　二部图（偶图） 309

9.6　树 309

9.7　根树（有向树） 311

9.7.1　根树的性质 312

9.7.2　根树在语法分析中的应用 313

9.7.3　根树在运算表达式表示中的应用 313

9.7.4　根树在前缀码表示中的应用 314

9.7.5　根树在搜索、决策和博弈问题中的应用 315

9.8　支撑树和割集 317

第10章　模型论浅述 319

10.1　逻辑科学的发展概要 319

10.2　数理逻辑的形成与发展 319

10.2.1　从莱布尼兹到布尔 320

10.2.2　数学公理化运动 320

10.2.3　从罗素悖论到希尔伯特方案 320

10.2.4　哥德尔不完全性定理 322

10.3　模型论的发展历史 322

10.4　模型论的研究内容 323

10.5　模型论的研究方法 326

10.5.1　一阶语言的语法 327

10.5.2　一阶语言的语义 329

参考文献 332