离散数学及其~~学不会~~应用名词和知识点（随缘）

-1出分记录:

我哪扣分了??

不过不得不说,这个已经很不错了,和你惨不忍睹的高数数电什么的比起来

1.数理逻辑

1.1 命题逻辑

命题：一个非真即假的陈述句

命题变量：p，q，r…

复合命题：由逻辑联结词（否定（一元运算），合取，析取，蕴含，双条件，异或，同或，与非，或非，条件否定）和其他命题构成

蕴含p->q的表述方式：

p是q的充分条件
q是p的必要条件
q除非¬p

命题（p->q），逆命题（q->p)，否命题（¬p->¬q），逆否命题（¬q->¬p）

双条件：p↔q=(p→q)∧(q→p) 当且仅当充分必要条件

真值表行数：命题变量为n，则有2^n行

等价命题：若两个命题真值完全相同，则命题等价

证明命题不等价：说明有一种情况真值不相同

1.2 命题翻译

翻译语句：个人理解，满足所有命题条件时，语句的真值为真

系统规范：基于逻辑的精确规范语言

系统规范一致：若能够给命题变量赋真值，使每个命题为真，那么这些命题是一致的/存在真值指派使所有语句为真

逻辑难题：假设，假设

逻辑电路：热风冰

1.3 命题等价

永真式（重言式）：真值永远为真

永假式（矛盾式）：真值永远为假

可满足式：可能真，也可能假

逻辑等价：等价命题：若两个命题真值完全相同，则命题等价（？）

¬p∨q≡p->q

证明xx式子逻辑等价

德摩根定律：不想打了hh

逻辑等价式：一大堆，背不过，会用就行

结合律，合取和析取都满足，(p∧q)∧r==p∧(q∧r)

分配律，合取和析取都可以分配

等价性证明：用逻辑等价式推导一个到另一个

最小联结词组：功能完备且最小

与非(↑)，或非(↓)

1.4 谓词逻辑

命题内部的逻辑结构研究，对原子命题进一步分解

谓词：将描述客体的谓语部分单独分离出来，表达具有相同性质的一类命题（但本身不是一个命题）

一元谓词：只有一个客体，A(x)

二元、三元…：有2/3/…个客体 B(x,y)

n元命题函数：由一个谓词，n个客体变元组成的表达式，又称简单命题函数或原子谓词公式

三元命题函数 L(x,y,z)

个体域：客体变元的论述/取值范围

全总个体域：一切可以做客体的对象的集合

量词：全称量词&存在量词

命题函数成为命题：用具体客体取代客体变元；用量词量化客体变元

谓词演算的合式公式：一堆谓词公式组合起来，简称谓词公式

1.5 变元的约束

约束变元：量词后面跟的x叫做量词的指导变元/作用变元/约束变元（对于任意x，…）

自由变元：除约束变元外的变元，没有被量词限定范围的变元

约束变元换名：根据作用域，若x换z则作用域内所有x都换

自由变元换名：若自由变元x换z则所有自由变元x都换（若有约束变元x，不能换）

蕴含式：⇒

等价式：⇔

逻辑等价式推广到谓词逻辑中可用

量词否定：¬(∀x)P(x)==(∃x)¬P(x) ¬(∃x)P(x)==(∀x)¬P(x)

量词作用域的扩张与收缩：

作用域可以扩张到包含自由变元
(∀x)(A(x)->B)==((∃x)A(x)->B) 可以证明，主要是条件这个符号比较奇妙
(B->(∀x)A(x))==(∃x)(B->A(x))
量词的分配律：
1. 全称量词对合取满足分配律，对析取不满足！
2. 存在量词对析取满足分配律，对合取不满足！

析取范式：若命题公式由n个析取组成，其中每个析取由(1,…,m)个原子公式的合取或原子公式的否定组成，则它是析取范式

合取范式：若命题公式由n个合取组成，其中每个析取由(1,…,m)个原子公式的析取或原子公式的否定组成，则它是合取范式

主析取范式：（最小项之和）

主合取范式：（最大项之和）

前束范式：若量词均在一个命题公式的开头，且作用域为整个命题公式，该公式称为前束范式

