离散数学公式

1.双重否定律 A ┐┐A 2.幂等律 3.交换律 4.结合律

A A∨A,

A A∧A

A∧B B∧A

(A∧B)∧C A∧(B∧C)

A∨B B∨A，

(A∨B)∨C A∨(B∨C)

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

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

A∨1 1,A∧0 0 A∨0 A，A∧1 A A∨┐A 1

A∧┐A 0 A→B ┐A∨B AB (A→B)∧(B→A) A→B ┐B→┐A (A→B)∧(A→┐B) ┐A

6.德·摩根律 ┐(A∨B) ┐A∧┐B ┐(A∧B) ┐A∨┐B 7.吸收律 8.零律

9.同一律 10.排中律 11.矛盾律

12.蕴涵等值式 13.等价等值式 14.假言易位 16.归谬论

15.等价否定等值式AB ┐A┐B 求给定公式范式的步骤 (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) 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

设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)或UG规则。 A(y)A(c)A(y)EG规则。 A(c)xA(x)EI规则。 xA(x)xA(x)A∪B＝{x|x∈A∨x∈ 、 B } A(c)UI规则。

A∩B＝{x|x∈A∧x∈B } A－B＝{x|x∈A∧xB } 幂集 P(A)＝{x | xA}

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

AB＝(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＝B∩A

A∩E＝A

集合恒等式 幂等律 交换律 分配律 同一律 零律 排中律 矛盾律 吸收律

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

A∪B＝B∪AA∪＝AA∪E＝EA∪～A＝E A∪(A∩B)＝A

(A∩B)∩C＝A∩(B∩C)

A∪(B∩C)＝(A∪B)∩(A∪C)

A∩(B∪C)＝(A∩B)∪(A∩C)

A∩＝

A∩(A∪B)＝A

A∩～A＝

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

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

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

＝E

双重否定律 ～(～A)＝A集合运算性质的一些重要结果 A∩BA，A∩BBAA∪B，BA∪B A－BA

A－B＝A∩～B

E＝

A∪B＝B AB A∩B＝A A－B＝AB＝BA A＝A AA＝

(AB)C＝A(BC)

AB＝AC 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＝ A×B≠B×A

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

(2)一般的说，笛卡儿积运算不满足交换律，即 (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)AC ∧ BD A×B C×D 常用的关系 对任意集合A，定义

全域关系 EA={|x∈A∧y∈A}=A×A 恒等关系 IA={|x∈A} 空关系

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

整除关系：DB={|x,y∈B∧x整除y}，其中 AZ* ，Z*是非零整数集 包含关系：R＝{|x,y∈A∧xy}，其中 A是集合族。

关系矩阵和关系图

设 A={1,2,3,4}，R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>}， 则R的关系矩阵和关系图分别是 定义域 dom R ＝ {x | y(∈R )} 值域 ran R＝{y | x(∈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＝{|∈R}

右复合 FG＝{ | t(∈F∧∈G)} R↑A={|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)(FG)H＝F(GH) (2)(FG)-1＝G-1 F-1

设R为A上的关系，则R IA＝IA R＝R 设F，G，H是任意的关系，则 (1) F(G∪H)＝FG∪FH (2) (G∪H)F＝GF∪HF (3) F(G∩H)FG∩FH (4) (G∩H)FGF∩HF

设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(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)，

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

反对称 xy(x,y∈A∧∈R∧∈R→x=y)， 传递 xyz(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上传递当且仅当 RRR

(1)若R1，R2是自反的和对称的，则R1∪R2也是自反的和对称的。 (2)若R1和R2是传递的，则R1∩R2也是传递的。 关系性质的特点 自反性 反自反性 对称性 反对称性 传递性 集合表达式 关系矩阵 IA R R∩IA＝ R＝R-1 R∩R-1 IA RRR 主对角线元素主对角线元素矩阵是对称矩若rij＝1，且i对M2中1所在全是1 全是0 阵 ≠j，则rji＝0 位置，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。 偏序集中的特殊元素

设为偏序集，BA，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的极大元 24 36 B 12 6 2 3 最大元 最小元 极大元 极小元 无 6 无 6 24，36 2,3 12 6 6 6 2,3 6 12 6 6 {2,3,6,12,24,36} 无 {6,12} {2,3,6} {6} 上界 下界 无 2,3,6 上确界 无 12 6 6 下确界 无 6 无 6 B {2,3,6,12,24,36} 无 {6,12} {2,3,6} {6} 函数相等

12,24,36 6,12,24,36 无 6,12,24,36, 2,3,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)

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(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＝是n阶m条边的无向图，则下面各命题是等价的：

（1）G是树。 （2）G中任意两个顶点之间存在唯一的路径。 （3）G中无回路且m＝n1。 （4）G是连通的且m＝n1。 （5）G是连通的且G中任何边均为桥。

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

例题 已知无向树T中，有1个3度顶点，2个2度顶点，其余顶点全是树叶，试求树叶数，并画出满足要求的非同构的无向树。 解答 设有x片树叶，于是结点总数

n＝1+2+x＝3+x

由握手定理和树的性质m＝n1可知，

2m＝2(n1)＝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)＝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