本教材是以内容简明、面向应用为特色的离散数学教材，它适合于课程学时数为30~50的教学需要。
全书内容遵循少而精的原则，重点突出，学以致用，并且做到深入浅出。全书共有7章：绪言、集合论基础、关系、代数系统、图论、数理逻辑、离散建模。
本教材适用于普通高等学校计算机应用型本科及高职高专学生“离散数学”课程教材之用，也可作为自考、成人业余高校相关专业教材及教学参考之用。

离散数学是计算机专业的核心课程,自20世纪70年代末开设至今已有30余年历
史。在这些年中随着科学技术不断发展、改革开放不断深入,对离散数学课程也不断有
新的认识,特别是近年来的变化,使得对离散数学课程的教学改革需要有一个新的
飞跃。
1. 离散数学课程教学环境的变化
近年来离散数学教学改革环境产生了重大的变化,主要表现为:
(1)离散数学课程设置由计算机专业而扩展至信息技术领域的多个专业,由大学本
科而扩展至高职高专,由研究型而扩展至应用型,由全日制而扩展至业余及成人教育等
多种类型。
(2)不同类型与性质学校、不同专业对离散数学的要求也大不相同。
(3)由于高等教育由精英化走向大众化,因此离散数学参学人数越来越多,但学生
知识起点参差不齐。
从以上3点可以看出,过去大一统的模式,即统一要求、统一内容及统一学时的时
代已经结束,而多元化的“春秋战国”时代已经开始,设法解决这些问题就成为离散数
学课程教学改革的当务之急。
2. 课程发展趋势
从目前发展趋势看,离散数学课程的要求大致分为以下两类:
第一类:以计算机研究型本科(及以上)为主,其理论要求高,内容多,课程学时
数为70~100。此类型学生占目前的少数。
第二类:以计算机应用型本科(及以下)为主,其理论要求不高,重在计算机科学
与技术中的应用,课程学时数为30~50。此类型学生占目前的大多数。据不完全统计,
此类就读人数占整个课程就读人数七成以上。
3. 目前教材市场现状
从目前离散数学教材市场现状看,占多数的是第一类教材,第二类教材偏少。因
此,编写第二类应用型离散数学教材已成为当务之急。
4. 第二类课程目标与要求
为编写此类应用型离散数学教材,必须明确课程目标与要求,根据长期调查研究,
我们认为,此类教材应该有如下特点:
(1)培养抽象思维与计算思维能力。
(2)为学生所学后续课程(如数据结构、数据库、人工智能、编译原理、软件工
程、数据通信、数字逻辑电路)提供知识支撑,也为他们进一步的理论需求(如论文撰
写、应用研究)提供基础。
(3)培养学生离散建模能力,为其以后在工作中,将离散数学应用于本专业的研究
与开发中提供相应能力。
5. 教材编写原则
根据课程目标与要求,在教材的具体编写中,坚持以下几项原则:
(1)少而精原则
在内容选材上坚持少而精,选取具有代表性的核心内容,通过精讲精练达到举一反三
的效果。还要注重所选知识的关联性与一致性,使所选的整体内容是完整的、一致的,
从而达到一种新的知识平衡。
教材篇幅适合30~50学时的教学需要。
随着科学技术迅速发展,目前的教科书越写越厚。本教材反其道而行之,崇尚“少
而精”原则,使学生能在最少时间内掌握离散数学最基本的、必需的知识。
(2)深入浅出原则
教材是面向学生的,为使学生接受数学抽象思维与离散思维,培养其相应能力,在
教材中须对离散数学的基本概念与性质做详细的讲解,从具体例子出发以达到抽象的目
的。在了解数学的抽象表示的同时,更要注重其形式语义,使学生能掌握离散数学的精
髓并能灵活应用。
(3)学以致用原则
离散数学是计算机专业的核心课程,与学习高等数学有着本质上的不同。学习离散
数学必须与计算机相结合,为计算机应用服务,而应用的主要内容是包括离散建模在内
的一些内容,通过对这些内容的学习,使学生能将离散数学作为工具,解决日常工作中
的实际问题。
6. 教材内容组成
(1)基本内容
离散数学内容虽然很多,但根据多年积累,还是以传统四门学科为核心,即集合论
(包括关系)、代数系统、图论、数理逻辑。其原因如下:
①从学科观点看,这四门学科相互关联,构成逻辑上的整体。其中集合论是它们的
共同研究基础,关系是它们的共同研究内容,代数系统、图论、数理逻辑则反映了对关
系研究的不同特色。代数系统是以运算规律研究作为其特色;图论是以抽象结构规律研
究作为其特色;数理逻辑是以推理规律研究作为其特色。这三种研究特色较为全面地反
映了离散数学研究概貌。
②从目标与要求看,这四门学科能满足一般的离散建模要求,它们也能为后续课程
提供支撑,同时,也能较好地培养离散思维与抽象思维能力。
(2)内容的组织
本教材共有七章:绪言、集合论基础、关系、代数系统、图论、数理逻辑、离散建
模等。其重点为集合论基础与数理逻辑两章。书中标有“*”的章节不是必需的,可供
参考、选择之用。
本书由徐洁磐任主编,宋毅、王嘉鹏、宋艳艳、蒋东玉任副主编。其中第1~4章
及第6、7章由徐洁磐编写,第5章由宋毅、王嘉鹏、宋艳艳、蒋东玉编写,最后由徐
洁磐统一定稿。宋毅整理了本书的课件等教学资料,需要的读者可以到http://
www.51eds.com 网站进行下载。在本书出版之际,感谢天津师范大学张桂芸教授为审
阅本书所做出的辛勤工作,同时感谢南京大学计算机科学与技术系及计算机软件新技术
国家重点实验室的费翔林教授、徐永森教授、朱怀宏副教授、柏文阳副教授为本书所提
供的支持。
由于编者水平有限,书中不足在所难免,恳请读者不吝赐教。
编 者
2015年4月