化为前束范式方法：

去掉条件和双条件，换为与或非；换名和代入变量
否定符号深入到命题变元和谓词之前
扩张任意存在量词

1.6 谓词演算的推理理论

P：已知条件

T：前面已经证明的结论

US(Universal Specification)全称指定规则：指定对某个任意客体成立

UG(Universal Generalization)全称推广规则：对于任意客体都成立，可以推广到全部

ES(Existential Specification)存在指定规则：指定对某个客体成立，一般先于US使用

EG(Existential Generalization)存在推广规则：对一个客体成立，可以推广到存在

CP：神奇的东西

要证P⇒(Q->R)，可以转换为证明P∧Q⇒R

证不出来：丢人，万能的真值表

2. 集合论

2.1 集合

集合：一组无序对象的合集 set 集合可以嵌套集合

元素/成员：集合中的对象

描述方法：枚举法,描述法

常用集合：N,N+,Z,Z+,R,R+,C(复数集),Q

区间符号 [] ()

全集：U

空集：Ø

集合相等 A=B：当且仅当两个集合具有相同的元素 ∀x(x∈A<->x∈B)

子集 A⊆B：当且仅当A中每个元素也是B中元素 ∀x(x∈A->x∈B)

平凡子集：集合自身和空集，因为每个集合都有这两种子集

真子集 A⊆B且A≠B

集合基数 |A|：A的不同的元素个数

|Ø|=0；

|{Ø}|=1；

集合的后继：

(A+)=A∪{A}={A,{A}}

(Ø+)=Ø∪{Ø}={Ø}

((Ø+)+)={Ø}∪={Ø,{Ø}}

可以嵌套

幂集P(A)：集合A的所有子集的集合

A={a,b} P(A)={Ø,{a},{b},{a,b}}

若一个集合基数为n，则幂集的基数为2^n

多元组 n元组：例如G={V,E} 二元组

笛卡尔积：AxB={(a,b)|a∈A∧b∈B}

笛卡尔积的子集R称为从集合A到集合B的关系

AxBxC=(a,b,c) 三元组

(AxB)xC=((a,b),c) 二元组

量词的真值集：使P(A)为真的元素的集合

2.2 集合运算

交集

并集

补集

差集 A-B=A∩(not B)：包含A中不属于B的元素的集合

对称差集 A⊕B=(A-B)∪(B-A)：仅属于A和仅属于B

满足逻辑运算

证明集合相等：

1. 证明第一个是第二个的子集，且第二个也是第一个的子集
2. 使用集合运算，逻辑运算
3. 真值表yyds

集合的计算机表示：

U={0,1,2,3,4,5} A={1,2,3}

A可以用位串表示为：011100

运算可以用位运算

2.3 函数

函数/映射/变换：A,B为非空集，从A到B的函数，表示为f:A->B，是A中每一个元素对B中相应元素的指派

若b是B由函数f指派给A的元素a的唯一元素，则写作f(a)=b

可以多对一，但不能一对多

A：f的定义域

B：f的陪域

a：b的原像

b：a（在f下）的像

单射函数：一对一

满射函数：B中每个元素都能在A中找到它的原像，称为满射或映上的

双射函数：满足单射和满射，亦称一一对应，集合等势

反函数：双射函数才有反函数；f-1(b)=a iff f(a)=b

复合函数：g: A->B, f: B->C 则fog(x)=f(g(x))

2.4 序列和求和

序列：从整数集合的子集到集合S的函数

emmmmmm？

等差序列

等比序列

字符串：是有限集合（字母表）中的有限字符序列

空串用λ表示（类似ASCII中\0)，长度为0
abcde的长度为5

递归关系

斐波那契数列

迭代法

求和

直积

等比级数（？好家伙）

2.5 集合的基数

当且仅当AB之间存在双射关系/一一对应/等势时，满足|A|=|B|

若AB间存在单射，则|A|<=|B|

可数集：A的每个元素都能与自然数集N的每个元素之间建立一一对应的集合

是“可以计数”的：尽管计数可能永远无法终止，集合中每一个特定的元素都将对应一个自然数

当无限集可数时，用aleph0表示集合的基数

