离散数学概念总结

2023年12月6日发(作者：山东2016春考数学试卷)

离散数学概念总结

命题逻辑

命题

命题

能确定真值的陈述句

原子命题

不能再细分的命题

复合命题

由联结词、标点符号和原子命题复合构成的命题

重言式

给定一个命题公式，若无论对分量作怎样的指派，其对应的真值永为，则称命题公式为重言式

蕴含式

设为两个命题，复合命题“如果则”称为与的蕴含式，记作

矛盾式

无论对分量作怎样的指派，其对应的真值永为，记为

子公式

如果是合式公式的一部分，且本身也是一个合式公式，则称为公式的子公式

置换

设是合式公式的子公式，且，将中的用来置换，得到新的公式，则

命题公式

命题公式

1. 单个命题变元是一个命题公式

2. 如果和是命题公式，那么都是命题公式

3. 当且仅当能够有限次地应用(1),(2)生成的公式是命题公式

命题公式的等价

设命题公式

同。则称和

和，

是等价的

, , ..., 为所有出现于和中的原子变元，若给, , ..., 任一组真值指派，和的真值都相

命题公式的对偶式

命题公式中含联结词，，将与互换，T 与 F 互换所得公式称为的对偶式

联结词

：不可兼析取

：条件否定

：与非

：或非

范式

求范式的步骤

1. 将命题公式的联结词全部化为

2. 利用德·摩根律，将否定符号直接移到各命题变元之前

3. 利用分配律、结合律将命题公式化为范式

小项

个命题变元的合取式，称为布尔合取或小项，在任一小项中

1. 每个变元与它的否定不能同时出现

2. 但与必须出现且仅出现一次

大项

个命题变元的析取式，称为布尔析取或大项，在任一小项中

1. 每个变元与它的否定不能同时出现

2. 但与必须出现且仅出现一次

谓词逻辑

谓词公式

谓词公式

1. 原子谓词公式是谓词公式

2. 若是谓词公式则是一个谓词公式

3. 若和都是谓词公式，则，，和是谓词公式

4. 如果是谓词公式，是中出现的任何变元，则和都是谓词公式

5. 只有经过有限次应用规则(1), (2), (3), (4)所得到的公式是谓词公式

谓词公式的等价

任意给定两个谓词公式wff

和在

和wff，设它们有共同的个体域，若对和的任一组变元进行赋值，所得命题的真值相同，则称谓词公式

上是等价的，并记作：

前束范式

定义

1. 所有量词都位于该公式的最左边

2. 所有量词前都不含否定

3. 量词都辖域都延伸到整个公式都末端

运算方法

1. 消去 、

2. 否定右移

3. 量词左移（分配等值、辖域收缩扩张、变项改名）

分配等值：

对 不满足

对 不满足

辖域收缩扩张： ， 含 自由出现， 不含

推理理论

P规则

前提引入：前提在推导过程中的任何时候都可以引入

T规则

结论引用：在推导中，如果有一个或多个公式重言蕴含着公式（结论），则公式可以引入推导之中

CP规则

要证明，转化为证明

R：附加前提

全称指定规则（US）

全称推广原则（UG）

存在制定原则（ES）

存在推广原则（EG）

集合论

平凡子集

非空集合的子集和

全集

在一定范围内，若所有集合均为某一集合的子集，则称该集合为全集，记作

幂集

给定集合，以的全体子集为元素构成的集合，称为的幂集，记为（或）

商集

设为非空集合上的等价关系，其等价类集合称为关于的商集，记为

集合的划分

设为非空集合，，其中, ，

，则称为的划分

例：集合的一个划分确定的元素间的一个等价关系

证明：

设集合有一个划分

是一个等价关系。因为

，现定义一个关系，当且仅当在同一分块中。可以证

明这样规定的关系

1. 与在同一分块中，故必有。即是自反的

2. 若与在同一分块中，与也必在同一分块中，即,故是对称的

3. 若与在同一分块中，与在同一分块中，因为

即属于且仅属于一个分块，故与必在同一分块中，故有

即是传递的。

满足上述三个条件，故是等价关系，由的定义可知，就是

