“离散数学”是现代数学的一个重要分支，也是计算机科学与技术、电子信息技术、生物技术等专业的理论基础。本书首先将离散数学的体系结构分为以下五个主要部分：数理逻辑、集合与关系、数论与组合论、图论、代数结构。第六部分介绍离散数学在计算机科学中的一些典型应用。
本书在每章后面配备了相当数量的难易程度不同的练习题，并在附录中给出了几套模拟试题，供读者进行自测。
本书内容丰富，条理清晰，层次分明，逻辑性强，内容和方法前后贯通，阐述深入浅出，适合作为高等学校计算机和软件工程专业及相关专业离散数学课程的本科教材,也可供计算机科学工作者和科技人员阅读与参考。
离散数学
冯伟森 栾新成 石 兵◎等编著
本书是作者根据多年从事“离散数学”精品课程的教学经验，充分听取广大学生对该课程的意见，精心编写而成。
本书结合计算机科学和现代数学发展的最新成果，将离散数学的主要内容体系结构分为以下五个主要部分：数理逻辑、集合与关系、数论与组合论、图论、代数结构。本书第六部分是离散数学在计算机科学中的一些典型应用，目的是培养和提高学生的抽象思维能力和严密的逻辑推理能力，为学生今后处理离散信息以及用计算机处理大量的日常事务和科研项目、从事计算机科学和应用打下坚实的基础。
本书特色
全书内容丰富，条理清晰，层次分明，逻辑性强，阐述深入浅出。每章后配有大量难易程度不同的练习题，并在附录中给出了几套模拟试题，供读者进行自测。
适用对象广泛。本书适合作为普通高等学校计算机和软件工程专业及相关专业离散数学课程的本科生教材，也可供计算机科学工作者和科技人员阅读与参考。
“离散数学”是现代数学的一个重要分支，也是计算机科学与技术、电子信息技术、生物技术等专业的核心基础课程。它是研究离散量（如整数、有理数、有限字母表等）的数学结构、性质及关系的学问。它一方面充分地描述了计算机科学离散性的特点，为学生进一步学习算法与数据结构、程序设计语言、操作系统、编译原理、电路设计、软件工程与方法学、数据库与信息检索系统、人工智能、网络、计算机图形学等专业课打好数学基础；另一方面，通过学习离散数学课程，学生在获得离散问题建模、离散数学理论、计算机求解方法和技术知识的同时,还可以培养和提高抽象思维能力和严密的逻辑推理能力，为今后处理离散信息以及用计算机处理大量的日常事务和科研项目、从事计算机科学和应用打下坚实基础。特别是对于那些从事计算机科学与理论研究的高层次计算机人员来说，离散数学更是必不可少的基础理论工具。
本书是在四川大学老一辈名师吴子华、张一立、唐常杰所编《离散数学教程》和本书作者编写的“离散数学”讲义的基础上，结合计算机科学和现代数学发展的最新成果，以及作者多年从事“离散数学”精品课程的教学经验，充分听取广大学生对该课程的意见编写而成的。全书由六部分组成，首先将离散数学的体系结构分为五个主要部分：数理逻辑、集合与关系、数论与组合论、图论、代数结构。第六部分是离散数学在计算机科学中的一些典型应用。本书内容丰富，条理清晰，层次分明，逻辑性强，阐述深入浅出，每章后都配有大量难易程度不同的练习题，不仅适合作为普通高等院校计算机和软件工程专业及相关专业离散数学课程的本科生教材，也可供计算机科学工作者和科技人员阅读与参考。
根据我们的经验，使用本书可在110学时内完成全部教学任务（第六部分除外）。
本书的第1章至第6章、第18章的18.2节和18.3节由冯伟森编写；第7章至第9章、第14章至第17章由栾新成编写；第10章至第13章由石兵编写；第18章的18.1节、18.4节、18.5节、18.6节和部分习题由陈瑜编写；最后，全书由冯伟森统稿。
在本书的编写过程中，我们参阅了大量的离散数学书籍和资料，在此向有关作者表示衷心的感谢。本书的编写得到了四川大学计算机学院、软件学院各级领导和课程组各位老师的关心和大力支持，特别是朱敏副院长一直以来对本教材的关心和支持，在此向他们表示诚挚的感谢。感谢使用本教材的四川大学2008级和2009级计算机科学与技术专业、软件工程专业的同学们，他们对本教材提出了不少宝贵意见。同时，感谢机械工业出版社华章分社的王璐和白宇两位编辑对本书顺利出版的大力支持。
编 者
2010年11月
计算机\离散数学
前言
第一部分 数理逻辑
第1章 命题逻辑3
1.1 命题与逻辑联结词3
1.2 命题公式及其赋值7
1.3 命题公式的等价9
1.4 联结词的完备集12
1.5 命题公式的范式表示13
1.6 命题公式的蕴涵19
1.7 命题逻辑的推理方法21
习题一23
第2章 一阶谓词逻辑27
2.1 量词化逻辑27
2.2 谓词公式及其赋值30
2.3 谓词公式的等价与范式表示33
2.4 谓词公式的蕴涵37
2.5 谓词逻辑的推理方法39
习题二42
第二部分 集合与关系
第3章 集合代数47
3.1 集合的基本概念47
3.2 集合的运算49
3.3 幂集和笛卡儿集51
习题三53
第4章 二元关系55
4.1 二元关系及其表示55
4.2 关系的性质57
4.3 关系的运算59
4.4 关系的闭包61
习题四65
第5章 特殊关系67
5.1 等价关系67
5.2 偏序关系69
5.3 全序集与良序集71
习题五73
第6章 函数75
6.1 函数的定义与性质75
6.2 单射、满射和双射77
6.3 函数的复合与逆函数78
6.4 集合的基数、可数集和不可数集…81
习题六85
第三部分 数论与组合论
第7章 初等数论89
7.1 整数集合89
7.2 商和余数90
7.3 整除和素因子分解92
7.4 最大公因子93
7.5 数学归纳法95
习题七97
第8章 基本计数方法99
8.1 排列计数99
8.2 组合计数101
8.3 组合恒等式104
8.4 容斥原理106
8.5 鸽巢原理108
习题八110
第9章 生成函数和递推关系112
9.1 序列与生成函数112
9.2 组合问题的生成函数115
9.3 递推关系式及其解118
9.4 递推关系式的生成函数求解123
习题九126
第四部分 图论
第10章 图的基本概念131
10.1 图131
10.2 通路与回路136
10.3 图的连通性138
10.4 图的矩阵表示141
习题十146
第11章 树及其应用148
11.1 无向树及其性质148
11.2 生成树149
11.3 根树及其应用151
习题十一155
第12章 平面图及其应用157
12.1 平面图的基本概念157
12.2 欧拉公式158
12.3 平面图的判断159
12.4 平面图的对偶图160
12.5 平面的点着色与图的着色161
习题十二163
第13章 欧拉图与哈密顿图164
13.1 欧拉图与中国邮递员问题164
13.2 哈密顿图与推销商问题168
习题十三173
第五部分 代数结构
第14章 代数系统177
14.1 二元运算及其性质177
14.2 代数系统的定义与特异元178
习题十四179
第15章 半群与群181
15.1 半群181
15.2 群和子群183
15.3 交换群和循环群186
15.4 陪集与拉格朗日定理187
15.5 正规子群与商群189
15.6 群的同态与同构190
习题十五193
第16章 环与域195
16.1 环的定义及其性质195
16.2 整环与域197
习题十六198
第17章 格与布尔代数199
17.1 格的定义与性质199
17.2 子格与格同态201
17.3 分配格与有补格204
17.4 布尔代数206
17.5 布尔表达式209
习题十七214
第六部分 应用
第18章 典型应用218
18.1 数字逻辑电路设计218
18.2 形式语言220
18.3 有限状态自动机229
18.4 关系数据库管理系统235
18.5 网络236
18.6 群码242
习题十八244
附录 离散数学模拟试题248
参考文献259
