离散_期末复习[战损版]

psych

2023-06-14

课内

离散, 课内

第一章_集合论

集合的基本概念

集合：集合通常是由指定范围内满足给定条件的所有对象聚集在一起构成的。

元素：指定范围内的每个对象称为这个集合的元素。将语句"ａ是集合Ａ中的元素"或"ａ属于Ａ"记为ａ∈Ａ

基数：将集合中元素的个数称为集合的基数。记为Ａ。由此把集合分为有限集和无限集

集合的表示

列举法例如 A={0,1,2,3};B={0,1,4,9,···,n^2,···}。
描述法记为{xP(x)} ->x是代表元，P(x)表示x具有性质P
例如 A={xx是’psych’中的所有字母}
归纳法归纳法是通过归纳定义集合的方法，其定义主要有三部分组成：
- 第一部分：基础，支出某些最基本的元素属于某集合。
- 第二部分：归纳，指出有基本元素造出新元素的方法。
- 第三部分：极小性，指出改集合的界限
例如，集合A按照如下方式定义：
(1)0和1都是A中的元素
(2)如果a,b是A中的元素，则ab，ba也是A中的元素
(3)有限次使用(1),(2)后所得到的的字符串都是A中的元素
显然->0,1,00,101等都是A中的元素
递归指定集合法例如：设a(0) = 1;a(i+1)=3a(i);定义S={a(0),a(1),a(2),…,}={a(k)k∈N}
文氏图法:利用平面上的点表示集合中的元素

集合与集合的关系

集合中的元素是无序且互异的。

集合相等：A和B中的元素完全相同，则A和B这两个集合相等，记为Ａ＝Ｂ。

子集：如果B中的每个元素都是A中的元素，则称B是A的子集，也称B被A包含(A包含B)，记作Ｂ⊆Ａ.特别的如果B≠A，则A真包含B，即B是A的真子集，记作 Ｂ⊂Ａ

几个特殊集合

空集：不含任何元素的集合称为空集，记作⌀。

1	空集可以表示为： ⌀={xx≠x}

空集是客观存在的。例如 Ａ＝{ｘｘ∈Ｒ且x^２<０} 就是一个空集

空集是一切集合的子集
空集是绝对唯一的

**全集(论集)**：在一个相对固定的范围内，包含此范围内的所有元素的集合，称为全集或者论集。用U或E表示

全集是相对唯一的。

集族：以集合为元素的集合称为集族

幂集：设A为任意集合，称A的所有不同子集构成的集合为A的幂集，记作P(A)或 2^Ａ,即 P(A)＝{xx⊆A}。幂集是一个集族

给定一个有限集，作出如下规定：

称含有n个元素的集合为n元集

若A为n元集，则称A的含有ｍ个(０≤ｍ≤ｎ)元素的子集为它的ｍ元子集。

集合的运算

总的来说，集合的元素有以下这几种基本运算：并运算，交运算，差运算，补运算，对称差运算

Ａ∪Ｂ -> 取A与B的并集，为并运算，符号为∪
Ａ∩Ｂ -> 取A与B的交集，为交运算，符号为∩
Ａ-Ｂ -> 取A与B的差集，为差运算，符号为-特别的如果A=U，即A是全集是，A-B又称为集合B的补集，运算为补运算。
Ａ⊕Ｂ=(Ａ-Ｂ)∪(Ｂ-Ａ) ->取A中除开B的部分加上B中除开A的部分，为对称差运算，符号为⊕ 文氏图为：

一些运算公式：（看看得了）

无限集

与集合相关的应用

第二章_命题逻辑

命题与命题联结词

命题

定义：能够判断真假的陈述句称为命题。称’真’和’假’为命题的真值，用’T’(1)和’F’(0)表示。

判断：一个语句是命题，当且仅当它是陈述句且有明确的真值。

命题联结词

原子命题：不能再分解为更简单命题的命题，称为原子命题。