集合的覆盖

设为非空集合， 其中,

则称为的覆盖

交叉划分

若与是同一集合的两种划分，则其中所有组成

的集合，称为是原来两种划分的交叉划分

划分的加细

设

，则

与

称为是

是同一集合

的加细

的两种划分，若对于每个均有，使

集合的等势

集合的元素与集合的元素之间存在一一对应

集合的对称差

设和为任意两个集合，和的对称差是由或者属于，或者属于，但不能既属于又属于但元素所组成的集合

集合的基数

所有与集合等势的集合所组成的集合，叫做集合的基数，记为（或）

无限集

设为一个集合，若为空集或与集合等势，则称为有限集，否则为无限集

等价定义：是无限集当且仅当与其某一个真子集等势

可数集

与自然数集合等势的集合

连续统的势

：我们把集合的基数记为\"\"，因为~，故

可数集合的基数

：与自然数集合等势的任意集合称为可数的，可数集合的基数用表示

集合的置换

设是一个非空集合，从集合到的一个双射称为的一个置换

集合的运算

集合的对称差

又称环和

关系

关系

笛卡尔积的子集为关系

笛卡尔积

令

记作

和是任意两个集合，若序偶的第一个成员是的元素，第二个成员是的元素，所有这样的序偶集合，称为集合和的笛卡尔积，

集合上的二元关系

的一个子集为集合上的一个二元关系

对称关系

设是上的关系，对于每一个，每当时，就有，则称为上的对称关系

反对称关系

设为上的关系，对于每一个，每当，时，必有，则称为上的反对称关系

等价关系

一个二元关系若满足自反性，对称性和传递性则称为等价关系

等价类

设是非空集合上的等价关系，，令

称为关于的等价类

简称为的等价类，简记为

称为等价类的代表元素

相容关系

相容关系

若集合上的二元关系是：

1. 自反的

2. 对称的

则称是上的相容关系

相容关系又称相似关系

相容类

设是集合的相容关系，子集满足，则称为关于的相容类

最大相容类

设是集合的相容关系，子集满足：

1.

2. R

则称为关于的最大相容类

完全覆盖

在集合上给定相容关系，其最大相容类的集合，称作集合的完全覆盖，记作

偏序关系

偏序关系

若集合上的二元关系是

自反的

、

反对称的

和

传递的

，则称是上的偏序关系

序偶称为偏序集

又称半序

盖住

设为偏序集，

，则称盖住

，若，且不存在使得

哈斯图

设有偏序集，，适当排列结点的顺序使得：

1. 若，则将画在的下方

2. 若盖住，则用一条直线连接和

偏序集合的子集的特殊元素

  设为偏序集，，对，

极大元

若中不存在元素，使且，则为的极大元

极小元

若中不存在元素，使且，则为的极小元

最大元

若中任意元素，有，则称为的最大元

最小元

若中任意元素，有，则称为的最小元

最大元与极大元的比较

最大元与其他所有元素均可比；而极大元不一定与所有元素都可比，只要没有比它大的元素，它就是极大元

都不一定存在，但非空有限元中极大元一定存在

最大元存在即唯一，极大元可有多个

唯一的极大元最大元

上界

若成立，则称为的上界

下界

若成立，则称为的下界

上确界

设是的一个上界，若对所有上界均有，则称为的最小上界或上确界，记为或

下确界

设是的一个下界，若对的所有下界均有，则称为的最大下界或下确界，记为或

拟序关系

设是一个集合，如果上的一个集合，满足

反自反的

和

传递的

，则称是上的一个拟序关系

全序关系

在偏序集中，若是一个链，则称为全序集合或线序集合

自反、反对称、传递、每个元素之间都有关系

良序集合

在偏序集中，若的每一个非空子集总含有最小元，则称为良序集合

自反、反对称、传递、每个元素之间都有关系、子集存在最小元

称二元关系为上的良序

对称闭包

设是一个二元关系，如果存在一个关系

，则称为

满足：是

对称的

，，对于任何对称关系，如果有就有

的对称闭包

自反闭包

