离散函数

离散函数

-

2023年3月3日发(作者：拙政园图片)

.

.

基本等值式

1.双重否定律A┐┐A

2.幂等律AA∨A,AA∧A

3.交换律A∨BB∨A，A∧BB∧A

4.结合律(A∨B)∨CA∨(B∨C)(A∧B)∧CA∧(B∧C)

5.分配律A∨(B∧C)(A∨B)∧(A∨C)（∨对∧的分配律）

A∧(B∨C)(A∧B)∨(A∧C)（∧对∨的分配律）

6.德·摩根律┐(A∨B)┐A∧┐B┐(A∧B)┐A∨┐B

7.吸收律A∨(A∧B)A，A∧(A∨B)A

8.零律A∨11,A∧00

9.同一律A∨0A，A∧1A

10.排中律A∨┐A1

11.矛盾律A∧┐A0

12.蕴涵等值式A→B┐A∨B

13.等价等值式AB(A→B)∧(B→A)

14.假言易位A→B┐B→┐A

15.等价否定等值式AB┐A┐B

16.归谬论(A→B)∧(A→┐B)┐A

求给定公式范式的步骤

(1)消去联结词→、(若存在)。

(2)否定号的消去(利用双重否定律)或内移(利用德摩根律)。

(3)利用分配律：利用∧对∨的分配律求析取范式，∨对∧的分配律求合取范式。

推理定律--重言蕴含式

(1)A(A∨B)附加律

(2)(A∧B)A化简律

(3)(A→B)∧AB假言推理

(4)(A→B)∧┐B┐A拒取式

(5)(A∨B)∧┐BA析取三段论

(6)(A→B)∧(B→C)(A→C)假言三段论

(7)(AB)∧(BC)(AC)等价三段论

(8)(A→B)∧(C→D)∧(A∨C)(B∨D)构造性二难

(A→B)∧(┐A→B)∧(A∨┐A)B构造性二难(特殊形式)

(9)(A→B)∧(C→D)∧(┐B∨┐D)(┐A∨┐C)破坏性二难

.

.

设个体域为有限集D={a1,a2,…,an},则有

（1）xA(x)A(a1)∧A(a2)∧…∧A(an)

（2）xA(x)A(a1)∨A(a2)∨…∨A(an)

设A(x)是任意的含自由出现个体变项x的公式，则

（1）┐xA(x)x┐A(x)

（2）┐xA(x)x┐A(x)

设A(x)是任意的含自由出现个体变项x的公式，B中不含x的出现，则

（1）x(A(x)∨B)xA(x)∨B

x(A(x)∧B)xA(x)∧B

x(A(x)→B)xA(x)→B

x(B→A(x))B→xA(x)

（2）x(A(x)∨B)xA(x)∨B

x(A(x)∧B)xA(x)∧B

x(A(x)→B)xA(x)→B

x(B→A(x))B→xA(x)

设A(x)，B(x)是任意的含自由出现个体变项x的公式，则

（1）x(A(x)∧B(x))xA(x)∧xB(x)

（2）x(A(x)∨B(x))xA(x)∨xB(x)

全称量词“”对“∨”无分配律。

存在量词“”对“∧”无分配律。

UI规则。

UG规则。

EG规则。

EI规则。

A(c)

xA(x)

或

A(y)

xA(x)









xA(x)

A(y)



xA(x)

A(c)



A(c)

xA(x)





.

.

A∪B＝{x|x∈A∨x∈B}、

A∩B＝{x|x∈A∧x∈B}

A－B＝{x|x∈A∧xB}

幂集P(A)＝{x|xA}

对称差集AB＝(A－B)∪(B－A)

AB＝(A∪B)－(A∩B)

绝对补集～A＝{x|xA}

广义并∪A＝{x|z(z∈A∧x∈z)}广义交∩A＝{x|z(z∈A→x∈z)}

设A＝{{a,b,c},{a,c,d},{a,e,f}}B＝{{a}}C＝{a,{c,d}}

