离散数学笔记Discrete Mathematics

---

离散数学笔记

Discrete Mathematics

• —————————————————————————————–Design By 2100301629王家寧

第一章 集合

1.集合的运算

①补运算

---

②对称差运算

2.集合运算的性质

①集合运算的基本恒等式

（可用文氏图进行相关推导）

重点记忆德摩根律和补交转换律 ⑩和⑪

德摩根律：补集分配进括号里面就把括号里面的交并符号反过来

补交转换律：交补连着写可以换成差

---

在证明题中，可以使用假设X来进行代入来证明，也可以通过举反例来列出具体的实例来推翻命题

---

②容斥原理

容斥原理由来：将相容重的集合部分在计算并集集合的基数的时候进行排斥出去，故称容斥原理

基数：集合中元素的个数

---

---

第二章 关系

1.序偶与笛卡尔积

• 序偶中有几个元素就叫做几元序偶

笛卡尔积的定义

---

---

笛卡尔积的性质

• 笛卡尔积不满足交换律和结合律，但是对交和并都满足分配律
• 

---

2.关系的定义

---

---

几种特殊的关系：空关系、全域关系、恒等关系

---

　　关系的定义域和值域

---

3.关系的表示

• 关系图通过有向弧的方式表示

---

• 关系矩阵表示法

  

---

4.关系的性质

①自反性与反自反性

---

②对称性与反对称性

---

---

对称性和反对称性并非对立关系

③传递性

关系性质的判别

5.关系的基本运算

关系是一种特殊的集合，因此集合的基本运算对关系也同样适用

---

6.关系的复合运算

---

复合关系的关系矩阵

---

• 矩阵相乘是将==前矩阵==的第一行分别和==后矩阵==的各列进行相乘并相加得到==新矩阵==的==第一行元素==
• 这里改为布尔与和布尔或运算是因为，有时运算结果是2或者更多，但是==实际上是一个序偶==，所以结果为一

---

复合运算满足==并运算==的分配律，但是不满足==交运算==的分配律

---

7.关系的逆运算

• 将元素对调，矩阵转置即为关系的逆运算

---

逆运算的性质

---

8.关系的幂运算

R的零次幂就是A上的恒等关系

---

关系的幂运算的关系矩阵示例

---

---

---

幂运算的性质：简言之，有限集A上的关系R的幂序列R的0~n次幂是一个周期变化的序列（n无穷大）

也就是==鸽巢原理==：如果有n+1个鸽子飞进了n个鸽巢中，那么必定有鸽巢中至少飞进了2只鸽子。

---

9.关系的闭包运算

三种闭包运算也即添加最少序偶元素来让序偶集合符合自反、对称、传递关系的运算

自反闭包 r(R)

对称闭包 s(R)

传递闭包 t(R)

---

---

---

• 闭包运算的性质

10.等价关系

①等价关系的定义

满足自反、对称、传递的关系即为等价关系

---

②等价类的定义

等价类后面的括号里包括自身

---

---

11.商集

①商集的定义

特别的可以记一下A关于==恒等关系==还有==全域关系==的商集

• ==不要记错商集是共有的后边的元素而不是等价类==
  • ==也就是满足特定关系的各个划分的集合共同组成一个新的集合==

②划分的定义

特别的，一一对应的商集和划分，对应某等价关系的商集所形成的划分，叫做由该等价关系导出的==等价划分==

由某划分确定的等价关系，称为由该==划分所导出的等价关系==

---

通过划分求对应的等价关系

• 通过划分的各个集合求笛卡尔积之后再求并集，所得结果即为所求等价关系

通过等价关系求对应划分

• 通过等价类导出对应的商集，所得商集即为所求等价划分

---

12.偏序关系

①偏序关系的定义

自反的、反对称的、传递的。

---

可比与盖住的定义

---

X、Y符合关系则为可比的

不存在中间元素，则为盖住

---

13.哈斯图和特殊关系

①哈斯图的定义以及绘制步骤

---

②特殊元素

最大元和最小元

---

极大元与极小元

---

总结与分辨

---

上界与下界

---

上确界与下确界

---

总结与分辨

---

第三章 函数

1.函数的定义

①函数的定义

---

②函数与关系的区别

---

③函数的特点

---