命题联结词：像“或者”这种联结命题的关键词，称为命题联结词。

复合命题：有命题联结词联结原子命题而形成的命题称为复合命题

最常见的语句间的关系主要有一下5种：

表示否定关系的:’不’，’非’，’否’… –>否定联结词
表示并列关系的:’并且’，’和’，’即…，又…’ –>合取联结词
表示选择关系的:’…或者…’，’…或…’ –>析取联结词
表示条件关系的:’如果…，则…’，’如果…，那么…’ –>蕴含联结词
表示等价关系的:’…当且仅当…’ –>等价联结词

自然语言的命题符号化

真值表

蕴含： 100,其他全部为1

等价：相同为真，不同为假

优先级

所有五个联接词的优先顺序为：否定，合取，析取，蕴涵，等价；

命题公式，解释与真值表

命题公式

原子命题又被称作命题常量或常值命题，而其他P,Q,R等通常(真值可变)被称为命题变量或命题变元。命题公式诸如¬ (Ｐ∧Ｑ)→¬ Ｒ 又被称为 P, Q 和R的真值函数。常被记为Ｇ(Ｐ,Ｑ,Ｒ)

命题公式的解释与真值表

我们进行如下定义：

公式G的真值全为’真’，则称公式G为永真公式(重言式)
公式G的真值全为’假’，则称公式G为永假公式(矛盾式)
公式G的真值至少存在一个为’真’，则称公式G为可满足公式

如果题目要求_判断公式的类型_，就是让我们化简，看公式是重言式还是矛盾式还是可满足公式···

命题公式的基本等价定律

范式

对于任意的命题公式，是否有一个唯一的，标准的表示形式呢？这就是范式要解决的问题。

联结词的完备集

括号组成的有限长度的符号串，又可以知道“→”和“↔”可用“¬ ” “∧”和“∨”等价表示。因此，可以说任何命题公式都可以由“¬ ”“∧”和“∨”这３个联结词来等价表示。称这３个联结词构成的集合{¬ ， ∧， ∨}为联结词的完备集。

给出定义：

 设S,T是任意联结词集合。
 (1)如果任意一个命题公式都可以用S中的联结词进行等价表示，则称S是联结词的完备集
 (2)设S是一个联结词的完备集且 Ｔ⊂Ｓ。如果至少存在一个命题公式不能用T中的联结词进行等价表示，则称S为#极小联结词的完备集#
     补：极小联结词的完备集还有{¬ ，∨}

析取范式和和取范式

理论上，选用不同的联结完备词可以更加方便的对命题公式进行研究。但是同一个命题公式用不同的联结完备词就会得到不同的表达式，这给研究带来了不便。

我们着重研究用联结完备词：{¬ ， ∧， ∨}表示的命题公式的标准形式——范式。

下面先将一些概念：

文字：称命题变元或者命题变元的否定为文字
合取式或短语：如果一个命题具有形式式Ａ１∧Ａ２∧…∧Ａｎ(ｎ≥１)。其中Ａｉ(ｉ＝１，２，…，ｎ)是文字，则称该命题公式为合取式或短语。
析取式或字句：如果一个命题公式具有形式Ａ１∨Ａ２∨…∨Ａｎ(ｎ≥１)。其中Ａｉ(ｉ＝１，２，…，ｎ)是文字，则称该命题公式为析取式或字句。
合取范式：如果一个命题具有形式式Ａ１∧Ａ２∧…∧Ａｎ(ｎ≥１)。其中Ａｉ(ｉ＝１，２，…，ｎ)是析取式，则称该命题公式为合取范式。
析取范式：如果一个命题公式具有形式Ａ１∨Ａ２∨…∨Ａｎ(ｎ≥１)。其中Ａｉ(ｉ＝１，２，…，ｎ)是合取式，则称该命题公式为析取范式。

计算合取范式，析取范式：