则∪A＝{a,b,c,d,e,f}

∪B＝{a}

∪C＝a∪{c,d}

∪＝

∩A＝{a}

∩B＝{a}

∩C＝a∩{c,d}

集合恒等式

幂等律A∪A＝AA∩A＝A

结合律(A∪B)∪C＝A∪(B∪C)(A∩B)∩C＝A∩(B∩C)

交换律A∪B＝B∪AA∩B＝B∩A

分配律A∪(B∩C)＝(A∪B)∩(A∪C)A∩(B∪C)＝(A∩B)∪(A∩C)

同一律A∪＝AA∩E＝A

零律A∪E＝EA∩＝

.

.

排中律A∪～A＝E

矛盾律A∩～A＝

吸收律A∪(A∩B)＝AA∩(A∪B)＝A

德摩根律A－(B∪C)＝(A－B)∩(A－C)A－(B∩C)＝(A－B)∪(A－C)

～(B∪C)＝～B∩～C～(B∩C)＝～B∪～C

～＝E～E＝

双重否定律～(～A)＝A

集合运算性质的一些重要结果

A∩BA，A∩BB

AA∪B，BA∪B

A－BA

A－B＝A∩～B

A∪B＝BABA∩B＝AA－B＝

AB＝BA

(AB)C＝A(BC)

A＝A

AA＝

AB＝ACB＝C

对偶(dual)式：一个集合表达式，如果只含有∩、∪、～、、E、＝、、，那么同时把∩与∪互换，把

与E互换，把与互换，得到式子称为原式的对偶式。

有序对具有以下性质：（1）当x≠y时，≠。

（2）＝的充分必要条件是x＝u且y＝v。

笛卡儿积的符号化表示为A×B＝{|x∈A∧y∈B}

如果|A|=m,|B|=n,则|A×B|=mn。

笛卡儿积的运算性质

(1)对任意集合A，根据定义有

A×＝,×A＝

(2)一般的说，笛卡儿积运算不满足交换律，即

A×B≠B×A(当A≠∧B≠∧A≠B时)

(3)笛卡儿积运算不满足结合律，即

(A×B)×C≠A×(B×C)(当A≠∧B≠∧C≠时)

(4)笛卡儿积运算对并和交运算满足分配律，即

A×(B∪C)=(A×B)∪(A×C)(B∪C)×A=(B×A)∪(C×A)

A×(B∩C)=(A×B)∩(A×C)(B∩C)×A=(B×A)∩(C×A)

(5)AC∧BDA×BC×D

常用的关系

对任意集合A，定义

全域关系EA={|x∈A∧y∈A}=A×A

恒等关系IA={|x∈A}

空关系

.

.

小于或等于关系：LA={|x,y∈A∧x≤y}，其中AR。

整除关系：DB={|x,y∈B∧x整除y}，其中AZ*，Z*是非零整数集

包含关系：R＝{|x,y∈A∧xy}，其中A是集合族。

关系矩阵和关系图

设A={1,2,3,4}，R={,,,,}，

则R的关系矩阵和关系图分别是

定义域domR＝{x|y(∈R)}

值域ranR＝{y|x(∈R)}

域fldR＝domR∪ranR

例求R={,,,}的定义域、值域和域。

解答domR＝{1,2,4}ranR＝{2,3,4}fldR＝{1,2,3,4}

逆R-1＝{|∈R}

右复合FG＝{|t(∈F∧∈G)}

限制R↑A={|xRy∧x∈A}

像R[A]=ran(R↑A)

例设R＝{，，，，}

R↑{1}＝{，}R↑＝R↑{2,3}＝{，}，}

R[{1}]＝{2,3}R[]＝R[{3}]＝{2}

设F是任意的关系，则

(1)(F-1)-1＝F

(2)domF-1＝ranF，ranF-1＝domF

设F，G，H是任意的关系，则

(1)(FG)H＝F(GH)

(2)(FG)-1＝G-1F-1

设R为A上的关系，则RIA＝IAR＝R