④函数的数量问题

---

---

2.特殊函数

①特殊函数的分类

单射函数、满射函数、双射函数

---

②特殊函数的必要条件

---

③特殊函数的数量

---

---

3.函数的运算

①函数的基本运算

函数是一种==特殊的关系==，因此关系的所有运算都适用于函数，如，集合的基本运算、关系的复合运算和逆运算等。但运算的结果并不一定都是函数，如下基本运算就不是函数

---

②函数的复合运算

函数是一种特殊的关系，能进行关系的复合运算。函数经复合运算之后仍然是函数。

---

③函数复合的性质

---

④逆运算的定义

---

⑤复合函数的实例（洗牌）

​

---

---

⑥复合函数与逆函数的实例（凯撒密码）

---

第四章 命题逻辑

1.命题

①命题的定义

---

②简单命题/原子命题

---

③复合命题

---

2.命题联结词

否定联结词 ¬

合取联结词 ∧

析取联结词 ∨

蕴含联结词 → ==前真后假方为假==

等价联结词 ↔ ==同真同假方为真==

---

3.命题符号化及其应用

• 命题符号化一般分为三个步骤

①简单命题的符号化

②联结词的符号化

③“联结”简单命题

4.命题公式和真值表

①命题常量和命题变元定义

---

②成真赋值和成假赋值

---

③真值表

---

5.命题公式的分类

①重言式/永真命题公式

任何情况下均为真

---

②可满足公式

至少存在一种为真的情况

• 重言式是特殊的可满足公式

---

③矛盾式/永假命题公式

在任何情况下均为假

---

6.命题公式的逻辑等值及应用

①命题公式的等值式

---

②基本等值式

可以和集合的交并补等操作进行互换

==重点== ⑪~⑯ 德摩根律、蕴含等值式、等价等值式、假言易位（逆否）、等价否定等价式（逆否）、归谬论

---

③等值演算

==在等值演算的时候要注意符号的优先级，确定好式子的前界和后界==

• 同时也要合理使用结合律来简化操作去除括号
• 优先级越高越放在最后看，先看优先级低的，将其转化为优先级高的

证明两个公式等值

---

---

简化公式

• 也可以再写一步蕴含等值式，得出¬p∨r

---

等值演算也可以用来判断公式的类型：重言式、矛盾式等

---

示例

---

7.范式

①简单析取式和简单合取式

简单析取式和简单合取式的定义

---

②合取范式

合取范式的定义

---

③命题公式的范式求解

任何命题公式都存在与之等值的析取范式和合取范式，但是不一定唯一

重点==蕴涵等值式、等价等值式、双重否定律==

---

示例

---

④命题公式的范式应用

示例例题

• 首先把各种能达到齐全功能的选择方案进行合取（这里是根据题意进行操作）来得到原始式子
• 之后通过命题公式的规律求解得到命题范式，这里是简单析取式
• 其中简单合取式子里面的每一个命题单元就是一个方案

---

8.主范式

①极小项和极大项

简单合取式中，每个命题变元和其否定不同时出现，但是一定要出现一个

n个命题变项可以生成2^n^个极小项和2^n^个极大项。

---

其中，从（0,0,0）开始赋值，此时的符号表示为==m0== 此后依次赋值改为1 并向后递推

极大项和极小项的成真赋值和成假赋值，彼此之间进行取非，一一对应，如上图

---

②极小项和极大项的性质以及对应关系

---

③主析取范式

每个简单合取式之中都要有该命题变元的极小项，也就是一定要有某个命题变元的本身或者其否定，==但不是同时有，只要有一个，其本身和其否定不能同时出现==

任何命题公式都存在与之等值的唯一主析取范式

---

• 主析取范式的求解步骤

主要使用排中律进行求解添项

---

• 主析取范式的求解示例

---

④主合取范式

每个简单析取式之中都要有该命题变元的极大项，也就是一定要有某个命题变元的本身或者其否定，==但不是同时有，只要有一个，其本身和其否定不能同时出现==

任何命题公式都存在与之等值的唯一主合取范式

---

• 主合取范式的求解步骤

主要使用同一律和矛盾律进行求解添项

---

• 主合取范式的求解示例

---

其中符号下标的表示可以参考极小项和极大项的对应表格

