|
关于我们
 书单推荐 新书推荐 |
离散数学简明教程 
定 价：39.5 元
9 7 4 8 6 7 0 3 6 0 2 2 6 
离散数学是研究离散量的结构和相互间关系的学科，是计算机、软件工程等专业的理论基础.
本书依据教育部计算机科学与技术教学指导委员会编制的《高等学校计算机科学与技术专业规范》和《高等学校计算机科学与技术专业核心课程教学实施方案》进行编写，简要介绍离散数学的集合论、抽象代数、图论和数理逻辑4个部分，主要包括集合及其运算，关系，函数，代数系统，群、环和域，格和布尔代数，图与树，特殊图，命题逻辑，谓词逻辑共10章，“整数的整除与同余”一章作为预备知识供学习集合论和代数系统部分时参考.由于教材以集合论开头，便于学生学习时循序渐进，同时由于教材内容简明扼要，例题和习题多且包含一些实际应用问题，从而可以调动学生的学习积极性，培养学生的数学思维和解决实际问题的能力，为后续专业课程的学习奠定良好的基础.
本书可作为高等院校计算机、软件工程及相关专业本科生“离散数学”课程的教材，也可供从事计算机、软件工程及相关领域研究和应用开发人员自学或参考.
离散数学是研究离散量的结构和相互间关系的学科，是计算机、软件工程等专业的理论基础。本书依据教育部计算机科学与技术教学指导委员会编制的《高等学校计算机科学与技术专业规范》和《高等学校计算机科学与技术专业核心课程教学实施方案》进行编写，简要介绍了离散数学的集合论、抽象代数、图论和数理逻辑4个部分，主要包括集合及其运算，关系，函数；代数系统，群、环和域，格和布尔代数；图与树，特殊图；命题逻辑，谓词逻辑等十章，“整数的整除与同余”一章作为预备知识供学习代数系统部分时参考。由于教材以集合论开头，便于学生学习时循序渐进，同时由于教材内容简明扼要，例题和习题多且包含一些实际应用问题，从而可以调动学生的学习积极性，培养学生的数学思维和解决实际问题的能力，为后续专业课程的学习奠定良好的基础。
本书是作者根据多年从事离散数学课程教学实践，并在参阅国内外优秀经典教材的基础上编写完成的。 主要特色如下： （1）内容简明扼要，便于自学； （2）符号统一规范； （3）例题侧重应用实际； （4）习题由易到难分层编排。
离散数学是相对于连续数学而言的.从数学的发展历程来看，最开始的数学是离散的数学，如计数；后面出现微积分这样连续的数学；随着计算机的出现，离散数学重新找到了它应有的位置.
广义来讲，离散数学包括两个方面，一个是连续数学的离散化，即计算数学或数值分析的研究内容；另一个就是离散量自身的研究内容.一般而言，离散数学是研究离散量的结构和相互间关系的学科.离散结构则是离散数学和组合数学的统称. 离散数学是计算机、软件工程专业的一门核心基础课程，其主要作用如下： （1）离散数学为后继专业课程如数据结构、数据库原理、数字逻辑、信息安全、编译原理、人工智能、操作系统等提供必要的数学基础； （2）离散数学为从事计算机科学各方面的工作以及解决计算机科学中遇到的实际问题等提供有力的工具； （3）离散数学是现代数学的一个重要分支，通过该课程的学习可以提高逻辑思维与抽象思维能力、创造性思维能力以及分析和解决实际问题的能力等，培养出高素质的人才. 离散数学课程的主要内容可以分为4个部分，其导图如下.课程以离散量为研究对象，内容丰富，涉及面宽，具有4个主要的特点：以集合论为基础；高度的抽象性；推理的严密性；应用的广泛性. 本课程概念多、定理多、推理多，并且内容较为抽象.但由于它是为后继专业知识的学习做必要的数学准备的，因此它研究的内容均比较基础，难度不大.在学习离散数学的过程中，不必过分关注它的用处以及它在计算机学科中所起的作用，而应从以下几个方面入手，力争学好本课程的全部内容. （1）熟读教材，重于细节.这是学好离散数学不可缺少的一环，要准确理解各个概念和定理的含义，要看懂必要的推理过程. （2）独立思考，加强练习.在熟读教材的基础上，必须通过练习、独立思考来真正获取知识.（3）注重抽象思维能力的培养.要学好这门课程，必须具有较强的抽象思维能力，才能深入掌握课程内容.证明技巧的训练，可以促进推理技能的提高、逻辑抽象的深入、思维方式的严谨和理解能力的增强. 本教材是编者根据多年从事离散数学课程教学实践，并在参阅国内同行编著的多本教材的基础上编写完成的，特别是在教学中一直选用洪帆教授主编的《离散数学基础》组织教学，因此受到了许多潜移默化的影响，在此表示衷心的感谢.教材的编写得到了华中科技大学教材建设项目的资助和清华大学出版社的支持，在此一并表示衷心的感谢. 讲授本教材的基本部分约需64～80学时.教材习题分为A类题和B类题两类，其中B类题多为知识拓展和难度较大的综合题，供学习者选做.另有思考题散布于教材内容之中.教材还配有电子教案，与教材配套的习题解答也在整理之中. 限于编者的水平，书中错误和疏漏之处在所难免，敬请读者不吝指正. 编者2017年4月于武汉
卢力，博士，华中科技大学软件学院副教授，硕士研究生导师。主持和参加过多项科研课题的研究工作，近几年发表科研论文二十余篇，主要研究方向是高性能计算、图像信号处理、信息安全等。讲授过多门本科生和研究生的公共基础课、专业基础课和专业课。近年来主要为本科生讲授“离散数学”、“数学建模”等课程。是湖北省高等学校省级精品课程：“软件项目管理与分析”成员。出版《线性代数学习与考试指导》和华中科技大学网络教育视频课件系列: 线性代数。
第0章整数的整除与同余1
0.1整除及带余除法1
0.1.1整数1
0.1.2整除的概念与性质2
0.1.3带余除法3
0.1.4整数的进制表示法4
0.1.5数学归纳法7
0.2整数分解8
0.2.1最大公因数及其性质8
0.2.2欧几里得算法10
0.2.3因式分解法11
0.3同余15
0.3.1同余的概念和性质15
0.3.2线性同余方程18
0.3.3中国剩余定理20
0.3.4威尔逊定理、欧拉定理与费马小定理22
习题25
第1篇集合论27
第1章集合及其运算29
1.1集合的基本概念29
1.1.1集合和元素29
1.1.2集合的表示方法30
1.1.3集合的基数31
1.2集合间的关系31
1.2.1集合的包含31
1.2.2集合的相等32
1.2.3维恩图32
1.2.4幂集33
1.2.5有限集合幂集元素的编码表示341.3集合的运算和运算定律34
1.3.1集合的运算34
1.3.2集合运算的定律35
1.3.3集合恒等式的证明方法37
1.3.4包含排斥原理39
1.4集合成员表40
1.4.1并、交和补集的成员表40
1.4.2有限个集合产生的集合的成员表40
1.4.3利用集合成员表证明集合恒等式41
1.5集合的覆盖与分划42
1.6集合的标准形式43
1.6.1最小集标准形式43
1.6.2最大集标准形式46
1.6.3集合范式的说明47
1.7多重集合49
习题49
第2章关系54
2.1笛卡儿积与关系54
2.1.1笛卡儿积54
2.1.2关系的基本概念56
2.2关系的表示方法57
2.2.1集合表示法57
2.2.2矩阵表示法58
2.2.3关系图表示法58
2.3关系的运算59
2.3.1关系的并、交、差、补运算59
2.3.2关系的逆运算60
2.3.3关系的复合运算61
2.4关系的性质66
2.4.1关系性质的定义66
2.4.2关系性质的判别67
2.5关系的闭包702.5.1关系闭包的定义70
2.5.2关系闭包的性质72
2.5.3关系闭包的求法74
2.6等价关系77
2.6.1等价关系的基本概念77
2.6.2等价类的性质78
2.6.3等价关系与分划79
2.6.4等价关系的其他性质80
2.7相容关系81
2.7.1相容关系的基本概念81
2.7.2相容关系与覆盖82
2.8偏序关系84
2.8.1偏序关系的基本概念84
2.8.2偏序关系的次序图84
2.8.3偏序集的特殊元素85
2.8.4全序和良序87
习题88
第3章函数95
3.1函数及性质95
3.1.1函数的基本概念95
3.1.2函数的性质97
3.2复合函数99
3.2.1复合函数的定义99
3.2.2函数复合运算的性质100
3.2.3复合函数的性质101
3.3逆函数103
3.3.1逆函数的定义103
3.3.2逆函数的性质104
3.3.3左、右逆函数105
3.4无限集的基数106
3.4.1抽屉原理106
3.4.2集合的等势107
3.4.3可数集的基数1083.4.4不可数集的基数111
3.4.5集合基数的比较112
习题114
第2篇抽象代数119
第4章代数系统121
4.1代数运算121
4.1.1代数运算的概念121
4.1.2二元运算的性质123
4.1.3特殊元素124
4.2代数系统与子代数128
4.2.1代数系统的概念128
4.2.2子代数的概念129
4.3代数系统的同态与同构130
4.3.1代数系统的同态130
4.3.2满同态的性质132
4.3.3同构的性质132
4.4代数系统的积代数134
习题135
第5章群、环和域139
5.1半群和独异点139
5.1.1半群和独异点的基本概念139
5.1.2子半群和子独异点142
5.1.3半群和独异点的同态143
5.2群143
5.2.1群的基本概念143
5.2.2群的基本性质146
5.2.3群的同态148
5.3置换群与循环群148
5.4子群及其陪集152
5.4.1子群的定义1525.4.2子群的判别153
5.4.3陪集与正规子群155
5.4.4拉格朗日定理158
5.5环和域160
5.5.1环160
5.5.2整环162
5.5.3域163
5.5.4环和域的同态165
习题166
第6章格和布尔代数170
6.1格及其性质170
6.1.1格的偏序集定义170
6.1.2格的性质171
6.1.3格的代数系统定义174
6.1.4子格175
6.1.5格的同态176
6.2分配格和有补格177
6.2.1分配格177
6.2.2有补格179
6.2.3有补分配格181
6.3布尔代数182
6.3.1布尔代数的基本概念182
6.3.2布尔代数的性质184
习题186
第3篇图论191
第7章图与树195
7.1图的基本概念195
7.1.1图及其图解表示195
7.1.2完全图与补图197
7.1.3结点的度与握手定理1987.1.4图的连通性199
7.1.5图的同构202
7.1.6子图与分图204
7.1.7图的运算207
7.2图的矩阵表示208
7.2.1图的关联矩阵208
7.2.2图的邻接矩阵209
7.2.3图的连接矩阵211
7.3树213
7.3.1树的基本概念213
7.3.2树的基本性质213
7.3.3最小生成树215
7.4有向树219
7.4.1有向树的基本概念219
7.4.2二元树及其周游221
7.4.3有向树中的一些数量关系222
习题223
第8章特殊图229
8.1欧拉图229
8.1.1欧拉图的基本概念229
8.1.2欧拉图的判别230
8.1.3中国邮路问题232
8.2哈密顿图233
8.2.1哈密顿图的基本概念233
8.2.2哈密顿图的判别233
8.2.3流动售货员问题235
8.3二部图237
8.3.1二部图的基本概念237
8.3.2二部图的判别238
8.3.3匹配问题239
8.4平面图240
8.4.1平面图的基本概念240
8.4.2平面图的判别2428.4.3地图着色问题246
习题248
第4篇数理逻辑253
第9章命题逻辑257
9.1命题的基本概念257
9.2命题联结词258
9.3命题公式的基本概念262
9.4命题公式的等值关系和蕴含关系266
9.4.1命题公式的等值关系266
9.4.2基本的等值式266
9.4.3等值式的判定267
9.4.4命题公式的蕴含关系271
9.4.5基本的蕴含式271
9.4.6蕴含式的判定272
9.4.7命题公式的对偶274
9.5命题公式的范式275
9.5.1析取范式和合取范式275
9.5.2主析取范式和主合取范式277
9.6命题演算的推理理论281
9.6.1推理的概念281
9.6.2推理的方法281
习题285
第10章谓词逻辑293
10.1个体、谓词和量词293
10.2谓词公式的基本概念297
10.3谓词公式的等值关系与蕴含关系300
10.3.1谓词公式的类型300
10.3.2谓词公式间的等值与蕴含关系301
10.3.3谓词公式的对偶30510.4谓词公式的范式305
10.4.1前束范式305
10.4.2前束合取范式与前束析取范式306
10.4.3斯柯林范式308
10.5谓词演算的推理理论309
10.5.1推理规则310
10.5.2推理规则的应用311
习题314
参考文献319
第5章群、环和域
接下来的两章将介绍常见的几种代数结构，它们是用代数方法建立的数学模型.本章着重讨论具有一个二元运算的代数系统，包括半群、独异点和群以及具有两个二元运算的代数系统，包括环和域.群、环和域在组合计数、编码理论、形式语言与自动机理论等学科中都发挥了重要作用，而群是抽象代数中最古老且发展得最完善的代数系统.在计算机科学中，对于代码的查错和纠错、自动机理论等各个方面的应用的研究，群是其基础. 本章的主要内容为半群、独异点和群的定义和基本性质，子群及其陪集，环和域的定义和基本性质等. 5.1半群和独异点〖*4/5〗5.1.1半群和独异点的基本概念定义5.1设S是一个非空集合，是S上的一个二元运算，如果运算是可结合的，则称代数系统是半群. 若在半群中，运算满足交换律，则称为交换半群. 例如，(1)代数系统和、和、和都是半群，且都是交换半群.但和不是半群，因为运算不满足结合律. (2)代数系统，都是半群，是交换半群,不是交换半群. (3)代数系统<2U；∪>和<2U；∩>都是半群，且都是交换半群. (4)设S={R|R是集合A上的关系}，则对于关系的复合运算，代数系统是半群，但不是交换半群. 若F={f|f是A上的函数}，则对于函数的复合运算，代数系统也是半群，但不是交换半群. 【例5.1】设S是非空集合，对任意的x，y∈S，定义xy=y，则代数系统是半群，但不是交换半群. 【例5.2】设代数系统是半群，a∈S，如果对任意的x，y∈S，每当ax=ay都有x=y，则称元素a是左可约的.试证明，如果a，b是左可约的，则ab也是左可约的. 证明对任意的x，y∈S，假设有(ab)x=(ab)y. 因为是半群，所以是可结合的，有(ab)x=a(bx)，(ab)y=a(by)则由假设有a(bx)=a(by)因为a是左可约的，所以bx=by. 又因为b是左可约的，所以x=y. 即对任意的x，y∈S，如果(ab)x=(ab)y，则有x=y.所以由左可约的定义可知，ab也是左可约的. 因为半群中运算是可结合的，所以可以定义元素的幂. 定义5.2设是一个半群，则对任意的x∈S和任意正整数n，定义x的n次幂为x1=x，xn+1=xnx（n∈Z+）（5.1）并称n为x的指数. 对任意的正整数m，n和任意的x∈S，有xmxn=xm+n，(xm)n=xmn（5.2）定理5.1设是一个有限的半群，则必有a∈S，使得a是一个幂等元. 证明对任意的x∈S，因为是半群，故由运算的封闭性和结合律知，x2=xx∈S，x3=x2x=xx2∈S，…因为S是有限集，所以根据鸽笼原理知，必存在正整数j>i，使得xi=xj. 令p=j-i，便有xi（=xj=xp+i）=xpxi. 由此可得xq=xpxq（正整数q≥i）. 因为p≥1，所以总可以找到正整数k≥1，使得kp≥i. 对于S中的元素xkp，就有xkp=xpxkp =xp(xpxkp) =x2pxkp =… =xkpxkp.此即证得，在S中存在元素a=xkp，使得aa=a.■ 定义5.3若半群中的运算有单位元，则称该半群为含幺半群，常称为独异点. 若独异点中的运算满足交换律，则称该独异点为交换独异点. 例如，(1)代数系统和、和、和都是独异点，且都是交换独异点.但和不是独异点. (2)代数系统，都是独异点，是交换独异点，不是交换独异点. (3)代数系统<2U；∪>和<2U；∩>都是独异点，且都是交换独异点. (4)设S={R|R是集合A上的关系}，则对于关系的复合运算，代数系统是独异点，但不是交换独异点. 若F={f|f是A上的函数}，则对于函数的复合运算，代数系统也是独异点，但不是交换独异点. 注意: (1)独异点中唯一的单位元常记为e. (2)设为独异点，则关于运算的运算表中没有两行或两列是相同的. 事实上，对任意的x，y∈S，当x≠y时，总有xe=x≠y=ye和ex=x≠y=ey，所以在的运算表中不可能有两行或两列是相同的. 在独异点中也可定义元素的幂. 定义5.4设是一个独异点，则对任意的x∈S和任意非负整数n，定义x的n次幂为x0=e，xn+1=xnx（n∈N）（5.3）并称n为x的指数. 对任意的非负整数m，n和任意的x∈S，有xmxn=xm+n，(xm)n=xmn（5.4）定义5.5在独异点中，如果存在元素g∈S，使得S中的每一元素a都能写成gi（i∈N）的形式，则称独异点为循环独异点，元素g称为该循环独异点的生成元. 【例5.3】试证是循环独异点，并求其生成元. 证明是独异点，且0是加法运算的单位元. 对任意的i∈N，若i≠0，则i=1+1+…+1（i个1相加）=1i；若i=0，则有0=10. 故为循环独异点，其生成元为1. 【例5.4】是一个独异点，其中S={1，a，b，c，d}，是S上的二元运算，其运算表如表5.1所示.表5.1 1abcd11abcdaaabddbbbdaaccdabbdddabb因为1是单位元，a是幂等元，b3=d3=a，因此1，a，b，d的任意非负整数次幂最多只能表示S中4个不同元.而c0=1，c1=c，c2=b，c3=a，c4=d所以独异点是一个循环独异点，其中c是生成元. 定理5.2每一个循环独异点都是交换独异点. 证明设为循环独异点且g为其生成元，则对任意的x，y∈S，存在m，n∈N，使得x=gm，y=gn.于是xy=gmgn=gm+n=gn+m=gngm=yx所以是交换独异点.■ 定理5.3设是一个有限的独异点，则对每一个x∈S存在正整数j，使得xj是一个幂等元. 证明见定理5.1的证明.■ 例如,例5.4中1，a，b3（=a），d3（=a），c3（=a）是幂等元. 定理5.4设是独异点，a，b∈S且可逆，则 (1)(a-1)-1=a. (2)(ab)-1=b-1a-1. 证明(1)设a-1是a的逆元，则有aa-1=a-1a=e，因此a-1可逆，且(a-1)-1=a. (2)设a-1是a的逆元，b-1是b的逆元，因为(ab)(b-1a-1)=a(bb-1)a-1=aea-1=aa-1=e， (b-1a-1)(ab)=b-1(a-1a)b=b-1eb=b-1b=e，所以ab可逆，且(ab)-1=b-1a-1.■ 5.1.2子半群和子独异点 定义5.6设是一个半群，若是的子代数，则称为的子半群. 设是一个独异点，若是的子代数，且单位元e∈H，则称为的子独异点. 由定义知，子半群（子独异点）是一个半群（独异点）；半群（独异点）是自身的一个子半群（子独异点）.此外，<{e}；>也是独异点的子独异点. 【例5.5】对于半群的任一元素x∈S，令集合H={x，x2，x3，…}，则是的子半群. 【例5.6】对于半群，Z+的子集A2={2n|n∈Z+}，A3={3n|n∈Z+}，A4={4n|n∈Z+}，…都是的子半群. 【例5.7】对于独异点，子集A2，A3，A4，…（同例5.6）均不能形成的子独异点；而B2={2n|n∈N}，B3={3n|n∈N}，B4={4n|n∈N}，…都能形成的子独异点. 定理5.5设是一个交换独异点，则S的所有幂等元的集合H形成的一个子独异点. 证明由于S中单位元e适合e2=e，所以e∈H，于是H是S的非空子集且包含S中的单位元e. 对任意的x，y∈H，由x2=x，y2=y和运算是可交换的得知(xy)2=x2y2=xy因此xy∈H，于是H对于运算是封闭的，从而是的一个子独异点.■ 【思考5.1】设代数系统和都是独异点，若HS，则是的子独异点吗？ 5.1.3半群和独异点的同态 代数系统的同态（单同态、满同态）、同构和积代数的概念以及一些有关的结论可以推广到半群和独异点中. 定理5.6设h是从代数系统V1=到代数系统V2=的满同态，其中运算和都是二元运算，则 (1)若V1是（交换）半群，则V2也是（交换）半群. (2)若V1是（交换）独异点，则V2也是（交换）独异点. 推论5.1（交换）半群的同态像是（交换）半群，（交换）独异点的同态像是（交换）独异点. 定理5.7给定代数系统V1=和V2=，其中运算和都是二元运算，则 (1)若V1和V2是（交换）半群，则V1×V2也是（交换）半群. (2)若V1和V2是（交换）独异点，则V1×V2也是（交换）独异点. 5.2群〖*4/5〗5.2.1群的基本概念〖*2〗1.群的定义定义5.7设是一个代数系统，如果G上的二元运算满足下列条件，则称是一个群，简记成群G. (1)运算是可结合的; (2)存在单位元e∈G; (3)G中所有元素都可逆. 如果群的运算是可交换的，则称该群为交换群或阿贝尔群. 例如，代数系统、、、、<2U；∪>、<2U；∩>都是群，且为交换群.但、、、都不是群，因为不是所有元都可逆. 【例5.8】代数系统为群，且为交换群. 证明(1)先证运算满足结合律. 对任意的a，b，c∈Nn，令a+b=nm1+resn(a+b)，b+c=nm2+resn(b+c)则有 (anb)nc=resn(a+b)nc=resn(resn(a+b)+c)
你还可能感兴趣
我要评论
|
