离散数学引论PDF电子书下载

前言 1

第一章 基本概念 4

1 引言 4

2 命题 8

3 命题连接词 12

4 集合 14

5 量词 21

6 字母表与字 22

7 次序 24

8 计算程序 26

9 算法 28

10 逻辑运算与布尔矩阵 30

习题一 33

1 关系 36

第二章 关系与函数 36

2 关系的图形表示和矩阵表示 38

3 关系的运算 41

4 关系的性质 45

5 关系的闭包运算 50

6 等价关系 54

7 序关系 59

8 函数 67

9 两个集合之间的一一对应 73

习题二 74

第三章 信息图 78

1 基本概念与术语 78

2 路与连通性 80

3 无向图、加权图、多重图及同构 82

4 图的一些基本性质 86

5 图的矩阵表示 88

6 欧拉通路与汉密尔顿通路 98

7 根树 108

8 根树的应用 113

9 无向树 118

10 生成树与割集 119

习题三 122

第四章 代数系统与布尔代数 126

1 基本概念 126

2 群 134

3 环与域 138

4 格 140

5 布尔代数 143

6 二值布尔代数 148

7 逻辑结构 151

习题四 153

第五章 命题演算 156

1 原始符号及形成规则 156

2 形式公理与形式推演规则 160

3 形式证明与形式定理 161

4 形式推演 163

5 演绎定理 170

6 归谬律及反证法 174

7 斜式证明法 175

8 一些重要的形式定理 178

9 等值词 188

10 范式 189

习题五 194

1 原始符号与形成规则 196

第六章 谓词演算 196

2 形式公理与形式推演规则 201

3 形式证明与形式定理 203

4 形式推演 205

5 演绎定理 207

6 辅助导出规则 213

7 一些重要的形式定理 214

8 前束范式 224

习题六 227

第七章 一阶逻辑的语义与模型 228

1 真值概念 228

2 一致性与完全性 231

3 判定问题 234

4 真值表方法 235

5 检查范式法 237

6 分支法 239

7 归结法 246

8 论域与模型 249

9 归结法(续) 252

10 一阶逻辑的基本定理 254

习题七 256

第八章 形式语言与形式文法 257

1 形式命题语言 257

2 形式文法 258

3 文法的类型 263

4 1型文法的递归性 266

5 2型文法的派生树 269

6 3型文法的状态图 271

习题八 274

1 基本概念 275

第九章 有穷自动机 275

2 状态图 278

3 状态输出机 282

4 有穷自动机的简化 287

5 有穷识别器与正规语言 295

6 有穷识别器的模型 302

习题九 303

第十章 图灵机器 305

1 引言 305

2 指令形式的图灵机 307

3 图灵机的四元有序组形式 315

4 两种图灵机的等价性 321

5 可计算函数 324

6 图灵识别器 343

习题十 345

1 初等形式系统举例 346

第十一章 初等形式系统与递归关系 346

2 初等形式系统的定义 348

3 可表达性 350

4 形式命题集合的形式可表达性 354

5 命题演算中定理集合的形式可表达性 354

6 正整数的递归可枚举集合 356

7 哥德尔数 357

8 形式可表达的集合在存在可定义下的封闭性 358

9 存在可定义的几个实例 360

10 某些基本关系的递归可枚举性 362

11 递归函数 363

12 车赤论题与图灵论题 365

习题十一 367

参考文献 368