第1章 绪言………………………………………………………………………………… 1
第2章 集合论基础………………………………………………………………………… 5
2.1 集合的基本概念………………………………………………………………… 6
2.1.1 集合介绍………………………………………………………………… 6
2.1.2 集合的表示方法………………………………………………………… 7
2.1.3 集合概念间的关系……………………………………………………… 8
2.1.4 集合的基本性质……………………………………………………… 10
2.2 集合运算………………………………………………………………………… 11
2.2.1 集合基本运算………………………………………………………… 11
2.2.2 集合运算的21个定律………………………………………………… 12
*2.2.3 集合运算定律的证明………………………………………………… 13
2.2.4 集合运算的应用……………………………………………………… 16
2.3 集合的扩充运算………………………………………………………………… 17
2.3.1 集合的扩充运算之一———集合差运算与对称差运算……………… 17
2.3.2 集合扩充运算之二———幂运算……………………………………… 18
2.3.3 集合扩充运算之三———笛卡儿乘…………………………………… 19
2.3.4 集合扩充运算之四———无序偶笛卡儿乘…………………………… 21
2.3.5 集合运算扩充之五———n 元有序组与n 阶笛卡儿乘……………… 21
*2.4 有限集与无限集………………………………………………………………… 22
小结…………………………………………………………………………………… 23
习题…………………………………………………………………………………… 24
第3章 关系……………………………………………………………………………… 27
3.1 关系的基本概念………………………………………………………………… 27
3.1.1 关系介绍……………………………………………………………… 27
3.1.2 关系的表示…………………………………………………………… 29
*3.2 关系性质………………………………………………………………………… 31
2 离散数学简明教程
3.3 关系运算………………………………………………………………………… 32
3.3.1 关系的并、交、补运算……………………………………………… 32
3.3.2 关系的复合运算与逆运算…………………………………………… 33
3.3.3 关系上的闭包运算…………………………………………………… 36
*3.4 两种常用的关系………………………………………………………………… 39
3.4.1 次序关系……………………………………………………………… 39
3.4.2 等价关系……………………………………………………………… 45
3.5 函数……………………………………………………………………………… 48
3.6 n 元关系与多元函数…………………………………………………………… 50
小结…………………………………………………………………………………… 51
习题…………………………………………………………………………………… 52
第4章 代数系统………………………………………………………………………… 55
4.1 代数系统基本概论……………………………………………………………… 56
4.1.1 代数系统介绍………………………………………………………… 56
4.1.2 代数运算中的常见性质……………………………………………… 58
4.1.3 代数系统的同态与同构……………………………………………… 61
4.1.4 代数系统的分类……………………………………………………… 67
4.2 群论……………………………………………………………………………… 68
4.2.1 群及其性质…………………………………………………………… 69
*4.2.2 群同态与变换群……………………………………………………… 70
4.2.3 有限群………………………………………………………………… 73
*4.2.4 置换群………………………………………………………………… 73
4.2.5 循环群………………………………………………………………… 75
4.2.6 子群…………………………………………………………………… 77
4.3 布尔代数………………………………………………………………………… 79
4.3.1 格介绍………………………………………………………………… 79
4.3.2 布尔代数介绍………………………………………………………… 80
4.3.3 布尔函数……………………………………………………………… 82
4.3.4 布尔代数应用………………………………………………………… 83
小结…………………………………………………………………………………… 83
习题…………………………………………………………………………………… 85
第5章 图论……………………………………………………………………………… 88
5.1 图论的基本概念………………………………………………………………… 88
目录3
5.1.1 图的定义……………………………………………………………… 88
5.1.2 结点的度……………………………………………………………… 90
5.1.3 完全图和补图………………………………………………………… 92
5.1.4 子图与图的同构……………………………………………………… 93
5.2 通路、回路与连通图…………………………………………………………… 94
5.2.1 通路…………………………………………………………………… 94
5.2.2 图的连通性…………………………………………………………… 95
5.3 图的矩阵表示…………………………………………………………………… 96
5.3.1 无向图的关联矩阵…………………………………………………… 96
5.3.2 无环有向图的关联矩阵……………………………………………… 97
5.3.3 有向图的邻接矩阵…………………………………………………… 97
5.3.4 无向图的邻接矩阵…………………………………………………… 98
5.3.5 有向图的可达矩阵…………………………………………………… 99
5.3.6 无向图的可达矩阵…………………………………………………… 100
5.4 树……………………………………………………………………………… 101
5.4.1 树的概念……………………………………………………………… 101
5.4.2 生成树及其应用……………………………………………………… 102
5.4.3 根树及其应用………………………………………………………… 105
小结…………………………………………………………………………………… 108
习题…………………………………………………………………………………… 109
第6章 数理逻辑………………………………………………………………………… 113
6.1 命题逻辑……………………………………………………………………… 114
6.1.1 命题…………………………………………………………………… 114
6.1.2 命题联结词…………………………………………………………… 115
9.1.3 命题公式……………………………………………………………… 120
6.1.4 命题公式的真值表与重言式………………………………………… 121
6.1.5 命题逻辑的等式推理………………………………………………… 123
6.1.6 命题逻辑的蕴涵推理………………………………………………… 127
6.2 谓词逻辑……………………………………………………………………… 131
6.2.1 谓词逻辑的三个基本概念———个体、谓词与量词………………… 131
6.2.2 谓词逻辑中的个体变元补充概念———自由变元与约束变元……… 134
6.2.3 谓词公式……………………………………………………………… 135
6.2.4 谓词逻辑的永真公式………………………………………………… 137
4 离散数学简明教程
6.2.5 谓词逻辑的等式推理………………………………………………… 139
6.2.6 谓词逻辑的蕴涵推理………………………………………………… 141
*6.3 自动推理———消解原理介绍………………………………………………… 144
6.3.1 范式…………………………………………………………………… 144
6.3.2 谓词公式的进一步规范———子句与子句集………………………… 145
6.3.3 消解原理……………………………………………………………… 146
6.3.4 PROLOG语言简介………………………………………………… 148
小结…………………………………………………………………………………… 150
习题…………………………………………………………………………………… 152
第7章 离散建模………………………………………………………………………… 156
7.1 离散建模概念与方法………………………………………………………… 156
7.1.1 离散建模概念………………………………………………………… 156
7.1.2 离散建模方法………………………………………………………… 157
7.1.3 离散建模方法的五个步骤…………………………………………… 159
7.2 操作系统中死锁检测的离散建模…………………………………………… 160
7.3 数字逻辑电路的离散建模…………………………………………………… 163
7.4 智力测验———水容器问题的离散建模……………………………………… 168
*7.5 电话线路故障影响分析中的离散建模……………………………………… 171
小结…………………………………………………………………………………… 175
习题…………………………………………………………………………………… 176
参考文献…………………………………………………………………………………… 178

