《离散数学》求取 ⇩

第一篇 数理逻辑5

第一章 命题逻辑5

1.1 命题和联结词6

1.2 公式和真值赋值10

1.3 等值演算16

1.4 对偶定理19

1.5 联结词的完全集21

1.6 范式25

1.7 逻辑推论30

习题32

第二章 谓词逻辑39

2.1 谓词和量词39

2.2 项和公式45

2.3 解释和赋值50

2.4 永真式59

2.5 等值演算64

2.6 逻辑推论69

习题71

第三章 公理系统75

3.1 命题逻辑的公理系统76

3.2 谓词逻辑的公理系统82

习题89

第四章 归结法原理91

4.1 命题逻辑的归结法91

4.2 前束范式与斯科伦范式97

4.3 谓词逻辑的归结法100

习题110

参考文献113

名词索引114

第二篇 集合论123

第五章 集合的基本概念及其运算123

5.1 集合与元素123

5.2 集合间的相等和包含关系125

5.3 幂集129

5.4 集合的运算131

5.5 有穷集的计数原理140

5.6 集合的归纳定义法142

5.7 有序偶和笛卡儿乘积148

习题151

第六章 关系154

6.1 关系及其性质154

6.2 关系的运算160

6.3 次序关系169

6.4 等价关系、划分及其它174

习题181

第七章 函数186

7.1 基本概念186

7.2 函数的复合192

7.3 特殊性质的函数196

7.4 集合的特征函数201

习题203

第八章 自然数和基数207

8.1 自然数及数学归纳法207

8.2 基数212

习题221

名词索引223

9.1 有向图及无向图229

第九章 基本概念229

第三篇 图论229

9.2 图的基本结构232

9.3 子图236

9.4 连通性239

9.5 顶点基和强分图248

习题253

第十章 通路问题257

10.1 最短通路257

10.2 关键通路261

习题266

第十一章 图的矩阵表示268

11.1 邻接矩阵268

11.2 有向图的可达性矩阵272

11.3 关联矩阵276

习题277

第十二章 树279

12.1 树的一般定义279

12.2 根树与有序树282

12.3 二元树284

12.4 生成树290

12.5 割集294

习题297

第十三章 穿程问题300

13.1 欧拉图300

13.2 哈密顿图305

习题309

第十四章 二分图的匹配问题311

14.1 基本概念311

14.2 二分图的最大匹配314

14.3 从X到Y的匹配317

习题320

第十五章 平面图及色数322

15.1 平面图322

15.2 色数330

习题335

参考文献337

名词索引338

16.1 代数系统343

第十六章 基本概念343

第四篇 代数系统343

16.2 同态和同构347

16.3 子代数和商代数349

习题353

第十七章 半群和群354

17.1 半群的概念354

17.2 子半群和半群同态356

17.3 商半群和半群直积357

17.4 群的概念359

17.5 子群和群的同态362

17.6 变换群、置换群和循环群365

17.7 不变子群和商群367

习题373

第十八章 环和域375

18.1 环和域的概念375

18.2 子环和环的同态378

18.3 理想和商环379

习题382

19.1 格的定义与基本性质384

第十九章 格和布尔代数384

19.2 子格和格的同态387

19.3 布尔代数388

19.4 布尔代数的表示391

习题394

第二十章 抽象数据类型的代数规范395

20.1 标记、项和代数规范395

20.2 Σ--代数和范畴402

20.3 代数规范的初始语义404

习题407

参考文献409

名词索引410

第五篇 有限自动机理论415

第二十一章 基本概念415

21.1 字符表、字符串及其集合的运算415

21.2 有限自动机的定义416

21.3 有限自动机的等价423

21.4 Mealy机与Moore机424

习题429

22.1 最小有限自动机的定义及性质431

第二十二章 有限自动机的简化431

22.2 状态集的S划分和格LM434

22.3 有限自动机的最小化443

习题451

第二十三章 有限自动机和正则表达式453

23.1 有限自动机的识别功能453

23.2 非确定有限自动机455

23.3 正则表达式460

23.4 由正则表达式构造FA的算法463

23.5 有限自动机和正则表达式的等价性472

23.6 正则集合及其性质476

习题478

第二十四章 有限自动机的综合与应用481

24.1 有限自动机的综合481

24.2 FA理论在算法设计中的应用487

24.3 FA理论与形式语言理论的关系492

习题498

参考文献499

名词索引500