希尔伯特旅馆悖论

这一问题虽然被称作“悖论”，但事实上它并不矛盾，而仅仅是与我们直觉相悖而已。在有无限个房间时，“每个房间都客满”与“无法入住新的客人”两者其实并不等价。

无限集合的性质与有限集合的性质并不相同。对于拥有有限个房间的旅馆，其奇数号房间的数量显然总是小于其房间总数的。然而，在希尔伯特所假想的这一旅馆中，奇数号房间数与总房间数是相同的。在数学上可以表述为包含所有房间的集合的势与包含所有奇数号房间的子集的势相同。事实上，无限集合都拥有这样的特点，所有无限集合都与它的某些子集的势相同。对于可数集，其势记为（阿列夫零）

另外，我们还可以说，对于任意可数无限集，都存在由这一集合至自然数集的双射，即便这一集合（如有理数集）本身就包含了自然数集。

2.6 矩阵

matrix 建议复习线代

矩阵转置

对称

0-1矩阵

0-1矩阵的并和交

0-1矩阵的布尔积

0-1矩阵的布尔幂

其实就和普通矩阵乘法一样。。。

9. 关系

~~345678被吃掉了（悲）~~

二元关系：A B是集合，一个从A到B的二元关系是AxB的子集。

0Ra 表示（0，a）∈R

集合上的二元关系：R是AxA的子集或从A到A的关系

集合上关系个数/A子集的个数：2^|A|^2

自反关系：对于每个元素a∈A有（a，a）∈R

矩阵：对角线上所有元素都有定义

图：都有自环

反自反关系：对于每个元素a∈A有（a，a）∈/R（不属于）

矩阵：对角线上所有元素都无定义

图：都无自环

*两种关系并非完全对立，例如对角线上 010 既不是自反，也不是反自反

对称关系：对于任意a，b∈R，只要(a，b)∈R就有(b，a)∈R

矩阵：对称矩阵，对应位置要么全0要么全1

图：两点间若有边，则一定为双向边（2条）

反对称关系：对于任意a，b∈R，只要(a，b)∈R就有(b，a)∈/R（不属于）

矩阵：若一边为1，则另一边一定为0

图：两点间若有边，一定为单向边

*并非完全对立，如

1 0 0

0 1 0

0 0 1 既对称又反对称

1 1 1

0 1 1

1 0 1 既不对称又不反对称

传递关系：若（a，b）∈R,（b，c）∈R，则（a，c）∈R

矩阵：用幂求？

图：构成一个神奇的三角形…

若a=c，是满足传递性的

若a=b=c，也是

*证明某些关系（整除，

关系的组合：使用基本集合操作，R1∩R2 等等

合成：类似复合函数，R2oR1

关系的幂：R^n+1=R^n o R

矩阵表示关系：A={123}, B={12}

R={(2,1)}，2与1有关，表示为1；其他为0

0 0

1 0

0 0

矩阵求关系的幂：矩阵相乘

图表示关系：应该还会

用图求关系的幂：若在R中存在从x到y长度为n的路径，则(x,y)在R^n中

关系的闭包

关系的闭包运算：

自反闭包r(R)：把不在R中的所有（a，a）加到关系R中

对称闭包s(R)：所有（a，b）加到关系R中 R∪R-1是关系R的对称闭包

传递闭包t(R)：含有n个元素的关系的n次幂复合用矩阵和图如何计算

矩阵：矩阵M^1+M^2+。。。。

图：用图求关系的幂：若在R中存在从x到y长度为n的路径，则(x,y)在R^n中

当然也可以玄学画图，毕竟咱们人力比较智能

？等价关系

等价关系：同时满足自反、对称、传递

*证明某个关系是等价关系

模M同余，整除…

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

三个命题等价：aRb，[a]=[b]，[a]∩[b]≠Ø

集合的划分：等价类构成A的划分，所有等价类的并集就是集合A

划分的性质：

Ai≠Ø；Ai∩Aj=Ø；ΣAi=S

一个n元素集合可以构成多少个划分？

n元素集合有多少种不同的方法划分成两块？**(2^n-2)/2种**

相容关系

自反、对称

