离散数学整理

Discrete mathematics

数理逻辑

合取

在逻辑中，有时会用“但是”一词替代“并且”一词来表示合取∧

真值表

两个命题析取∨的真值表

p	q	p ∨ q
1	1	1
1	0	1
0	1	1
0	0	0

蕴含

条件语句p→q是命题“如果p，则q”

• p→q只是声明“如果p为真，那么q为真”
  • 如果p为假，无论q为何命题， p→q总为真
  • 如果q为真，无论p为何命题， p→q总为真

几种表述方式

“q当p”，”p仅当q“，”p蕴含q“，”q除非¬p“

双条件语句

p↔q

当p和q有同样真值时，双条件语句为真，否则为假

逻辑运算符

合取运算符∧优先于析取运算符∨

比特串

是0比特或多比特的序列

长度就是它所含比特的数目

永真式（重言式）、永假式（矛盾式）、可能式(可满足式)

逻辑等价

在所有可能情况下都具有相同真值的两个复合命题称为逻辑等价的

如果p↔q是永真式，则复合命题p和q称为是逻辑等价的，用记号p≡q或p⇔q表示

判定两个复合命题是否等价

1. 使用真值表

   p和q是完全等价的当且仅当对应它们真值的两列完全一致

2. 展开一系列逻辑等价式

德摩根律

¬(p∨q)≡¬p∧¬q
¬(p∧q)≡¬p∨¬q

一个重要的等价式

p→q≡¬p∨q

几个逻辑等价式

p∨(p∧q)≡p
p∧(p∨q)≡p

p∨(q∧r)≡(p∨q)∧(p∨r)
p∧(q∨r)≡(p∧q)∨(p∧r)

条件命题的逻辑等价式

p→q≡¬p∨q
p→q≡¬q→¬p
p∨q≡¬p→q
p∧q≡¬(p→¬q)
p→(q→r)≡(p∧q)→r

双条件命题的逻辑等价式

p↔q≡(p∧q)∨(¬p∧¬q)
p↔q≡(p→q)∧(q→p)
p↔q≡¬p↔¬q
¬(p↔q)≡p↔¬q

可满足性

一个复合命题称为是可满足的，如果存在一个对其变量的真值赋值使其为真（即当它是一个永真式或可满足式时）

确定一个复合命题是否可满足

1. 使用真值表

2. 对真值做一些推理

范式

质合取式

一个命题公式若具有p1*∧p2*∧…∧pn*的形式(n≥1)，其中pi*是pi或其否定¬pi

质析取式

一个命题公式若具有p1*∨p2*∨…∨pn*的形式(n≥1)，其中pi*是pi或其否定¬pi

质合取式的析取称为析取范式

即具有A1∨A2∨…∨An(n≥1)的形式的公式，其中Ai是质合取式

质析取式的合取称为合取范式

即具有A1∧A2∧…∧An (n≥1)的形式的公式，其中Ai是质析取式

最小项 最大项

主析取范式

由不同最小项所组成的析取式

主合取范式

由不同最大项所组成的合取式

小项编码

用1表示变元本身，0表示变元的否定形式

大项编码

用0表示变元本身，1表示变元的否定形式

将范式化为主范式

1. 拆项

   p≡p∧1≡p∧(q∨¬q)≡(p∧q)∨(p∧¬q)
   p≡p∨0≡p∨(q∧¬q)≡(p∨q)∧(p∨¬q)

2. 用真值表

   p↔q的真值表

   | p | q | p ↔ q |
   | ——- | ——- | ——————- |
   | 1 | 1 | 1 |
   | 1 | 0 | 0 |
   | 0 | 1 | 0 |
   | 0 | 0 | 1 |

   真值为“1”的对应最小项

   p↔q≡(p∧q)∨(¬p∧¬q)

   m11∨m00

   ¬(p↔q)≡(p∧¬q)∨(¬p∧q)

   p↔q≡¬(p∧¬q)∧¬(¬p∧q)≡(¬p∨q)∧(p∨¬q)

   M10∧M01

