《离散数学引论》求取 ⇩

前言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