离散数学第四章二元关系和函数知识点总结Word下载.docx
- 文档编号:5653728
- 上传时间:2023-05-05
- 格式:DOCX
- 页数:29
- 大小:401.15KB
离散数学第四章二元关系和函数知识点总结Word下载.docx
《离散数学第四章二元关系和函数知识点总结Word下载.docx》由会员分享,可在线阅读,更多相关《离散数学第四章二元关系和函数知识点总结Word下载.docx(29页珍藏版)》请在冰点文库上搜索。
3,b>
3,c>
}
B´
A={<
a,1>
b,1>
c,1>
a,2>
b,2>
c,2>
a,3>
<
b,3>
c,3>
A={Æ
},P(A)´
A={<
Æ
Æ
>
{Æ
},Æ
性质:
不适合交换律A´
B¹
B´
A(A¹
B,A¹
B¹
)
不适合结合律(A´
B)´
C¹
A´
(B´
C)(A¹
对于并或交运算满足分配律
(BÈ
C)=(A´
B)È
(A´
C)
(BÈ
C)´
A=(B´
A)È
(C´
A)
(BÇ
B)Ç
(BÇ
A)Ç
若A或B中有一个为空集,则A´
B就是空集.
=Æ
´
B=Æ
若|A|=m,|B|=n,则|A´
B|=mn
证明A´
C)
证任取<
∈A×
(B∪C)
x∈A∧y∈B∪C
x∈A∧(y∈B∨y∈C)
(x∈A∧y∈B)∨(x∈A∧y∈C)
B∨<
C
∈(A×
B)∪(A×
所以有A×
(B∪C)=(A×
C).
例3
(1)证明A=BÙ
C=DÞ
C=B´
D
(2)A´
D是否推出A=BÙ
C=D?
为什么?
解
(1)任取<
Î
CÛ
xÎ
BÙ
DÛ
(2)不一定.反例如下:
A={1},B={2},C=D=Æ
则A´
D但是A¹
B.
二元关系的定义
定义设A,B为集合,A×
B的任何子集所定义的二元
关系叫做从A到B的二元关系,当A=B时则叫做A上
的二元关系.
例4A={0,1},B={1,2,3},R1={<
0,2>
},R2=A×
B,R3=Æ
R4={<
0,1>
}.那么R1,R2,R3,R4是从A到B
的二元关系,R3和R4同时也是A上的二元关系.
计数
|A|=n,|A×
A|=n2,A×
A的子集有个.所以A上有
个不同的二元关系.
例如|A|=3,则A上有=512个不同的二元关系.
设A为任意集合,
是A上的关系,称为空关系
EA,IA分别称为全域关系与恒等关系,定义如下:
EA={<
|x∈A∧y∈A}=A×
A
IA={<
x,x>
|x∈A}
例如,A={1,2},则
1,1>
1,2>
2,1>
2,2>
}
小于等于关系LA,整除关系DA,包含关系RÍ
定义:
LA={<
|x,y∈A∧x≤y},AÍ
R,R为实数集合
DB={<
|x,y∈B∧x整除y},
BÍ
Z*,Z*为非0整数集
RÍ
={<
|x,y∈A∧xÍ
y},A是集合族.
类似的还可以定义大于等于关系,小于关系,大于关系,真包含关系等等.
例如A={1,2,3},B={a,b},则
1,3>
2,3>
3,3>
DA={<
A=P(B)={Æ
{a},{b},{a,b}},则A上的包含关系是
RÍ
{a}>
{b}>
{a,b}>
{a},{a}>
{a},{a,b}>
{b},{b}>
{b},{a,b}>
{a,b},{a,b}>
二元关系的表示
表示方式:
关系的集合表达式、关系矩阵、关系图
关系矩阵:
若A={a1,a2,…,am},B={b1,b2,…,bn},R是从A到B的关系,R的关系矩阵是布尔矩阵MR=[rij]m´
n,其中rij=1Û
ai,bj>
Î
R.
关系图:
若A={x1,x2,…,xm},R是从A上的关系,R的关系图是GR=<
A,R>
其中A为结点集,R为边集.如果<
xi,xj>
属于关系R,在图中就有一条从xi到xj的有向边.
注意:
A,B为有穷集,关系矩阵适于表示从A到B的关系或者A上的关系,关系图适于表示A上的关系
A={1,2,3,4},
R={<
2,4>
4,2>
},
R的关系矩阵MR和关系图GR如下:
4.2关系的运算
基本运算定义:
定义域、值域和域
domR={x|$y(<
R)}
ranR={y|$x(<
fldR=domRÈ
ranR
例1R={<
4,3>
},则
domR={1,2,4}
ranR={2,3,4}
fldR={1,2,3,4}
逆与合成
R-1={<
|<
R}
R∘S=|<
x,z>
|$y(<
RÙ
y,z>
S)}
例2R={<
1,4>
S={<
3,2>
R-1={<
4,1>
R∘S={<
S∘R={<
定义F在A上的限制
F↾A={<
|xFyÙ
A}
A在F下的像
F[A]=ran(F↾A)
实例R={<
R↾{1}={<
R[{1}]={2,4}
R↾Æ
R[{1,2}]={2,3,4}
F↾AÍ
F,F[A]Í
ranF
基本运算的性质
定理1设F是任意的关系,则
(1)(F-1)-1=F
(2)domF-1=ranF,ranF-1=domF
证
(1)任取<
由逆的定义有
∈(F-1)-1Û
∈F-1Û
∈F
所以有(F-1)-1=F
(2)任取x,
x∈domF-1Û
$y(<
∈F-1)
∈F)Û
x∈ranF
所以有domF-1=ranF.同理可证ranF-1=domF.
定理2设F,G,H是任意的关系,则
(1)(F∘G)∘H=F∘(G∘H)
(2)(F∘G)-1=G-1∘F-1
(F∘G)∘HÛ
$t(<
x,t>
∈F∘G∧<
t,y>
∈H)
$t($s(<
x,s>
∈F∧<
s,t>
∈G)∧<
∈H)
$t$s(<
∈G∧<
$s(<
∈F∧$t(<
∈H))
s,y>
∈G∘H)
∈F∘(G∘H)
所以(F∘G)∘H=F∘(G∘H)
(2)任取<
∈(F∘G)-1
∈F∘G
$t(<
y,t>
∈F∧(t,x)∈G)
∈G-1∧(t,y)∈F-1)
∈G-1∘F-1
所以(F∘G)-1=G-1∘F-1
幂运算
设R为A上的关系,n为自然数,则R的n次幂定义为:
(1)R0={<
|x∈A}=IA
(2)Rn+1=Rn∘R
对于A上的任何关系R1和R2都有
R10=R20=IA
对于A上的任何关系R都有
R1=R
定理3设A为n元集,R是A上的关系,则存在自然数s和t,使得Rs=Rt.
证R为A上的关系,由于|A|=n,A上的不同关系只有个.
当列出R的各次幂
R0,R1,R2,…,,…,
必存在自然数s和t使得Rs=Rt.
定理4设R是A上的关系,m,n∈N,则
(1)Rm∘Rn=Rm+n
(2)(Rm)n=Rmn
证用归纳法
(1)对于任意给定的m∈N,施归纳于n.
若n=0,则有
Rm∘R0=Rm∘IA=Rm=Rm+0
假设Rm∘Rn=Rm+n,则有
Rm∘Rn+1=Rm∘(Rn∘R)=(Rm∘Rn)∘R=Rm+n+1,
所以对一切m,n∈N有Rm∘Rn=Rm+n.
(2)对于任意给定的m∈N,施归纳于n.
(Rm)0=IA=R0=Rm×
0
假设(Rm)n=Rmn,则有
(Rm)n+1=(Rm)n∘Rm=(Rmn)∘Rm=Rmn+m=Rm(n+1)
所以对一切m,n∈N有(Rm)n=Rmn.
4.3关系的性质
自反性
反自反性
定义设R为A上的关系,
(1)若"
x(x∈A→<
R),则称R在A上是自反的.
(2)若"
Ï
R),则称R在A上是反自反的.
反关系:
A上的全域关系EA,恒等关系IA
小于等于关系LA,整除关系DA
反自反关系:
实数集上的小于关系
幂集上的真包含关系
例1A={1,2,3},R1,R2,R3是A上的关系,其中
R1={<
R2={<
R3={<
R2自反,
R3反自反,
R1既不是自反也不是反自反的
对称性
反对称性
(1)若"
x"
y(x,y∈A∧<
∈R→<
∈R),则称R为A上对称的关系.
(2)若x"
∈R∧<
∈R→x=y),则称R为A上的反对称关系.
对称关系:
A上的全域关系EA,恒等关系IA和空关系Æ
反对称关系:
恒等关系IA,空关系是A上的反对称关系.
例2设A={1,2,3},R1,R2,R3和R4都是A上的关系,
其中
},R2={<
},R4={<
R1对称、反对称.
R2对称,不反对称.
R3反对称,不对称.
R4不对称、也不反对称.
传递性
定义设R为A上的关系,若"
y"
z(x,y,z∈A∧<
∈R),
则称R是A上的传递关系.
A上的全域关系EA,恒等关系IA和空关系Æ
小于等于关系,小于关系,整除关系,包含关系,
真包含关系
例3设A={1,2,3},R1,R2,R3是A上的关系,其中
R1和R3是A上的传递关系
R2不是A上的传递关系
关系性质的充要条件
设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在A上自反
任取x,
AÞ
……………..….…….Þ
R
前提推理过程结论
例4证明若IAÍ
R,则R在A上自反.
证任取x,
IAÞ
因此R在A上是自反的.
证明模式证明R在A上对称
任取<
x,y>
RÞ
……………..….…….Þ
例5证明若R=R-1,则R在A上对称.
R-1Þ
因此R在A上是对称的.
证明模式证明R在A上反对称
………..……….Þ
x=y
例6证明若R∩R-1Í
IA,则R在A上反对称.
RÙ
y,x>
R-1
Þ
R∩R-1Þ
因此R在A上是反对称的.
证明模式证明R在A上传递
,<
y,z>
…..……….Þ
例7证明若R°
R,则R在A上传递.
R°
因此R在A上是传递的.
4.4关系的闭包
闭包定义
定义设R是非空集合A上的关系,R的自反(对称或传递)闭包是A上的关系R¢
使得R¢
满足以下条件:
(1)R¢
是自反的(对称的或传递的)
(2)RÍ
R¢
(3)对A上任何包含R的自反(对称或传递)关系R¢
¢
有R¢
Í
.一般将R的自反闭包记作r(R),对称闭包记作s(R),传递闭包记作t(R).
闭包的构造方法
定理1设R为A上的关系,则有
(1)r(R)=R∪R0
(2)s(R)=R∪R-1
(3)t(R)=R∪R2∪R3∪…
说明:
对于有穷集合A(|A|=n)上的关系,(3)中的并最多不超过Rn.若R是自反的,则r(R)=R;
若R是对称的,则s(R)=R;
若R是传递的,则t(R)=R.
设关系R,r(R),s(R),t(R)的关系矩阵分别为M,Mr,Ms和Mt,则
Mr=M+E
Ms=M+M’
Mt=M+M2+M3+…
E是和M同阶的单位矩阵,M’是M的转置矩阵.
注意在上述等式中矩阵的元素相加时使用逻辑加.
设关系R,r(R),s(R),t(R)的关系图分别记为G,Gr,Gs,Gt,则Gr,Gs,Gt的顶点集与G的顶点集相等.除了G的边以外,以下述方法添加新边:
考察G的每个顶点,如果没有环就加上一个环,最终得到Gr.考察G的每
条边,如果有一条xi到xj的单向边,i≠j,则在G中加一条xj到xi的反方向边,最终得到Gs.考察G的每个顶点xi,找从xi出发的每一条路径,如果从xi到路径中任何结点xj没有边,就加上这条边.当检查完所有的顶点后就得到图Gt.
4.5等价关系和偏序关系
定义设R为非空集合上的关系.如果R是自反的、对称的和传递的,则称R为A上的等价关系.设R是一个等价关系,若<
∈R,称x等价于y,记做x~y.
实例设A={1,2,…,8},如下定义A上的关系R:
R={<
|x,y∈A∧x≡y(mod3)}其中x≡y(mod3)叫做x与y模3相等,即x除以3的余数与y除以3的余数相等.
验证模3相等关系R为A上的等价关系,因为
"
x∈A,有x≡x(mod3)
x,y∈A,若x≡y(mod3),则有y≡x(mod3)
x,y,z∈A,若x≡y(mod3),y≡z(mod3),
则有x≡z(mod3)
自反性、对称性、传递性得到验证
定义设R为非空集合A上的等价关系,"
x∈A,令
[x]R={y|y∈A∧xRy}
称[x]R为x关于R的等价类,简称为x的等价类,简
记为[x].
实例A={1,2,…,8}上模3等价关系的等价类:
[1]=[4]=[7]={1,4,7}
[2]=[5]=[8]={2,5,8}
[3]=[6]={3,6}
等价类的性质:
定理1设R是非空集合A上的等价关系,则
(1)"
x∈A,[x]是A的非空子集.
(2)"
x,y∈A,如果xRy,则[x]=[y].
(3)"
x,y∈A,如果xy,则[x]与[y]不交.
(4)∪{[x]|x∈A}=A,即所有等价类的并集就是A.
A={1,2,…,8}上模3等价关系的等价类:
[1]=[4]=[7]={1,4,7},
[2]=[5]=[8]={2,5,8},
以上3类两两不交,
{1,4,7}È
{2,5,8}È
{3,6}={1,2,…,8}
定义设R为非空集合A上的等价关系,以R的所有等价类作为元素的集合称为A关于R的商集,记做A/R,A/R={[x]R|x∈A}
实例A={1,2,…,8},A关于模3等价关系R的商集为
A/R={{1,4,7},{2,5,8},{3,6}}
A关于恒等关系和全域关系的商集为:
A/IA={{1},{2},…,{8}}
A/EA={{1,2,…,8}}
集合的划分:
定义设A为非空集合,若A的子集族π(πÍ
P(A))满足下面条件:
(1)Æ
π
y(x,y∈π∧x≠y→x∩y=Æ
(3)∪π=A
则称π是A的一个划分,称π中的元素为A的划分块.
例1设A={a,b,c,d},
给定π1,π2,π3,π4,π5,π6如下:
π1={{a,b,c},{d}},π2={{a,b},{c},{d}}
π3={{a},{a,b,c,d}},π4={{a,b},{c}}
π5={Æ
{a,b},{c,d}},π6={{a,{a}},{b,c,d}}
则π1和π2是A的划分,其他都不是A的划分.
等价关系与划分的一一对应
商集A/R就是A的一个划分
不同的商集对应于不同的划分
任给A的一个划分π,如下定义A上的关系R:
R={<
|x,y∈A∧x与y在π的同一划分块中}
则R为A上的等价关系,且该等价关系确定的商集就是π.
例2给出A={1,2,3}上所有的等价关系
求解思路:
先做出A的所有划分,然后根据划分写
出对应的等价关系.
例3设A={1,2,3,4},在A´
A上定义二元关系R:
RÛ
x+y=u+v,
求R导出的划分.
解A´
3,1>
3,4>
4,4>
根据<
的x+y=2,3,4,5,6,7,8将A´
A划分成7个
等价类:
(A´
A)/R={{<
},{<
{<
},
4,4>
}}
定义非空集合A上的自反、反对称和传递的关系,称为A上的偏序关系,记作≼.设≼为偏序关系,如果<
∈≼,则记作x≼y,读作x“小于或等于”y.
实例
集合A上的恒等关系IA是A上的偏序关系.
小于或等于关系,整除关系和包含关系也是相应集合上的偏序关系.
x与y可比:
设R为非空集合A上的偏序关系,
x,yÎ
A,x与y可比Û
x≼y∨y≼x.
结论:
任取两个元素x和y,可能有下述情况:
x≺y(或y≺x),x=y,x与y不是可比的.
全序关系:
R为非空集合A上的偏序,"
x,yÎ
A,x与y都是可比的,则称R为全序(或线序)
数集上的小于或等于关系是全序关系
整除关系不是正整数集合上的全序关系
覆盖:
设R为非空集合A上的偏序关系,x,y∈A,如果x≺y且不存在zÎ
A使得x≺z≺y,则称y覆盖x.
{1,2,4,6}集合上的整除关系,
2覆盖1,
4和6覆盖2.
4不覆盖1.
定义集合A和A上的偏序关系≼一起叫做偏序集,记作<
A,≼>
.
整数集和小于等于关系构成偏序集<
Z,≤>
,幂集P(A)和包含关系构成偏序集<
P(A),RÍ
.
哈斯图:
利用偏序自反、反对称、传递性简化的关系图
特点:
每个结点没有环,两个连通的
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 第四 二元关系 函数 知识点 总结
![提示](https://static.bingdoc.com/images/bang_tan.gif)