推理规则

推理规则	名称
p→q，p⇒q
p→q，¬q⇒¬p
p→q，q→r⇒p→r
p∨q，¬p⇒q
p⇒p∨q
p∧q⇒p
p，q⇒p∧q
p∨q，¬p∨r⇒q∨r	消解

附加前提

A1，A2，…，An⇒A→B等价于A1，A2，…，An，A⇒B

反证法

若要证A1, A2 , …, An ⇒ B

将¬B加入前提，通过证明¬A1，A2，…，An,，¬B⇒C，¬C完成证明

量词

量词P(x)的论域是D时

∀xP(x)，对于D中的每一个a，均有P(a)

∃xP(x)，D中存在一个a，使P(a)

∃!xP(x)，D中存在唯一一个a，使P(a)

量词的德摩根律

¬∀xP(x)≡∃x(¬P(x))

¬∃xP(x)≡∀x(¬P(x))

嵌套量词

∀x∀yP(x, y)≡∀y∀xP(x, y)

对于所有的x，y，P(x, y)均为真

∃x∃yP(x, y)≡∃y∃xP(x, y)

存在一对x，y，P(x, y)均为真

∀x∃yP(x, y)

对于每个x，均存在y使P(x, y)均为真，y可依赖于x

∃y∀xP(x, y)

存在y使得，对于每个x，P(x, y)均为真，y不依赖于x

∃y∀xP(x, y)⇒∀x∃yP(x, y)

约束变量 自由变量

特性谓词

∀xP(x) ⇝∀x(A(x)→P(x))

∃xP(x) ⇝∃x(A(x)∧P(x))

翻译自然语言

只有p，才q，q推出p

未必，不是一切，¬∀x

集合

两个集合相等

当且仅当它们拥有同样的元素

注意：同一个元素被列出来不止一次也没关系

子集

A⊆B当且仅当量化式∀x(x∈A→x∈B)

A是B的真子集当且仅当∀x(x∈A→x∈B)∧∃x(x∈B∧x∉A)

每个非空集合都至少有两个子集，空集和集合本身

证明A是B的子集

证明如果x属于A则x也属于B

证明A不是B的子集

找到一个x∈A使得x∉B

证明两个集合相等

证明A⊆B且B⊆A

幂集

2^A=P(A)={x|x⊆A}

一个集合有n个元素，它的幂集就有2^n个元素

笛卡尔积

A和B的笛卡尔积A*B表示，是所有序偶(a, b)的集合，其中a∈A，b∈B

A*B={(a, b)|a∈A∧b∈B}

集合运算

A∪B={x|x∈A∨x∈B}

A∩B={x|x∈A∧x∈B}

A-B={x|x∈A∧x∉B}=A∩(B的补集)

A的补集={x∈U|x∉A}

两个集合称为是不相交的，如果它们的交集为空集

几个集合恒等式

A∪(A∩B)=A

A∩(A∪B)=A

集合的基数

可数无限集，和正整数集合具有相同基数的集合

有理数集合是可数无限的

实数集是不可数的

两个集合间基数的关系

集合A和集合B有相同的基数，当且仅当存在从A到B的一个一一对应

当A和B有相同的基数时，就写成|A|=|B|

如果存在一个从A到B的一对一函数，则A的基数小于或等于B的基数

可数集合

把无限集分为两组，一组与自然数集合有相同的基数，另一组具有不同的基数

一个集合或者是有限集或者与自然数集具有相同的基数，这个集合就称为可数的

一个集合不是可数的，就称为不可数的

可数集合的任意子集合都是可数的

如果A和B是可数集合，则A∪B也是可数集合，两个可数集合的并依然是可数集合

证明一个集合是可数的

给出这个集合（针对无限集）与正整数集合之间的一个一一对应

