《离散数学》共14章,第1~2章为数理逻辑,第3~5章为集合论,第6~8章为代数系统,第9~10章为组合分析与算法数论,第11~14章为图论。每部分内容尽量由浅入深,同时都尽量安排了“应用”,试图让读者懂得“学以致用”。其中有些应用对科技进步产生重要作用,有些应用在科学理论上意义重大。
《离散数学》内容丰富翔实,条理清晰,可作高等院校计算机、电类及相关专业“离散数”课程的教材,也可作为相关科研人员的参考书。

第1章 命题逻辑
本章介绍命题逻辑的基本知识、基本思想和方法。命题逻辑又称命题演算,是以命题为研究对象、以推理中前提和结论之间的形式关系为研究目的的逻辑学科,包括命题与联结词、命题公式(特别是真值���技术)、等值演算、命题公式的范式、联结词的功能完全集、永真蕴涵式、命题逻辑的推理理论、命题逻辑推理的机械化方法等。
1.1 命题与联结词
1.1.1 命题基本概念
命题对于命题逻辑来说是一个原始的概念,因此不能在命题逻辑的范围内给出它的**定义,只能描述它的性质。
【定义1.1】在经典命题逻辑中,把能判断真假但不能既真又假的陈述句的内容称为命题。
命题必须为陈述句的内容,而不是陈述语句。有关语句的介绍可见第6章。
为了说明命题是陈述语句的内容,通常在陈述语句外面加引号来表示命题。例如,陈述语句:3是素数。构成的命题是“3是素数”,即3是素数是语句(不是命题),“3是素数”是命题。
命题必须具有真假值。疑问句、祈使句、感叹句的内容没有真假之分,所以它们不是命题。例如,“北京是中国的首都”是命题;“关门!”,“你上哪里?”这种命令和问话语句其内容不能判断真假,所以不是命题;“太阳系外有外星人”,目前人类尚无法确定其真假,但从事物的本质而论,该语句的内容是可分辨真假的,所以它也是命题。
顾名思义,离散数学是研究离散对象及其相互间关系的一个数学分支,它的基本内容已出现在现代科学技术的各个领域。例如,计算机科学、程序设计、计算机网络、信息论与编码、通信理论、现代密码学、数字信号处理和形式语言等都与离散数学密切相关。正因为如此,离散数学在国际上已受到高度重视,在我国也已成为理工科高等院校各专业的重要基础课,尤其是计算机和应用数学专业。
离散数学的内容非常广泛,它至少包含了数理逻辑、集合论、代数学、组合数学、数论、图论、计算理论和复杂性理论、复杂网络以及协同网络计算等内容。这些内容里面又细分了许多个分支学科,包含了当前国际前沿的数学和科学技术理论研究课题。在已出版的众多离散数学教科书及其习题解答中,大部分都是介绍那些应用广泛且易理解、可接受的基本知识和方法。我们也出版了一本《离散数学学习指导》,该书的写作风格类似于国外流行的Schaum’s Outline Series教材,在内容上则增加了“密码学”或“信息**理论”的数学基础内容,使离散数学的基本内容有了一些扩展。而本书是在《离散数学学习指导》的基础上编写的一本适应面广、内容适中的离散数学教材。
全书共五篇,依次为数理逻辑、集合论、代数系统、组合分析与算法数论、图论,分成14章:命题逻辑,谓词逻辑,集合,关系,函数,半群、语言和自动机,群、环和域,格与布尔代数,组合分析,算法数论,无向图,平面图与图着色,有向图,树。各章都尽量安排了“应用”,试图让学生学以致用。其中,有些应用是对科技进步产生重要作用的,例如,自动定理证明、数字电路、语言与有限自动机、基于身份的密码设计等;有些应用在科学理论上意义重大,例如,超越数无穷的集合论证明等。另外,第10章(算法数论)还引进了*新的研究成果,特别是近几年才产生的“双线性配对与基于身份的密码”,供读者选学。