关系图：每个节点都有自环；若有边则为双向边

最大相容类：设A是一个相容关系，C是A的子集，若：1.对于任意a，b∈C，aAb；2.对任意x∈A-C，在C中至少存在一个元素c，使xA/c（x和c之间没有关系），则C是相容关系A的最大相容类

求最大相容类：用关系图，每一个能构成完全图的最大结点集合就是一个最大相容类

完全覆盖：A的所有最大相容类的集合就A的一个完全覆盖

已知覆盖求相容关系：每一个集合求笛卡尔积

覆盖：一个集合A拆分成许多子集，子集的并等于A，就是一个覆盖；

划分：要求这些子集没有交集

偏序

偏序关系：同时满足自反、反对称、传递

表示序关系的符号：≼，由于≤关系是偏序关系的范例

≺，满足a≼b，但a≠b（满足反自反，反对称，传递的严格偏序关系）

可比性：偏序（S，≼），若a≼b或b≼a，则称a和b是可比的；

不可比：当a和b都是S中的元素且既没有a≼b，也没有b≼a，则a和b是不可比的

全序集/线序集/链：S中每对？？（任意两个）元素都是可比的，≼称为全序/线序

良序集：若S是全序，并且S的每个非空子集都有一个最小元素

举例：（Z，≥）全序，不是良序因为没有最小元素

（Z+，≤）全序良序，最小元是1

字典顺序：先比较前面的元素大小，再看后面的

哈塞图（Hasse）：省略了由于自反性和传递性而必须出现的边

最小元素放在最下面，原来存在的箭头应该全部向上

全序的哈塞图是一条链

n元素集合能定义n！个全序关系

对于集合A：

极大元：没有比极大元a还大的元素（不存在a≼N）

极小元：没有比极小元b还小的元素（不存在N≼b）

最大元：对于集合中任意元素x，均有x≼a

最小元：对于集合中任意元素x，均有b≼x

引理：每个有穷非空偏序集（S,≼）至少有一个极小元

*极大元是哈塞图最顶层元素，极小元是哈塞图最底层元素；

最大元当且仅当最顶层元素只有一个时存在，最小元同理；

不同的极大元之间不可比，它们处在哈塞图的同一层次

对于集合A的一个子集B：

若存在a∈A，对于B中任意元素x满足

上界：x≼a

下界：a≼x

上确界/最小上界：若a是B的上界，且对B的任意上界a’有a≼a‘

下确界/最大下界：若a是B的下界，且对B的任意上界a’有a’≼a

*集合可能没有上下界，若有，可能在B中，也可能在B外；

若有上下确界，则一定唯一；

若是B的最大元/最小元，则它必是B的上/下确界

拓扑排序：从一个偏序构造一个相容的全序叫做拓扑排序

相容的：如果只要aRb就有a≼b，则称一个全序≼与偏序R是相容的。

引理：每个有穷非空偏序集（S,≼）至少有一个极小元

∴递归的在集合A中选择A的极小元

a≺b≺c≺d

逆关系

R^-1={(b,a)|(a,b)∈R}

当(R)^-1==R时，R是对称的

10. 图

10.1基本概念

图由点和边构成

无向边-无向图

有向边-有向图

混合图

邻接点：由一条边关联的两个点

邻接边：由一个点关联的两条边

自环：一个点关联的一条边

关联：点和边之间有关系

邻接：点和点，边和边之间的关系

孤立结点：不与任何结点邻接的结点

悬挂点：度数为1的顶点

零图：若干孤立点组成的图（没有边）

平凡图：只有一个孤立点构成的图

度数：与结点v关联的边数 degv

Δ(G)：最大度

δ(G)：最小度

度序列：图的各个顶点度数按照非递增顺序排列的序列

握手定理：Σdegv=2|E| 结点数之和等于边数两倍

推论：图中度数为奇数的结点数目一定为偶数

入度：

出度：

有向图结点度数=入度+出度

Σ入度=Σ出度

平行边：连接同一对结点的多条边

多重图：含平行边的图

伪图：含平行边和自环的图

简单图：不含平行边和自环的图

完全图Kn：每对结点之间都有边相连，边数n(n-1)/2