一个无限集是可数的当且仅当可以把集合中的元素排列成序列（下标是正整数）

不可数集合

康托尔对角线法

任何含有不可数子集合的集合都是不可数的

基数研究中的一个关键定理

证明两个集合有相同的基数

如果A和B是集合且|A|小于等于|B|且|B|小于等于|A|，则|A|=|B|

换言之，如果存在一对一函数f从A到B和g从B到A，则存在A和B之间的一一对应函数

函数

一对一函数

当且仅当对于定义域中的所有a和b有f(a)=f(b)蕴含a=b

∀a∀b(f(a)=f(b)→a=b)

∀a∀b(a不等于b→f(a)不等于f(b))

映上函数

值域和陪域相等，陪域中的每个成员都是定义域中某个元素的像

当且仅当对每个b∈B有元素a∈A使得f(a)=b

∀y∃x(f(x)=y)

证明f是单射的

证明对于任意x，y属于A，如果f(x)=f(y)，则x=y

证明f不是单射的

找到特定的x，y属于A，使得x不等于y且f(x)=f(y)

证明f是满射的

考虑任意元素y属于B，并找到一个元素x属于A使得f(x)=y

证明f不是满射的

找到一个特定的y属于B，使得对于任意x属于A有f(x)不等于y

关系

设A和B是集合，一个从A到B的二元关系是A*B的子集

一个从A到B的二元关系是集合R，其中每个有序对的第一个元素取自A而第二个元素取自B

当(a, b)属于R时，称a与b有关系R

集合的关系

集合A上的关系是从A到A的关系，是A*A的子集

n元素集合有2^(n^2)个关系

关系的性质

这里的关系指一个集合上的关系

自反性

∀a((a, a)∈R)

n元素集合有2^(n*(n-1))个自反的关系

对称性

∀a∀b((a, b)∈R→(b, a)∈R)

反对称性

∀a∀b(((a, b)∈R∧(b, a)∈R)→(a=b))

一个关系可以同时具有对称性和反对称性或者两种性质都没有

传递性

∀a∀b∀c(((a, b)∈R∧(b, c)∈R)→(a, c)∈R)

注意：A={1, 2, 3, 4}，R={(1, 2), (3, 4)}，符合传递性

关系的组合

用S◦R表示R与S的合成

如何找到这些合成

在图中，检查所有通过两条有向边的路径，该路径能从最左边的元素，经过一个中间元素，到达最右边的元素

传递关系的幂是该关系的子集

集合A上的关系是传递的，当且仅当对n=1, 2, 3, ……有R^n⊆R

关系的表示

用矩阵表示关系

关系R可以用矩阵MR=[mij]来表示，其中当(ai, bj)∈R时mij=1，(ai, bj)∉R时mij=0

表示定义在一个集合上的关系的矩阵是一个方阵

如果主对角线上的所有元素都等于1，那么R是自反的

R是对称的当且仅当MR=(MR的转置)，即MR是对称矩阵

关系R是反对称的，当i不等于j时，mij=0或mji=0

用图表示关系

这里的关系指一个集合上的关系

把一个有穷集上的关系看作有向图

一个关系是自反的，当且仅当有向图的每个顶点都有环

一个关系是对称的，当且仅当在两个不同的顶点之间的每一条边都存在方向相反的边

一个关系是反对称的，当且仅当在两个不同的顶点之间不存在两条方向相反的边

一个关系是传递的，当且仅当只要存在一条从顶点x到顶点y的边和一条从顶点y到顶点z的边，就有一条从顶点x到顶点z的边

关系的闭包

当R不具有性质P时，我们将求在集合A上，包含关系R且具有性质P的最小关系S

关系R的自反闭包，R∪A上的对角关系

关系R的对称闭包，R∪R的逆

传递闭包

用有向图表示关系有助于构造关系的传递闭包