用“¬ ”“∧”和“∨”等价替换掉“→”和“↔”
利用双重否定律消去多余的否定联结词，德摩根律将否定联结词内移
利用分配率，结合律，幂等律等整理得到对应的析取范式和合取范式

有一个小技巧：得到析取范式后可以直接转换得到合取范式

(¬Ｐ∧¬Ｑ)∨(Ｐ∧Ｑ)∨Ｒ

(¬ Ｐ∨Ｐ∨Ｒ)∧(¬ Ｐ∨Ｑ∨Ｒ)∧(¬ Ｑ∨Ｐ∨Ｒ)∧(¬ Ｑ∨Ｑ∨Ｒ)

主合取范式和主析取范式

极大项和极小项

定义：在含有n个命题变元的合/析取式中，如果每个命题变元与其否定不同时存在，但二者之一恰好出现且仅出现一次，则称这个合/析取式为关于这n个命题变元的一个极大/小项。

极大项 -> 析取式
极小项 -> 合取式

编码规则

极大项的编码规则：命题变元极其否定对应 0和 1

极小项的编码规则：命题变元极其否定对应 1 和 0

主合取范式和主析取范式

主合取范式：一个命题公式具有形式：Ａ1∧Ａ2∧…∧Ａn(ｎ≥１)，其中Ai是极大项，则称改命题公式为主合取范式
主析取范式：一个命题公式具有形式：Ａ1∨Ａ2∨…∨Ａ3(ｎ≥１)，其中Ai是极小项，则称该命题公式为主析取范式。

主合/析取范式的计算方法

先计算出合取范式或析取范式
将析取/合取范式中的每一个式子变成极大项/极小项
小技巧：Ｐ＝Ｐ∧１＝Ｐ∧(¬ Ｑ∨Ｑ)；Ｐ＝Ｐ∨０＝Ｐ∨(¬ Ｑ∧Ｑ)
利用幂等律将相同的极大/极小项合并，同时利用交换律进行顺序调整，从而得到主/合取范式。

命题逻辑的推理理论

基本概念

定义：设Ｇ１，Ｇ２，···，Ｇｎ，Ｈ是命题公式。对任意解释 I，如果Ｇ１∧Ｇ２∧···∧Ｇｎ为真，Ｈ也为真。或者Ｇ１∧Ｇ２∧，∧Ｇｎ为假，则称Ｈ是Ｇ１，Ｇ２，···，Ｇｎ的逻辑结果(Logic Conclution)。或者Ｇ１，Ｇ２，···，Ｇｎ共同蕴涵Ｈ。记为Ｇ１，Ｇ２，···，Ｇｎ⇒Ｈ。

定理2.6：公式Ｈ是前提集合{Ｇ１，Ｇ２，···，Ｇｎ }的逻辑结果当且仅当Ｇ１∧Ｇ２∧···∧Ｇｎ→Ｈ为永真公式。

判别方法

真值表技术：构造真值表，配合定理2.6去判断 (→)

等价公式转换法：

合取所有前提作为蕴含式的前件，结论作为蕴含式的后件
化简这个蕴含式
如果化简结果为1，则推理有效，否则推理无效。

演绎法：从前提(假设)出发，依据公认的推理规则和推理定律导出结论的方法。

为了正确地使用演绎法去判定推理的有效性，还需要了解推理定律和推理规则

_推理定律_：

_推理规则_：

（1）P规则(Premise前提引用规则) 在推理过程中，如果引入前提集合中的一个前提，则称使用了P规则

（2）T 规则(Transformation，逻辑结果引用规则) 在推理过程中，如果引入推理过程中产生的某个中间结果，则称使用了T规则。

（3）)CP规则(Conclusion premise，附加前提规则) 在推理过程中，如果逻辑结果为蕴涵式，并且将该蕴涵式的前件作为前提引入，则称使用了CP规则。