---

⑤主范式相关关系

---

如题，可以发现主合取范式的符号表示正好和主析取范式的符号表示在0~7之间互补，因此可以复习一下之前的知识点

• 主范式的符号表示（m0）对应的极小元（命题公式pVqVr）根据命题单元的个数n决定数量，其个数为2^n^
• 主析取范式使用小写m0表示，主合取范式使用大写M0表示
• 主析取范式的下标和主合取范式的下标在0~2^n^-1范围内互补^(？)^
• (?)的原因是：极大项和极小项的成真赋值和成假赋值，彼此之间进行取非，一一对应，可以参考四.8.①表格，详细证明见下

---

---

⑥主范式的作用

• 通过求解主析取范式和主合取范式可以统一表示某个问题的表达，因为其具有唯一的主范式，通过此唯一的主范式可以求出其对应的成真赋值和成假赋值

• 因此可以判断命题公式的类型：重言式、矛盾式、非永真式的可满足式

• 判断命题公式是否等值：当且仅当其具有相同的主析取范式/主合取范式

• 因此也便于计算机求解相关问题

---

---

简记：

• 小m全有为重言式/永真式

• 大M全有为矛盾式

• 只有一部分则非永真式的可满足式

---

⑦主范式的实际应用

派人问题

9.简单证明推理

①推理的基本形式定义

---

②永真/重言蕴含式的定理及定义

---

---

③简单证明推理例题

---

如上例题，将所有前提以及结论使用命题公式表示出来，再进行交集操作，因为要保证这些要同时成立

之后解法有三：

①利用等值演算

②利用主析取范式和主合取范式

③利用真值表

---

---

10.构造证明推理

引言

---

①构造证明推理定义

基于永真蕴含式或推理规则进行的命题公式的推理称为构造证明推理

②构造证明推理规则

---

==重点记忆==

---

---

③置换规则

①前提引入规则:在证明的任何步骤上，都可以引入前提
②结论引入规则:在推理中，若一个或一组前提已证出结论B，则B可引入到以后的推理中作为前提使用。
③置换规则:在推理过程的任何步骤上，命题公式中的任何命题公式都可以用与之等值的命题公式置换。

---

④直接构造证明推理

---

⑤间接构造证明推理

---

---

也就是将所求结论的前界加入到前提之中形成析取命题公式，之后继续推导结论的后界为真即可

---

---

除上述两种方法之外，还可以使用归谬法来证明原命题的正确性，也即把结论取反，然后和前提进行等值演算得出其结果为0（假）

---

第五章 谓词逻辑

1.谓词逻辑的基本概念

①个体词的定义

个体词→个体常量、个体变量

个体域→全总域

---

②谓词定义

谓词常量

谓词变量

n元谓词，特殊的有0元谓词

---

• 谓词的使用示例

---

③函词

函词的定义

---

函词就是一般意义下的函数，n元函词就是n元函数，只不过函词的定义域为==个体域的笛卡尔积==，函词的值域为==个体域==

值得注意的是：n元谓词也是一个n元函数，其区别在于：前者的值域为0和1，而后者的值域为个体域

• 函词和谓词的区别：

函词使用小写，谓词使用大写

函词是映射，谓词表示特定的性质或者关系

函词通常是==是什么==，谓词通常是==的什么==或者==在……北方==之类的

④量词

一、全称量词

---

二、存在量词

---

2.谓词符号化

①谓词符号化的常用规则

---

②谓词符号化应用（机器人移盒子问题）

---

3.谓词公式

①项

项的定义

---

②原子谓词公式

可以类比简单公式/原子公式

---

③谓词逻辑公式

---

④约束变元和自由变元

辖域/作用域/约束域、作用变元/指导变元、约束出现/约束变元、自由出现/自由变元

---

• 约束变元和自由变元示例

---

在不造成公式冲突的情况下，可以更改一个或者多个变元的符号

这样可以使原得公式更为清晰明了

---

4.谓词公式的解释和分类

①谓词公式的解释定义

---

示例

---

---

由此可见，根据不同的解释，谓词公式在其解释下的取值有所不同，这里可以类比第四章的命题公式的成真、成假赋值

②谓词公式的分类

永真谓词公式、可满足谓词公式、永假谓词公式