设R是集合A上的关系，从a到b存在一条长为n（n为正整数）的路径，当且仅当(a, b)∈R^n

求一个关系的传递闭包等价于在相关的有向图确定哪些顶点对之间存在路径

设R是集合A上的关系，连通性关系R*由形如(a, b)的有序对构成，使得在关系R中，从顶点a到b之间存在一条长度至少为1的路径

因为R^n由有序对(a, b)构成，使得存在一条从顶点a到b的长为n的路径，所以R*是所有R^n的并集

关系R的传递闭包等于连通性关系R*

R*包含R

设A是含有n个元素的集合，R是集合A上的关系，如果R中存在一条从a到b的长度至少为1的路径，那么这两点间存在一条长度不超过n（a不等于b时为n-1）的路径

求传递闭包

1. 传递闭包的0-1矩阵是R的前n次幂的0-1矩阵的并

   MR*=MR∨(MR^2)∨(MR^3)∨……∨(MR^n)

   这里指MR的n次方

2. 沃舍尔算法

   for k=1……n
     for i=1……n
       if wik=1
         第k行加至第i行

等价关系

定义在集合A上的关系叫做等价关系，如果它是自反的，对称的和传递的

模m同余

a≡b(mod m)，当且仅当m整除a-b

等价类

设R是定义在集合A上的等价关系，与A中的一个元素a有关系的所有元素的集合叫作a的等价类

换句话说，如果R是定义在集合A上的等价关系，则元素a的等价类是[a]R={s|(a, s)∈R}

模m同余类

A中两个元素所在的等价类或者是相等的或者是不相交的

a与b之间有等价关系⇔a的等价类和b的等价类相同⇔a的等价类和b的等价类相交不为空

等价类与划分

一个等价关系怎样划分一个集合

集合S的划分是S的不相交的非空子集构成的集合，且它们的并集就是S

集合上等价关系的等价类构成了这个集合的划分

怎样从一个划分构造一个等价关系

两个元素关于这个关系是等价的，当且仅当它们在S的划分的同一子集中

设R是定义在集合S上的等价关系，那么R的等价类构成S的划分

反过来，给定集合S的划分{Ai|i∈I}，则存在一个等价关系R，它以集合Ai作为它的等价类

当一个整数除以m时，可能得到m个不同的余数，因此存在m个不同的模m同余类

偏序

自反的，反对称的，传递的

集合S与定义在其上的偏序R一起称为偏序集，记作(S, R)

集合S中的成员称为偏序集的元素(S, R)中，记号a≤(弯)b表示(a, b)∈R

在一个偏序集

可比的 不可比的

哈塞图

有穷偏序集的有向图中，有许多边可以不必显示出来，因为它们是必须存在的

极大元 极小元

最大元 最小元

上界 最小上界

下界 最大下界

图

图G=(V, E)由顶点的非空集V和边集E构成

简单图

无向

每条边都连接两个不同的顶点且没有两条不同的边连接一对相同顶点

基本术语

邻接

图G中，顶点v的所有相邻顶点的集合，记作N(v)，称为顶点v的邻居

若A是V的子集，我们用N(A)表示图G中至少和A中一个顶点相邻的所有顶点的集合

在无向图中，顶点的度是与该顶点相关联的边的数目，表示成deg(v)，顶点上的环为顶点的度做出双倍贡献

度为0的顶点是孤立的，度为1的顶点是悬挂的

设G是有m条边的无向图，则2m=顶点度之和（握手定理）

顶点的度之和是边数的两倍

无向图中顶点的度之和是偶数，有偶数个度为奇的顶点

带有向边的图中，所有顶点的入度之和与所有顶点的出度之和相同，这两个和都等于图中的边数

带有向边的图忽略边的方向后得到的无向图称为基本无向图

一些特殊的简单图

完全图K

每对不同顶点之间都恰有一条边

圈图C

轮图W