设是一个二元关系，如果存在一个关系

，则称为

满足：是

自反的

；；对于任何自反的关系如果有就有

的自反闭包

传递闭包

设是一个二元关系，如果存在一个关系

，则称为

满足：是

传递的

；；对于任何传递的关系如果有就有

的传递闭包

Warshall算法

procedure Warshell（ 的 0-1 矩阵）

for to

//按列遍历

    for to

        for to

       

//若第列是1则把第行上的元素逻辑加到第行上

return

主对角线可跳过

第行均为零可跳过

链

设是一个偏序集合，在的一个子集中，如果每两个元素都是有关系的，则这个子集为链

反链

设是一个偏序集合，在的一个子集中，如果每两个元素都是无关的，则这个子集为反链

函数

函数

设和是任何两个集合，是到的一个关系，如果对于每一个，有唯一的，使得，则称关系为函数

亦称为到的映射

满射

对于映射，如果则称这个映射为满射

入射

对于映射

射）

，如果都存在唯一的使得，则称是入射（或一对一映

双射

若既是满射又是入射，则称是双射

逆函数

设是一双射函数，称的双射函数为的逆函数，记作

常函数

函数，，使得，，即

恒等函数

如果，则称函数为恒等函数

基数的比较

概念

如果两个集合能够建立双射函数，则该两集合应具有相同的基数

连续统的势：我们把集合的基数记为\"\"，因为~，故

可数集合的基数：与自然数集合等势的任意集合称为可数的，可数集合的基数用表示

若从集合到集合存在一个入射，则称的基数不大于的基数，记作

若从集合到集合存在一个入射，但不存在双射，则称的基数小于的基数，记作

Cantor-Schroder-Bernstein 定理

设和是任意集合，若，则

例题

1. 证明和有相同的基数

证明：作入射函数：

2. 设，，，，求证：

证明：

定义一个从到正实数的函数，

>

因为是一个入射函数，且

所以

此外，作映射

因为是入射的，故

因此

代数系统

闭运算

对于集合，一个从到的映射，称为集合上的一个元运算，如果，则称该元运算是封闭的（集合上的运算

的结果都是在原来的集合中）

代数系统

一个非空集合连同若干个定义在该集合上的运算所组成的系统就称为一个代数系统，记作

二元运算

运算性质

封闭性

设是定义在集合上的一个二元运算，如果对于任意的，都有，则称二元运算在上是封闭的

表中每个元素都属于

可交换性

设是定义在集合上的一个二元运算，如果对于任意的，都有，则称该二元运算是可交换的

表关于主对角线是对称的

可结合性

设是定义在集合上的一个二元运算，如果对于任意的，都有，则称该二元运算是可结合的

可分配性

设是定义在集合上的两个二元运算，如果对于任意的，都有

则称运算对运算是可分配的

吸收律

设是定义在集合上的两个二元运算，如果对于任意的，都有

则称运算和运算满足吸收律

等幂性

设是定义在集合上的一个二元运算，如果对于任意的，都有，则称运算是等幂的

运算表的主对角线上的每个元素与它所在的行（列）表头元素相同

幺元

左幺元：，都有

右幺元：，都有

幺元：，，有

设是定义在集合上的一个二元运算，且在中有关于运算的左幺元和右幺元，则，且中的幺元是唯一的

表中元素所对应的行和列依次与运算表的行和列一致

零元

左零元：，都有

右幺元：，都有

幺元：，，有

设是定义在集合

，且

上的一个二元运算，且在中有关于运算的左零元和右零元，则

中的零元是唯一的

表中元素所对应的行和列中的元素都与该元素相同

逆元

左逆元：，，使得

右逆元：，，使得

逆元：，，既是的右逆元又是的左逆元

左右逆元不一定相等、不一定唯一、不一定同时存在

表中和互逆，当且仅当位于所在行，所在列的元素以及所在行，所在列的元素都是幺元

群

群的概念

群的定义

广群

一个代数系统，其中是非空集合，是上的一个二元运算，如果是封闭的，则称代数系统为广群

半群

一个代数系统，其中是非空集合，是上的一个二元运算，如果：

