《离散结构》要点（2022 年）

1．命题逻辑推理及应用

2．谓词逻辑推理及应用

3．主析取/主合取范式；相关应用

4．鸽巢原理及包含容斥原理的应用

5．关系定义、性质及运算（特别关系闭包）

• 关系及其表示
  ** 定义：

集合A到B的二元关系R为A × B的子集，用于刻画A中的元素和B中的元素的对应关系。
关系实质上是序偶 (x,y)的集合，其中序偶的第一个元素来自集合A,第二个元素来自集合B。
————————————————
版权声明：本文为CSDN博主「养猪去」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_44846324/article/details/105565212

** 关系表示法：
*** 列举法
*** 关系矩阵
*** 关系图

• 关系的五种基本性质
  ** 定义：

** 表示法中的特点：

• 关系的运算
  ** 复合关系
  **

** 逆关系
*** 定义：设R是集合A到B的二元关系，则定义一个B到A的二元关系R^-1 ={<b,a>|<a,b>a∈R}，称为R的逆关系，记作R^-1。
PS：
-- R^-1 就是将所有R中的有序对中的两个元素交换次序成为R^-1，故|R| = |R^-1|；
-- R^-1 的关系矩阵是R的关系矩阵的转置
--（*）R^-1的关系图是将R的关系图中的弧改变方向所得

** 关系幂
*** 定义：设R为A上的关系，n为自然数，则R的n次幂定义为
（1）R^0 = {<x,x>|x∈A} = Ia
（2）R^n+1 = R^n ● R
*** 不同表示法给出关系幂运算：
**** 集合表达式给出，通过n-1次右复合计算得到
**** 关系矩阵给出，即n个矩阵M之积，其中相加为逻辑加（1+1 = 1；1+0 = 0+1 = 1；0+0 = 0）
**** 关系图给出，！下图底部红色字体

image.png

** 关系的闭包
*** 定义：设R是集合A上的二元关系，R的自反（对称、传递）闭包是满足以下条件的关系R'：

（i）R'是自反的（对称的、传递的）；

（ii）R'⊇R；

（iii）对于A上的任何自反（对称、传递）关系R"，若R"⊇R，则有R"⊇R'。--Baidu

（说人话就是：）添加尽可能少的有序对使集合R满足自反（对称或传递）关系，得到的新关系R‘就称为R的自反（对称或传递）闭包

*** 闭包的求法（定理）：
定理：
（1）r(R) = R ∪ Ia
（2）s(R) = R ∪ R^-1
（3）t(R) = R ∪ R^2 ∪ R^3 ∪ ... ∪ R^n

image.png

*** 闭包的性质

image.png

• 集合的划分与覆盖
  ** 定义：

image.png

image.png

image.png

6．等价关系判别与证明

• 定义：
  ** 设R为非空集合A 上的关系。如果R是
  （1）自反的（2）对称的（3）传递的；则称R是A上的等价关系。
  ** 设R是一个等价关系，若<x,y>∈R，则称x等价于y，记作x~y。
  ** 设R为非空集合A上的等价关系，令任意x属于A，[x]R = {y|y∈A∧xRy}，则称[x]R为x关于R的等价类，简称为x的等价类，简记为[x] 或R（x）。
  ** 实例：模n同余
  ** 商集与划分
  *** 定义：

7．偏序关系判别与证明，哈斯图，偏序关系中的最小元、最大元、极小元、极大元、上界、下界、最小上界、最大下界等

• 定义：
  ** 设R为非空集合A上的关系。
  （1）自反的
  （2）反对称
  （3）传递的
  则称R是A上的偏序关系，记作≤。设≤为偏序关系，如果<x,y>∈≤，则记作x≤y，读作“小于或等于”
  （此处小于等于不是指数值大小，而是偏序关系中的顺序性）
  ** 设R为非空集合A上的偏序关系，如果a≤b或b≤a，则称a和b是可比的。如果既没有a≤b也没有b≤a，则称a和b是不可比的。

• 偏序集与哈斯图
  ** 定义：集合A和A上的偏序关系≤一起叫做偏序集，记作<A,≤>。
  ** 哈斯图：表示偏序关系和偏序集的（简化）关系图
  *** 偏序关系反对称且传递，关系图中任何两个不同节点之间不可能有相互到达的边或通路，因此与欸的那个边的向上方向为箭头方向，省略全部箭头。
  *** 将由传递性可推得的边省略
  *** 偏序关系是自反的，则用“圆圈”代替自环。
  ** 哈斯图作法：
  （1）以“圆圈”表示元素
  （2）若x＜y，则y画在x上层
  （3）若y覆盖x则连线
  （4）不可比的元素画在同一层