---

在谓词逻辑中，谓词公式的解释依赖于个体域，导致了真值表法在判断一个谓词公式的类型时很难实施。

---

---

---

---

5.谓词公式的逻辑等值

①谓词公式的等值式

---

②谓词公式的代换实例

通过使用谓词公式代换命题变元所得到的谓词公式称为其对应的一个代换实例

注：可满足公式的代换实例不一定是可满足式

---

---

③命题逻辑等值式的推广

注意这里的全称量词和存在量词要保持一致

注意这里的A(x)里面的x为自由变元，因为要保证其确定性，所以取任何值不能影响其结果，不能只在一部分情况下适用

---

⑤量词消去律

全称量词也就是对任意的个体变元都适用，在这里我们使用交集

存在量词也就是存在一个个体变元使用，在这里我们使用并集

注意在这里量词的顺序很重要，顺序不同结果不同，因此并不能随意的调换

A(x)是谓词公式，并不要简单的理解为原子谓词公式

---

• 示例

---

⑥量词与否定的交换律

也就是量词和否定转换之后，量词的全称和存在属性要改变

---

⑦量词辖域收缩与扩张律

就是贴一块儿而已，简单，感觉没必要记，但是还是写一下

---

⑧量词分配律和双量词交换律

注意第三、四条的X和Y的变化

---

• 例题示例

---

6.前束范式

①前束范式的定义

前束范式、母式

前束范式可以类比前面的主范式，但是是两个完全不同的东西，互通的方面也不是很多

---

任何谓词公式都存在与之等值的前束范式，但是并不唯一，因为前面的量词位置可以不同，约束变元的表达形式也可以不同

---

②前束范式的求法原理

---

• 示例

---

---

7.谓词逻辑推理

在谓词逻辑中，谓词公式的推理依赖于个体域，求解谓词公式在各种解释下的真值往往非常繁琐，甚至异常困难

这就导致了命题逻辑中的简单证明推理在谓词逻辑中不容易实施

在谓词逻辑中的推理通常是基于永真蕴含式或构造逻辑推理

---

①谓词逻辑推理的基本形式

可以类比命题逻辑推理的基本形式

---

---

②简单证明推理

可以转换为重言式的证明或者矛盾式的证明

矛盾式也就是将==重言式的蕴含式==使用蕴涵等值式之后将左侧的==非==再进行代入，如下图

---

也可以代入实例

---

---

命题逻辑中的推理规则也可用在谓词逻辑的构造证明推理中。

---

③构造证明推理规则

构造证明推理可以有效解决苏格拉底假言三段论的问题

---

以下为多出来的有关量词的消去规则

注意：约束变元的限制条件

选择一个常数a进行代入就可以

US规则

UG规则

同样选择一个常数a代入就可以

ES规则

EG规则

---

---

---

• 示例

---

---

---

不能交换的原因：③是由②所得来的，是存在量词，③具有特殊性，而④是由①推导来的，是全称量词，④具有一般性

特殊可以满足一般，但是一般不一定满足特殊，而c又已经确定为同一个，因此该顺序不能交换

---

④附加前提证明法

在谓词逻辑的推理中，如果结论是以蕴含式形式给出，则蕴含式的前件可作为推理的前提使用。

---

• 例题示例

---

⑤反证法/归谬法

结论的否定引入

---

• 示例例题

---

---

---

• 上下册分分界线

---

---

---

第六章 代数系统

1.代数系统的基本概念

①代数运算的定义及其性质

唯一性、全域性、==封闭性==

---

• 代数运算的判断示例

---

模K加法

---

模K乘法

---

②运算表

---

③代数系统的定义

---

④子代数系统的定义

---

• 示例及其证明

---

2.代数运算的基本性质

交换律、结合律、分配律

---

①交换律

是否满足交换律也可以通过看运算表是否对称的方式来判断

---

②结合律

---

③分配律

注意区分左可分配、右可分配

---

④幂运算的定义

注意其中示例的运算方法，要根据具体的代数系统来进行操作

---

• 实例

---

3.代数运算的吸收律性质

问题引入：如何像交并、析取合取一样抽象表述代数运算的吸收律

吸收律简记：括号内外的运算不同，而括号外有和括号内相同的部分，则不同的部分（B）被吸收，只留下相同的部分（A）

