电子工业出版社-网上书店

本书共8章，以数理逻辑为基础，介绍命题逻辑、谓词逻辑、集合论基础、关系、函数、运算与代数系统、图和初等数论基础的相关内容，配套微课视频、电子课件、知识导图、部分习题解答等。本书内容不求大求全，根据工程教育的要求，着重介绍有应用价值的理论，避免理论上的缠绕，内容讲解通俗明了，同时还增加了相当数量的工程应用方面的简介，使学习者能够快速了解这些理论的实际工程用途。本书可作为高等学校计算机科学与技术、软件工程、信息与计算科学以及其他信息领域相关专业离散数学课程的教材，也可供相关领域读者自学使用。

目    录
 
第1章  命题逻辑	1
1.1  命题	1
思考与练习1.1	3
1.2  逻辑联结词	3
1.2.1  基本联结词	3
1.2.2  其他联结词	6
思考与练习1.2	6
1.3  命题公式与真值表	7
1.3.1  命题公式	7
1.3.2  真值表	8
思考与练习1.3	8
1.4  命题翻译	9
1.4.1  命题的合取	9
1.4.2  命题的析取	9
1.4.3  条件句复合命题	10
1.4.4  多联结词构成的复合命题	11
思考与练习1.4	12
1.5  命题公式的分类与逻辑等价	13
1.5.1  命题公式的分类	13
1.5.2  命题公式等价	14
1.5.3  联结词的功能完备集	16
1.5.4  对偶原理	17
思考与练习1.5	18
1.6  范式	18
1.6.1  简单的范式	18
1.6.2  小项与大项	19
1.6.3  主析取范式与主合取范式	20
思考与练习1.6	23
1.7  推 理 理 论	24
1.7.1  蕴含与论证	24
1.7.2  自然推理系统	26
思考与练习1.7	33
第2章  谓词逻辑	34
2.1  谓词、个体词与量词	34
2.1.1  个体词和谓词	34
2.1.2  量词与量化	36
思考与练习2.1	37
2.2  谓词逻辑的命题翻译	38
2.2.1  特殊化个体词的命题	38
2.2.2  量词量化的命题	38
思考与练习2.2	41
2.3  量词约束与谓词公式的解释	42
2.3.1  量词对个体词变元的作用	42
2.3.2  谓词公式的解释与求值	42
2.3.3  量词与联结词的搭配	44
思考与练习2.3	44
2.4  谓词公式的等价和蕴含	45
2.4.1  基本等价与蕴含关系	45
2.4.2  利用等价关系计算前束范式	48
思考与练习2.4	49
2.5  谓词逻辑的推理理论	50
2.5.1  推理定律	50
2.5.2  量词的消除与产生规则	50
2.5.3  谓词逻辑的自然推理示例	52
思考与练习2.5	55
2.6  *数学证明初步	56
2.6.1  数学论题的描述	56
2.6.2  证明方法	56
2.6.3  证明策略	58
思考与练习2.6	59
第3章  集合论基础	61
3.1  集合的概念和表示方法	61
3.1.1  集合描述	61
3.1.2  集合的包含与相等	62
3.1.3  空集和全集	63
3.1.4  集合的幂集	65
思考与练习3.1	66
3.2  集合运算	66
3.2.1  基本运算	66
3.2.2  多集合的交与并	68
思考与练习3.2	70
3.3  集合运算的性质	71
3.3.1  集合算律与恒等变换	71
3.3.2  基于定义的运算性质验证	72
思考与练习3.3	74
3.4  集合划分和计数	74
3.4.1  集合的划分与覆盖	75
3.4.2  *集合计数的容斥原理	76
思考与练习3.4	77
3.5  序偶与笛卡儿积	78
3.5.1  序偶和元组	78
3.5.2  笛卡儿积	79
思考与练习3.5	81
第4章  关系	82
4.1  二元关系的含义与表示	82
4.1.1  二元关系	82
4.1.2  关系的矩阵和图表示法	84
思考与练习4.1	85
4.2  关系运算	86
4.2.1  关系的逆与复合	86
4.2.2  关系运算的性质	87
4.2.3  关系运算的图和矩阵实现	88
4.2.4  关系的幂	90
思考与练习4.2	92
4.3  关系的性质	93
4.3.1  自反与反自反关系	93
4.3.2  对称与反对称关系	94
4.3.3  传递关系	95
4.3.4  关系性质的等价描述与判定	95
思考与练习4.3	97
4.4  关系的闭包	98
4.4.1  闭包的概念	98
4.4.2  闭包计算	99
思考与练习4.4	102
4.5  等价关系	102
4.5.1  等价与相容	102
4.5.2  等价类	103
4.5.3  划分与等价关系的对应	104
思考与练习4.5	106
4.6  序关系	107
4.6.1  体现部分序的偏序关系	107
4.6.2  哈斯图	108
4.6.3  链与全序关系	109
4.6.4  偏序集的特殊元素	111
思考与练习4.6	112
第5章  函数	114
5.1  从关系到函数	114
5.1.1  函数的概念	114
5.1.2  函数集	115
5.1.3  函数的性质与特殊函数	116
思考与练习5.1	118
5.2  函数的逆与复合	119
5.2.1  双射的反函数	119
5.2.2  函数复合	119
5.2.3  函数运算的性质	121
思考与练习5.2	122
5.3  集合的基数	122
5.3.1  集合等势	122
5.3.2  有限集与无限集	123
5.3.3  可数集与不可数集	123
5.3.4  基数比较	125
思考与练习5.3	126
第6章  运算与代数系统	127
6.1  运算及其性质	127
6.1.1  运算的概念	127
6.1.2  二元运算的性质	128
思考与练习6.1	129
6.2  二元运算中的特殊元素	130
6.2.1  幺元	130
6.2.2  零元	131
6.2.3  逆元	132
思考与练习6.2	133
6.3  代数系统	133
6.3.1  代数与子代数	133
6.3.2  同态与同构	134
思考与练习6.3	135
6.4  半群与独异点	136
思考与练习6.4	137
6.5  群与子群	138
6.5.1  群的概念	138
6.5.2  群的性质	139
6.5.3  子群	140
思考与练习6.5	141
6.6  循环群与置换群	142
6.6.1  循环群	142
6.6.2  置换群	143
思考与练习6.6	145
6.7  群的陪集分解	145
6.7.1  陪集	146
6.7.2  拉格朗日定理	147
思考与练习6.7	148
6.8  环和域	148
6.8.1  环与整环	148
6.8.2  域	150
思考与练习6.8	150
6.9  格	151
6.9.1  格与其诱导的代数系统	151
6.9.2  子格	153
6.9.3  几种特殊格	153
思考与练习6.9	155
6.10  布尔代数	156
6.10.1  布尔代数的定义	156
6.10.2  二值布尔代数	157
思考与练习6.10	159
第7章  图	160
7.1  图的基本概念	160
7.1.1  图及其组成	160
7.1.2  结点的度与握手定理	161
7.1.3  完全图与正则图	163
7.1.4  子图、补图与图同构	163
思考与练习7.1	165
7.2  图的连通性	165
7.2.1  路与回路	165
7.2.2  无向图的连通性	166
7.2.3  有向图的连通性	167
思考与练习7.2	168