1. 运算是封闭的

2. 运算是可结合的，即对任意的满足

则称代数系统为半群

子半群

设是一个半群，且在上是封闭的，那么也是一个半群。通常称是半群的子半群

独异点

含有幺元的半群称为独异点

性质：

设是一个独异点，则在关于运算的运算表中任何两行和两列都是不相同的

设是独异点，对于任意，且均有逆元，则

有逆元，且

群

设是一个代数系统，其中是非空集合，是上的一个二元运算，如果

1. 运算是封闭的

2. 运算是可结合的

3. 存在幺元

4. 对于每一个元素，存在这它的逆元

则称是一个群

有限群

设是一个群。如果是有限集，那么称为有限群

有限群的阶数

有限集中元素的个数，记为

无限群

设是一个群。如果是无限集，那么称为无限群

等幂元

代数系统中，如果存在，有，则称为等幂元

子群

设是一个群，是的一个非空子集，如果也构成群，则称是的一个子群

阿贝尔群

如果群中的运算是可交换的，则该群为阿贝尔群，或称交换群

循环群

设为群，若存在，使得中的任意元素都由的幂组成，则称该群为循环群，元素 称为循环群的生成元

左陪集

设是群的一个子群，，则集合称为由所确定的在中的左陪集

拉格朗日定理

设是有限群的一个子群，，，则

群的性质

群中不可能有零元

零元不存在逆元

设是一个群，对于，必存在唯一的，使得

消去律：设是一个群，对于任意的，如果有或者，则必有

群的运算表中的每一行或每一列都是的元素的一个置换

设是一个群，是的非空子集，如果是一个有限集，那么，只要运算在上封闭，必定是的子群

设是群，

的子群

是的非空子集，如果对于中的任意元素 和 有，则是

群是阿贝尔群的充要条件：对任意的，有

设是一个由元素生成的有限循环群。如果，则，且

为元素的阶

群的积：设是一个群，, 记

群的逆：

拉格朗日定理

推论：

1. 任何质数阶的群不可能有非平凡子群

非平凡子群：,

2. 有限群中任何元素 的阶可整除，进而有

3. 质数阶的群一定是循环群

陪集

设是群的子群，

左陪集：称为由所确定的在中的左陪集，简称为关于的左陪集记为

右陪集：称为由所确定的在中的右陪集，简称为关于的右陪集记为

同态与同构

同态

同态

设和是两个代数系统，若

1. 是一函数

2. ，有

则称是到到一个同态映射，简称同态

同态于，记作

称为到一个同态象

先算后映 = 先映后算

例：,

自同态

设是一个代数系统，若是到的一个同态，则称为自同态

满同态

设是到的一个同态，若是到的满射，则称是到的满同态（或同态满射）

单一同态

设是到的一个同态，若是到的入射（即单射），则称是到的单一同态

同态核

设是群

简称同态核

到群的同态，是的幺元，称 为同态映射的核，

同态的性质

设是代数系统到的同态映射

若是半群，则也是半群

若是独异点，则也是独异点

若是群，则也是群

若是阿贝尔群，则也是阿贝尔群

设是群到群的同态，则是群的子群；若令，则

同构

同构

设是

与

到

同构

的一个同态，若是到的双射（即一一映射），则称是到的同构映射，并称

记作

自同构

设是一个代数系统，若是到的一个同构，则称为自同构

同构关系的性质

同构关系是等价关系

证明：

1. 自反性：

，作恒等映射，，

则是双射，并且有：

所以，

2. 对称性：

设代数系统，则存在双射，并且，有：所以， 也是双射，，，使得：，，即，，故有：

因此，

3. 传递性设

则存在双射 和 ，故 也为双射有：所以，因此，代数系统间的同构关系是等价关系

同余

同余关系

设是一个代数系统，是上的等价关系，若，有：

则称是上关于运算的同余关系

同余类

同余关系将非空集合划分称的等价类称为同余类

同余与同态关系

设是一个代数系统，

的同态象

是上的同余关系.是由诱导的一个划分，则必存在同态映射，使是

