离散数学公式Word文档下载推荐.docx
《离散数学公式Word文档下载推荐.docx》由会员分享,可在线阅读,更多相关《离散数学公式Word文档下载推荐.docx(23页珍藏版)》请在冰点文库上搜索。
(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
、
设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∧xB}
幂集P(A)={x|xA}
对称差集AB=(A-B)∪(B-A)
AB=(A∪B)-(A∩B)
绝对补集~A={x|xA}
广义并∪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∩BA,A∩BB
AA∪B,BA∪B
A-BA
A-B=A∩~B
A∪B=BABA∩B=AA-B=
—
AB=BA
(AB)C=A(BC)
A=A
AA=
AB=ACB=C
对偶(dual)式:
一个集合表达式,如果只含有∩、∪、~、、E、=、、,那么同时把∩与∪互换,把与E互换,把与互换,得到式子称为原式的对偶式。
有序对<
x,y>
具有以下性质:
(1)当x≠y时,<
≠<
y,x>
(2)<
=<
u,v>
的充分必要条件是x=u且y=v。
|
笛卡儿积的符号化表示为A×
B={<
|x∈A∧y∈B}
如果|A|=m,|B|=n,则|A×
B|=mn。
笛卡儿积的运算性质
(1)对任意集合A,根据定义有
A×
=,×
A=
(2)一般的说,笛卡儿积运算不满足交换律,即
B≠B×
A(当A≠∧B≠∧A≠B时)
(3)笛卡儿积运算不满足结合律,即
(A×
B)×
C≠A×
(B×
C)(当A≠∧B≠∧C≠时)
(4)笛卡儿积运算对并和交运算满足分配律,即
]
(B∪C)=(A×
B)∪(A×
C)(B∪C)×
A=(B×
A)∪(C×
A)
A×
(B∩C)=(A×
B)∩(A×
C)(B∩C)×
A)∩(C×
(5)AC∧BDA×
BC×
D
常用的关系
对任意集合A,定义
全域关系EA={<
|x∈A∧y∈A}=A×
A
恒等关系IA={<
x,x>
|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的关系矩阵和关系图分别是
定义域domR={x|y(<
∈R)}
值域ranR={y|x(<
∈R)}
域fldR=domR∪ranR
例求R={<
1,3>
4,3>
}的定义域、值域和域。
;
解答domR={1,2,4}ranR={2,3,4}fldR={1,2,3,4}
逆R-1={<
|<
∈R}
右复合FG={<
|t(<
x,t>
∈F∧<
t,y>
∈G)}
限制R↑A={<
|xRy∧x∈A}
像R[A]=ran(R↑A)
例设R={<
,<
2,2>
3,2>
}
R↑{1}={<
}R↑=R↑{2,3}={<
},<
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)(FG)H=F(GH)
(2)(FG)-1=G-1F-1
设R为A上的关系,则RIA=IAR=R
【
(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=RnR
幂运算的性质
设A为n元集,R是A上的关系,则存在自然数s和t,使得Rs=Rt。
设R是A上的关系,m,n∈N,则
(1)RmRn=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→<
∈R),
反自反x(x∈A→<
R),
对称xy(x,y∈A∧<
∈R→<
∈R)
反对称xy(x,y∈A∧<
∈R∧<
∈R→x=y),
传递xyz(x,y,z∈A∧<
y,z>
x,z>
关系性质的等价描述
设R为A上的关系,则
?
(1)R在A上自反当且仅当IAR
(2)R在A上反自反当且仅当R∩IA=
(3)R在A上对称当且仅当R=R-1
(4)R在A上反对称当且仅当R∩R-1IA
(5)R在A上传递当且仅当RRR
(1)若R1,R2是自反的和对称的,则R1∪R2也是自反的和对称的。
(2)若R1和R2是传递的,则R1∩R2也是传递的。
关系性质的特点
自反性
反自反性
?
对称性
反对称性
传递性
集合表达式
IAR
R∩IA=
R=R-1
R∩R-1IA
RRR
关系矩阵
主对角线元素全是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
R1R2
闭包的构造方法
设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。
:
偏序集中的特殊元素
设<
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的极大元
B
最大元
最小元
极大元
极小元
{2,3,6,12,24,36}
无
无
24,36
2,3
{6,12}
12
6
6
{2,3,6}
{6}
上界
*
下界
上确界
下确界
12,24,36
#
2,3,6
12
6,12,24,36
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={<
3,b>
f2={<
2,b>
}f3={<
f4={<
1,b>
}f5={<
f6={<
}f7={<
设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=f=1。
(4)f是满射、单射、双射的,因为它是单调函数并且ranf=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={a,b,c,d},
E={<
a,a>
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=<
是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=<
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)=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
.
!
├断定符(公式在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→Yf是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偏序集范畴
,