设F，G，H是任意的关系，则

(1)F(G∪H)＝FG∪FH

(2)(G∪H)F＝GF∪HF

(3)F(G∩H)FG∩FH

(4)(G∩H)FGF∩HF



























0010

0000

1100

0011

M

R

.

.

设F为关系，A,B为集合，则

(1)F↑(A∪B)＝F↑A∪F↑B

(2)F[A∪B]＝F[A]∪F[B]

(3)F↑(A∩B)＝F↑A∩F↑B

(4)F[A∩B]F[A]∩F[B]

关系的幂运算

设R为A上的关系，n为自然数，则R的n次幂定义为：

（1）R0＝{|x∈A}＝IA

（2）Rn+1＝RnR

幂运算的性质

设A为n元集，R是A上的关系，则存在自然数s和t,使得Rs=Rt。

设R是A上的关系，m,n∈N，则

(1)RmRn＝Rm+n(2)(Rm)n＝Rmn

设R是A上的关系，若存在自然数s,t(s

(1)对任何k∈N有Rs+k=Rt+k

(2)对任何k,i∈N有Rs+kp+i=Rs+i，其中p=t-s

(3)令S={R0，R1，…，Rt-1}，则对于任意的q∈N有Rq∈S

自反x(x∈A→∈R)，

反自反x(x∈A→R)，

对称xy(x,y∈A∧∈R→∈R)

反对称xy(x,y∈A∧∈R∧∈R→x=y)，

传递xyz(x,y,z∈A∧∈R∧∈R→∈R)

关系性质的等价描述

设R为A上的关系，则

（1）R在A上自反当且仅当IAR

（2）R在A上反自反当且仅当R∩IA＝

（3）R在A上对称当且仅当R＝R-1

（4）R在A上反对称当且仅当R∩R-1IA

（5）R在A上传递当且仅当RRR

(1)若R1，R2是自反的和对称的，则R1∪R2也是自反的和对称的。

(2)若R1和R2是传递的，则R1∩R2也是传递的。

.

.

关系性质的特点

自反性反自反性对称性反对称性传递性

集合表达式

IAR

R∩IA＝R＝R-1R∩R-1IA

RRR

关系矩阵主对角线元素

全是1

主对角线元素全

是0

矩阵是对称矩阵若rij＝1，且i≠j，

则rji＝0

对M2中1所在位

置，M中相应的

位置都是1

关系图每个顶点都有

环

每个顶点都没有

环

如果两个顶点之

间有边，一定是

一对方向相反的

边(无单边)

如果两点之间有

边，一定是一条有

向边(无双向边)

如果顶点xi到xj

有边，xj到xk有

边，则从xi到xk

也有边

关系的性质和运算之间的关系

自反性反自反性对称性反对称性传递性

R1-1√√√√√

R1∩R2√√√√√

R1∪R2√√√××

R1－R2×√√√×

R1R2

√××××

闭包的构造方法

设R为A上的关系，则有

（1）自反闭包r(R)＝R∪R0

（2）对称闭包s(R)＝R∪R-1

（3）t(R)＝R∪R2∪R3∪…

关系性质与闭包运算之间的联系

设R是非空集合A上的关系，

（1）若R是自反的，则s(R)与t(R)也是自反的。

（2）若R是对称的，则r(R)与t(R)也是对称的。

（3）若R是传递的，则r(R)是传递的。

.

.

等价类的性质

设R是非空集合A上的等价关系，则

（1）x∈A，[x]是A的非空子集。

（2）x,y∈A，如果xRy，则[x]＝[y]。

（3）x,y∈A，如果R，则[x]与[y]不交。

（4）∪{[x]|x∈A}＝A。

偏序集中的特殊元素

设为偏序集，BA，y∈B。

（1）若x(x∈B→y≤x)成立，则称y为B的最小元。

（2）若x(x∈B→x≤y)成立，则称y为B的最大元。

（3）若x(x∈B∧x≤y→x＝y)成立，则称y为B的极小元。

（4）若x(x∈B∧y≤x→x＝y)成立，则称y为B的极大元

B上界下界上确界下确界

{2,3,6,12,24,36}无无无无

{6,12}12,24,362,3,6126

{2,3,6}6,12,24,36无6无

{6}6,12,24,36,2,3,6,66

函数相等

由定义可知，两个函数F和G相等,一定满足下面两个条件：

（1）domF＝domG

（2）x∈domF＝domG，都有F(x)＝G(x)

所有从A到B的函数的集合记作BA，读作“B上A”，符号化表示为BA＝{f|f：A→B}。

例：设A＝{1,2,3}，B＝{a,b}，求BA。

BA＝{f0,f1,f2,f3,f4,f5,f6,f7}。其中

f0＝{,,}f1＝{,,}

f2＝{,,}f3＝{,,}

f4＝{,,}f5＝{,,}

f6＝{,,}f7＝{,,}

设f:A→B，（1）若ranf＝B，则称f:A→B是满射(surjection)的。

（2）若y∈ranf都存在唯一的x∈A使得f(x)＝y，则称f:A→B是单射(injection)的。

B最大元最小元极大元极小元

{2,3,6,12,24,36}无无24，362,3

{6,12}126126

{2,3,6}6无62,3

{6}6666

36

3

24

2

12

6

.

.

（3）若f既是满射又是单射的，则称f:A→B是双射(bijection)

单射双射函数满射

例：判断下面函数是否为单射、满射、双射的，为什么?

(1)f：R→R，f(x)=-x2+2x-1(2)f：Z+→R，f(x)=lnx，Z+为正整数集

(3)f：R→Z，f(x)=x(4)f：R→R，f(x)=2x+1。

解（1）f在x=1取得极大值0。既不是单射也不是满射的。

（2）f是单调上升的，是单射的，但不满射。ranf={ln1,ln2,…}。

（3）f是满射的，但不是单射的，例如f(1.5)=f(1.2)=1。

（4）f是满射、单射、双射的，因为它是单调函数并且ranf=R。

例：(1)给定无向图G＝，其中V＝{v1,v2,v3,v4,v5}，

E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)}.

