离散数学及其应用课程复习KennethH.Rosen

2023年12月16日发(作者：初中语文数学试卷评语)

离散数学及其应用课程复习

离散数学及其应用课程笔记

MiracleZero

文章目录

chap1 The Foundations: Logic and Proofs

英文

proposition

predicate

inference

中文

命题

谓词

推理

合取ANDKaTeX parse error: Undefined control sequence: and at position

1: and

异或XOR

⊕

IF AND ONLY IF

↔

前件

结论

逆

反

骑士

永真式

可能式

对偶式

与非$

析取范式

子句

全称量词

∀

英文

equivalence

quantifier

negation

中文

等价式

量词

否定NOT

¬

析取OR

∨

IF-THEN

→

假设

前提

后件

逆否

逐位

无赖

矛盾式

范式

或非

↓

satisfiable

合取范式

论域

存在量词

∃

唯一性量词

conjunctionDisjunction

Exclusive or

Biconditional

antecedent

conclusion

converse

inverse

knight

Tautologies

Contingencies

Dual

Sheffer stroke

DNF

clause

Implication

hypothesis

premise

consequence

contrapositive

bitwise

knave

Contradictions

Normal Forms

Pierce arrow

$

CNF

domain

Existential

Quantifier

Uniqueness

Quantifier

nested

proof

axioms

corollary

trivial

rational number

Universal Quantifier

counterexample反例

∃!

嵌套的

证明

公理

推论

平凡证明

有理数

scope

argument

theorem

lemma

（变量的）作用域

论证

定理

引理

猜想

vacuous proof

without loss of

空证明

without loss of

英文

generality

不失一般性

中文英文中文

异或

p

T

T

F

F

q

T

F

T

F

p⊕q

F

T

T

F

IF p THEN q

p implies q

p only if q=q if p

q when p

q whenever p

q follows from p

p is sufficient for q 充分

q is necessary for p 必要

q unless

¬

p

逆、逆否、反

符号含义

is the **converse **of

p

定义

q→p

¬q→¬p

¬p→¬q

优先级

operator

→q

→q

逆(左右颠倒)

逆否(与原命题等价)

反

is the contrapositive of

p

is the inverse of

p→q

precedence

1

2

3

4

5

¬

∧

∨

→

↔

对偶式

S=(p∨¬q)∧r∧T

S

∗

=

(p∧¬q)∨r∨F

即所有and变成or，所有or变成and，所有T变成F，所有F变成T

s⇔t

if and only if

s

∗

⇔t

∗

功能完备符号：

{¬,∨}

、

{¬,∧}

、

{∣}

、

{↓}

析取DNF范式：

(A

1

∧A

2

)∨B

1

∨(C

1

∧C

2

)

合取CNF范式：

(A

1

∨A

2

)∧B

1

∧(C

1

∨C

2

)

量词优先级比逻辑运算符更高

命题中的变量必须是Bound variable（被赋值的或被量词约束的）

corresponding tautology

Modus Ponens

Modus Tollens

Hypothetical Syllogism

Disjunctive Syllogism

Addition

Simplification

Conjunction

Resolution

假言推理

取拒式

假言三段论

析取三段论

附加律

简化律

合取律

消解律

(p∧(p→q))→q

(¬q∧(p→q))→¬p

((p→q)∧(q→r))→(p→r)

(¬p∧(p∨q))→q

p→(p∨q)

(p∧q)→p

KaTeX parse error: Undefined control sequence: and at position 5: ((p)and(q))rightarrow…

((¬p∨r)∧(p∨q))→(r∨q)

平凡证明：

p→T

is

T

空证明：

F→q

is

T

chap2 Basic Structures: Sets, Functions, Sequences, Sums, and Matrices

英文

Sequences

Cardinality

Power Set

Cartesian Product

intersection

Inclusion-Exclusion

Domain

Image

Injection

Bijection

progression

lexicographic

中文

序列

基数

幂集

笛卡尔积

集合的交

∩

容斥原理

定义域

像

单射

双射

级数

字典序

英文

Summation

paradox

tuple

union

complement

symmetric difference

Codomain

Preimage

Surjection

Inverse Function

Recurrence Relations