出版者的话
序言
前言
教学建议
**篇 数理逻辑
第1章 命题逻辑
1.1 命题与联结词
1.1.1 命题基本概念
1.1.2 命题联结词
1.1.3 复合命题
1.2 命题公式
1.2.1 定义
1.2.2 赋值
1.2.3 真值表技术
1.3 等值演算
1.3.1 基本等值式
1.3.2 等值演算过程
1.3.3 对偶公式和内否公式
1.4 命题公式的范式
1.4.1 析取范式和合取范式
1.4.2 主范式
1.5 联结词的功能完全集
1.5.1 真值函数
1.5.2 功能完全集
1.6 永真蕴涵式
1.6.1 基本永真蕴涵式
1.6.2 证明永真蕴涵式的方法
1.7 命题逻辑推理
1.8 命题逻辑归结推理法
1.9 命题逻辑推理的机械化方法
第2章 谓词逻辑
2.1 谓词逻辑的基本概念
2.1.1 谓词的概念
2.1.2 量词的概念
2.2 谓词逻辑公式
2.2.1 合式公式
2.2.2 约束变元和自由变元
2.2.3 赋值
2.2.4 换名规则和替换规则
2.3 谓词逻辑的等值演算与前束范式
2.3.1 基本等值式
2.3.2 前束范式
2.4 Skolem 标准型
2.4.1 前束范式
2.4.2 无前束范式
2.5 谓词逻辑的推理理论
2.5.1 基本永真蕴涵式
2.5.2 推理规则
2.5.3 推理实例
2.6 谓词逻辑的归结推理法
2.6.1 归结证明过程
2.6.2 归结证明实例
第二篇 集合论
第3章 集合
3.1 集合的定义
3.2 集合的基本运算
3.3 有限集合的计数
3.4 集合表达式的相等与包含
3.5 集合的特征函数
第4章 关系
4.1 二元关系
4.2 二元关系的表示及按性质分类
4.2.1 二元关系的关系矩阵和关系图表示
4.2.2 二元关系的按性质分类
4.3 二元关系的运算
4.4 二元关系的合成
4.5 关系的闭包
4.6 等价关系和偏序关系
4.6.1 等价关系
4.6.2 偏序关系
第5章 函数
5.1 函数的基本概念
5.2 函数的性质
5.3 函数的复合与反函数
5.4 可逆函数集与置换
5.5 二元运算
5.6 基数
第三篇 代数系统
第6章 半群、语言和自动机
6.1 半群与语言
6.2 语言和文法
6.3 有限状态机
6.4 有限状态自动机
6.5 语言与自动机的关系
第7章 群、环和域
7.1 群的基本概念
7.2 子群
7.3 群的同态与同构
7.4 子群的陪集
7.5 对称群、置换群、正规性与商群
7.6 群在集合上的作用
7.7 同态基本定理与同构定理
7.8 环的基本概念
7.9 子环、理想与商环
7.10 交换环中的因子分解
7.11 多项式环
7.12 多项式环的因子分解
7.13 域的基本概念
7.14 分裂域
7.15 有限域
第8章 格与布尔代数
8.1 格的概念
8.2 分配格
8.3 有补格
8.4 布尔代数
8.5 布尔表达式
8.6 数字电路与*小化
第四篇 组合分析与算法数论
第9章 组合分析
9.1 计数
9.2 排列与组合
9.3 递推序列
9.4 抽屉原理
9.5 生成函数
第10章 算法数论
10.1 整数论
10.2 与整数有关的典型算法
10.3 素性测试、因数分解与公钥密码学
10.3.1 素性测试
10.3.2 因数分解
10.3.3 公钥密码
10.4 有限域上的椭圆曲线算术和ECC
10.5 配对和基于身份的公钥密码体制
10.5.1 双线性配对
10.5.2 基于身份的密码
第五篇 图论
第11章 无向图
11.1 无向图的基本概念
11.2 无向图的表示
11.3 无向图的连通性
11.4 欧拉图与哈密顿图
11.4.1 欧拉图
11.4.2 哈密顿图
11.5 *短通道问题
第12章 平面图与图着色
12.1 平面图的基本概念
12.2 欧拉公式和极大平面图
12.3 平面图的对偶图
12.4 图着色
第13章 有向图
13.1 有向图的基本概念
13.2 有向图的连通性
第14章 树
14.1 基本定义和性质
14.2 生成树与*小生成树
14.3 有根树
14.4 二叉树和哈夫曼树
参考文献

……

讲解透彻:深入浅出地介绍离散数学所包含的基本知识。
内容新颖:融合了作者自己的理解、体会、方法和结果。
注重应用:介绍了一些相关知识在现代科学技术领域的应用。
习题适中:便于学生巩固所学知识、加深理解,学以致用。