在运算系统中，还要注意其左右位置

---

这里的*和Δ仅仅表示二元运算

---

这里说====对==Δ==是左可吸收的，也就是指====是在括号的外面，而==Δ==在括号的里面，同理可得右可吸收的

---

• 实例

---

4.代数运算的幂等律和消去律

①幂等律定义

也就是二元运算作用于个体域中的每一个对象之后，结果还是它本身，那就符合幂等律

---

②消去律定义

也就是等式相同可以推到得出等式同项相消除，留下来的部分相等

---

• 示例

---

---

5.代数运算的特殊元素

①等幂元

在某个代数系统中，某个元素通过代数运算之后，结果还等于它自身，则该元素就是关于该运算的等幂元

---

• 示例

---

②零元

任何元素和一个特定元素进行二元运算之后的结果始终等于该特殊元素，则该特殊元素称为零元

零元也有左右之分

零元必为等幂元

---

零元具有唯一性，因为不能有两个特殊元素保证运算后和自身相等

运算表中，某元素是等幂元的充要条件是该元素在对角线上的取值为其本身

运算表中，某元素是零元的充要条件是该元素对应的行、列元素均与该元素相同

---

③单位元

任何元素和一个特殊元素进行二元运算，所得结果都为选取的任何元素，则该特殊元素称为代数系统的单位元

幺元也必为等幂元

单位元也有左右之分

单位元又称为幺元

---

幺元也具有唯一性，同理零元

---

• 幺元的求法

假设代入求解法，此方法也适用于其他代数运算的特殊元素

---

④逆元

某元素和另一个元素进行二元运算，所得结果为单位元e，则该元素称为某元素的逆元

逆元也有左右之分

每个元素的逆元都是唯一的

---

元素逆元的逆元是其本身

---

---

• 实例

---

⑤可消去元

定义

---

---

如果a存在逆元，则a就是可消去元，证明如下

---

---

⑥特殊元素求解

等幂元求解、零元求解

---

单位元求解、幺元求解

---

逆元求解

---

可消去元求解

---

6.同构代数系统

引入：使用双射函数来表示两个结构相同的代数系统之间的关系

①同构代数系统定义

---

证明代数系统同构，要构造出其符合的双射函数

---

②同构代数系统的证明

---

③自同构代数系统

---

④自同构映射示例

---

⑤代数系统同构关系性质

代数系统的同构关系是等价关系

---

---

这里函数是有具体含义的，不能直接换给另一个用

---

*　###### 同构代数系统的概念可以推广到含有多个代数运算的代数系统

---

7.同态代数系统

引入：两个代数系统没有完全相同的结构，但存在一些相似的性质

①同态代数系统的定义

---

---

设函数f是代数系统<S,﹡>到<T,◦>的同态映射，则同态像f(S)是集合T的非空子集。

---

• 示例

---

---

②自同态代数系统

---

• 示例

---

N6中的元素为012345

---

自同态映射的证明最关键的一步

---

③同态核

设函数f是代数系统<S,﹡>到<T,◦>的同态映射，则同态核Ker(f)是集合S的非空子集。

同态核可以用来求解子代数系统

注意==f(x)==的结果要是**==幺元==**才行

---

---

8.同态映射的性质

引子

---

①可交换性和可结合性对应

---

②单位元和零元一一对应

---

③逆元和等幂元一一对应

---

• 示例

---

④代数系统同态的意义

---

⑤同态概念推广

---

9.代数系统的应用

引入问题分析

---

---

①同余关系

---

②国际标准书号校验码

---

---

---

第七章 典型代数系统

1.半群和子半群

①半群的定义

---

查看是否有结合性判断半群

---

• 示例

---

②半群的性质

---

---

③子半群的定义

---

根据封闭性判断是否是子半群

---

2.独异点和子独异点

①独异点的定义

---

根据幺元判定独异点

---

---

②子独异点的定义

---

根据子群、相同幺元、封闭性判断子独异点

---

---

3.群

①群的定义

---

根据结合律、幺元、逆元判定群

---

---

---

③群的阶数定义、无限群

---

④元素的阶数

---

④群的应用 Klein四元群

---

---

4.群的性质

①性质一

