离散数学公式

1

SpongeBob SquarePants

基本等值式

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

A ? A∨A,

A ? A∧A

A∧B ? B∧A

A∨B ? B∨A，

(A∨B)∨C ? A∨(B∨C) (A∧B)∧C ? A∧(B∧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 A?B ? (A→B)∧(B→A) A→B ? ┐B→┐A (A→B)∧(A→┐B) ? ┐A

5.分配律 A∨(B∧C) ? (A∨B)∧(A∨C) （∨对∧的分配律） 6.德·摩根律 ┐(A∨B) ? ┐A∧┐B ┐(A∧B) ? ┐A∨┐B 7.吸收律 8.零律

9.同一律 11.矛盾律

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

15.等价否定等值式 A?B ? ┐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 (7) (A?B) ∧ (B?C) ? (A ? C)

(6) (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)破坏性二难

1

2

SpongeBob SquarePants

设个体域为有限集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

设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规则。

EI规则。

EG规则。

?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

?xA(x)?xA(x)或?A(y)?A(c)A(y)??xA(x)A(c)??xA(x)?xA(x)?A(c)2

3

SpongeBob SquarePants

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＝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} ∩B＝{a} ∩C＝a∩{c,d}

3

4

SpongeBob SquarePants

排中律  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 A??＝A A?A＝?

对偶(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)A?C ∧ B?D ? A×B ? C×D

常用的关系 对任意集合A，定义

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

A∪B＝B ? A?B ? A∩B＝A ? A－B＝?





(A?B)?C＝A?(B?C)

      

A?B＝A?C ? B＝C

4

5

SpongeBob SquarePants

小于或等于关系：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={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>}， 则R的关系矩阵和关系图分别是

?1?0MR???0??0

100101000?1??0??0?

定义域 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}

右复合 F?G＝{ | ?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)(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

5

6

SpongeBob SquarePants

设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次幂定义为：

幂运算的性质

设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也是传递的。

（1） R0＝{|x∈A}＝IA （2） Rn+1＝Rn ? R

6

7

SpongeBob SquarePants

关系性质的特点 自反性 反自反性 对称性 反对称性 传递性 集合表达式 关系矩阵 IA ? R R∩IA＝? R＝R-1 R∩R-1 ? IA R?R?R 主对角线元素主对角线元素全矩阵是对称矩阵 若 rij＝1，且i≠j，对M2中1所在位全是1 是0 则rji＝0 置，M中相应的位置都是1 关系图 每个顶点都有每个顶点都没有如果两个顶点之如果两点之间有如果顶点xi到xj环 环 间有边，一定是边，一定是一条有有边，xj到xk有一对方向相反的向边(无双向边) 边，则从xi到xk边(无单边) 也有边

关系的性质和运算之间的关系 自反性 反自反性 对称性 反对称性 传递性 R1-1 √ √ √ √ √ R1∩R2 √ √ √ √ √ R1∪R2 √ √ √ × × R1－R2 × √ √ √ × R1 ? R2 √ × × × ×

闭包的构造方法

设R为A上的关系，则有

关系性质与闭包运算之间的联系 设R是非空集合A上的关系，

（1）若R是自反的，则s(R)与t(R)也是自反的。 （2）若R是对称的，则r(R)与t(R)也是对称的。 （3）若R是传递的，则r(R)是传递的。 （1）自反闭包 r(R)＝R∪R0 （2）对称闭包 s(R)＝R∪R-1 （3）t(R)＝R∪R2∪R3∪…

7

8

SpongeBob SquarePants

等价类的性质

设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的极大元

24 36 B 最大元 最小元 极大元 极小元 无 6 无 6 24，36 2,3 12 6 6 6 2,3 6 12 6 2 B {2,3,6,12,24,36} 无 {6,12} {2,3,6} {6} 下界 无 2,3,6 上确界 无 12 6 6 下确界 无 6 无 6 12 6 6 3 上界 {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)的。

8

9

SpongeBob SquarePants

（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} 关联集：IG(v1) ＝{e1，e2，e3}

先驱元集：Г-D(d ) ＝{a，c} 邻域： 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

9

10

SpongeBob SquarePants

设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)＝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中层数最大顶点的层数

10

本文来源：https://www.bwwdw.com/article/r202.html