7.3  图的矩阵表示	168
7.3.1  邻接矩阵	168
7.3.2  关联矩阵	170
思考与练习7.3	170
7.4  几种特殊的图	171
7.4.1  二部图	171
7.4.2  欧拉图	173
7.4.3  汉密尔顿图	175
思考与练习7.4	176
7.5  平面图	177
7.5.1  平面图与欧拉定理	177
7.5.2  平面图着色	179
思考与练习7.5	180
7.6  树	180
7.6.1  无向树	180
7.6.2  生成树	182
7.6.3  *单源最短路径	184
7.6.4  根树	186
思考与练习7.6	189
第8章  初等数论基础	190
8.1  整数除法与素数	190
8.1.1  整数除法与整除	190
8.1.2  素数与合数	191
8.1.3  最大公约数与最小公倍数	193
思考与练习8.1	196
8.2  同余与同余方程	196
8.2.1  模算术与同余	196
8.2.2  一次同余方程及方程组	198
思考与练习8.2	200
8.3  费马小定理与欧拉定理	201
8.3.1  费马小定理	201
8.3.2  *欧拉函数与欧拉定理	202
8.3.3  *RSA密码系统原理	202
思考与练习8.3	204
附录  符号索引	205
参考文献	207

前    言
离散数学是研究离散量的结构及其相互关系的一门学科，是由逻辑学、集合论、关系理论、图论、抽象代数、布尔代数，甚至算法设计、组合分析、离散概率、数论和计算模型等汇集起来的一门综合学科。按照《中国计算机科学与技术学科教程2002》标准，离散数学是计算机科学与技术专业的核心基础课程，也是美国IEEE＆ACM中计算机专业的核心课程。
应该说，计算机及其相关专业的绝大部分课程，都是直接以离散数学作为理论基础的，也可说是离散数学的直接运用，需要依靠离散数学课程中建立的观点、方法和逻辑思维能力去解决具体问题。因此，离散数学课程的教学目的就是要建立逻辑（数学）推理能力，了解重要的离散对象与结构，构建和应用解决离散问题的模型并分析求解等。
本书的写作目的是为普通高等学校的计算机、软件工程及其相关专业提供一本易于理解，易于自学，有一定工程应用背景和实际问题引导的教材。因此，本书不追求体系的完整、内容的全面和对理论的深入探讨，为了达到目标，体现自身的特点，我们注重如下问题：
?  内容按教学实际取舍。舍弃中学学过的简单组合计数，前文提到的离散概率、组合设计、形式语言等内容，以及数据结构等课程中涵盖的算法，并尽量避免与后续课程重复，不使内容冗余。
?  次序编排突出逻辑思维。以逻辑学而不是集合论为出发点，用命题逻辑和谓词逻辑主导解决后续所有问题的思维，以便强化分析、解决问题的逻辑性和能力。
?  对问题平实、透彻讲解。离散数学是数学，内容抽象。通过信息相关领域实例、问题引导、分析、评价、辨析等步骤，将知识点讲解透彻，甚至利用“理解”标签予以提示并展示应理解的程度，避免读者需要花过长的时间思考或借助参考书才能读懂。特别地，对大量值得注意或需要认真分析的关键问题，通过“辨析”标签给出讨论和警示。
?  概括、突出问题核心。对解决一类问题的核心内容突出给予总结和概括，说明此类问题的实质和解决方法的关键，而不是仅给出一个具体题目的解法。
?  适当引入工程问题。选取相关领域中有代表性的工程应用实践问题作为示例或习题，理论联系实际，激发学习和解决实际问题的兴趣。
?  对思考和应用进行引导。作为教材，对于新的成果、大量的相关问题及其解决方案不可能面面俱到。对于很多问题，通过“拓展”标签指出其发展方向、实际应用案例、存在的解决方法等，并列出可供参考的资料，以引导学生自己探索。当然，这些内容作为课堂的延伸，以辅助学习和思考为主，研究为辅。
?  精简定理与习题。过多罗列已有的结果令人眼花缭乱，还会误导学生机械记忆，而不是由基本概念出发进行主动思考、探究和发现结果。同时，尽管多做习题有助于问题的理解，但需要大量时间和精力。为此，本书尽量精简了定理与习题。考虑到本课程中概念（定义）对内容理解和题目求解的重要性，故将重要概念纳入习题，直接提醒学生深刻理解这些核心定义。
本书的编写基于教学实际情况、教学要求及人才培养要求等因素。我们认为，在把更多的时间、思考、总结、发现等交给学生时，教师要能使学生学会学习，教材要有助于学生自主学习。教材既不能包罗万象，求深求全，也不能只是“干巴巴”的纲。考虑到目前离散数学课程多在大学一年级开设，我们只给学有余力的读者列出了部分建议性的编程问题，没有对算法的描述以及程序实现提出过多要求，以免徒增额外负担且冲淡主题。
全书分为8章，分别是命题逻辑、谓词逻辑、集合论基础、关系、函数、运算与代数系统、图、初等数论基础。这种章节次序安排的目的是期望以严密的逻辑思维贯穿各部分内容，使思考和推理更富有理论依据。全书建议学习64个学时。
本次再版，我们适当融入了课程思政的元素；对相容关系和对偶图等部分做了删减，增补了数学证明和数论的初步知识；将划分、覆盖与容斥原理融合，以直接体现前者的应用；删减并合并了2个运算的代数结构内容。此外，对重点内容、每章的知识结构和各思考与练习的部分习题分别增加了微课视频讲解、知识结构导图和解题导引，可以通过扫描书中的二维码自主学习。
本书的作者都有多年课程教学经验，且未间断地从事本科离散数学课程的教学工作，无论对课程内容、体系、教学方法和安排，还是工程教育的发展方向与普通高等学校工科的实际情况均有着深刻的理解，使得本书的写作更富有针对性。我们期望通过本书使离散数学的内容更容易理解、学习和掌握，更便于促进学习者技能的提高，但囿于个人见解，仍会存在诸多缺憾，欢迎读者指出其不足，也期待能与读者做更多交流（niulq@sut.edu.cn）。
此外，作为学校的重点规划教材，本书的出版和再版得到了沈阳工业大学的支持及诸多老师的支持和帮助，我们深表感谢！

作  者  
2023年1月

本书配套资源下载

对不起，暂无音视频资源！

工科离散数学（第2版）