n+1个顶点

2n条边

n立方体图Q

2^n个顶点

n*2^(n-1)条边

二分图

若把简单图G的顶点集分成两个不相交的非空集合V1和V2，使得图中的每一条边都连接V1中的一个顶点与V2中的一个顶点（因此G中没有边连接V1中的两个顶点或V2中的两个顶点），则G称为二分图，(V1, V2)称为G的顶点集的一个二部划分

对点是否一定有边相连没有限制

回路长度为偶数

完全二分图

两个顶点之间有边当且仅当一个顶点属于第一个子集而另一个顶点属于第二个子集

m+n个顶点

mn条边

判断一个图是否为二分图

当且仅当能够对图中的每个顶点赋予两种不同的颜色，并使得没有两个相邻的顶点被赋予相同的颜色

匹配

在简单图G中的一个匹配M就是图中边集E的子集，该子集中没有两条边关联相同的顶点

若一个顶点是匹配M中的一条边的端点，该顶点在M中被匹配

包含边数最多的一个匹配称为最大匹配

在二分图G中的一个匹配M，其划分为(V1, V2)，若V1中每个顶点都是匹配中的边的端点或|M|=|V1|，则称匹配M是从V1到V2的完全匹配

霍尔婚姻定理

带有二部划分(V1, V2)的二分图G中有一个从V1到V2的完全匹配当且仅当对于V1的所有子集A，有|N(A)|大于等于|A|

子图与导出的子图

G是一个简单图，图(W, F)是由顶点集V的子集W导出的子图，其中边集F包含E中的一条边当且仅当这条边的两个端点都在W中

边的收缩

从图中删除顶点

删除一个顶点v以及所有与它相关联的边

图的并集

包含这些图的所有顶点和边的新图被称为这些图的并图

若G是有n个顶点的简单图，则G和G的补图的并图是Kn

图的表示

邻接表

邻接矩阵

带n个顶点的图有n!个邻接矩阵

关联矩阵

图的同构

当两个图同构时，两个图的顶点之间具有保持相邻关系的一一对应

判定两个简单图是否同构

说明两个图不同构

顶点数、边数、顶点的度、长度为k的简单回路的存在性

说明从图G的顶点集到图H的顶点集的函数f是一个同构

G的邻接矩阵与H的邻接矩阵相同

为了求出可能的同构，沿着经过所有顶点并且使得两个图中的对应顶点的度都相同的通路前进

通路

无向图

长度为n的通路是n条边的序列

简单图时，用顶点序列表示这条通路

若一条通路在相同的顶点开始和结束且长度大于0，则回路

若通路或回路不重复地包含相同的边，则它是简单的（顶点可以重复）

长度为0的通路由单个顶点组成

有向图时，除有向外，概念区别不大

无向图的连通性

若无向图中每一对不同的顶点之间都有通路，则该图称为连通的

在连通无向图的每一对不同顶点之间都存在简单通路

图G的连通分支是G的一个极大连通子图

图是如何连通的

有时删除图中的一个顶点和它所关联的边，就产生比原图具有更多连通分支的子图

割点或关节点 点割集 点连通度 点割集中最小的顶点数

割边或桥 边割集 边连通度 边割集中最小的边数

有向图的连通性

强连通

弱联通

基本无向图是连通的

强连通分支，即极大强连通子图

计算顶点之间的通路数

邻接矩阵A

从vi到vj长度为r的不同通路的数目等于A^r的第(i, j)项

还可以用来判定图是否连通

图是连通的当且仅当A+A^1+……+A^(n-1)的对角线外元素都是正数

欧拉通路与欧拉回路

包含G的每一条边的简单回路（通路）

含有至少2个顶点的连通多重图具有欧拉回路当且仅当它的每个顶点的度都为偶数

连通多重图具有欧拉通路但无欧拉回路当且仅当它恰有2个度为奇数的顶点

