离散数学公式

基本等值式

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∪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＝A A∩A＝A

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

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

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

同一律  A∪Æ＝A A∩E＝A

零律  A∪E＝E A∩Æ＝Æ

排中律  A∪～A＝E

矛盾律  A∩～A＝Æ

吸收律 A∪(A∩B)＝A A∩(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互换，把Í与Ê互换，得到式子称为原式的对偶式。

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

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

笛卡儿积的符号化表示为 A×B＝{<x,y>|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,y>|x∈A∧y∈A}=A×A

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

空关系 Æ

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

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

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

关系矩阵和关系图

设 A={1,2,3,4}，R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>}，
则R的关系矩阵和关系图分别是

定义域 dom R ＝ {x | $y(<x,y>∈R )}

值域 ran R＝{y | $ x(<x,y>∈R)}

域 fld R＝dom R ∪ ran R

例 求R={<1,2>,<1,3>,<2,4>,<4,3>}的定义域、值域和域。

解答 dom R＝{1,2,4} ran R＝{2,3,4} fld R＝{1,2,3,4}

逆 R-1＝{<x,y>|<y,x>∈R}

右复合 F°G＝{<x,y> | $t(<x,t>∈F∧<t,y>∈G)}

限制 R↑A={<x,y>|xRy∧x∈A}

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

例 设R＝{<1,2>，<1,3>，<2,2>，<2,4>，<3,2>}

R↑{1}＝{<1,2>，<1,3>} R↑Æ ＝Æ R↑{2,3}＝{<2,2>，<2,4>}，<3,2>}

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

设F是任意的关系，则

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

(2)dom F-1＝ran F，ran F-1＝dom F

设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

设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,x>|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<t)使得Rs=Rt，则

(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→<x,x>∈R)，

反自反 "x(x∈A→<x,x>ÏR)，

对称 "x"y(x,y∈A∧<x,y>∈R→<y,x>∈R)

反对称 "x"y(x,y∈A∧<x,y>∈R∧<y,x>∈R→x=y)，

传递 "x"y"z(x,y,z∈A∧<x,y>∈R∧<y,z>∈R→<x,z>∈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-1

R∩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，如果<x,y>ÏR，则[x]与[y]不交。

（4）∪{[x]|x∈A}＝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}

无

无

24，36

2,3

{6,12}

12

6

12

6

{2,3,6}

6

无

6

2,3

{6}

6

6

6

6

B

上界

下界

上确界

下确界

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

无

无

无

无

{6,12}

12,24,36

2,3,6

12

6

{2,3,6}

6,12,24,36

无

6

无

{6}

6,12,24,36,

2,3,6,

6

6

函数相等

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

（1）dom F＝dom G

（2）"x∈dom F＝dom G，都有 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} 。其中

f 0＝{<1,a>,<2,a>,<3,a>} f 1＝{<1,a>,<2,a>,<3,b>}

f 2＝{<1,a>,<2,b>,<3,a>} f 3＝{<1,a>,<2,b>,<3,b>}

f 4＝{<1,b>,<2,a>,<3,a>} f 5＝{<1,b>,<2,a>,<3,b>}

f 6＝{<1,b>,<2,b>,<3,a>} f 7＝{<1,b>,<2,b>,<3,b>}

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

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

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

单射 双射 函数 满射

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

(1) f：R→R，f(x)= -x2+2x-1 (2) f：Z+→R，f(x)=ln x，Z+为正整数集
(3) f：R→Z，f(x)=ëxû (4) f：R→R，f(x)=2x+1。

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

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

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

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

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

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

　画出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

设G＝<V,E>是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＝<V,E,W>有m条边。不妨设G中没有环（否则，可以将所有的环先删去），将m条边按权从小到大排序：e1,e2,…,em。

(2)取e1在T中。

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

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

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

W(T1)＝6 W(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

中序行遍法：b a (f d g) c e 前序行遍法：a b (c (d f g) e)

后序行遍法：b ((f g d) e c) a

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

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

┐ 命题的“非”运算

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

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

→ 命题的“条件”运算

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

A<=>B 命题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→Y f是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 偏序集范畴