推论：设是群到群的同态映射，为的幺元，，定义上的二元关系：

，若，则

环与域

环

环

设是代数系统，若

1. 是阿贝尔群

封闭、可结合、幺元、逆元、交换律

2. 是半群

封闭、可结合

3. 乘法对加法可分配，即有

则称是一个环

称第一个运算为

加法

，并记为

称第二个运算为

乘法

，并记为

在环中

加法幺元记为

加法逆元记为

记为

环的性质

设是环，

1. 环的加法幺元必为乘法零元，即

2.

3.

4.

5.

零因子

零因子

设是环，若

是零因子环

，使，则称为零因子，

无零因子

，必有

无零因子的环称为无零因子环

性质

环无零因子，当且仅当满足消去律

即，若，，必有

整环

交换环

给定环，若可交换，则称为交换环

含幺环

给定环，若含幺元，则称为含幺环

整环

给定环，若可交换、含幺元、无零因子（或满足消去律），则称为整环

整环 = 环 + 乘法幺元 + 乘法可交换 + 无零因子（或乘法消去律）

设是代数系统，若

1. 是阿贝尔群

2. 是可交换独异点，且无零因子（或满足消去律）

3. 运算对可分配

则称是一个整环

域

域

设是代数系统，若

1. 是阿贝尔群

2. 是阿贝尔群

3. 运算对可分配

则称是域

域与整环

整环

是可交换独异点，且无零因子

域

是阿贝尔群

域 = 整环 + 除了零元外，每个元素都有逆元

域无零因子

域一定是整环

有限整环一定是域

两个运算代数系统间的同态

同态映射

设和是两个代数系统，若存在映射 满足：，有

1.

2.

则称是到的一个同态映射，并称是的同态象

同态映射的性质

任一环的同态象是一个环

格

格的定义

若偏序集

格

中任意两个元素都有

最小上界

和

最大下界

，则称是

通常记：,

由于最小上界、最大下界若存在则唯一，所以、是二元运算，分别称为并运算和交运算

称为由格所诱导的代数系统

子格

设

若运算和

是格，

在中封闭，则称

是由

是

所诱导的代数系统，设

的子格

且，

格的对偶

设是偏序集，用 表示偏序关系的逆关系，则

也是偏序集

和的哈斯图是互为颠倒的

称与为彼此对偶的偏序集

若是格，则也是格，反之亦成立，称这两个格互为对偶

，的对应于的

，的对应于的

格的对偶原理

设是对任意格都为真的命题，将中的, , 分别换成, , , 得命题，则对任意格也

是真的命题

格的基本性质

1. 自反性

2. 反对称性

3. 传递性

4. 确界描述一

5. 确界描述二

6. 盖住的等价

7. 交换律8. 结合律9. 幂等律吸收律10. 11. 若12. 保序性若，则13. 分配不等式，则

14. 模不等式

15. 推论：

16. 引理：若是一个代数系统，其中，都是二元运算且满足

吸收律

，则，必满足

幂等律

17. 定理一：设

，使

是一个代数系统，其中

是一个格

，都是二元运算且满足交换律，结合律和吸收律，则上存在偏序关系

格同态与格同构

格同态

设

，若存在映射，对

是格，它们所诱导的代数系统分别是

，有：

则称是从到的格同态

称是的格同态象

格同构

若是双射，则称是从到的格同构

也称格与同构

格同构的性质

设是格到的格同态，，若，必有

逆命题不成立

设两个格和

的格同构，当且仅当

，是到的双射，则是格到

分配格

分配格

设是由格所诱导的代数系统，若，满足

则称是分配格

分配格的性质

1. 若在一个格中交运算对并运算可分配，则并运算对交运算也一定可分配，反之亦然

2. 设是分配格，则，有

分配格的判定

1. 定义

其一成立

2. 格是分配格当且仅当中不含与

钻石格

或

五角格

同构的子格

3. 分配格的子格必是分配格

4. 每个链是分配格

模格

模格的定义

设是由格所诱导的代数系统，若，当时，满足

则称是模格

分配格与模格的关系

分配格必是模格

模格不一定是分配格

