离散数学公式
基本等值式
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 14. 假言易位 A →B ⇔ ┐B →┐A 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) (AB) ∧ (BC) ⇒ (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)
全称量词“∀”对“∨”无分配律。 存在量词“∃”对“∧”无分配律。
∀xA(x)∀xA(x)UI 规则。
或
∴A(y)∴A(c)UG 规则。
A(y)
∴∀xA(x)
A(c)EG 规则。
∴∃xA(x)
∃xA(x)EI 规则。
∴A(c)
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 互换，把⊆与⊇互换，得到式子称为原式的对偶式。
有序对具有以下性质： （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 的关系矩阵和关系图分别是
⎡1⎢0M R =⎢
⎢0⎢⎣0
1001
0100
0⎤1⎥⎥0⎥⎥0⎦
定义域 dom R ＝ {x | ∃y(∈R )} 值域 ran R＝{y | ∃ x(∈R)} 域 fld R＝dom R ∪ ran R
例 求R={,,,}的定义域、值域和域。 解答 dom R＝{1,2,4} ran R＝{2,3,4} fld R＝{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)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 (4) (G∩H) ︒F ⊆G ︒F ∩H ︒F
设F 为关系，A,B 为集合，则 (2) F[A∪B]＝F[A]∪F[B] (3) 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
(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也是传递的。
关系性质的特点
关系的性质和运算之间的关系
闭包的构造方法
设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 的极大元
函数相等
由定义可知，两个函数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 ＝{ f 0, f 1, f 2, f 3, f 4, f 5, f 6, f 7} 。其中
f 0＝{,,} f 1＝{,,} f 2＝{,,} f 3＝{,,} f 4＝{,,} f 5＝{,,} f 6＝{,,} f 7＝{,,}
设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 )
a b c
1 2 3 4
a b c
d
1 2 3
a b c
1 2 3
a b c
1 2 3
4 d
4 d
单射 双射 函数
满射 例：判断下面函数是否为单射、满射、双射的，为什么?
(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 ＝{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(v 1) ＝{v 2，v 5} 后继元集：Г+D (d ) ＝{c } 闭邻域：NG(v 1) ＝{v 1，v 2，v 5} 先驱元集：Г-D(d ) ＝{a ，c } 关联集：IG(v 1) ＝{e 1，e 2，e 3} 邻域： ND(d ) ＝{a ，c }
闭邻域：ND(d ) ＝{a ，c ，d }
d (v 1) ＝4(注意，环提供2度) ， 出度：d +(a ) ＝4，入度：d -(a ) ＝1 △＝4，δ＝1， (环e 1提供出度1，提供入度1) ， v 4是悬挂顶点，e 7是悬挂边。 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 ＝是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 条边按权从小到大排序：e 1, e 2, …, em 。 (2)取e 1在T 中。
(3)依次检查e 2, …, em ，若ej (j ≥2) 与已在T 中的边不构成回路，取ej 也在T 中，否则弃去ej 。
(4)算法停止时得到的T 为G 的最小生成树为止。 例：求下图所示两个图中的最小生成树。
W (T 1) ＝6 W (T 2) ＝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
f g ) e 前序行遍法：b ( (f g ) e )
后序行遍法：b ((f g d ) e c ) a