二分图Cn：边数n^2

有向完全图：完全图每条边确定一个方向

补图：G中所有节点和所有能使G成为完全图的添加边组成的图

子图：G‘={V’,E’}，V’ E’是V E的子集

生成子图：G’包含G的所有节点时

真子图：G‘不包含G的所有节点时

同构：两个图的结点和边分别存在一一对应，且保持关联关系

同构的必要条件：v e相等；结点度数对应相等

10.2路与回路

路：点边交替序列v0e1v1e2v2…envn称为从v0到vn的路

起点：v0

终点：vn

路的长度：边的数目n

回路：当v0=vn时，构成一个回路

迹：所有边均不相同的路

通路：所有顶点均不相同的路

圈：闭的通路？？

简单图的路可以用结点序列表示

有向图中，结点数大于一的路可以用边序列表示

定理1：n顶点图中若vi到vj存在路，则这条路的长度必<=n-1

连通：无向图中顶点u，v之间存在路，则称u和v是连通的

顶点之间的连通性是V上的等价关系

连通分支：若V1,V2…Vn是图结点集V的一个划分，则G(V1),G(V2),…,G(Vn)都是图的连通分支

连通分支的数目：W(G)

连通图：只有一个连通分支的图

删除结点：点和点关联的边都删去

删除边：仅删除边

点割集：删除这一点割集中的所有结点，图不连通；删除这一点割集的任意真子集，图连通

割点：一个点构成的点割集

割点充要条件：存在两个结点u和w，使u和w的每一条路都通过v

点连通度k(G)：最小删除的点的数目

不连通图的k(G)=0；

有割点的连通图的连通度=1；

完全图Kn的点连通度=n-1

边割集：

割边/桥：

边连通度λ(G)：最小删除边的数目

k(G)<=λ(G)<=δ(G)

可达：有向图中，若u到v之间存在一条路，称从u可达v

d<u,v>：u和v之间最短路

图的直径：maxd<u,v>

弱连通：略去边的方向后，若该无向图连通，则该有向图为弱连通

单侧连通：若任意一对结点之间至少有一个结点到另一个结点是可达的

强连通：任意两个结点之间是相互可达的

强连通：当且仅当G中有一个回路至少包含每个结点一次

强连通分支/强分图：有向图G的子图是强连通的，但不包含在更大的强连通子图中（具有强连通性质的最大子图）

单侧分图：

弱分图：

强分图中，每个结点位于且仅位于一个强分图中

10.3图的矩阵表示

邻接矩阵：aij=1 vi邻接vj

有向图中，vi->vj；行–入度；列–出度

计算vi到vj长度为x的路的数目：矩阵记为A，数目=A^x中元素aij

可达性矩阵：pij=1 vi到vj至少存在一条路

是邻接矩阵A+A^2+A^3+…+A^n得到后把所有不为0的数改为1

也可以邻接矩阵全用01（布尔矩阵）

关联矩阵：

mij=1 vi是ej的起点（无向图中，vi与ej关联）

mij=-1 vi是ej的终点（无向图没有-1项）

10.4 欧拉欧拉欧拉

欧拉路

欧拉路：连通图G，经过图G每条边一次且仅一次的路称为欧拉路；。。。。。。且仅一次的回路称为欧拉回路

欧拉图：具有欧拉回路的图

欧拉（？）定理：无向图G具有一条欧拉路，当且仅当G连通且有0个或2个奇数度的顶点

推论：无向图G具有一条欧拉回路，当且仅当每个结点度数均为偶数

单向欧拉路：通过G中每边一次且仅一次的单向路；。。。。。。单向欧拉回路

定理2：有向图具有单向欧拉回路，当且仅当G连通且每个结点的入度=出度

汉密尔顿回路

连通图G，经过图G每个结点一次且仅一次的路称为汉密尔顿路；。。。。。回路。。。

汉密尔顿图：具有汉密尔顿回路的图

定理：必要条件：G有汉密尔顿回路，对结点集V的每个非空子集S有：W(G-S)<=|S|

去掉s个结点后的连通分支数小于等于去掉的点的数量

?书上没有

