离散数学

第1章命题逻辑1

1.1命题与联结词1

1.2合式公式及分类5

1.3等价式与等价演算8

1.4对偶式与蕴涵式11

1.5联结词的扩充与功能完全组14

1.6公式标准型范式17

1.7公式的主范式19

1.8命题逻辑的推理理论23

1.9归结原理在自动定理证明中的应用27

习题130

第2章谓词逻辑34

2.1个体谓词和量词34

2.2谓词公式与翻译36

2.3约束变元与自由变元38

2.4公式解释与类型40

2.5等价式与蕴涵式43

2.6谓词公式范式45

2.7谓词逻辑的推理理论46

习题249

第3章集合54

3.1集合论基础54

3.2集合运算及其性质57

3.3集合的笛卡儿积与无序积62

3.4有限集合的计数63

习题365

第4章关系67

4.1二元关系67

4.2关系运算71

4.3关系类型76

习题484

第5章函数87

5.1函数基本概念87

5.2函数类型89

5.3函数运算91

5.4基数93

习题596

第6章代数结构的概念及性质98

6.1代数结构的定义与例98

6.2代数结构的基本性质99

6.3同态与同构104

6.4同余关系109

6.5商代数111

6.6积代数113

习题6114

第7章半群与群116

7.1半群和独异点的定义及其性质116

7.2半群和独异点的同态与同构118

7.3积半群121

7.4群的基本定义与性质122

7.5置换群和循环群124

7.6子群与陪集128

7.7群的同态与同构134

7.8群码及在数字通信中的应用137

习题7144

第8章环和域146

8.1环146

8.2子环与理想148

8.3环同态与环同构151

8.4域152

8.5有限域154

习题8156

第9章格与布尔代数158

9.1格158

9.2布尔代数167

9.3子布尔代数、积布尔代数和布尔代数同态169

9.4布尔代数的原子表示170

9.5布尔代数173

9.6布尔表达式及其范式定理174

习题9177

第10章图的概念与表示180

10.1图的基本概念180

10.2链(或路)与圈(或回路)184

10.3图的矩阵表示189

10.4最短链与关键路198

习题10201

第11章几类重要的图204

11.1欧拉图与哈密尔顿图204

11.2二部图209

11.3树213

11.4平面图224

习题11229

第12章数论232

12.1数论基本概念232

12.2整数分解唯一性定理237

12.3模运算与同余238

12.4剩余类和剩余系240

12.5一次同余式和一次同余式组243

12.6数论在计算机科学中的应用247

习题12249

参考文献252

　　本书是笔者结合多年教学实践与科学研究，参考国内外教材，在力求通俗、简明、扼要的指导思想下编写而成的。力求做到“少而精”，注意突出重点，论证详细明了，便于自学。在加强基本理论教学的同时，注意了分析问题、解决问题的技能培养和训练。书中各知识点均配有典型例子，并加以说明。一方面每章有独立性，教师根据需要可以单独选讲几章；另一方面，尽可能注意各章之间联系。规范并统一了符号和术语。　　本书共12章，内容包括命题逻辑、谓词逻辑、集合、关系、函数、代数结构的概念及性质、半群与群、环和域、格与布尔代数、图的概念与表示、几类重要的图以及数论。　　全书编写力求通俗、简明、扼要。各章都配有典型例题和大量的习题，便于读者理解与掌握内容。　　本书可作为高等学校计算机及相关专业的教材，也可供相关技术人员学习参考。【作者简介】　　李盘林，大连理工大学计算机系教授。从教四十余年，为本科生、研究生讲授了十余门课程，主编主译著作十余本，其中离散数学荣获教育部于2002年颁发的全国高校优秀教材二等奖；主持科研十余项。其中有的达到世界先进水平，发表在计算机学报等刊物上的主要学术论文二十余篇，指导研究生四十余名；曾任《计算机丛书》、《理论计算机》、《现代教育技术》刊物的编委，以及“国家教委工科计算机课程教学指导委员会”和“辽宁省计算机基础教学指导委员会”委员。