离散数学基础__简单的期末复习
文章目录
第一课：命题逻辑的基本概念、命题及其真值
一个真命题就是一个真命题
假命题是真值为假的命题
简单和复合命题
简单命题（原子命题）：由简单陈述句组成的命题
复合命题是通过连接词连接简单命题形成的陈述句
连接词和复合命题
如果p，则q称为p和q的蕴涵，记为p→q p是蕴涵的前件，q是蕴涵的后件→称为蕴涵连接词
p→q的逻辑关系
q 是 p 的必要条件
p 是 q 的充分条件
第二课公式作业
设p,q,…为公式A中出现的所有命题变量，将一组真值赋给p,q,…，称为A的赋值或解释。
使公式为真的赋值称为真赋值
使公式为假的赋值称为假赋值
命题公式的分类
重言式（永恒的真理）：没有错误赋值的命题公式
矛盾（永久错误）：没有真正赋值的命题公式
可满足：非矛盾命题公式 注意：重言式是可满足的，但反之则不行。
第三课：命题逻辑等价演算、等价算法
//德摩根律
¬(A∨B)⇔¬A∧¬B
¬(A∧B)⇔¬A∨¬B
//蕴涵等值式
A→B⇔¬A∨B
//假言易位
A→B⇔¬B→¬A
第四课推理
推理是从前提推导出结论的思考过程。前提是指已知的命题公式，结论是从前提导出并应用推理规则的命题公式。前提可以是多个。
定义：
令 H1, H2, …, Hn, C 为命题公式
如果 (H1∧H2∧…∧Hn)→C 是重言式，则称 C 是一组前提 H1,H2,…,Hn 的有效结论
记为：H1∧H2∧…∧Hn⇒C
推理方法
1.真值表法
2.如果H1、H2、…、Hn都是T(True)，C也是T(True)；
3.如果C为F(False)，则H1、H2、…、Hn中至少有一个为假
重言式包含
定义当且仅当 A→B 为真，我们说“A 重言式蕴含 B”，并将其表示为 A⇒B。
重言式蕴含A⇒B的证明方法
1、A→B是永恒的真理风格
2、证明¬B⇒¬A
3、如果 A 是 T，B 是 T，或者如果 B 是 F，A 是 F，那么 A⇒B。
4、直接使用共同蕴涵（p51推理法）
推理法则 – 同义反复
(A→B)∧A⇒B //★假言推理
(A→B)∧¬B⇒¬A //★拒取式
(A∨B)∧¬B⇒A //★析取三段论
(A→B)∧(B→C)⇒(A→C) //★假言三段论
第五课推理法直接证明
PT 法：
P 定律：在推导过程中引用了前提。
T 定律：已经引入的公式可以在后续推导过程中引用。包括 TI 法则（重言式蕴涵）和 TE 法则（等价）。
间接证明法前提证明法：
证明A1,A2, …,Ak→(C→B)
前提：A1,A2, …,Ak
结论：C→B
等价证明
前提：A1,A2, …,Ak,C
结论：B
简化为荒谬（矛盾的证据）：
证明A1,A2, …,Ak→B
前提：A1,A2, …,Ak
结论：B 将 ¬B 添加到前提。如果引入矛盾，则推理是正确的。
第六课范式：简单析取和简单合取
文本：命题变量及其否定集合
简单析取：由有限字符组成的析取，例如 p,¬q,p∨¬q,p∨q∨r, …
简单连词：由有限字符组成的连词，如p,¬q,p∧¬q,p∧q∧r,…
析取范式和合取范式
析取范式
由有限简单合取A1∨A2∨…∨Ar组成的析取
其中 A1,A2,…,Ar 是简单的连词
连接范式
合取A1∧A2∧…∧Ar，由有限简单析取组成，
其中 A1,A2,…,Ar 是简单的析取
范式：析取范式和合取范式的统称
范式存在定理
定理 任何命题公式都有其等价的析取范式和合取范式
主要析取范式 主要析取范式：由最小项组成的析取范式
例如当n=3时，命题变量为p,q,r
(¬p∧¬q∧r)∨(¬p∧q∧r)是主析取范式
定理
任何命题公式都有一个等价的主析取范式并且是唯一的。
问主析取范式的方法
假设公式A包含命题变量p1,p2,…,pn
(1) 求 A 的析取范式 A′=B1∨B2∨… ∨Bs，其中 Bj 是简单的合取 j=1,2, … ,s
(2) 如果 Bj 既不包含 pi 也不包含 ¬pi，则将 Bj 展开为 Bj⇔Bj∧(pi∨¬pi) ⇔(Bj∧pi)∨(Bj∧¬ pi) 重复此过程直到所有简单连词是长度为 n 的最小项
(3)消除重复的最小项，即用mi代替mi∨mi
(4)按下标从小到大排列最小的项
附： ∧1 m001 m010…保证m…为1自然数是整数的逆命题，记为Σ
求连词范式的方法
假设公式A包含命题变量p1,p2,…,pn
(1) 求 A 的合取范式 A′=B1∧B2∧…∧Bs，其中 Bj 是简单析取 j=1,2,…,s。
(2) 如果 Bj 既不包含 pi 也不包含 ¬pi，则将 Bj 展开为 Bj⇔Bj∨(pi∧¬pi) ⇔(Bj∨pi)∧(Bj∨¬pi) 重复此过程直到所有简单析取是长度为 n 的最大项。
(3) 消除重复的极大项，即将Mi∧Mi替换为Mi。
(4) 将极大的项目从小到大排列。
附： ∨0 M001 M010…保证M…为0，记为Π
初级析取范式的集合表示
找出公式的真赋值和假赋值
判断公式的类型
判断两个公式是否等价
第 3 章 – 一阶逻辑
量词：表达数量的词
万能量词∀：表示任意、全部、全部等
如果 ∀x 表示对于单个域中的所有 x，x∀x F(x) 表示所有 x 都具有属性 F
存在量词∃：表示有，有，至少一个等
例如，∃x 表示在单个域中存在 x∃x。 F(x) 表示有 x 的性质为 F
第1章集合和集合枚举的关系表示
如A={a,b,c,d},N={0,1,2,…}
说明 { x | P(x) } 如 N={ x | x 是自然数}
**集合属性：**
(1)集合中的元素不同。例如，{1,2,3}={1,1,2,3}
(2)集合中的元素不能重复。
(3)集合中的元素没有顺序。例如，{1,2,3}={3,1,2}={1,3,1,2,2}
(4)集合中的元素也可以是集合。
共同收藏
自然数集N，整数集Z，正整数集Z+，有理数集Q，非零有理数集Q，实数集R，非零实数集R，复数集C，区间[ a,b],(a, b) 等待**
第八课：集合之间的关系①包含和等于
包含（子集）A⊆B ⇔ ∀x(x∈A→x∈B)
排除 A⊈B ⇔ ∃x(x∈A∧x∉B)
等于 A=B ⇔ A⊆B∧B⊆A
不等于 A≠B ⇔ A⊈B ∨B⊈A
真包含（真子集）A⊂B ⇔A ⊆B∧A≠B
②空集和完全集
空集∅：没有元素的集合
完整集 E：所讨论的集合仅限于 E 的子集
③电源组
幂集 P(A)：A 的所有子集的集合
P(A)=x∣x⊆AP(A) = { x| x⊆A }P(A)=x∣x⊆A
如果 |A| = n，则 |P(A)| = 2^n
第九课，第四章，关系，有序对
定义
由x和y等两个元素按一定顺序组成的对称为有序对，记为
笛卡尔积
定义设A、B为集合，A与B的笛卡尔积记为A×B，A×B = { | x∈A ∧y∈B }.
定义域、范围和域
域：domR= {x| ∃y(∈R) }
范围：ranR= {y| ∃x(∈R) }
fldR=domR∪ranR
示例 R={,,,},
然后 domR =ranR =fldR = { a, c, {a}, d } {{b}, d, {d}}{ a, c, {a}, d , {b}, {d} }
重要的关系
令 A 为任意集合
1、∅是A上的一个关系，称为空关系
2、EA、IA分别称为全局关系和身份关系。
KaTeX 解析错误：意外字符：第 27 位的“”：…| x∈A ∧y∈A}=A×A̲
IA=∣x∈AIA={ | x∈A}IA=∣x∈A
例如，A={1,2}，那么
EA={,,,}
IA={,}
关系的表示
关系矩阵
如果 A={x1, x2, …, xm}, B={y1, y2, …, yn}，则 R 是 A 到 B 的关系
R的关系矩阵是一个布尔矩阵MR= [ rij] m×n，其中rij= 1⇔ ∈R
第十课：逆关系
令R为X与Y的二元关系，
R的反比关系记为RC(或R-1),
即：R-1={| ∈R }
显然，如果R⊆A×B，那么R-1 ⊆B×A
R和S的复合关系
R∘S= | | ∃y(∈R∧∈S) }
**示例 R={, , , }S={, , , ❤️,2>, ❤️,3>} **
R∘S={, , }
S∘R={, , ❤️,2>, ❤️,3>}
A 上关系的取幂
定义设R为A上的关系，n为自然数，则R的n次方为
(1) R0 = { | x∈A } = IA
(2) Rn+1 = Rn∘R
求幂方法
对于一个集合表示的关系R，计算Rn就是n个R的合成。一个矩阵表示的关系是矩阵乘法，加法采用逻辑加法
自反性和自反性
定义
令 R 为 A 上的关系，
(1) 如果∀x(x∈A→∈R)，则称R在A上是自反的
(2) 如果∀x(x∈A→∉R)，则称R在A上是自反的。
自反：A 上的全局关系 EA，恒等关系 IA，小于或等于关系 LA，可分关系 DA 反反：实数集上的小于关系，幂集上的真包含关系。
通俗解释：
包括所有：反身
排除所有：反身
部分包含：既不自反也不自反
对称和反对称
定义令R为A上的关系，
(1) 若∀x∀y(x,y∈A∧∈R→∈R)，则称R为A上的对称关系。
(2) 如果∀x∀y(x,y∈A∧∈R∧∈R→x=y),
然后称 R 为 A 上的反对称关系。
实例对称性：A 上的全局关系 EA、恒等关系 IA 和空关系 ∅。反对称：恒等关系IA，空关系是A上的反对称关系。
通俗解释：
对称：在关系R中，如果R是对称的，对于R中的任何有序对，在R中都有一个相反的有序对。
反对称：在关系R中，如果R是反对称的，那么对于R中具有相反元素对的有序对，它们的两个元素必须相等。
传递
定义R是A上的关系
如果∀x∀y∀z(x,y,z∈A∧∈R∧∈R→∈R)，则称R是A上的传递关系。
示例：A 上的全局关系 EA、恒等关系 IA 和空关系 ∅、小于等于关系、小于关系、可分关系、包含关系、真包含关系
通俗解释：
传递性：在关系R中，如果R具有传递关系，则必然存在∈R∧∈R→∈R
第十一课等价关系
定义
令 R 为非空集上的关系。如果 R 是自反的、对称的和传递的，则称 R 为 A 上的等价关系。
令R为等价关系，若∈R，则称x等价于y，记为x～y。
等价类
定义令R为非空集A上的等价关系，
∀x∈A，令 [x]R = { y | y∈A∧xRy } 称[x]R为x关于R的等价类，简称为x的等价类
商业
定义令R为非空集A上的等价关系，
以R的所有等价类为元素的集合称为A关于R的商，记为A/R，
等价关系与除法一一对应
A/R 商是 A 的除法
不同的商对应不同的除法
给定 A 的一个分区 π，A 上的关系 R 定义如下： R ={ | x,y∈A∧x和y在π的同一个分区}
那么R是A上的等价关系，由等价关系确定的商是π。
第十二课：偏序关系
定义
非空集A上的自反、反对称和传递关系称为A上的偏序关系，
表示为≼。设≼为偏序关系，
如果∈≼，则写x≼y，读作x“小于或等于”y
偏序集和哈斯图
定义
集合A和A上的偏序关系≼统称为偏序集，记为。
例子：整数的集合和数的小于等于关系构成偏序集，幂集P(A)和包含关系构成偏序集
.
哈斯图：每个节点没有圈，两个相连的节点之间的顺序关系用节点位置的高度来表示，位置较低的元素的顺序在前面覆盖关系的两个节点之间。并排。
偏序集合的特定元素
(【集合论】序关系( 偏序关系中的八个特殊元素 | ① 最大元素 | ② 最小元素 | ③ 最大元素 | ④ 最小元素 | ⑤ 上界 | ⑥ 下界 | ⑦ 最小上界 精确界| ⑧ 最小下界infermum
图无向图的基本概念
定义
无向图 G=,
其中V≠∅称为顶点集，其元素称为顶点或节点；
E是V&V的多重子集，称为边集，其元素称为无向边，或简称边。
有时V(G)和E(G)分别用来表示V和E
定义有向图 D=,
其中V≠∅称为顶点集，其元素称为顶点或节点；
E是V×V的多重子集，称为边集，其元素称为有向边，简称边。
有时V(D)和E(D)分别用来表示V和E
有限图：V 和 E 都是有限图集 n 阶图：具有 n 个顶点的图 零图：具有 E=∅ 的图 平凡图：一阶零图
空图：V=∅的图
顶点和边的关联和邻接
假设一个无向图G=,ek=(vi, vj)∈E，称vi,vj为ek的端点，ek与vi(vj)相关联。
若vi≠vj，则ek与vi(vj)的关联数为1；若vi=vj，则ek与vi的关联数为2；
如果vi不是边e的端点，则称e和vi之间的关联数为0。
设vi,vj∈V,ek,el∈E,若(vi,vj)∈E,vi,vj称为相邻；如果 ek,el 有一个公共端点，则 ek,el 是相邻的。
顶点度数
令 G= 为无向图，v∈V，
v的度数(degree) d(v)：v是边的端点数之和
悬垂顶点：1 度的顶点悬垂边：与悬垂顶点关联的边
G的最大度Δ(G)=max{d(v)|v∈V}
G的最小度δ(G)=min{d(v)|v∈V}
第十三类握手定理
定理
任何图（无向和有向）中所有顶点的度数之和等于边数的 2 倍。
有向图中所有顶点的入度之和等于出度与边数之和。
推理
任何图（无向图和有向图）都有偶数个奇数度顶点
示例：在一群人中，一定有偶数个朋友有奇数个。
简单图
定义
在无向图中，与同一对顶点相关联的两条或多条边称为平行边，平行边的数量称为多重性。
在有向图中，起点和终点相同的两条或多条边称为有向平行边，或简称平行边，平行边的数量称为多重性。
具有平行边的图称为多重图。既没有平行边也没有环的图称为简单图。
完全图和正则图 无向完全图：
每对顶点之间只有一条边的无向简单图。
n阶无向完全图记为Kn，顶点数为n
边数m=n(n- 1)/2,Δ=δ=n- 1
有向完全图：
每对顶点之间有两条对边的有向简单图。
顶点数n，边数m=n(n-1)
Δ=δ=2(n- 1)
k-正则图：顶点数n，边数m=kn/2
子图
定义集G=自然数是整数的逆命题，G′=为两个图（都是无向图，或者都是有向图），
若V′⊆V和E′⊆E，则称G′为G的子图，G为G′的父图，
记为G′⊆G。若G′⊆G且V′=V，则称G′为G的生成子图。
若V′⊂V或E′⊂E，则称G′为G的真子图。
图的同构
定义
如果说 G1 和 G2 同构，则写为 G1≅G2
那么两个图的节点数相同，每个节点的度数相同，知识节点的排列组合不同
第十四课图的矩阵表示是有向/无向图的邻接矩阵
通路和回路
定义
给定图 G=（无向或有向）
G中顶点和边的交替序列Γ=v0e1v1e2…elvl.G顶点和边的交替序列Γ=v_0e_1v_1e_2…e_lv_l.G顶点和边交替序列Γ= v0e1v1e2…elvl.
如果
∀i(1≤i≤l),ei=(vi−1,vi)∀_i(1≤i≤l),e_i=(v_i-1,v_i)∀i(1≤i≤l ) ),ei=(vi−1,vi)
(对于有向图，ei=)，则Γ称为v0到vl的路径
v0和vl分别是通路的起点和终点，l是通路的长度。
如果 v0=vl，则 Γ 称为循环。
如果一个路径（循环）中的所有顶点（for循环，v0=vl除外）都不同，则称为主路径或路径（primary loop or loop）。
如果路径（循环）中的所有边都不同，则称为简单路径（simple loop），否则称为复杂路径（complex loop）
无向图的连通性和连通分支
令无向图G=,u,v∈V
u 和 v 连通：如果 u 和 v 之间存在路径，则规定 u 和自身始终连通。
连通图：任意两点相连的图。平凡图是连通图。
连通性 R={|u, v∈V and u and v are connected}。 R是等价关系。
连通分支：V 的等价类关于 R 的派生子图。
设V/R={V1,V2,…,Vk}，G的连通分支为G[V1],G[V2],…,G[Vk]
连通分支的数量p(G)=k，G是连通图⇔p(G)=1
有向图的连通性和分类
有向图 D=,u,v∈V,
u 到 v 可达：从 u 到 v 有一条路径，规定 u 到自身总是可达的。
u 和 v 是相互可达的：u 取决于 v，v 取决于 u
D弱连通（connected）：省略每条边的方向得到的无向图是连通图
D是单向连通的：∀u，v∈V，u可以到达v或者v可以到达u
D是强连通的：∀u,v∈V，u和v互可达
无向图的相关矩阵
令无向图 G=,V={v1,v2,…,vn},E={e1,e2,…,em}。
设mij为vi和ej的关联数，称(mij)n×m为G的关联矩阵，
M(G).mij的可能取值为：0,1,2
无环有向图的关联矩阵
设无环有向图D=,V={v1,v2,…,vn},E={e1,e2,…,em}
mij = 0 vivj 不连通 mij = 1 vi 为起点 mij=-1 vj 为终点
第十五课：欧拉图
欧拉路径：一条经过所有顶点且每条边只经过一次的路径。
欧拉回路：经过所有顶点且每条边仅经过一次的回路。
欧拉图：带有欧拉回路的图。
判别定理
无向图 G 具有欧拉回路当且仅当 G 是连通的且没有奇异顶点。
Branch：V 的等价类关于 R 的派生子图。**
设V/R={V1,V2,…,Vk}，G的连通分支为G[V1],G[V2],…,G[Vk]
连通分支的数量p(G)=k，G是连通图⇔p(G)=1
有向图的连通性和分类
有向图 D=,u,v∈V,
u 到 v 可达：从 u 到 v 有一条路径，规定 u 到自身总是可达的。
u 和 v 是相互可达的：u 取决于 v，v 取决于 u
D弱连通（connected）：省略每条边的方向得到的无向图是连通图
D是单向连通的：∀u，v∈V，u可以到达v或者v可以到达u
D是强连通的：∀u,v∈V，u和v互可达
无向图的相关矩阵
令无向图 G=,V={v1,v2,…,vn},E={e1,e2,…,em}。
设mij为vi和ej的关联数，称(mij)n×m为G的关联矩阵，
M(G).mij的可能取值为：0,1,2
无环有向图的关联矩阵
设无环有向图D=,V={v1,v2,…,vn},E={e1,e2,…,em}
mij = 0 vivj 不连通 mij = 1 vi 为起点 mij=-1 vj 为终点
第十五课：欧拉图
欧拉路径：一条经过所有顶点且每条边只经过一次的路径。
欧拉回路：经过所有顶点且每条边仅经过一次的回路。
欧拉图：带有欧拉回路的图。
判别定理
无向图 G 具有欧拉回路当且仅当 G 是连通的且没有奇异顶点。
G 有欧拉回路，但没有欧拉回路当且仅当 G 是连通的并且恰好有两个奇数顶点。
常见问题FAQ
- 免费下载或者VIP会员专享资源能否直接商用？
- 本站所有资源版权均属于原作者所有，这里所提供资源均只能用于参考学习用，请勿直接商用。若由于商用引起版权纠纷，一切责任均由使用者承担。更多说明请参考 VIP介绍。
- 提示下载完但解压或打开不了？
- 找不到素材资源介绍文章里的示例图片？
- 欧资源网
