离散数学公式.docx

资源描述

离散数学公式.docx

《离散数学公式.docx》由会员分享，可在线阅读，更多相关《离散数学公式.docx（19页珍藏版）》请在冰点文库上搜索。

离散数学公式.docx

离散数学公式

基本等值式

1.双重否定律A┐┐A

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

3.交换律A∨BB∨A，A∧BB∧A

4.结合律（A∨B）∨CA∨（B∨C）（A∧B）∧CA∧（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∨11,A∧00

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

10.排中律 A∨┐A1

11.矛盾律 A∧┐A0

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＝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={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>}，

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

定义域domR＝{x|∃y（∈R）}

值域ranR＝{y|∃x（∈R）}

域fldR＝domR∪ranR

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

解答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＝{<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）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

设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-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，如果∉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的极大元

最大元

最小元

极大元

极小元

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

无

24，36

2,3

{6,12}

{2,3,6}

无

2,3

{6}

上界

下界

上确界

下确界

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

无

{6,12}

12,24,36

2,3,6

{2,3,6}

6,12,24,36

无

{6}

6,12,24,36,

2,3,6,

函数相等

由定义可知，两个函数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＝{<1,a>,<2,a>,<3,a>}f1＝{<1,a>,<2,a>,<3,b>}

f2＝{<1,a>,<2,b>,<3,a>}f3＝{<1,a>,<2,b>,<3,b>}

f4＝{<1,b>,<2,a>,<3,a>}f5＝{<1,b>,<2,a>,<3,b>}

f6＝{<1,b>,<2,b>,<3,a>}f7＝{<1,b>,<2,b>,<3,b>}

设f:

A→B，

（1）若ranf＝B，则称f:

A→B是满射（surjection）的。

（2）若∀y∈ranf都存在唯一的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）=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

设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

展开阅读全文