主要著译者顺序姓名学历职称学科专长通讯地址1 徐洁磐博士 教授 离散数学、数据库工作单位南京大学 邮政编码 电话025-83596710 2 工作单位 邮政编码 电话 3 工作单位 邮政编码 电话 审校者（主审者）姓名学历职称 工作单位天津师范大学 邮政编码 电话 张桂芸 博士 教授 工作单位 邮政编码 电话 徐洁磐，南京大学计算机科学与技术系教授，博导。主要研究计算机理论与数据库技术，曾任中国人工智能学会理事，离散数学学会理事长，中國计算机学会计算机理论专业委员会副主任，数据库专委会委员。教育部计祘机教学指导委员会第一、二届委员。1957年南京大学数学系毕业，1963年苏联莫斯科大学数理逻辑副博士研究生毕业，1957年至今南京大学数学系、计算机系讲师，副教授、教授。宋毅：硕士、讲师，就职于哈尔滨华德学院计算机科学与技术，主讲课程有离散数学、数据结构、操作系统、 c语言程序设计和计算机实用基础。张桂芸，博士后，教授，硕士生导师，中共党员。现兼任教育部高等学校计算机科学与技术专业教学指导分委员会专家工作组成员；中国人工智能学会离散数学专委会常务理事兼秘书长；中国计算机学会新科技与计算机继续教育分委会理事；中国计算机学会YOCSEF天津分论坛学术委员会(AC)委员（筹）,中国计算机学会高级会员