幺元是唯一的等幂元

---

---

②性质二

G中至少有两个元素时，不存在零元

---

---

③性质三

V a,b∈G， 如果a====b =b或者b====a=b， 则a是关于运算“*”的幺元。

---

---

④性质四

任一元素都是可消去元

---

---

⑤性质五

待转换公式

---

---

⑥性质六

待转换公式

---

---

⑦性质七

待转换公式

---

---

⑧⑨性质八九

待转换公式

---

---

群性质的应用

---

---

5.子群

①子群的定义

---

②子群的求解

---

---

6.子群的性质

性质一

---

性质二

---

性质三

---

• 示例

---

性质四

有限子群的判定方法

---

性质五

---

拉格朗日定理

---

子群性质的应用 Klein

Klein

---

7.交换群和循环群

①交换群的定义

---

②循环群的定义

---

③循环群的判定

---

• 示例

---

---

---

8.循环群的性质

---

---

---

---

• 示例

---

---

---

9.群的应用

引入

---

---

奇偶校验码

---

汉明距离定义

---

汉明距离性质

---

• 实例

---

---

---

第八章 图论基础

1.图的基本概念

①无序对、无序序偶、无序积

---

②图的阶数、有向边、无向边、自环、关联边

---

• 示例

---

③重复边、重数

---

④图的分类定义

---

---

2.子图

①子图的定义

---

②生成子图的定义

---

④导出子图的定义

---

示例

3.握手定理

①节点度数定义

---

②握手定理

---

---

---

• 推论

---

---

• 示例

---

③握手定理的应用

---

4.图的同构

①图的同构定义

---

②图同构的必要条件

---

③同构实例

---

---

5.通路和回路

①通路和回路的定义

---

---

②通路和回路的性质

---

---

示例

---

---

---

6.图的连通性

①无向图的连通性

---

---

②连通分支

---

③有向图的连通性

弱连通图、单向连通图、强连通图

---

弱连通分支、单向连通分支、强连通分支

---

---

④示例

---

---

7.图的操作

①删除边

---

②删除结点

---

③收缩边

---

示例

---

8.图的表示

①关联矩阵表示

---

---

---

---

②邻接矩阵表示

---

③可达矩阵表示

---

9.赋权图和最短通路问题

①赋权图定义

---

②边权矩阵定义

---

③最短通路问题

---

• 示例

---

---

---

---

---

④最短通路问题的应用-设备更新问题

---

---

---

10.欧拉图及其应用

①哥尼斯堡七桥问题

---

②欧拉图定义

---

③欧拉图的判定

无向欧拉图的判定定理

---

有向欧拉图的判定定理

---

④欧拉图的应用

蚂蚁赛跑问题

---

道路清扫车问题

---

11.哈密顿图及其应用

引入

---

---

①哈密顿图定义

---

②哈密顿图的判定

---

---

---

---

③哈密顿图的判定定理

---

④哈密顿图的应用

---

---

---

欧拉图和哈密顿图的对比

---

第九章 树

1.无向树

①无向树定义

---

②树的性质定理

---

• 推导证明

---

---

---

④树的应用

---

---

2.生成树

问题引入

---

①生成树的定义

---

②生成树的性质

---

③生成树算法

---

3.最小生成树及其应用

问题引入

---

①最小生成树定义-边赋权树

---

②最小生成树算法-Kruskal避圈法

---

③最小生成树算法-破圈法

---

④最小生成树的应用

---

​

---

4.有向树和根树

引入

---

①有向树定义

---

---

②有向树的性质

---

③根树定义

---

---

儿子、兄弟、祖先、后代

---

④根子树定义

---

⑤根树的应用

---

---

5.根树的遍历

引入

---

①有序树定义

---

②根树的遍历

---

---

---

③根树遍历的应用

---

---

---

---

6.二叉树

引入

---

①二叉树的定义

---

---

②二叉树的性质

---

---

---

③前缀码

---

④二叉树的应用

---

7.最优树及其应用

引入

---

①叶赋权树

---

②最优二叉树

---

③最优树的构造-Huffman算法

---

---

最优二叉树不一定唯一

---

④最优树的应用

---

---

---

---

---

---

完	结	:cherry_blossom:	撒	花

---

---

---