《离散数学的理论和习题》求取 ⇩

第一篇 数理逻辑1

第一章 命题演算1

1.1 引言1

1.2 基本概念1

1.3 逻辑联词与命题公式2

1.4 永真复合命题的刻画5

1.5 简化真值表法10

1.6 对偶定律13

1.7 命题公式的范式15

第二章 命题演算的推理理论17

2.1 命题演算的语义推理与语法推理17

2.2 命题演算的公理化方法18

2.3 命题演算的性质23

第三章 一阶谓词30

3.1 谓词、客体和变元30

3.2 量词、约束变元和自由变元33

3.3 谓词代数38

第四章 一阶谓词演算的推理理论40

4.1 谓词公式的语义解释40

4.2 语义学的论证41

4.3 一阶谓词演算的公理化方法44

4.4 一阶谓词演算的性质49

4.5 例题52

4.6 包含等关系的一阶谓词演算公理系统61

第五章 机器推理技术67

5.1 命题演算的归结法原理67

5.2 合式谓词公式的斯科林范式68

5.3 谓词演算的归结法70

5.4 归结法与人工智能73

参考文献78

第二篇 集合论80

第一章 集合论的基本概念80

1.1 集合及其有关概念80

1.2 集合的相等和包含87

1.3 幂集89

1.4 集合的运算92

1.5 集合运算的定理和关系式98

1.6 有穷集合基数的运算105

1.7 有序偶和笛卡尔乘积109

第二章 关系114

2.1 关系及其性质114

2.2 关系的运算123

2.3 等价关系及其它135

2.4 偏序关系及其它143

第三章 函数149

3.1 函数的基本概念149

3.2 逆函数及函数的复合154

3.3 特征函数和模糊子集161

第四章 自然数和基数165

4.1 自然数与数学归纳法165

4.2 基数170

4.3 基数的比较175

第五章 递归函数178

5.1 递归函数及其特点178

5.2 初始函数和算子180

5.3 递归函数183

5.4 递归集合及递归谓词189

参考文献193

第三篇 图论194

第一章 基本术语194

1.1 引言194

1.2 有向图及无向图196

1.3 图的基本结构197

1.3 子图200

第二章 连通性203

2.1 可达性203

2.2 连通类205

2.3 顶点基和强分图208

2.4 块211

第三章 有向图的矩阵表示214

3.1 邻接矩阵214

3.2 可达性矩阵216

第四章 树220

4.1 树的一般定义220

4.2 根树与有序树222

4.3 二元树223

4.4 生成树227

4.5 割集229

第五章 穿程问题233

5.1 欧拉图233

5.2 哈密顿图236

第六章 二分图的匹配问题240

6.1 基本概念240

6.2 二分图的最大匹配242

6.3 从X到Y的匹配243

第七章 平面图及色数247

7.1 平面图247

7.2 色数252

第八章 通路问题256

8.1 最短通路256

8.2 最优通路260

8.3 关键通路267

参考文献267

第四篇 有限自动机理论269

第一章 有限自动机与基本概念269

1.1 独异半群269

1.2 有限自动机的定义270

1.3 有限自动机的等价性275

1.4 mealy机与moore机276

第二章 有限自动机的简化278

2.1 最小自动机的定义及性质278

2.2 S划分和格LM280

2.3 FA的最小化286

第三章 有限自动机的分析与综合293

3.1 关于有限自动机的功能293

3.2 正则序列集与正则表达式294

3.3 正则序列集与FA的关系297

3.4 非确定性FA300

3.5 由正则表达式构造FA的算法304

3.6 FA的综合311

第四章 FA理论在计算机科学中的应用315

4.1 FA理论与形式语言理论的关系315

4.2 FA理论在算法综合中的应用319

参考文献323

第五篇 代数系统324

第一章 基本概念324

1.1 代数系统324

1.2 同态和同构327

1.3 子代数和商代数328

2.1 半群的概念332

第二章 半群和群332

2.2 子半群和半群同态333

2.3 商半群和半群直积334

2.4 群的概念336

2.5 子群和群的同态338

2.6 变换群、置换群和循环群339

2.7 不变子群和商群341

3.1 环和域的概念346

第三章 环和域346

3.2 子环和环的同态348

3.3 理想和商环349

第四章 抽象数据类型代数规范初步352

4.1 标记、项和代数规范352

4.2 Σ-代数和范畴357

4.3 代数规范的初始语义358

参文考献361