狄拉克定理：若G是有n个顶点的简单图，且n>=3，G中每个顶点的度数至少为n/2，则G有汉密尔顿回路

欧尔定理：若G是有n个顶点的简单图，且n>=3，对于G中每一对不相邻的顶点u，v，都有degu+degv>=n，则G有汉密尔顿回路

汉密尔顿路：每对顶点度数之和>=n-1，则有汉密尔顿路

三个充分条件

反例：C5(圈图)存在汉密尔顿回路，但并不满足以上两个定理的条件

二度结点：度数为2的结点

10.5 平面图

平面图：若能将无向图G的所有结点和边画在一个平面上，使任何两条边除了端点外没有其他交点，则G是一个平面图

面r：G是连通平面图，若G的边所围成区域内没有图的结点也没有图的边，则称这一区域为面

面的边界：包围该面的边所构成的回路

面的次数degr：面的边界的回路长度

定理1：有限平面图，Σdegr=2|E|

欧拉定理(2)：连通平面图G有 v点e边r面，则欧拉公式v-e+r=2成立

定理3：连通简单平面图G有v点e边，若v>=3，则e<=3v-6

三个定理都是必要条件，可用于判定某些图不是平面图

在二度结点内同构：G1和G2同构，反复插入或删除度数为2的结点也同构

平面图充要条件：当且仅当它不包含与K3,3或K5在二度结点内同构的子图

10.6 对偶图和图的着色

对偶图：一个面抽象成一个点，两面之间的公共边连接这两个面抽象成的点，当且仅当一条边是一个面的边界时，存在一个自环，和这条边相交

连通平面图的对偶图是平面图

自对偶图：对偶图G*与G同构

图的着色：对任意平面图，不存在两个邻接点有同一种颜色

四色定理：平面图的着色数不超过4

10.7最短路

背！

procedure Dijkstra a-z的最短路 O(n^2)

L(vi) 从a到vi的路径长度，w(vi,vj) 从vi到vj的权值

for i := 1 to n

L(vi) := ∞

L(a) := 0

S := Ø

{初始化标记，使起始点a标记为0，其他为∞，S为空集}

while z∈/S

u := a

S := S∪{u}

for 所有不属于S的顶点v

if L(u)+w(u,v)<L(v) then L(v) := L(u)+w(u,v)

return L(z)

procedure Floyd O(n^3)

for i := 1 to n

for j := 1 to n

d(vi,vj) := w(vi,vj)

for i := 1 to n

for j := 1 to n

for k := 1 to n

if d(vj,vi)+d(vi,vk)<d(vj,vk)

then d(vj,vi)+d(vi,vk)=d(vj,vk)

return d(vi,vj) {返回从i到j的最短路}

Havel 定理

可简单图化充要条件：递归删除最大度的结点（度数x），并把接下去x个顶点度数-1，最后没有负数度结点

11. 树

11.1 生成树

树：一个连通且无回路的无向图

树叶：度数为1的结点

分支点/内点：度数>1的结点

森林：多个无回路的无向图，它的每个连通分图使树

关于树的定义等价：

无回路的连通图

e=v-1

增加一条新边，得到一个且仅一个回路

删除任意一边后不连通

任意两结点之间有且仅有一条路

任意一棵树中至少有2片树叶

证明：设T=<V,E>,|V|=n

T是连通图，所以deg(v)>=1且Σdeg(v)=2e=2(n-1)=2n-2

若没有两片树叶，则所有结点度数均大于等于2，此时Σdegv>=2n，与上式矛盾；

若有一片树叶，其他结点度数均大于等于2，则Σdegv>=1+2(n-1)=2n-1，与上式矛盾；

故T中至少有2片树叶，满足Σdegv=2n-2.

生成树：若图G的生成子图是一棵树，则该树为G的生成树

树枝：生成树T的边

弦：G的不在T中的边

生成树的补：所有弦的集合

定理：连通图至少有一棵生成树

秩：使G变为生成树所需删除的边数

定理：一条回路和任何一棵生成树的补至少有一条公共边

定理：一个边割集和任何生成树至少有一条公共边

带权生成树

边权：W(e) 边带有权值

树权：生成树T的所有边权之和C(T)