例：钻石格是模格但不是分配格

有界格

全下界

设是格，若存在，对任意有，则称为的全下界，记为0

若存在必唯一

全上界

设是格，若存在，对任意有，则称为的全上界，记为1

若存在必唯一

有界格

具有全下界和全上界的格称为有界格

有界格的性质

设为有界格，则有

在有界分配格中，若某元素有补元，则必唯一

补元

设是有界格，，若 ，使

则称是的补元

和互为补元

有补格

在一个有界格中，如果每个元素至少有一个补元，则称此格为有补格

布尔代数

布尔格

若一个格既是有补格，又是分配格，则此格称为有补分配格，又称布尔格

布尔格中任一元素的补元存在且唯一，记为

原子

设格具有全下界0，若有元素盖住0，则称元素为原子

布尔代数

布尔格可以诱导一个代数系统，则此代数系统为布尔代数

布尔代数的性质

设是布尔代数中任一两个元素，则

设是一个具有全下界0的有限格，若，则至少存在一个原子，使

布尔代数的同构

设

，有：

和是两个布尔代数，则存在双射满足：

1.

2.

3.

则称和同构

有限布尔代数

有限布尔代数

具有有限个元素的布尔代数

有限布尔代数的结论

1. 对任一正整数，必存在含有个元素的布尔代数

2. 任一有限布尔代数的元素的个数必为，为正整数

3. 元素个数相同的布尔代数是同构的

有限布尔代数的引理

1. 在布尔格中，当且仅当

2. 设是一个有限布尔代数，若

的所有原子，则

，且，又设是中满足

3. 设是一个有限布尔代数，若

的所有原子，则

，且，又设是中满足

是将表示为原子的的并的唯一形式

4. 设是布尔格，为任意一个原子，，则

和两式中，有且仅有一个成立

布尔表达式

布尔表达式

设是布尔代数

1. 中任何元素(即布尔常元)是布尔表达式

2. 任何布尔变元是布尔表达式

3. 若是布尔表达式，则都是布尔表达式

4. 尤其仅有通过有限次地运用规则(2),(3)所构造的符号串是布尔表达式

布尔常元

中的元素

布尔变元

以为取值范围的变元

n元布尔表达式

一个含格相异变元的布尔表达式，称为元布尔表达式，记作

其中为布尔变元

布尔表达式的值

设是布尔代数，元布尔表达式的值是指：

将中的布尔常元作为变元的值来代替表达式中相应的变元(即对变元赋值)，从而计算得出表达式的值

布尔表达式的等价

设

对格变元的任意赋值

和是布尔代数

均有

上的两个元布尔表达式，若

则称布尔表达式是等价的，记作：

布尔表达式的小项

布尔函数

布尔函数

设

达式来表示，则该函数为布尔函数

是布尔代数，一个由到的函数若能用上的一个元布尔表

布尔函数的小项

一个含有个变元的布尔表达式，如果它有形式

其中是或中的任一个，则我们称这个布尔表达式为小项

布尔函数的大项

一个含有个变元的布尔表达式，如果它有形式

其中是或中的任一个，则我们称这个布尔表达式为大项

布尔函数的析取范式

析取范式

形如的表达式称为析取范式

其中表示小项

一般布尔代数上的析取范式

设是布尔代数上任一布尔表达式，若

布尔函数的合取范式

形如的表达式称为合取范式

其中表示大项

图论

相关概念及约定

图

一个图是一个三元组，其中

是一个非空的结点集合

是边集合

是从边集合到结点无序偶（有序偶）集合上的函数

无向图

每条边都是无向边的图

有向图

每条边都是有向边的图

混合图

既有无向边又有有向边的图

多重图

包含平行边的图

零图

仅由孤立点组成的图

平凡图

由一个孤立结点构成的图

简单图

不含平行边和环的图

完全图

简单图中，若每对结点之间均有边相连，则称该图为完全图

有个结点的无向完全图记作

边数为

补图

由图的

所有结点

和所有能使图称为完全图的

添加边

所组成的图，称为图相对于完全图的补图，或简称为的补图，记作