第一篇 集合论第1章 集 合（1）
1.1 集合的概念及其表示（1）
1.2 集合的基本运算（3）
1.3 笛卡尔积（4）
第2章 关 系（7）
2.1 关系及其表示（7）
2.2 关系的运算（8）
2.3 等价关系（11）
2.4 序关系（13）
第3章 映 射（18）
3.1 基本概念（18）
3.2 映射的运算（19）
第4章 可数集与不可数集（21）
4.1 等 势（21）
4.2 集合的基数（22）
4.3 可数集与不可数集（23）
第二篇 图 论第5章 图与子图（26）
5.1 图的概念（26）
5.2 图的同构（28）
5.3 顶点的度（29）
5.4 子图及图的运算（30）
5.5 通路与连通图（31）
5.6 图的矩阵表示（33）
5.7 应 用（34）
第6章 树（41）
6.1 树的定义（41）
6.2 生成树（43）
6.3 应 用（45）
第7章 图的连通性（48）
7.1 点连通度和边连通度（48）
7.2 块（50）
7.3 应 用（52）
第8章 E图与H 图（55）
8.1 七桥问题与E图（55）
8.2 周游世界问题与H 图（56）
8.3 应 用（60）
第9章 匹配与点独立集（63）
9.1 匹 配（63）
9.2 独立集和覆盖（67）
9.3 Ramsey数（69）
9.4 应 用（72）
第10章 图的着色（76）
10.1 顶点着色（76）
10.2 边着色（78）
10.3 色多项式（81）
第11章 平面图（85）
11.1 平面图的概念（85）
11.2 欧拉公式（87）
11.3 可平面性判定（89）
11.4 平面图的面着色（90）
第12章 有向图（93）
12.1 有向图的概念（93）
12.2 有向通路与有向回路（94）
12.3 有向树及其应用（97）
第13章 网络最大流与Petri网（101）
13.1 网络的流与割（101）
13.2 最大流最小割定理（103）
13.3 Petri网（107）
第三篇 数理逻辑第14章 命题逻辑（116）
14.1 命题与逻辑联结词（116）
14.2 命题公式与等值演算（119）
14.3 对偶与范式（122）
14.4 推理理论（127）
14.5 命题演算的公理系统（132）
第15章 一阶逻辑（138）
15.1 谓词与量词（138）
15.2 合式公式及解释（141）
15.3 等值式与范式（143）
15.4 一阶逻辑的推理理论（147）
第四篇 代数结构
第16章 整 数（154）
16.1 整除性（154）
16.2 质因数分解（159）
16.3 同 余（161）
16.4 孙子定理·Euler函数（163）
第17章 群（168）
17.1 群的概念（168）
17.2 子 群（171）
17.3 置换群（175）
17.4 陪集与Lagrange定理（179）
17.5 同态与同构（182）
第18章 环与域（189）
18.1 环与子环（189）
18.2 环同态（192）
18.3 域的特征·质域（196）
18.4 有限域（198）
18.5 有限域的结构（202）
第19章 格与布尔代数（209）
19.1 格的定义（209）
19.2 格的性质（211）
19.3 几种特殊的格（214）
19.4 布尔代数（218）
19.5 有限布尔代数的结构（224）
参考文献（231）
离散数学是计算机科学的基础数学，它以离散量为研究对象，充分描述了计算机科学离散性的特点.离散数学是随着计算机科学的发展而逐步建立的，它的主要内容在计算机出现之前就已散见于数学的各个分支中.它形成于20世纪70年代初，因此，国外也有人称之为“计算机数学”.离散数学包括的内容主要有：集合论、图论、数理逻辑、代数结构等，并且其内容一直随着计算机科学的发展而不断地扩充和完善.作为计算机专业的核心课程，它为后续课程提供了必要的数学基础.这些后续课程主要有：数据结构、编译理论、算法分析、自动机理论、计算机密码学、人工智能和可计算性理论等.本书是在多年讲授离散数学课程的基础上编写而成的，其目的在于通过讲授离散数学中的基本概念、基本定理和运算技巧及其在计算机科学中的应用，培养学生的数学抽象能力、用数学语言描述问题的能力、逻辑思维能力以及数学论证能力.因此，本书力求概念阐述严谨，证明推演详尽，较难理解的概念用实例说明.全书共分四篇：第一篇是集合论，主要介绍集合、关系、映射以及可数集与不可数集，这些内容是全书的基础知识和基本工具.第二篇是图论，主要介绍图与子图、树、平面图、匹配、图的着色、有向图、网络流以及Petri网等内容.由于图为任何一个包含二元关系的系统提供了一种离散数学模型，因此，应用图论来解决计算机科学以及工程技术等领域中的问题已显示出极大的优越性.此外，图论对于锻炼学生的组合思维能力，提高运用数学工具描述并解决实际问题的能力也大有益处.第三篇是数理逻辑，包括命题逻辑与一阶逻辑，它们是数理逻辑中与计算机科学关系较密切的内容.第四篇是代数结构，主要内容有群、环、域以及格与布尔代数，这些内容是自动机理论、计算机密码学等学科的基础.本书主要用作计算机专业基础课教材，也可以作为与计算机相关专业的基础知识教材.教师可以按授课对象的层次和专业对本书的章节进行取舍，根据需要讲授.对于计算机专业本科学生而言，本书可分作两个学期讲授，约140学时；对于计算机专业专科学生而言，本书可作一个学期的教材使用（其中带号的章节可以不讲）；对其它专业的学生，可根据需要讲授.参加本书编写工作的人员主要有：刘任任、张陵山、袁友伟、王婷、朱明娥、陈敏、吴湘华、罗扬、郑瑾、曹军、曹春红。由于编者的水平有限，难免存在错误和疏漏之处，恳请读者批评指正.最后，我们引用计算机科学巨匠、图灵奖获得者D.E.Kunth的一段话，来说明数学，特别是离散数学在计算机科学中的重要地位：“除了无穷维Hibert空间不可能用得上以外，其它数学理论都可能在计算机科学中得到应用.概括地说，在计算机科学的研究领域中，凡一2离散数学问题要求形式化、精确化表示，最可能用到的数学理论是数理逻辑，某些部分可能用到代数，甚至拓扑学；凡一问题要求表示出算法执行过程中各部分的逻辑结构或关系，最可能用到的数学理论是图论和数理逻辑，某些部分可能用到代数；凡一问题要求给出量的测定，最可能用到的数学理论是组合数学、数论和概率论等；凡一问题要求得出最优方案，最可能用到的数学理论是运筹学、数论，甚至将来有可能用到数学分析.”
编 者
2005年6月
公安网备 43010402000836 湘ICP备09001153号 新出网证(湘)字005号