computable

中文

求和

悖论

有序元组

集合的并

∪

ˉ

集合的补

A

对称差

陪域、值域

原像

满射

反函数

递推关系

可计算的

rectangular

英文

transpose

矩形的

中文

转置

identity matrix

英文

symmetric

单位矩阵

中文

对称的

集合的基数记为

∣A∣

，即集合中元素的个数

幂集

P(A)

：集合中所有子集组成的集合，一个n个元素的集合的幂集有

2

n

个元素

两个元素的元组被称为ordered pairs序偶

笛卡尔积：

A×B={(a,b)∣a∈A∧b∈B}

对称差：

A⊕B=(A−B)∪(B−A)

反函数的前提是原函数是双射的

f∘g(x)=f(g(x))

n!∼

2πn

(

e

)

n

n

SumClosed Form

ar

n+1

−a

r−1

,r

n(n+1)

2

n(n+1)(n+2)

6

n

2

(n+1)

2

4

1

1−x

1

(1−x)

2

∑

k=0

ar

k

∑

k=1

k

∑

k=1

k

2

∑

k=1

k

3

∑

k=0

x

k

,∣x∣<

1

∑

k=1

kx

k−1

∞

∞

n

n

n

n

=1



可数集：基是有限的或跟正整数集相同，则是可数的

一个无限且可数的集合的基被称为

ℵ

0

（可以跟正整数集建立一个一一对应的映射）

实数集的基为

ℵ

1

一个集合的幂集的基，一定大于原集合的基

chap3 Algorithms

英文

Brute-Force

Intractable

中文

暴力算法

难解

英文

Tractable

polynomial

中文

易解

多项式

Notation

Big-O:

f(x)

is

O(g(x))

Big-Omega:

f(x)

is

Ω(g(x))

Big-Theta:

f(x)

is

Θ(g(x))

Explaination

∣f(x)∣≤C∣g(x)∣

∣f(x)∣≥C∣g(x)∣

O(g(x))&Ω(g(x))

NP类：可以在多项式复杂度内被check，但不能在多项式复杂度内解决

NP完全类：if you find a polynomial time algorithm for one member of the class, it can be used to solve all the problems

in the class

chap5 Induction and recursion

数学归纳法:

P(1)∧∀k(P(k)→P(k+1))→∀nP(n)

BASIC STEP:

INDUCTIVE STEP:

Hence,…

每个简单多边形都会把一个区域变为内部区域和外部区域

任何一个简单多边形都有其内部的对角线（lemma）

良序性（正整数体系的公理）：A set is well ordered if every subset has a least element.

数学归纳法和强归纳法与良序性的成立是等价的

chap6 Counting

英文

Pigeonhole

Combination

distinguishable

中文

鸽巢

组合

可分辨的

英文

Permutation

Binomial Coefficient

中文

排列

二项系数

排列：

P(n,r)=

(n−r)!

组合：

C(n,r)=

(n−r)!r!

n!

n!

二项式定理：

(x+y)

n

=

n

Σ

j=0

(

j

)

x

n−j

y

j

n

n

Σ

k=1

(−1)

k

(

k

)

n

=

0

n+1nn

帕斯卡定理：

(

k

)

=

(

k−1

)+(

k

)

m+nmn

r

Vandermonde’s：

(

r

)

=

Σ

k=0

(

r−k

)(

k

)

2n

n

2

n

推论：

(

n

)

=

Σ

k=0

(

k

)

有n种饼干，取出共r个饼干的组合数量为：

C(n+r−1,r)

n个物体，k个盒子：

n个物体

不同

相同

不同

相同

r个盒子

不同

不同

相同

相同

数量

n!

n

1

!n

2

!⋅⋅n

k

!

C(n+r−1,n−1)

–

–

chap8 Advanced Counting Techniques

英文

Homogeneous

generating function

Derangement

中文

齐次的

生成函数

错位排序

英文

Nonhomogeneous

Inclusion-Exclusion

中文

非齐次的

容斥原理

degree：

a

n

=a

n−1

+a

n−8

的degree为8

a recurrence relation of degree 8

Hanoi汉诺塔（3个柱子）：

H

n

=2

