离散数学基础
试试你东 b 的离散书,very good
1️⃣ 集合论:从集合到二元关系到函数
2️⃣ 代数系统:从二元关系到代数系统到群
3️⃣ 数理逻辑
4️⃣ 图论
# 数理逻辑
# 命题逻辑
# 命题公式
命题:能够确定真值的陈述句
连结词:非、合取、析取、蕴含、异或、等价
- 老哥,合取是 ∩,析取是 ∪,整本书学完了才发现理解反了
- 异或只在两个原子命题真值相异时真值为真,与等价存在非的关系
- 其中,非、合取、析取为基本连结词
命题公式:永真式、矛盾式、可满足式
# 命题范式
蕴含等值式
等值公式:德摩根式(合取和析取的转化)
化范式的常见步骤
- 通过德摩根律将所有连结词化为:合取、析取、非
- 通过分配律和结合律,将析取/合取小项结合
范式
- 合取范式:小项为析取式 ∪,通过合取 ∩ 连接
- 析取范式:小项为合取式 ∩,通过析取 ∪ 连接
通过真值表法构造合取/析取范式
- 合取范式:假中取假,析取相耦,合取相连
- 析取范式:真中取真,合取相耦,析取相连
比如有命题公式A->¬B,有真值表
| A | B | A->¬B |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
合取范式:小项为析取式,全为假时项为假
- 取第四行,令每个原子命题均为 F,得合取范式
¬A∪¬B
析取范式:小项为合取式,全为真时项为真
- 取 1、2、3 行,令原子命题均为真,则有三个小项
¬A∩¬B、¬A∩B、A∩¬B - 通过析取 ∪ 相连,得到析取范式
(¬A∩¬B)∪(¬A∩B)∪(A∩¬B)
对于一般的情况,合取范式和析取范式可以通过分配律、结合律相互转化
# 推理规则
常用的推理规则
- 前提引入规则 P
- 结论引入规则 T
- 置换规则
真值表法
直接、间接证明法(推理的前提是条件永真)
- P 为条件
- T(1)(2) 表示当前命题公式(永真)由条件 1、2 推理得到
附加前提证明法(CP 规则)
等价于推理
此时有附加条件 C 为永真,只用推理出 D 永真,即可证明C->D永真
# 谓词逻辑
# 谓词和量词
谓词:由个体和谓词组成,如戴狗是个傻逼,个体就是戴狗,是个傻逼就是谓词,蕴含了逻辑
即对于所有 x,若 x 是戴狗 - F(x),则 x 是傻逼 - G(x)
量词:全称量词(所有),存在量词(存在)
谓词公式:由谓词和量词构成的复合谓词
论域(个体域,个体所涉及的范围)和辖域(量词所作用的范围)
# 前束范式
谓词公式的前束范式:量词提到最前面,每个量词的辖域都是整个谓词公式
求前束范式的一般过程
- 化蕴含:利用蕴含等值式(注意加括号)
- 去括号前的非:德摩根律(展开式同样要加括号)
- 去量词前的非:通过等价谓词转换
- 换变量:如同时存在 ∀xF(x) ∪ ∃xG(x),不妨将第二个个体换为 y,即 ∀xF(x) ∪ ∃yG(y),此时可以直接往前提量词
- 提量词:如上例,提为 ∀x∃y (F(x) ∪ G(y))
谓词的等价转换
不存在 F(x) = 全部都是 ¬F(x)
不全部都是 F(x) = 存在 ¬F(x)
还有一种情况,当给定了 x 的具体范围时,如 x ∈ {a, b},有这样的列举等价
前束析取范式和前序合取范式同样可以通过分配律、结合律相互转化
# 谓词推理
US:全称指定规则
ES:存在指定规则
通过消去量词,将谓词逻辑转化为命题逻辑
UG:全称推广规则(证明中用的很少)
EG:存在推广规则
其实和命题推理的相仿,主要思路就是将谓词指定为命题逻辑,命题间证明后再推广回谓词逻辑,得以证明
# 集合论
# 集合
# 集合、子集、幂集
基本概念
- 集合
- 元素
- 有限集
- 无限集
集合的表示法
- 穷举法(列举法)
- 描述法
空集:自身不包含任何元素的集合,空集 ∅ 是唯一的,为任何集合的子集
元素、集合的关系(包含的关系,箭头指向谁,谁被包含)
- 属于:记作 a ∈ A,即元素 a 属于集合 A(集合 A 中包含元素 a)
- 相等:两个集合相等当且仅当他们有相同的元素
- 子集:记为 ⊃,A ⊃ B 表示 A 包含 B(B 是 A 的子集),具有自反性、传递性
当两个集合互为对方的子集时,两集合相等,空集为任何集合的子集
注意属于和包含的符号,箭头朝哪边,哪个集合作宾语,即被包含的一方
子集与幂集
- 幂集:A 的幂集记为 P(A),P(A) 为“子集的集合”,其元素为集合 A 的所有子集,换句话说,P(A) 是 A 的所有子集组成的集合
一个集合 A,其包含 k 个元素的子集的个数有
故 A 的幂集 P(A) 元素个数为
即为 A 的子集的个数,其中 1 为空集
# 集合运算
集合的基本运算及性质:交与并,差与补
差的常用定理(结合概率论理解)
注意补是参照于全集的概念,如全集为 E,则 A 的补为
德摩根律:并的非 = 非的交
交的非 = 非的并
这和数理逻辑中合取析取的德摩根律是一样的
对称差,用异或符号表示
其中差运算可替换为
显然
且满足结合律
有点像概率里的加法(只是形式上,意义好像根本不搭嘎)
包含排斥原理,讨论有限集中元素的计数问题
比如
其中 |A| 表示集合 A 中元素的数量
参考概率论的包含排斥关系,包含排斥原理为
可以推广到多个集合
# 无限集
集合的基数:即集合中元素的个数
等势的集合:若两个集合之间可以通过一个双射函数进行映射,则这两个集合等势
- 显然,集合的基数相同是集合等势的必要条件
阿列夫零:用于形容无限集的基数
自然数集(非零整数)、有理数集(分数)的基数便是阿列夫零
- 且自然数集与有理数集等势
# 二元关系
# 关系的性质
序偶和笛卡尔乘积
- 序偶即有序的两个元素对
- 笛卡尔乘积
关系:序偶的集合
元素集合、序偶、二元关系的数量联系
- n 个元素的集合能构成 n^2 个不同的序偶(矩阵)
- m 个不同的序偶能构成 2^m 个不同的二元关系(不同的序偶集合)
关系及其表示:关系是逻辑,作用于集合之上才有意义
关系的性质:自反、传递、对称、反对称
- 均可以用关系矩阵来判断其性质
等价关系:自反、传递、对称
偏序关系:自反、传递、反对称
# 关系的运算
复合关系和逆关系
- 复合关系:即合成关系,通过中间命题传递,在关系矩阵中表现为矩阵乘法
- 逆关系:逻辑不变,序偶顺序改变,在关系矩阵中表现为矩阵转置
关系的闭包运算:自反闭包(r)、传递闭包(t)、对称闭包(s)
矩阵乘法计算关系的传递闭包
其中 n 指关系 R 的关系矩阵的阶数,这个式子就是把 n 个关系矩阵的幂运算结果并起来
写是要这么写,但很多时候可以通过结点间连通性来判断是否传递/可达
计算集合上的二元关系种类数量:假设 A 是三元集合
- 有 8(2^3) 个既对称又反对称的二元关系,有 3 种不同的序偶对
<a,a>,<b,b>,<c,c>可构成这样的关系 - 有 64(2^6) 个自反的二元关系,确定
{<a,a>,<b,b>,<c,c>}后剩下还有 6 个不同的序偶对 - 有 64(2^3*2^3)个对称的二元关系,自反的三个序偶和对称的三对序偶相组合
- 有 8(2^3) 个等价关系,确定
{<a,a>,<b,b>,<c,c>}后剩下三对对称的序偶对
# 偏序集与格
等价关系和等价类:满足自反性、传递性、对称性的关系
- 等价类的写法:和同余类一样,如模 3 同余类表示为
[0] = {0,3,6,...}
偏序关系:具有自反性、传递性、反对称性的二元关系集合(如整数集合上的小于等于关系)
偏序集的大小比较
- 注意能比较的前提是两元素具有偏序关系,所以孤立点不比任何元素大,也不比任何元素小,进而有孤立点的偏序集必定没有最大元和最小元
全序关系:在偏序关系中,每个元素之间均可以通过该偏序关系相比较,则该偏序关系为全序关系
哈斯图:通过关系图和 CovA 来构造
偏序集及其子集
- 极大元、极小元
- 最大元、最小元
- 上确界、下确界
格:在偏序集中,任意两个元素构成的子集均有其上下确界,这样的偏序集叫做格
分配格:?偏序关系满足交换律(这里总是不免想到群中的二元运算)
由格可以推导出一个代数系统,其二元运算为 ∩ 或 ∪,定义为
其中 a、b 的大小关系通过偏序关系确定,glb 表示上确界,lub 表示下确界
- 由于在格中,二者一定有上下确界,并且确界一定在集合 A 中,显然这是一个代数系统(满足封闭性)
# 函数
# 单射、满射和双射
函数是一种特殊的二元关系,他要求二元关系的前件集合 A 中的每个元素 x 在后件集合 B 中都有唯一一个元素 y 与之构成属于该函数的序偶
- 就是说,一个 x 只能对应一个 f(x),不能一对多,如
{<1,2>, <1,3>}就是不被允许的
单射:若 x1 ≠ x2,则 f(x1) ≠ f(x2)
- 即每个存在的 y 对应唯一的一个 x(单调函数就是典型的单射,但注意单射函数不一定单调),当然在后件集合 B 中允许有不被 x 映射的 y
满射:函数的值域为后件集合,即后件 B 被映射满了
双射:同时满足单射和漫射,此时每一个 x 和 y 一一对应(具有反函数)
集合的元素数量和单、满、双射关系
- 若为单射,则必有 |A| ≥ |B|
- 若为满射,则必有 |A| ≤ |B|
- 若为双射,则必有 |A| = |B|
# 函数运算
复合运算:和关系的复合运算一样,就是复合函数
这里的复合是左复合,和关系的复合恰好相反
- 关系的复合是将前件的定义域映射到后件的值域(前件的值域与后件的定义域相同)
如关系的复合
逆运算(反函数):只有双射的函数在经过逆运算之后才有反函数,若非双射,逆运算后会是一个普通的二元关系(而非函数)
# 代数系统
# 二元运算和代数系统
二元运算,一类函数,作用于序偶(二元关系)上
一般我们说,在某个集合上的二元运算(满足封闭性)构成一个代数系统
- 表示的是这个元素集合能够组成的二元关系和二元运算构成的系统
- 当然,代数系统不一定包含该集合上的所有二元关系
表示为<A,*>,其中 A 是组成二元关系的集合,* 为二元运算
# 群的分类
群是一类特殊的代数系统(广群即为一个基本的代数系统)
| 群的不同阶段 | 性质 |
|---|---|
| 广群 | 封闭性 |
| 半群 | 封闭性,结合律 |
| 含幺半群(独异点) | 封闭性,结合律,有幺元 |
| 群 | 封闭性,结合律,有幺元,有逆元 |
| 阿贝尔群 | 封闭性,结合律,有幺元,有逆元,交换律 |
群没有零元:反证法
# 群的性质
子群
- 子群:对于群
<A,*>,若集合 A 存在某一子集 B,在二元运算 * 的作用下仍构成群<B,*>,则说<B,*>是<A,*>的子群 - 平凡子群:群
<A,*>的平凡子群为<A,*>和<{e},*>,其中 e 是群的幺元
拉格朗日定理:子群集合的元素个数一定能够整除群的集合的元素个数,即若<B,*>是<A,*>的子群,则有 |B| 能够整除 |A|
循环群:由一生成元自循环可得到所有的集合元素
- 循环群一定是阿贝尔群(一定满足交换律)
阶数
- 群的阶数:即集合 A 中元素的个数(集合的基数)
- 元素的阶数:对于群中元素,若
a^k = e,则 k 为元素 a 的阶数,其中 e 为群的幺元
群的同态:若 f 是群 <A,*> 到群 <B,⊕> 的同态映射,则有
注意 f(a)、f(b) 为 B 中元素
群的同构:若同态映射 f 为双射(单射且满射),群 <A,*> 到群 <B,⊕> 是同构的
# 环和域
涉及同一集合上的两种运算,对于一个代数系统
若
<A,+>构成一个阿贝尔群<A,*>构成一个半群- 且 * 运算对于 + 运算在 A 上是可分配的,即
a*(b+c) = a*b + a*c = (b+c)*a
则代数系统<A,+,*>构成一个环
若<A,*>构成的是一个含幺半群,且不含零元,则代数系统<A,+,*>构成一个整环
若<A,*>构成的也是一个阿贝尔群(即含幺元、逆元且满足交换律),则代数系统<A,+,*>构成一个域
# 图论
# 图的表示
| 图的分类 | |
|---|---|
| 平凡图 | 由一个孤立点构成的图 |
| 简单图 | 无平行边,无环的图(注意有环的定义是存在某元素从自身到自身的边) |
| 完全图 | 任意两节点都有边相连的简单图 |
| 连通图 | 对于有向图,分为单向连通(图中每两个结点可以通过一个方向可达)和强连通 |
| 欧拉图 | 有欧拉回路的连通无向图 |
| 平面图 | 在一个平面上,无向图 G 的图解中若没有任何边的交叉,则称图 G 是个平面图;否则,称 G 是非平面图 |
图的表示:邻接矩阵(和 DS 一样)
- 若上半部分均为 1,则单向连通
- 简单图的主对角线全为零(无环)
- 若邻接矩阵中
G[i][j] = 1,则说明结点 i 和 j 之间存在通路 - 若邻接矩阵中
G^k[i][i] = 1,则说明结点 i 之间存在长度为 k 的回路
将图的可达矩阵:和求二元关系的传递闭包一样一样的,就说有点熟悉
# 图的性质
握手定理:任意图的总度数是边数的两倍
树边和结点的关系:在树中,结点数始终比边数要多一个
欧拉通路与回路
- 存在欧拉通路(经过所有结点的简单通路,无重复边)的图只存在 0 或 2 个奇数度结点
- 存在欧拉回路(经过所有结点的简单回路,无重复边)的图(即欧拉图)不存在奇数度结点
注意,存在偶数个结点的欧拉图总边数可以是奇数,因为边数 = 总度数/2,而总度数一定为偶数个偶数的和(有偶数个结点且每个结点度数均为偶数,但最后是相加),偶数的和的二分之一有可能是奇数,如 1x2+1x4 = 6,而 6/2 = 3
二部图(偶图)
对偶图
平面图:对于连通的平面图,有 n-e+r = 2,即结点数减去边数加上面数始终等于 2
对偶图
图的完全匹配
# 连通性与割集
无向图的连通性很简单:任意两个结点之间可达
有向图的连通性分为三种情况
- 强连通:任意两个结点之间可达(如双向链表)
- 单向连通:任意两个节点之间单向可达(如链表)
- 弱连通:不满足单向连通,但失去方向后,是一个连通的无向图
在图的矩阵表示中较为明显,若上半部分全为 1,则为单向连通,若除主对角线全为 1,则为强连通
边割集与点割集(对于无向图而言)
- 首先要求图是联通的
- 其次,找到一组边集合,删去这组边后,图将恰好变的非连通,那么这个边集合即为该图的边割集(很多时候边割集不唯一)
- 若某边割集仅含一个元素,那么这个边称为该图的割边
点割同理,只不过删的是结点(删结点时要删去所以何其相连的边)
对于一个图,定义其最小的点割集的基数为其点连通度,定义其最小的边割集的基数为其边连通度(基数即集合中元素个数)
- 显然具有割点、割边的图点连通度和边连通度均为 1
# 通路与回路
回路的进化历程(通路同理)
- 回路:出发点和终点相同,路径不做任何限制
- 简单回路:回路的基础上,路径中不经过相同的边
- 基本回路:回路的基础上,路径中不经过相同的结点(基本回路一定是简单回路)
- 欧拉回路:一条经过所有边的简单回路
欧拉通/回路与结点度数的关系
- 当一个无向图有欧拉通路,则其只有 0 个或 2 个奇数度结点
- 当一个无向图有欧拉回路,则其没有奇数度结点
欧拉图:具有欧拉回路的图
欧拉定理:对于连通平面图,其结点数 v,边数 e,面数 r 满足 v-e+r = 2
路径的长度:经过的边的个数
# 树和生成树
树是一种特殊的图
之前说过握手定理,图的度数是边数的两倍,同样适用于树,并且在树中,因为父亲结点只有一个,所以必然有边数等于结点数 -1
最小生成树
- 普利姆算法:从结点出发
- 克鲁斯卡尔算法:从边出发