-
绪章绪论
前言部分
-
●0.1前言
主要介绍 1.离散数学研究对象. 2.计算机有关专业为何要学习离散数学. 3.离散数学的主要内容. 4.离散数学的学习方法. 5.离散数学的学习资源
-
第一章集合、映射与运算
集合是现代数学的最基本概念，映射是现代数学的基本概念，运算本质上就是映射，其基本内容在中学已出现. 由于信息科学很多理论研究和应用研究都与集合、映射和运算有关，需要进一步较系统、深入地学习集合、映射和运算的有关内容.
集合、映射、运算和关系是贯穿于本书的一条主线，它们可使得离散数学内容不“离散”. -
●1.1集合的有关概念
集合是现代数学的基础, 是表示(离散)对象整体的数学工具.
-
●1.2映射的有关概念
映射就是函数, 研究的是任意两个集合之间的一种特殊对应关系，具有一定的抽象性.
-
●1.3运算的定义及性质
运算本质上是映射，是由已知对象得出新对象的一种方法.但运算更关注运算满足的一些运算性质，而根据这些性质可以对一些离散对象分门别类进行讨论.
-
●1.4 集合的运算
集合的常见运算:并运算、交运算、补运算、差运算和对称差运算
-
●1.5集合的划分与覆盖
集合的划分就是集合元素间的一种分类，比之更广的概念是集合的覆盖.
-
●1.6集合的对等
利用函数讨论集合的对等关系, 加深对集合特别是无限集合的理解.
-
第二章关系
世间万物都存在着联系，科学研究的主要任务是发现事物间的内在规律性. 借助于集合可以给出刻划这种联系的数学模型—关系(relation). 我们不以个别特殊关系为研究对象，而是关注关系的一般特性.
在信息科学中，数据与数据之间总存在着一定的关系，数据科学就是研究数据之间的关联关系. 关系这些内容对今后学习数据结构以及数据库等很多课程都是很重要的.
本章讨论的关系内容与数理逻辑、代数结构、图论以及组合计数等都有密切联系. 从这个角度去看，离散数学内容也是不离散的. -
●2.1关系的概念
借助于集合对各种各样实际关系建立的“关系”数学模型，推广函数概念.
-
●2.2关系的运算
关系的运算是为了从已知的关系得出新的关系.
-
●2.3关系的性质
在实际问题中，我们感兴趣的是具有某种性质或同时具有某几种特殊性质的关系.
-
●2.4关系的闭包
对于A上的关系R, 希望在R中添加一些有序对使其变成具有某些有用的性质，如自反性、对称性或传递性.
-
●2.5等价关系
等价关系基于某种标准将不同的事物看成是同一类，它同时具有自反性、对称性以及传递性.
-
●2.6相容关系
相容关系是对“相像”或“相似”事物进行的数学描述，它推广了等价关系.
-
●2.7偏序关系
序关系将依据某个标准对事物进行比较、排序，偏序关系是最常见的一种序关系，它本质上是两实数之间的小于等于关系“≤”的一种推广.
-
第三章命题逻辑
逻辑是一个常用的术语，平时说话、做事、思考问题等都要合乎逻辑. 比如，一位老师正在学校上课，而要说他在太空漫步就不合乎逻辑，把“逻辑地址”弄错了. 同时，逻辑推理也无处不在，从日常生活中的实际问题的解决到数学定理的证明以及程序正确性验证.
逻辑学是研究思维形式、思维方法及思维规律尤其是推理的学科，早在两千多年前就受到人们的重视，古希腊著名逻辑学家柏拉图的学生亚里士多德(Aristotle，公元前384--公元前322)是形式逻辑的创始人. 形式逻辑，现在称为普通逻辑学，要详细讨论概念(词项)、判断(命题)和各种形式的推理，研究逻辑基本规律等内容.
联合国教科文组织将逻辑学列为与数学、物理学、化学、天文学、地学、生物学同等重要的基础学科，在我国MBA 、MPA以及工程硕士入学考试加入了逻辑测试题，国内很多大公司、企业招聘高级员工时也开始加试逻辑测试.
德国数学家、哲学家莱布尼茨(G. Leibniz，1647--1716)首先提出用数学方法研究逻辑，就是建立一套表意符号体系，在符号之间进行形式推理. 莱布尼茨是数理逻辑的创始人. 也正因为这样，数理逻辑又称为符号逻辑，已有300多年的历史了.
除了传统的数理逻辑(内容包括逻辑演算、公理化集合论、模型论、递归论和证明论)外，还出现了各种各样的应用逻辑，如多值逻辑、模态逻辑、归纳逻辑、时序逻辑、动态逻辑、模糊逻辑、非单调逻辑、缺省逻辑、数字逻辑、电路逻辑、算法逻辑及程序逻辑等，这些都与计算机科学密切相关.
人们需要学习、思考机器特别是计算机是如何进行逻辑思维的，以便用硬件或软件去模拟(广义下的计算)实现人的逻辑思维，这是一种最好的计算思维(computational thinking)培养形式.
命题逻辑与谓词逻辑是数理逻辑的基础部分. 本章学习命题逻辑，内容涉及集合、映射、运算和关系等.
命题逻辑的研究对象是命题. -
●3.1命题的有关概念
计算过程就是推理过程,而每一步推理离不开判断,判断的对象就是命题.本节讨论命题的有关概念.
-
●3.2逻辑联结词
逻辑联结词类似于自然语言中的连词，它们是逻辑运算.
-
●3.3命题公式及其真值表
命题公式就是逻辑函数或逻辑表达式，将其所有可能的取值情况列成一个表，就得到命题公式的真值表.
-
●3.4逻辑等值的命题公式
两个命题公式逻辑等值是指它们在逻辑上说的事同一回事，是功能相同的两个逻辑电路.
-
●3.5命题公式的范式
命题公式的范式就是其标准形式或规范形式.
-
●3.6联结词集合的功能完备性
将联结词集S中的联结词理解为门电路，则S是功能完备的是指任何的组合逻辑电路都可以由这些门电路实现.
-
●3.7命题逻辑中的推理
推理是从一些前提推出结论的思维过程，本节讨论命题逻辑中的推理.
-
第四章谓词逻辑
原子命题是命题逻辑研究的基本单位, 没有对原子命题的内部结构及其逻辑关系进行讨论. 在实际思维中，仅有命题逻辑工具是不够的. 例如著名的苏格拉底(Scrates，柏拉图的老师)三段论
大前提：所有的人都是要死的.
小前提：苏格拉底是人.
结论：所以，苏格拉底是要死的.
这个推理的有效性在命题逻辑中无法证明，因为上面的每个命题都是原子命题，可以分别用 表示，然而 在命题逻辑中是无效推理.
之所以出现这种推理本身是正确的，但无法证明其有效性的问题，是因为没有对原子命题的内部形式结构及其逻辑关系进行讨论，这正是谓词逻辑首先要研究的内容，这些讨论涉及集合、映射、运算和关系.
本书讨论的谓词逻辑是一阶谓词逻辑.
利用谓词逻辑建立起来的数据库设计理论，具有牢固的数学基础和一定的智能特点. 同时，现实世界中的任何问题只要能用谓词逻辑推理系统方式表示出来，就可以将它写成逻辑程序设计PROLOG(PROgramming in LOGic)语言或LISP语言，并用计算机加以实现，如已经开发出的一些智能教学专家系统等. 1977年Amir Pnueli把时序逻辑(temporal logic)引入计算机科学获1996年图灵奖. -
●4.1个体、谓词、量词和函词
对原子命题的内部结构及其逻辑关系进行讨论.
-
●4.2谓词公式及命题的符号化
在谓词逻辑中将使用谓词将命题符号化得到的表达式就是谓词公式.
-
●4.3谓词公式的解释及类型
谓词公式的取值，取决于对其进行的解释或赋值.
-
●4.4逻辑等值的谓词公式
谓词公式在逻辑上说的是同一个意思就说它们等值.
-
●4.5谓词公式的前束范式
谓词公式的前束范式是将所有量词放在最前面的一种标准形式.
-
●4.6谓词逻辑中的推理
谓词逻辑中的推理就是谓词公式间的逻辑蕴涵式.
-
●4.7常用证明方法
常用证明方法有哪些
-
第五章初等数论
初等数论又称为算术，它起源于古希腊. 被C. F. 高斯誉为“数学皇冠”的数论是一门研究整数特别是正整数性质的学科，它有近四千年的古老历史却始终充满青春活力. 中国在数论研究方面也取得了辉煌的成就，如中国剩余定理和陈氏定理等.
初等数论在算法学、密码学等计算机领域有非常重要的应用，国外离散数学教材几乎都会有这部分内容，其讨论范围为离散的整数集Z = {…, -3, -2, -1, 0, 1, 2, 3, …}.
通过本章学习，可较深入体会集合、映射(即函数)、运算和关系在具体学科研究中所扮演的角色. -
●5.1整除关系与素数
与整数集Z 上的整除关系和素数有关的一些结论
-
●5.2模同余关系
介绍整数集Z上的模m同余关系
-
●5.3RSA密码算法
RSA密码算法是数论知识在密码学中的一个重要应用
-
第六章图论基础
图论的创始人是瑞士数学家L. Euler，他于1736年首次建立“图”模型解决了Köningsberg七桥问题.
1936年匈牙利的Deneskönig出版了第一本图论方面的专著，在这期间德国的G. R. Kirchhoff，英国的A. Cayley和W. R. Hamilton以及法国的M. E. C. Jordan等人都做出过开创性的工作.
将集合间的关系画图表示出来就是图. 图论讨论的是“拓扑结构”，涉及到集合、映射、运算和关系等，其应用领域非常广泛，它已经渗透到诸如语言学、逻辑学、物理学、化学、电信工程、信息论、控制论、经济管理等各个领域，特别是在计算机科学中的数据结构、计算机网络、计算机软件、算法理论、操作系统、分布式系统、编译系统以及数据挖掘等方面都扮演着重要角色.
实际上，数据库和软件工程中的E-R图, Internet、WWW和社会网络等复杂网络研究都要用到较深入的图论知识, 计算机算法很多都是归结到图论算法进行研究的.
知识图谱(KG, Knowledge Graph)是当前人工智能研究的热点之一. -
●6.1图的基本概念
将集合元素及其之间的关系画图表示出来就是图.本节介绍与图有关的一些基本概念.
-
●6.2节点的度数
与节点关联的所有边的关联次数之和即为该节点的度数.
-
●6.3子图和图同构
子图一般比原图要“小”，图同构指它们本质上是相同的.
-
●6.4路与回路
从一个节点出发，沿着一些边连续移动到另一个节点的问题，这得到路.
-
●6.5图的连通性
无向图的连通性及连通度；有向图的连通性
-
●6.6图的矩阵表示
把图用矩阵表示出来，便于用数学方法和计算机处理
-
●6.7赋权图及最短路径
将一些附加信息赋予图的边或节点，这就是赋权图.
-
第七章几类特殊的图
图论是处理离散对象的一种重要的数学工具. 本章讨论几类在理论研究和实际应用中都有着重要意义的特殊图.
-
●7.1Euler图
欧拉研究“七桥问题”时考虑的一种图
-
●7.2Hamilton 图
起源于汉密尔顿周游世界游戏
-
●7.3无向树
不含有圈的连通无向图称为无向树
-
●7.4有向树
一个有向图在不考虑边的方向时是一棵无向树，则该有向图称为有向树
-
●7.5平面图
把图画在一个平面上，同时使得图的边在非节点处不相交,该图就是平面图，起源于地图作色.
-
●7.6平面图的面着色
对平面图的每个面涂上一种颜色且相邻的面出现不同的颜色，就是该平面图的面着色.
-
●7.7二部图及其匹配
在诸如人员分配、资源分配等问题的讨论中，经常涉及到二部图及其匹配.
-
第八章组合计数
我们知道，离散数学研究离散对象. 组合计数，简称计数(counting)就是计算满足一定条件的离散对象的安置方式的数目.
对于给定离散对象的安置方式，要考虑其存在性问题、计数问题、构造方法、最优化问题，这些是组合数学研究的全部内容. 组合数学发源于数学消遣和数学游戏，其研究历史可追溯到公元前2200年中国的大禹治水时代，从洛河中浮出的神龟背部上出现的三阶幻方开始，该方阵的每一行、每一列以及两条对角线的三个数字之和都等于15，其研究方兴未艾.
计算机科学是研究算法的一门科学，组合计数是算法分析与设计的基础，它对于分析算法的时间复杂度和空间复杂度是至关重要的. 当然，组合计数在诸多领域的很多问题的讨论中也经常用到. 从儿时的数“数”也略知组合计数的重要性.
本章主要讨论组合计数的基本计数技巧和方法，包括计数原理、排列组合、二项式定理、生成函数与递归关系等内容，它们都与集合、映射、运算和关系密切联系. -
●8.1排列组合与二项式定理
排列与组合是组合计数的基本问题
-
●8.2生成函数
组合及排列计数的生成函数
-
●8.3递归关系
有一些计数问题可以归结到建立递归关系，求解递归关系
-
第九章代数结构
介绍代数结构的一般内容以及常见的几种代数结构，它是一种用代数方法建立的数学模型.
代数结构简称代数，不过是抽象代数(abstract algebra)或近世代数(modern algebra)，不是初等代数，也不是高等代数，它始于19世纪初，形成于20世纪30年代，在这期间，挪威数学家N. H. Abel、法国数学家E. Galois、英国数学家A. De Morgan和G. Boole等人都作出了杰出的贡献.
代数结构研究由一般元素(不仅仅是数字、符号等)组成的集合上的运算，以及运算满足一些给定性质的数学结构的性质.
代数结构在计算机科学中起着重要作用，前面几章分别讨论的是集合代数、关系代数和逻辑代数. 实际上，计算机系统本身就是一种代数结构. 众所周知利用布尔代数可进行逻辑电路设计的分析和优化. 利用代数结构可研究抽象数据结构的性质与操作，它也是程序设计语言的理论基础.
在本章讲解的群、环、域是根据运算及其所满足的性质按“代数结构”进行分类的，格和布尔代数是根据“序结构”进行的讨论，它们在组合计数、代数编码理论、形式语言与自动机理论等学科中都发挥了重要作用. 同时，代数结构的研究采用的是形式化方法，对于培养大家的抽象思维和计算思维能力是非常有用的. 各种进程代数(process algebra)是研究计算系统形式语义的重要方法. -
●9.1代数结构简介
代数结构是一种用代数方法建立数学模型的方法.
-
●9.2群的定义及性质
在研究用根式求解方程的过程中得到群的概念，在具有对称性问题研究中应用广泛.
-
●9.3环和域
环和域是有两个2元运算的代数结构. 环和域的理论在计算机科学特别是在编码理论的研究中有诸多应用.
-
●9.4格与布尔代数
布尔代数是英国数学家Boole在对逻辑思维法则进行研究时提出的,格是布尔代数的推广.