n

−

1

齐次：每个x都是1次方的

非齐次公式：

如果递推关系是为：

a

n

=c

1

a

n−1

+c

2

a

a−2

+⋅⋅⋅+c

k

a

n−k

+F(n)

非齐次项

F(n)

可以被记为

F(n)=(b

t

n

t

+b

t−1

n

t−1

+⋅⋅⋅+b

1

n+

b

0

)s

n

如果s是

a

n

=c

1

a

n−1

+c

2

a

a−2

+⋅⋅⋅+c

k

a

n−k

的一个根，m为次数，最后的特解可以被记为：

f(n)=n

m

(p

t

n

t

+

pn

t−1

+⋅⋅⋅+pn+p)s

n

p

t−1

n

t−1

+⋅⋅⋅+p

1

n+

p

0

)s

n

如果s不是是

a

n

=c

1

a

n−1

+c

2

a

a−2

+⋅⋅⋅+c

k

a

n−k

的一个根，最后的特解可以被记为：

f(n)=(p

t

n

t

+p

t−1

n

t−1

+⋅⋅⋅+p

1

n+

p

0

)s

n

例如

a

n

=6a

n−1

−9a

n−2

+F(n)

F(n)=(n

2

+

1)3

n

则$m=2, s=3, f(n)=n

2(p_2n

2+p_1n+p_0)3^n $（s=3为一个根）

a

n

=6a

n−1

−9a

n−2

+F(n)

F(n)=n

2

2

n

则$s=2, f(n)=(p_2n

2+p_1n+p_0)2

n $（s=2不是一个根）

分治算法复杂度：

f(n)=af(n/b)+cn

d

d

⎧

⎪

O(n)

⎨

O(n

d

logn)

⎪⎩

log

b

a

)

f(n) is