• 极大极小元
  ** 定义：设（A，≤）是偏序集，集合B是A的子集
  （1）存在元素b∈B，使得任意a∈B，若有b≤a，则a = b，则称b为B的极大元
  （2）存在元素b∈B，使得任意a∈B，若有a≤b，则a = b，则称b为B的极小元

• 最大最小元
  ** 定义：设（A，≤）是偏序集，集合B是A的子集
  （1）存在元素b∈B，使得任意a∈B，均有a≤b，则称b为B的最大元
  （2）存在元素b∈B，使得任意a∈B，均有b≤a，则称b为B的最小元

• 上下界
  ** 定义：设（A，≤）是偏序集，B是A的子集
  （1）a∈A，对B中任一元素x都有 x≤a，则称a为B的上界
  （2）a∈A，对B中任一元素x都有 a≤x，则称a为B的下界
  （3）在所有上界中最小的称为B的最小上界
  （4）在所有下界中最大的称为B的最大下界
  最小上界和最大上界可能不存在（类比高数中函数最值不一定存在）
  （5）综上可知，B的最小元（最大元）一定是B的下（上）界、最大下界（最小上界）。反之不一定成立，因为B的下（上）界不一定是B 中的元素

*应用案例
** 拓扑排序

8．代数系统/子代数系统/同态同构

• 二元运算及其性质
  ** 定义：设S为集合，函数f：S×S->S称为S上的二元运算，简称为二元运算。
  （1）任何两个元素都能进行这种运算
  （2）运算结果是唯一的
  （3）运算是封闭的
  ** 运算律：
  （1）交换律...... 满足x●y = y●x
  （2）幂等律...... 满足x●x = x ——（注：对于一切x∈S，x*x=x，则称x此种元素为等幂元素/等幂元）
  （3）分配律...... 略
  （4）吸收律......满足x●（x^y）= x和x^ （x●y）=x，则称●和^运算满足吸收律
  ** 特异元素：
  （1）（左或右）单位元（幺元）
  （2）（左或右）零元
  （3）（左或右）逆元，x的逆元存在，就称x是可逆的
  ** 定理：
  （1）单位元是唯一的
  （2）零元是唯一的
• 代数系统
  **

image.png

** 同类型代数系统
*** 如果两个代数系统中运算个数相同，对应运算的元数相同，且代数常数的个数也相同，则称这两个代数系统具有相同的构成成分，也称它们是同类型的代数系统。
** 子代数系统

** 同态同构

9．典型代数系统，群/子群的性质、判定与证明，几个典型群

• 半群
  ** 定义：

** 性质（略）

• 子系统与直积
• 群
  **

即
（1）运算满足封闭性
（2）运算满足结合律
（3）存在单位元
（4）每个元素都存在逆元

（4）有限群的阶：G的基数，记作|G|
（5）元素a的阶：使a^k = e成立的最小正整数k，记作|a| = k，也称a为k阶元。不存在这样的k则称a为无限阶元

** 群的性质
（1）幂运算满足:

• （a ^ -1）^-1 = a
• (ab)^-1 = a^(-1)b(-1)
• a^(n)a(m) = a^(m+n)， m,n∈Z
• (aⁿ⁾m = a^(nm)， m,n∈Z
• 若G为交换群，(ab)^n = a^(n)b(n)
  （2）方程 ax = b和 ya = b在G中有且仅有唯一解
  （3）G中适合消去律
• 若ab = ac，则b = c
• 若ba = ca，则b = c
  （4）|a| = r，k∈Z
• 当且仅当r|k（r能被k整除），a^k = e
• |a| = |a^-1|

• 子群
  ** 子群的定义

** 生成子群
定理：设G为群，a∈G，令H= {a^k|k∈Z}，即是a的所有幂构成的集合，则H是G的子群，称为由a生成的子群，记作<a>。

** 子群的判定
（1）H非空
（2）如果a∈H，b∈H，则a*b∈H ——封闭性
（3）若a∈H，则a^-1∈H ——均有逆元
*** 判定定理：
（一）

（二）

（三）

• 特殊的群
  ** 循环群
  *** 定义：设G为群，若存在a∈G，令G= {a^k|k∈Z}，则称G是循环群，记作G=<a>，a记作G的生成元。根据生成元a的阶可以分为n阶循环群和无限循环群。
  PS：（1）生成元不唯一（2） 生成子群一定是循环群
  *** 定理（给出求循环群生成元的方法）：
  （1）若G是无限循环群，则G只有两个生成元，即a和a^-1
  （2）若G是n阶循环群，则G含有Φ（n）个生成元。对于任何小于等于n且与n互质的正整数r，a^r是G的生成元
  Φ（n）是欧拉函数。对于任何正整数n，Φ（n）是小于等于n且与n互质的正整数个数。

其他典型的代数系统

• 环
• 域
• 格
  **（格作为偏序集） 定义：设<S,≤>是偏序集，如果∀x,y∈S,{x,y}都有最小上界和最大下界，则称这个偏序集是格。
  ** （格作为代数系统）定义：设<S,*,〇>是具有两个二元运算的代数系统，若*和〇运算适合
  （1）交换律
  （2）结合律
  （3）幂定律（可由吸收律推出，因此可省略）
  （4）吸收律
  ** 子格
  ** 格同态
  ** 分配格：满足分配律的格称为分配格。

*** 两种典型的非分配格：钻石格和五角格
同构于钻石格、五角格的格（或其子格同构于）不是分配格——通常据此判断是否为分配格

L3为钻石格，L4为五角格

** 有补格：

** 有界格：
*** 定义：设L是格，若L存在全下界和全上界，则称L为有界格，
记为<L,运算符1,运算符2, 0，1>
*** 全下（上）界a：若存在a属于L，使得∀x属于L有a≤x（x≤a）若存在则唯一确定，一般将格L的全下界记为0，全上界记为1

• 布尔代数
  ** （有补分配格）定义：若一个格式有补分配格，则称它为布尔代数（或布尔格）
  在分配格中如果一个元素存在补元，则是唯一的，因此在布尔代数中，每个元素都存在唯一的补元

** （作为代数系统）定义：设<B，*，〇>是代数系统，那两个为二元运算，且满足
（1）交换律
（2）分配律
（3）同一律（即存在0，1∈B）
（4）补元律（即每个元素都存在补元）

10.握手定理及其应用

• 图的相关概念

易知简单图的最大度为n-1

无向图没有出入度之分

• 图的基本定理——握手定理
  ** 定理

** 例题

11.图的建模与应用

• 相关概念
  ** 悬挂顶点：度数为1的顶点；悬挂边：与悬挂顶点关联的边
  ** 度数列：

** 可图化：

• 图的同构（难点非重点）
  ** 同构的必要条件:
  （1）节点数相同
  （2）边数相同
  （3）度数相同的节点数相同
  图之间的同构关系是等价关系

• 完全图
  ** 定义：设G为n阶无向简单图，若G中每个顶点均与其余的n-1个顶点相邻，则称G为n阶无向完全图，记作Kn（n≥1）。若为有向简单图，则当G中每两个顶点都有一条有向边关联，则称G是n阶有向完全图。
  ** 易知，n阶无向完全图的边数为n(n-1)/2；有向完全图则为n(n-1)

• 正则图

百度百科简介：正则图是指各顶点的度均相同的无向简单图

• 子图

百度百科简介：指节点集和边集分别是某一图的节点集的子集和边集的子集的图。若这个节点子集或边子集是真子集，则称这个子图为真子图。设S是V(G)的子集，以S为节点集，以G的所有那些两端点都在S内的边组成边集，所得到的G的子图称为S在G中的导出子图

• 补图

百度百科简介：图G的补图，通俗的来讲就是完全图Kn去除G的边集后得到的图Kn-G。

• 通路
  ** 图的连通性
  *** 无向图的连通性
  *** 有向图的连通性
  **** 强连通
  **** 弱连通（基图，即有向边换成无向边得到的无向图为连通图）
  ** 割边（桥）和割点
  ** 边割集（割边集）和点割集（割点集）
  ** 点连通度（描述图连通的程度）
• 回路

12.图的矩阵表示及应用

• 关联矩阵（顶点与边的关联次数）
  ** 一般为0次或1次，自环关联次数为2
• 有向图的邻接矩阵（有向图中顶点与顶点邻接的边的条数）
• 可达矩阵
  ** 1表示可达；0表示不可达
  ** 自己到自己规定为可达，所以可达矩阵主对角线上的元素全为1

13.欧拉图、哈密顿图应用

欧拉图

引例：七桥问题

• 定义1：通过（有向或无向）图中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路。
• 定义2：通过（有向或无向）图中所有边一次且仅一次行遍图中所有顶点的回路称为欧拉回路。
  ** 欧拉图：具有回路（必具有通路）
  ** 半欧拉图：具有通路，但不具有回路
• 定理：
  （1）当且仅当G是连通图，且G中没有奇度顶点时，无向图G才是欧拉图。
  （2）当且仅当G是连通图，且G中恰有两个奇度顶点时，无向图G才是半欧拉图。
  （3）当且仅当D是强连通的，且每个顶点的入度等于出度，有向图D才是欧拉图。
  （4）当且仅当D是单向连通，且D中恰有两个奇度顶点，其中一个的入度比出度大1，另一个的出度比入度大1，其余点入度等于出度时，有向图D才是半欧拉图。

哈密顿图

• 定义1：通过（有向或无向）图中所有顶点一次且仅一次的通路称为哈密顿通路。
• 定义2：通过（有向或无向）图中所有顶点一次且仅一次的回路称为哈密顿回路。
  ** 哈密顿图：具有回路（必具有通路）
  ** 半哈密顿图：具有通路，但不具有回路
  ** 平凡图是哈密顿图

如果图G是一个(1，0)图，则称为平凡图，或者说是由一个孤立点(即只有一个节点)组成的图叫平凡图。否则称为非平凡图

• 哈密顿图的判定：
  ** 定理：（暂略）
  *** 做题技巧：
  “交错标记法”：从某一结点用A、B交替标记其相邻结点。
  --- 标记过程中出现矛盾（即一个节点既是A又是B）则不是（半）哈密顿图；
  --- 若顺利标记完所有结点，则比较A、B标记个数；
  ---- 若A、B标记个数相等即为哈密顿图
  ---- 若标记个数恰好相差1，即为半哈密顿图
  ---- 其他情况则不是（半）哈密顿图

14.树的定义和应用、相关证明

• 定义：树是没有简单回路的连通无向图，常用T表示
  ** 相关概念
  *** （可忽略）森林：无向图至少有两个连通分支，每个连通分支都是树
  *** 根树：设T是n（n≥2）阶有向图（无向图没有出入度之分），若T中有一个顶点的入度为0，其余顶点入度均为1，则称T为根树。
  **** 入度为0的顶点称为树根
  **** 入度为1出度为0的顶点称为树叶
  **** 入度为1出度不为0的顶点称为内点（即度数≥2）
  **** 内点和树根统称为分支点
  **** 从树根到T的任意顶点v的通路（路径）长度称为v的层数
  **** 层数最大顶点的层数称为树高
  *** 设T为根树，若为T中层数相同的顶点都标定次序，则称为有序树
  *** 若根树的每个内点，都有不超过m个儿子，则称它为m叉树。若该树的每个分支顶点都恰好有m个儿子，则称它为正则m叉树

• 性质：
  一个无向图T = <V,E>是n阶m条边的无向图，则有等价命题：
  （1）T是树
  （2）每对顶点间有唯一的一条通路
  （3）T是连通的，且m=n-1
  （4）T无回路，且m=n-1
  （5）T无回路，但增加任一新边，得到且仅得到一个含新边的回路
  （6）T是连通的，但删去任一条边，图便不连通（n≥2）
  其中T是树——m=n-1可推出其余几条（连通无回路）

** 定理：任一树T中（非平凡无向树）中，至少有两片树叶（n≥2）

• 应用：

15.最小生成树及应用

• prim算法
  ** 执行方法：选择权最小的初始边，并且相继添加与树中顶点关联的不形成回路的权最小的边。得到最小生成树。（即第二次开始根据顶点选择权最小的边）
• kruskal算法
  ** 执行方法：选择图中权最小的一条边。相继添加不与已经选择的边形成简单回路的权的最小边。在挑选了n-1条边后就停止。（即每次都选择全局权最小的边）

16.哈夫曼树（最优二叉树）及哈夫曼编码

• 相关概念：
  （1）前缀码
  （2）由0，1符号串构成的前缀码称作二元前缀码

• 定理：
  任意一棵二叉树的树叶可对应一个二元前缀码，任意一个二元前缀码可对应一棵二叉树。