最小生成树：所有生成树中树权最小的一棵

procedure Kruskal

T := 空图

for i := 1 to n-1

e := G中权最小的任一边，且添加到T中不形成简单回路

T := T添加e

return T

11.2 根树及其应用

根树：有向图中一个结点入度为0，其余所有结点入度为1

m叉树：每个结点的出度≤m

完全m叉树：每个结点出度恰好等于m或0

正则m叉树：所有树叶层次相同

二叉树：任何一棵有序树均可改写成一棵二叉树（但是存储比较浪费）

定理：完全m叉树，树叶为t，分支点为i，则有mi+1=i+t

分支点儿子的总数为mi，再加上树根mi+1=所有结点数

分支点+树叶=所有结点数

通路长度：从树根到此结点的边的数目

内部通路长度：从树根到分支点

外部通路长度：从树根到树叶

定理：Σ内部通路长度=I；外部=E，n为分支点数，则E=I+2n

二叉树应用：

1. 最优树

这里是树叶带有权值wi；L(wi)是通路长度

带权二叉树：w(T)=ΣwiL(wi)

最优树：在所有带权二叉树中，w(T)最小的一棵

构造最优树：权值从小到大排列，权值最小的两树叶w1，w2是兄弟；新的分支点权值为w1+w2；递归构造

2. 前缀码

哈夫曼编码-最优编码

左边大数，编码0；右边小数，编码1

11.3树的遍历

1. 前序遍历

根->左子树->右子树

2. 中序遍历

左子树->根->右子树

3. 后序遍历

左子树->右子树->根

前缀，中缀，后缀记法

前缀表达式：从右向左，用右边的运算对象执行运算

中缀：正常算式

后缀：从左向右，用左边的运算对象执行运算

12. 格与布尔代数

格

格：在偏序集中，任意两个元素都有上/下确界

设<L,≼>是一个格，∧∨分别为L的交和并运算，则称代数系统<L,∧.∨>为由格所诱导的代数系统

格对偶原理：若将≤换为≥，<L,≤>与<L,≥>相互对偶

格的性质

保序性

满足幂等律

交换律

结合律

吸收律

格同态

格同构

分配格：满足分配律的格

若<L,≤>是全序集，则是分配格

模格

有界格：定义全上界、全下界，相应于偏序集中的最大元、最小元，若格既有全上界又有全下界，就是有界格对任意元素都有最大元最小元称最大元1 最小元0

补元：L中若a交b=0，a并b=1，b是a的补元

有补格：若有界格中每个元素都至少有一个补元，则称为有补格

若L是有补分配格，则补元唯一

布尔代数

积之和表达式：最小项

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

布尔表达式：由布尔常元和布尔变元构成的使用代数系统运算的表达式

布尔函数不同的主析取范式有|B|^2^n个

函数主析取范式有|B|^|B|^n个

计算模型

文法

有限状态机

M=(S,I,O,f,g,s0)

S：有限状态集

I：有限输入字母表

O：有限输出字母表

f：转移函数

g：输出函数，为每个状态和输入对指派一个输出

s0：初始状态

图灵机

T=(S,I,f,s0)

S：有限状态集

I：包含空白符B的字母表

f：从SxI到SxIx{R,L}的部分函数

s0：初始状态

带：两端都是无限的，在任何时刻其上都只有有限多个非空白符

控制器：在带上移动，有一个读写头

T(si,a,sj,b,R/L)若此时状态为(si,a)

进入状态sj
在当前方格中擦去a，写上符号b
若d=R，向右移动一格，若d=L，向左移动一格

若部分函数在(s,a)中没有定义，则图灵机T停机

在运行开始时假设图灵机处于初始状态s0，且处于带上最左边的非空白符上

如果带上都是空白符，则控制头可以处于任何方格上

控制头在开始时所处位置称为该机器的初始位置

-1出分记录:

1.数理逻辑

1.1 命题逻辑

1.2 命题翻译

系统规范一致：若能够给命题变量赋真值，使每个命题为真，那么这些命题是一致的/存在真值指派使所有语句为真

1.3 命题等价

逻辑等价：等价命题：若两个命题真值完全相同，则命题等价（？）