O(n

if

a

d

if

a=b

d

if

a>b

d

生成函数：

f(x)=Σ

k=0

a

k

x

k

,g(x)=

Σ

k=0

b

k

x

k

∞

∞∞

1.

f(x)+g(x)=Σ

k=0

(a

k

+b

k

)x

k

2.

α⋅f(x)=Σ

k=0

α⋅a

k

x

k

3.

x⋅f

′

(x)=

Σ

k=0

k⋅

a

k

x

k

4.

f(αx)=Σ

k=0

α

k

⋅a

k

x

k

5.

f(x)g(x)=Σ

k=0

(Σ

j=0

a

j

b

k−j

x

k

)

广义二项式定理：

∞

k

∞

∞

∞

u(u−1)⋅⋅⋅(u−k+1)/k!

if

k>0

u

if

k=0

(

k

)

=

{

1

u

∞

(1+x)

u

=Σ

k=0

(

k

)

x

k

例如

请找到

(1+x)

−n

的生成函数

(1+x)

−n

=

−n

Σ

k=0

(

−n

k

)

x

k

=Σ

−n

()x

=Σ

k=0

(−1)

k

C(n+k−1,k)x

k

n元素集合的错位排序个数：

D

n

=n![1−

1!

+

2!

−

3!

+⋅⋅⋅+(−1)

n

n!

]

1111

chap9 Relations

英文

properties

reflexive

antisymmetic

Composition

Equivalence

representive

partial ordering

lattices

chain

minimal

least element

中文

性质

自反的

反对称的

组合

等价

代表元

偏序

格

链

极小元

最小元

英文

closure

symmetric

transitive

diagonal

Congruence

partition

hasse diagram

total order/linear order

maximal

greatest element

compatible

中文

闭包

对称的

可传递的

对角线上

同余

划分

哈塞图

全序/线序

≼

极大元

最大元

兼容的

集合的性质

自反性Reflexive

(a,a)∈R

，

∀x[x∈U→(x,x)∈R]

空集上的空关系是自反的

对称性Symmetric

∀x∀y[(x,y)∈R→(y,x)∈R]

反对称性Antisymmetric

KaTeX parse error: Undefined control sequence: and at position 31: …ll y[(x,y)in Rand(y,x)in R to …

不存在除了自反之外的对称关系

传递性Transitive

KaTeX parse error: Undefined control sequence: and at position 42: … z [(x,y)in R and (y,z)in Rto (…

R

n

⊂R↔R is transitive

逆关系：

R

−1

=

{(a,b)∣(b,a)∈R}

关系操作：

(R∪S)

−1

=

R

−1

∪S

−1

(R∩S)

−1

=

R

−1

∩S

−1

(R)

−1

=

(R

−1

)

(A×B)

−1

=

B×A

transitive closure：

连通关系connectivity relation：

R

∗

=

∪

1

R

n

关系的传递闭包就是关系的连通关系

R

∗

=t(R)

等价关系：自反、对称且传递

∞

a b

R为集合A上的一个等价关系，则在集合A中与元素a相关的所有元素可以被表示为

[a]

R

（等价类）

[a]

R

={s∣(a,s)∈R}

代表元：等价类中的任何一个元素都可以被成为代表元

集合的划分：

pr(A)={A

i

∣i∈I}

R

1

、

R

2

为A上的两个等价关系，则

R

1

∪R

2

是A上的自反、对称关系，

(R

1

∪R

2

)

∗

是自反、对称、传递关系即等价关系

偏序关系：自反、传递、反对称（分大小的不平等关系）

poset(S,≼)

：定义在集合S上的一个偏序关系

如果集合中任意两个元素都是可比的，则成为全序、线序，整个集合被称为一个链

良序：拥有最小元素

极小（大）元：没有一个小于它

最小（大）元：所有元素都大于等于它

格：任意一对元素都拥有最大上界和最小下界的偏序集，被称为一个格

chap10 Graphs

英文

vertice

endpoint

pseudograph

incident

in degree

Bipartite

proper subgraph

path

articulation point

planer

Elementary subdivision

dual graph

中文

顶点

端点

伪图

关联

入度

二分图

真子图

通路

割点

平面图

初等细分

对偶图

英文

edge

multigraph

adjacent

pendant

out degree

regular graph

Isomorphism

connected component

Approximation algorithm

region

Homeomorphic

chromatic number

中文

边

多重图

相邻顶点

悬挂

出度

正规图

同构

连通部分

近似算法

区域

同胚

着色数

英文中文英文中文

G=(V,E)

无向图分类：

简单图：没有环，没有多重边

多重图：没有环，可以有多重边

伪图：可以有环和多重边

有关图的术语：

adjacent：两个顶点之间有边相连，则称这两个顶点相关联

incident with vertices u and v：这条边连接了顶点u和v

loop：环

degree of a vertex顶点的度：在无向图中即为有多少条边与这个点关联（环算两个度）

deg(v)=0

，v is isolated

deg(v)=1

，v is pendant

无向图中，

Σ

v∈V

deg(v)=2e

无向图中，偶数个顶点是奇数个度

有向图中，一条边的起点initial vertex，终点terminal vertex

Σ

v∈V

deg

+

(v)=Σ

v∈V

deg

−

(v)=

E

一些特殊的图：

完全图

K

n

：每对顶点之间有且只有一条边相连

圈图

C

n

：n个顶点围成一个圈首尾相连

轮图

W

n

：在圈图中间加个点

立方图

Q

n

完全二分图

K

mn

:两组集合中每个点都与对面任意一个点相连

正规图：每个顶点的度都相同

induced subgraph诱导子图：当且仅当子图中的边都在原图里，仅删除与子图中不存在的顶点相连的边

Incidence matrices关联矩阵：纵坐标为顶点，横坐标为边，针对无向图

path is simple：没有一条边被重复的通路

单个顶点的通路长度为0

图的连通：任意一对顶点间都有path

割点：关节点，删去后会增加connected components的个数

割边/桥：关节边，删去后会增加connected components的个数

任何一个强连通的有向图都是弱连通的，可以把弱连通看作无向图，而强连通指有向图每对顶点间都双向连通

strongly connected components/strong components：有向图中的最大强连接子图

欧拉回路：遍历所有的边，每条边只访问一遍

区别欧拉通路和欧拉回路：是否要求回到原点

欧拉图：包含欧拉回路的图

对于无向图：

欧拉回路充要条件：当且仅当每个顶点都是偶数个度

欧拉通路充要条件：当且仅当只有2个顶点是奇数个度

对于有向图

欧拉回路：弱连接+出度与入度相同

欧拉通路：弱连接+起点的出度多一个，终点的入度多一个

哈密尔顿问题：遍历所有点，每个点只访问一遍

还有没充要条件

充分条件（满足条件则一定有，不满足也可能有）：

狄拉克定理：

∀v∈V,deg(v)≥

2

则有哈密尔顿通路

欧尔定理：

∀不相邻顶点v,u∈V,deg(v)+deg(u)≥n

必要条件（用于判断不是哈密尔顿）：

连通图，每个顶点的度都必须大于等于1

最多只有两个顶点的度是1

如果一个顶点的度为2，则两条边都为哈密尔顿回路的一部分

从顶点集合V中去掉一组顶点S，则新图的连接部分数量<=S的个数

weighted graph加权图：

G=(V,E,W)

Dijkstra:寻找最短路径，要求所有路径都是正权重的

iterative

n

L

k

(v)=min{L

k−1

(v),L

k−1

(u)+w(u,v)}

O(n

2

)

旅行商问题

最短的哈密尔顿回路

近似算法

平面图：可以画在平面上且边与边不交叉

区域Region：包括有界区域和无界区域

欧拉公式：对于连通的平面简单图

r=e−v+2

对于非平面图也可能成立

区域的度：区域边的总数（绕一圈的边的总数）

推论1：

e≤3v−6,if v≥3

对于不连通的平面简单图也成立

推论2：对于一个平面简单图，G一定有一个顶点的度不超过5

推论3：对于一个平面简单图，如果任何一个回路的长度都大于3，则

e≤2v−4

Kuratowski定理

初等细分：增加原有道路上的细分点

同胚：可以通过一系列的初等细分所获得的图

一个图是非平面的

⇔

包含一个与

K

3,3

或

K

5

同胚的子图

着色问题

地图的对偶图，相邻的区域间连线

等价于对偶图的顶点着色，使每条边上的两个顶点不同颜色

最少着色数记为

χ(G)

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

chap11 Trees

英文

root

subtrees

preorder

postorder

backtracking

中文

根

子树

前序

后序

回溯

英文

internal vertice

isomorphic

inorder

spanning tree

中文

有孩子的节点

同构的

中序

生成树

树：没有简单回路的连通无向图

无向图是一棵树

⇔

每两个顶点之间都有唯一的简单通路

满m叉树：每个中间节点都有m个孩子

树的同构：

根树的同构（有向图的同构）

无根树的同构（无向图的同构）

树的性质：

n个顶点的树就有n-1条边

一个有i个内节点的满m叉树有

mi+1

和顶点

树一定是个二分图

二叉搜索树

插入一个新节点，最多发生

⌈log(n+1)⌉

次比较

决策树

由一系列节点生成一个解

prefix code

huffman code

生成树

一个简单图是连通的

⇔

包含一个生成树

DFS深度优先搜索（回溯）会形成一个根树

BFS广度优先搜索

最小生成树

Prim算法：找与已经连接的生成树距离最短的点，直到完全连通，

O(Elog(V))

Kruskal算法：找现存的最短边（不会产生回路），直到完全联通，

O(Vlog(E))

| | | |

树：没有简单回路的连通无向图

无向图是一棵树

⇔

每两个顶点之间都有唯一的简单通路

满m叉树：每个中间节点都有m个孩子

树的同构：

根树的同构（有向图的同构）

无根树的同构（无向图的同构）

树的性质：

n个顶点的树就有n-1条边

一个有i个内节点的满m叉树有

mi+1

和顶点

树一定是个二分图

二叉搜索树

插入一个新节点，最多发生

⌈log(n+1)⌉

次比较

决策树

由一系列节点生成一个解

prefix code

huffman code

生成树

一个简单图是连通的

⇔

包含一个生成树

DFS深度优先搜索（回溯）会形成一个根树

BFS广度优先搜索

最小生成树

Prim算法：找与已经连接的生成树距离最短的点，直到完全连通，

O(Elog(V))

Kruskal算法：找现存的最短边（不会产生回路），直到完全联通，

O(Vlog(E))