还有一个消解原理，不太会，有人说不怎么要求，就不整理了。。

事实上，消解原理就是反证法的一种形式

① Ｐ∨¬ ＲＰ

② ＲＰ

③ ＰＴ， ①， ②， 消解原理

命题逻辑的应用

命题联结词的应用

计算机中的比特运算

需要注意的就是XOR指的是异或(不可兼或)。

web搜索

命题公式的应用

化简电路，化简程序图

e.g:

用命题公式化简其对应的电路：

第三章_谓词逻辑

自然语言的谓词符号化

谓词

在原子命题中，可以独立存在的客体(句子中的主语、宾语等)称为个体词(Individual)。用以刻画客体性质或客体之间关系的部分称为谓词(Predicate)。

定义：设Ｐ(X1，X2 ，···，Xn )是定义在Ｄｎ上的ｎ元函数。其中Ｄ为非空的个体域，如果Ｐ(X1，X2 ，···，Xn )的值域是{0,1}。则称Ｐ(X1，X2 ，···，Xn )为n元命题函数或n元谓词 (Propositional Function）。

量词

谓词公式和解释

自由变元和约束变元

谓词公式的解释

在任意给定的解释I下，如果谓词公式G的取值全部为真，则称G为永真公式，如果全部为假则为永假公式。如果存在有真，就是可满足公式。

谓词公式的标准型——前束范式

设G,H是谓词公式，如果谓词公式G<->H是永真公式，那么称G,H是等价的，记作G=H

谓词逻辑的推理理论

谓词公式的标准型——前束范式

前束范式并不唯一

谓词逻辑的应用

推理规则

消去量词规则
- UI(全称量词消去)规则任意ｘＧ(ｘ)⇒Ｇ(ｙ) 其中Ｇ(ｘ)对ｙ是自由的。或者ｘＧ(ｘ)⇒Ｇ(ｃ) 其中ｃ为任意个体常量
- EI(存在量词消去)规则存在ｘＧ(ｘ)⇒Ｇ(ｃ) 其中ｃ为使Ｇ(ｃ)为真的特定个体常量
引入量词规则
- ＵＧ(全称量词引入)规则Ｇ(ｘ)⇒任意ｙＧ(ｙ) 其中Ｇ(ｘ)对于ｙ是自由的
- ＥＧ(存在量词引入)规则Ｇ(ｃ)⇒存在ｘＧ(ｘ) 其中ｃ为特定个体常量或者Ｇ(ｘ)⇒存在ｙＧ(ｙ) 其中Ｇ(ｘ)对于ｙ是自由的

推理定律

第四章_二元关系

二元关系及其表示

二元关系的定义：由两个元素ｘ，ｙ按照一定的次序组成的二元组被称为有序偶对，简称序偶。记作‹ｘ，ｙ›，读作“序偶ｘ，ｙ”。其中称ｘ为‹ｘ，ｙ›的第一元素，ｙ为‹ｘ，ｙ›的第二元素。

推广序偶的思想，可以定义任意ｎ个元素的有序序列：由ｎ个元素a１，ａ２，···，ａｎ按照一定次序组成的ｎ元组被称为ｎ重有序组，记作‹ａ１，ａ２，···，ａｎ›。

将序偶与集合联系起来，可以得到笛卡儿积的定义：

笛卡尔积的运算

注意：空集×任何子集==空集

第六章_图

图的基本概念

图的定义

一个图是一个序偶<V,E>，记为G=<V,E>。

V={v1,v2,v3···,vn}是有限非空集合，vi称为结点，简称点，V称为结点集。
E是有限集合，称为边集，E中的每个元素都有V中的结点对与之对应，称之为边。

注意上面的结点对可以使有序的也可以是无序的，分别为有向边和无向边。

图的表示

集合表示：将一个图记为G=<V,E>，并写出了V和E的集合表示，称为图的集合表示

图形表示：为了表示方便，一般往往只需要画出图形。

矩阵表示：

无向图和有向图的邻接矩阵有些不同，无向图的矩阵一定是对称的。

对角线的数值为1表示环。

图的操作

删除边：设 e∈Ｅ，用G-e表示从Ｇ中去掉边e得到的图，该操作称为删除边。又设Ｅ′⊆Ｅ，用G-E′表示从G中删除E′中所有边得到的图，操作称为删除边集。

删除点：设ｖ∈Ｖ，用Ｇ－ｖ表示从Ｇ中去掉结点ｖ及ｖ关联的所有边得到的图，该操作称为删除结点。又设Ｖ′⊂Ｖ，用G-Ｖ′表示从Ｇ中删除Ｖ′中所有结点及关联的所有边得到的图，该操作称为删除结点子集。

收缩边：设ｅ＝(ｕ，ｖ)∈Ｅ。用Ｇ＼ｅ表示从Ｇ中删除ｅ，将ｅ的两个端点ｕ、ｖ用一个新的结点ｗ代替，使ｗ关联除ｅ外的ｕ和ｖ关联的一切边，该操作称为边的收缩。一个图Ｇ可以收缩为图H，是指Ｈ可以从G 经过若干次边的收缩而得到。

新加边：设ｕ，v∈Ｖ(ｕ、ｖ可能相邻，也可能不相邻)。用Ｇ∪(ｕ，ｖ)表示在ｕ，ｖ之间加一条边(ｕ，ｖ)，该操作称为加新边。

邻接点与邻接边

邻接点：一条边的两个端点

邻接边：具有公共结点的两条边

孤立结点：图中不与任何结点相邻接的结点称为孤立结点

零图：仅由孤立结点组成的图。

平凡图：仅含有一个节点的零图

含有n个结点，m个边的图称为**(n,m)图**

*图的分类

有无方向：无向图，有向图，混合图

有无平行边：多重图，线图，简单图。

含有平行边的图称为多重图，平行边的条数称为重数【有向图中始边与终边相同才是平行边，无向图中两结点间的都是平行边】

非多重图就是线图

无环的线图就是简单图

是否含权：赋权图，无权图

子图与补图

生成子图：结点没变，边只有一部分

导出子图：一部分结点，但是这部分结点之间的边全部都有【比如全校数据中导出一个年级的数据来】

完全图：

无向简单图中[无环的线图]：G中任意两个结点之间都有边相连，称为无向完全图，简称完全图
有向简单图中：G中任意两个结点都有方向相反的两条边相连，称为有向简单图，也简称完全图

补图：结点集相同，边集是完全图边集的补集

注意结点和原图是一样的，就是说有可能有孤立结点的情况，不能漏了

握手定理

度：G=<V,E>中以结点v∈V为端点的边数（有环的时候计算两次）称为结点v的度数。，简称度，记为deg(v)

有向图中要区分入度与出度。入度为deg-(v),出度为deg+(v)

悬挂结点：度数为1的结点称为悬挂结点

悬挂边:以悬挂结点为端点的边称为悬挂边

定理6.1（握手定理）

图中结点度数的总和是边数的两倍

有向图中，入度之和等于出度之和等于边数

图的同构

形象的说，若结点可以任意挪动位置，而且边是完全弹性的，只要在不拉断和长度不压缩为0的情况下，一个图可以变成另外一个图，就称这两个图是同构的。

两个图同构有三个必要条件：

结点数目相同
边数相同
度数相同的结点数相同

也就是说，上述三个条件有一个不满足，就不同构，但他们都满足不能说明图是同构的。

通路与回路

给定G=<V,E>中结点和边相继交错出现的序列Γ＝v0e0v1e1v2···ekvk

通路：若v0和vk不是同一个结点，则Γ 称为v0到vk的一条通路

回路：v0=vk，则此通路称为回路。

简单通路：通路中所有的边互不相同，或一条迹

基本通路：通路中所有的结点互不相同(从而所有的边互不相同)

基本回路：回路中所有的结点互不相同(从而所有的边互不相同)

通路与回路的计算

可达与距离

可达：vi与vj之间存在通路，就称vi和vj是可达的。

距离：如果vi与vj是可达的，那么vi带vj的长度最短的通路的长度称为距离。记为d(vi,vj)

定理：在一个具有n个结点的图中，如果从结点vi到结点vj存在一条通路，那么从vi到vj存在一条长度不大于n-1的通路。 —–由鸽笼定理可以证得

定义可达性矩阵P：

图的连通性

无向图的连通性

连通图：无向图G中任意两个结点都是可达的，则称G为连通图，否则为非连通图，或分离图

连通分支：无向图G中结点之间的可达关系R的每个等价类导出的子图都成为G的一个连通分支，用P(G)表示。

显然，无向图G是连通图当且仅当p(G)=1；每个结点和每条边都在且仅在一个连通分支中。

有向图的连通性

弱连通图：略去方向之后是连通的，就称弱连通图，否则就是非连通图

单向连通图：G中任意一对结点之间，至少有一个结点到另一个结点是可达的

强连通图：G中任意一对结点都是相互可达的。

连通性的判断

连通分支：强连通分支/单向连通分支/弱连通分支 ···

第七章_特殊图

树

连通而不含回路的无向图称为无向树，简称树

树中度数为1的结点称为叶，度数大于1的结点称为分支点或者内部结点。每个连通分支都是树的无向图称为森林，平凡图称为平凡树

树中没有环和平行边，因此一定是简单图，并且任何非平凡树中，都没有度数为0的结点

定理7.1

以下6个命题等价：G=<V,E> V=n , E = m

G连通且不含回路，即G是树
G中无回路，且m=n-1 【边数是结点数减一】
G是连通的，且m=n-1
G中无回路，但在G中任意两个结点之间增加一个新边，就得到唯一的基本回路
G是连通的，但删除G中任一条边后，便不连通（n≥2）
G中每一对结点之间有唯一的基本通路（n≥2）

定理：任意非平凡树T=(n,m)都至少有两片叶[利用握手定理和m=n-1证得]

生成树及算法

生成树：给定图G，G的某个生成子图是树，则称为G的生成树，生成树中的边称为树枝，G中不存在生成树中的边称为弦，所有弦的集合称为生成树的补。

定理：一个图存在生成数的充分必要条件是G是连通的。

利用以下算法可以求得连通图的生成树

破圈法

每次删除回路中的一条边，其删除的边的总数为m-n+1

避圈法

每次选取G中的一条与已选取的边不构成回路的边，选取的边的总数为n-1。

广度优先搜索算法

可以从任意结点开始，比如说从a开始，把它标记为０(－)。与a邻接的结点是b和c，把它们标记为１(ａ)。接下来对邻接于b和c的未标记的结点e和f做标记。把它们分别标记为２(ｂ)和２(ｃ)。按这样的方法继续，直到所有的结点都有标记为止。一组可能的标记如图。连接每个结点到其前驱(在结点的标记中指明)的边就构成了一棵生成树

最小生成树

G是连通是赋权图，T是G的一颗生成树，T的每个树枝所赋权值之和称为T的权，记为W(T)，G中既有最小权的生成树称为G的最小生成树。

Kruskal 算法

Prim算法

根数

一个有向图，若略去所有有向边的方向所得到的无向图是一棵树，则称之为有向树。

一颗非平凡的有向树，如果恰有一个结点的入度为0，其余所有结点的入度均为1，则称之为根树或外向树。入度为0的结点称为根(root)；出度为0的结点称为叶；入度为1，出度大于0的结点称为内点；内点和跟统称为分支点。在根树中，从根到任一结点v的通路长度，统称为结点v的层数；所有结点的层数中最大的称为根树的高。