(2)给定有向图D=，其中V＝{a,b,c,d}，

E＝{,,,,,,}。

画出G与D的图形。

邻域：NG(v1)＝{v2，v5}后继元集：Г+D(d)＝{c}

闭邻域：NG(v1)＝{v1，v2，v5}先驱元集：Г-D(d)＝{a，c}

关联集：IG(v1)＝{e1，e2，e3}邻域：ND(d)＝{a，c}

闭邻域：ND(d)＝{a，c，d}

d(v1)＝4(注意，环提供2度)，出度：d+(a)＝4，入度：d-(a)＝1

△＝4，δ＝1，(环e1提供出度1，提供入度1)，

v4是悬挂顶点，e7是悬挂边。d(a)＝4+1＝5。△＝5，δ＝3，

△+＝4(在a点达到)

度数列为4,4,2,1,3。δ+＝0(在b点达到)

△-＝3(在b点达到)

δ-＝1(在a和c点达到)

按字母顺序，度数列：5,3,3,3

出度列：4,0,2,1入度列：1,3,1,2

a

b

c

1

2

3

d

a

b

c

1

2

3

4

a

b

c

1

2

3

4d

a

b

c

1

2

3

4d

.

.

设G＝是n阶m条边的无向图，则下面各命题是等价的：

（1）G是树。（2）G中任意两个顶点之间存在唯一的路径。

（3）G中无回路且m＝n1。（4）G是连通的且m＝n1。

（5）G是连通的且G中任何边均为桥。

（6）G中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到唯一的一个含新边的圈。

例题已知无向树T中，有1个3度顶点，2个2度顶点，其余顶点全是树叶，试求树叶数，并画出满足要

求的非同构的无向树。

解答设有x片树叶，于是结点总数

n＝1+2+x＝3+x

由握手定理和树的性质m＝n1可知，