德摩根定律：不想打了hh

1.4 谓词逻辑

谓词：将描述客体的谓语部分单独分离出来，表达具有相同性质的一类命题（但本身不是一个命题）

量词：全称量词&存在量词

1.5 变元的约束

量词作用域的扩张与收缩：

量词的分配律：

析取范式：若命题公式由n个析取组成，其中每个析取由(1,…,m)个原子公式的合取或原子公式的否定组成，则它是析取范式

合取范式：若命题公式由n个合取组成，其中每个析取由(1,…,m)个原子公式的析取或原子公式的否定组成，则它是合取范式

主析取范式：（最小项之和）

主合取范式：（最大项之和）

前束范式：若量词均在一个命题公式的开头，且作用域为整个命题公式，该公式称为前束范式

化为前束范式方法：

1.6 谓词演算的推理理论

CP：神奇的东西

2. 集合论

2.1 集合

集合基数 |A|：A的不同的元素个数

幂集P(A)：集合A的所有子集的集合

笛卡尔积：AxB={(a,b)|a∈A∧b∈B}

2.2 集合运算

2.3 函数

单射函数：一对一

满射函数：B中每个元素都能在A中找到它的原像，称为满射或映上的

双射函数：满足单射和满射，亦称一一对应，集合等势

2.4 序列和求和

2.5 集合的基数

2.6 矩阵

9. 关系

自反关系：对于每个元素a∈A有（a，a）∈R

反自反关系：对于每个元素a∈A有（a，a）∈/R（不属于）

对称关系：对于任意a，b∈R，只要(a，b)∈R就有(b，a)∈R

反对称关系：对于任意a，b∈R，只要(a，b)∈R就有(b，a)∈/R（不属于）

传递关系：若（a，b）∈R,（b，c）∈R，则（a，c）∈R

关系的闭包

自反闭包r(R)：把不在R中的所有（a，a）加到关系R中

对称闭包s(R)：所有（a，b）加到关系R中 R∪R-1是关系R的对称闭包

传递闭包t(R)：含有n个元素的关系的n次幂复合 用矩阵和图如何计算

？等价关系

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

集合的划分：等价类构成A的划分，所有等价类的并集就是集合A

划分的性质：

相容关系

最大相容类：设A是一个相容关系，C是A的子集，若：1.对于任意a，b∈C，aAb；2.对任意x∈A-C，在C中至少存在一个元素c，使xA/c（x和c之间没有关系），则C是相容关系A的最大相容类

完全覆盖：A的所有最大相容类的集合就A的一个完全覆盖

偏序

偏序关系：同时满足自反、反对称、传递

全序集/线序集/链：S中每对？？（任意两个）元素都是可比的，≼称为全序/线序

良序集：若S是全序，并且S的每个非空子集都有一个最小元素

哈塞图（Hasse）：省略了由于自反性和传递性而必须出现的边

极大元：没有比极大元a还大的元素（不存在a≼N）

极小元：没有比极小元b还小的元素（不存在N≼b）

最大元：对于集合中任意元素x，均有x≼a

最小元：对于集合中任意元素x，均有b≼x

上界：x≼a

下界：a≼x

上确界/最小上界：若a是B的上界，且对B的任意上界a’有a≼a‘

下确界/最大下界：若a是B的下界，且对B的任意上界a’有a’≼a

拓扑排序：从一个偏序构造一个相容的全序叫做拓扑排序

逆关系

10. 图

10.1基本概念

10.2路与回路

定理1：n顶点图中若vi到vj存在路，则这条路的长度必<=n-1

k(G)<=λ(G)<=δ(G)

强连通：当且仅当G中有一个回路至少包含每个结点一次

10.3图的矩阵表示

邻接矩阵：aij=1 vi邻接vj

可达性矩阵：pij=1 vi到vj至少存在一条路

关联矩阵：

10.4 欧拉欧拉欧拉

欧拉路

欧拉（？）定理：无向图G具有一条欧拉路，当且仅当G连通且有0个或2个奇数度的顶点

传递闭包t(R)：含有n个元素的关系的n次幂复合用矩阵和图如何计算