哈密顿通路与哈密顿回路

经过G中每一个顶点恰好一次的简单回路（通路）

存在的充分条件

G是有n个顶点的简单图，其中n大于等于3

狄拉克定理

G中每个顶点的度都至少为n/2

欧尔定理

对于G中每一对不相邻的顶点v和u来说，都有v与u的度之和大于等于n

证明哈密顿回路不存在

带有度为1的顶点的图，因为哈密顿回路中每个顶点都关联回路中的两条边（恰好两条）

若图中有度为2的顶点，则关联这个顶点的两条边属于任意一条哈密顿回路

当构造哈密顿回路且该回路经过某一个顶点时，除了回路所用到的两条边以外，这个顶点所关联的其他所有边不用再考虑

最短通路

迪克斯特拉算法

连通简单无向加权图

平面图

在平面中画出一个图而边没有任何交叉（可以不带交叉地画出它）

证明一个图是平面图

通过显示一种平面表示

必要条件

G是带e条边和v个顶点的连通简单平面图

v大于等于3，则e小于等于3v-6

v大于等于3并且没有长度为3的回路，则e小于等于2v-4

证明一个图不是平面图

库拉图斯基定理

一个图是非平面图当且仅当它包含一个同胚于K3,3或K5的子图

欧拉公式

G是带e条边和v个顶点的连通简单平面图，r是G的平面图表示中的面数

r=e-v+2

图着色

图的着色数是着色这个图所需要的最少颜色数

平面图的着色数不超过4

证明一个图的着色数为n

首先证明：用n种颜色可以着色这个图，构造出这样的着色即可

其次证明：用少于n种颜色不能着色这个图

完全图的着色数为n

完全二分图的着色数为2

圈图Cn

n为偶数时，着色数为2

n为奇数且大于1时，着色数为3

树

树是没有简单回路的连通无向图

一个无向图是树当且仅当在它的每对顶点之间存在唯一简单通路

有根树

若有根树的每个内点都有不超过m个孩子，则m叉树

若该树的每个内点都恰好有m个孩子，则满m叉树

性质

带有n个顶点的树含有n-1条边

带有i个内点的满m叉树含有n=mi+1个顶点

l是树叶数，n=l+i，一个顶点要么是树叶要么是内点

若一颗高度为h的m叉树的所有树叶都在h层或h-1层，则这棵树是平衡的（h-1层是满的）

在高度为h的m叉树中至多有m^h个树叶，若平衡，则m^(h-1)小于树叶数小于等于m^h

前缀码

用二叉树表示

通向左子树的边标记为0，通向右子树的边标记为1

哈夫曼编码

中缀、前缀（波兰）和后缀（逆波兰）记法

由表达式构造有序根树

前缀表达式求值，从右向左

后缀表达式求值，从左向右

生成树

简单图

包含原来简单图的所有顶点、边数最小的连通子图

简单图是连通的当且仅当它有生成树

最小生成树

通过添加还没有使用过的，具有特定性质的，权最小的边来进行

普林算法

首先选择带最小权的边，放进生成树，依次向树里添加与已在树里顶点关联的且不与已在树里的边形成简单回路的权最小的边，已经添加了n-1条边时就停止

克鲁斯卡尔算法

依次添加不与已经选择的边形成简单回路的权最小的边，已经添加了n-1条边时就停止

未分类

对偶式

在仅含有联结词与（∧）、或（∨）、非（¬）的命题公式A中，将∨换成∧，∧换成∨

若A中还含有0或1，则还需将其中的0换成1，1换成0，所得到的新命题公式A*就是A的对偶式

例如，命题公式A=¬(P∧0)的对偶式A*=¬(P∨1)

主合取范式与主析取范式的转化

假设子命题为3个

若主析取范式为 m0∨m2∨m6，或表示为 m000∨m010∨m011

则对应主合取范式为 M1∧M3∧M4∧M5∧M7