2m＝2(n1)＝2×(2+x)

＝1×3+2×2+x

解出x＝3，故T有3片树叶。

故T的度数应为1、1、1、2、2、3。

求最小生成树的算法（避圈法(Kruskal)）

(1)设n阶无向连通带权图G＝有m条边。不妨设G中没有环（否则，可以将所有的环先删去），

将m条边按权从小到大排序：e1,e2,…,em。

(2)取e1在T中。

(3)依次检查e2,…,em，若ej(j≥2)与已在T中的边不构成回路，取ej也在T中，否则弃去ej。

(4)算法停止时得到的T为G的最小生成树为止。

例：求下图所示两个图中的最小生成树。

W(T1)＝6W(T2)＝12

T是n(n≥2)阶有向树，

(1)T为根树—T中有一个顶点入度为0，其余顶点的入度均为1

(2)树根——入度为0的顶点

(3)树叶——入度为1，出度为0的顶点

(4)内点——入度为1，出度不为0的顶点

(5)分支点——树根与内点的总称

(6)顶点v的层数——从树根到v的通路长度

(7)树高——T中层数最大顶点的层数

.

.

根树的画法：树根放上方，省去所有有向边上的箭头。

树叶——8片内点——6个分支点——7个高度——5

求带权为1、1、2、3、4、5的最优树。

W(T)=38

中序行遍法：ba(fdg)ce前序行遍法：ab(c(dfg)e)

后序行遍法：b((fgd)ec)a

.

.

├断定符（公式在L中可证）

╞满足符（公式在E上有效，公式在E上可满足）

┐命题的“非”运算

∧命题的“合取”（“与”）运算

∨命题的“析取”（“或”，“可兼或”）运算

→命题的“条件”运算

↔命题的“双条件”运算的

AB命题A与B等价关系

A=>B命题A与B的蕴涵关系

A*公式A的对偶公式

wff合式公式

iff当且仅当

↑命题的“与非”运算（“与非门”）

↓命题的“或非”运算（“或非门”）

□模态词“必然”

◇模态词“可能”

φ空集

∈属于（∉不属于）

P（A）集合A的幂集

|A|集合A的点数

R^2=R○R[R^n=R^(n-1)○R]关系R的“复合”

א阿列夫

⊆包含

⊂（或下面加≠）真包含

∪集合的并运算

∩集合的交运算

-（～）集合的差运算

〡限制

[X](右下角R)集合关于关系R的等价类

A/R集合A上关于R的商集

[a]元素a产生的循环群

I(i大写)环，理想

Z/(n)模n的同余类集合

r(R)关系R的自反闭包

s(R)关系的对称闭包

CP命题演绎的定理（CP规则）

EG存在推广规则（存在量词引入规则）

ES存在量词特指规则（存在量词消去规则）

UG全称推广规则（全称量词引入规则）

US全称特指规则（全称量词消去规则）

R关系r相容关系

R○S关系与关系的复合

domf函数的定义域（前域）

ranf函数的值域

f:X→Yf是X到Y的函数

GCD(x,y)x,y最大公约数

LCM(x,y)x,y最小公倍数

aH(Ha)H关于a的左（右）陪集

Ker(f)同态映射f的核（或称f同态核）

[1，n]1到n的整数集合

d(u,v)点u与点v间的距离

d(v)点v的度数G=(V,E)点集为V,边集为E的图

W(G)图G的连通分支数

k(G)图G的点连通度

△（G)图G的最大点度

A(G)图G的邻接矩阵

P(G)图G的可达矩阵

M(G)图G的关联矩阵

C复数集

N自然数集（包含0在内）

N*正自然数集

P素数集

Q有理数集

R实数集

Z整数集

Set集范畴

Top拓扑空间范畴

Ab交换群范畴

Grp群范畴

Mon单元半群范畴

Ring有单位元的（结合）环范畴

Rng环范畴

CRng交换环范畴

R-mod环R的左模范畴

mod-R环R的右模范畴

Field域范畴

Poset偏序集范畴