离散数学第四章二元关系和函数知识点总结.docx
《离散数学第四章二元关系和函数知识点总结.docx》由会员分享，可在线阅读，更多相关《离散数学第四章二元关系和函数知识点总结.docx（29页珍藏版）》请在冰点文库上搜索。
离散数学第四章二元关系和函数知识点总结
集合论部分
第四章、二元关系和函数
4.1集合的笛卡儿积与二元关系有序对
定义由两个客体x和y，按照一定的顺序组成的
二元组称为有序对，记作
实例：
点的直角坐标（3,-4）
有序对性质
有序性¹（当x¹y时）
与相等的充分必要条件是=Ûx=uÙy=v
例1<2,x+5>=<3y-4,y>，求x,y.
解3y-4=2,x+5=yÞy=2,x=-3
定义一个有序n（n³3）元组是一个
有序对，其中第一个元素是一个有序n-1元组，即
=<,xn>
当n=1时,形式上可以看成有序1元组.
实例n维向量是有序n元组.
笛卡儿积及其性质
定义设A,B为集合，A与B的笛卡儿积记作A´B，即A´B={|xÎAÙyÎB}
例2A={1,2,3},B={a,b,c}
A´B={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>,
<3,a>,<3,b>,<3,c>}
B´A={,,,,,,
,,}
A={Æ},P（A）´A={<Æ,Æ>,<{Æ},Æ>}
性质：
不适合交换律A´B¹B´A（A¹B,A¹Æ,B¹Æ）
不适合结合律（A´B）´C¹A´（B´C）（A¹Æ,B¹Æ）
对于并或交运算满足分配律
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）
若A或B中有一个为空集，则A´B就是空集.
A´Æ=Æ´B=Æ
若|A|=m,|B|=n,则|A´B|=mn
证明A´（BÈC）=（A´B）È（A´C）
证任取
∈A×（B∪C）
Ûx∈A∧y∈B∪C
Ûx∈A∧（y∈B∨y∈C）
Û（x∈A∧y∈B）∨（x∈A∧y∈C）
Û∈A×B∨∈A×C
Û∈（A×B）∪（A×C）
所以有A×（B∪C）=（A×B）∪（A×C）.
例3
（1）证明A=BÙC=DÞA´C=B´D
（2）A´C=B´D是否推出A=BÙC=D?
为什么？
解
（1）任取
ÎA´CÛxÎAÙyÎC
ÛxÎBÙyÎDÛÎB´D
（2）不一定.反例如下：
A={1}，B={2},C=D=Æ,则A´C=B´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∈A}
例如,A={1,2},则
EA={<1,1>,<1,2>,<2,1>,<2,2>}
IA={<1,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},则
LA={<1,1>,<1,2>,<1,3>,<2,2>,<2,3>,<3,3>}
DA={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>}
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ÛÎR.
关系图：
若A={x1,x2,…,xm}，R是从A上的关系，R的关系图是GR=,其中A为结点集，R为边集.如果属于关系R，在图中就有一条从xi到xj的有向边.
注意：
A,B为有穷集，关系矩阵适于表示从A到B的关系或者A上的关系，关系图适于表示A上的关系
A={1,2,3,4},
R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>},
R的关系矩阵MR和关系图GR如下：
4.2关系的运算
基本运算定义：
定义域、值域和域
domR={x|$y（ÎR）}
ranR={y|$x（ÎR）}
fldR=domRÈranR
例1R={<1,2>,<1,3>,<2,4>,<4,3>},则
domR={1,2,4}
ranR={2,3,4}
fldR={1,2,3,4}
逆与合成
R-1={|ÎR}
R∘S=||$y（ÎRÙÎS）}
例2R={<1,2>,<2,3>,<1,4>,<2,2>}
S={<1,1>,<1,3>,<2,3>,<3,2>,<3,3>}
R-1={<2,1>,<3,2>,<4,1>,<2,2>}
R∘S={<1,3>,<2,2>,<2,3>}
S∘R={<1,2>,<1,4>,<3,2>,<3,3>}
定义F在A上的限制
F↾A={|xFyÙxÎA}
A在F下的像
F[A]=ran（F↾A）
实例R={<1,2>,<2,3>,<1,4>,<2,2>}
R↾{1}={<1,2>,<1,4>}
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）
Û$y（∈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
证
（1）任取,
Î（F∘G）∘HÛ$t（∈F∘G∧∈H）
Û$t（$s（∈F∧∈G）∧∈H）
Û$t$s（∈F∧∈G∧∈H）
Û$s（∈F∧$t（∈G∧∈H））
Û$s（∈F∧∈G∘H）
Û∈F∘（G∘H）
所以（F∘G）∘H=F∘（G∘H）
（2）任取,
∈（F∘G）-1
Û∈F∘G
Û$t（∈F∧（t,x）∈G）
Û$t（∈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.
若n=0,则有
（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）若"x（x∈A→ÏR）,则称R在A上是反自反的.
实例：
反关系：
A上的全域关系EA,恒等关系IA
小于等于关系LA,整除关系DA
反自反关系：
实数集上的小于关系
幂集上的真包含关系
例1A={1,2,3},R1,R2,R3是A上的关系,其中
R1＝{<1,1>,<2,2>}
R2＝{<1,1>,<2,2>,<3,3>,<1,2>}
R3＝{<1,3>}
R2自反,
R3反自反,
R1既不是自反也不是反自反的
对称性
反对称性
定义设R为A上的关系,
（1）若"x"y（x,y∈A∧∈R→∈R）,则称R为A上对称的关系.
（2）若x"y（x,y∈A∧∈R∧∈R→x=y）,则称R为A上的反对称关系.
实例：
对称关系：
A上的全域关系EA,恒等关系IA和空关系Æ
反对称关系：
恒等关系IA，空关系是A上的反对称关系.
例2设A＝{1,2,3},R1,R2,R3和R4都是A上的关系,
其中
R1＝{<1,1>,<2,2>}，R2＝{<1,1>,<1,2>,<2,1>}
R3＝{<1,2>,<1,3>}，R4＝{<1,2>,<2,1>,<1,3>}
R1对称、反对称.
R2对称，不反对称.
R3反对称，不对称.
R4不对称、也不反对称.
传递性
定义设R为A上的关系,若"x"y"z（x,y,z∈A∧∈R∧∈R→∈R）,
则称R是A上的传递关系.
实例：
A上的全域关系EA,恒等关系IA和空关系Æ
小于等于关系,小于关系，整除关系，包含关系，
真包含关系
例3设A＝{1,2,3},R1,R2,R3是A上的关系,其中
R1＝{<1,1>,<2,2>}
R2＝{<1,2>,<2,3>}
R3＝{<1,3>}
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ÍR
证明模式证明R在A上自反
任取x,
xÎAÞ……………..….…….ÞÎR
前提推理过程结论
例4证明若IAÍR，则R在A上自反.
证任取x,
xÎAÞÎIAÞÎR
因此R在A上是自反的.
证明模式证明R在A上对称
任取
ÎRÞ……………..….…….ÞÎR
前提推理过程结论
例5证明若R=R-1,则R在A上对称.
证任取
ÎRÞÎR-1ÞÎR
因此R在A上是对称的.
证明模式证明R在A上反对称
任取
ÎRÙÎRÞ………..……….Þx=y
前提推理过程结论
例6证明若R∩R-1ÍIA,则R在A上反对称.
证任取
ÎRÙÎRÞÎRÙÎR-1
ÞÎR∩R-1ÞÎIAÞx=y
因此R在A上是反对称的.
证明模式证明R在A上传递
任取，
ÎRÙÎRÞ…..……….ÞÎR
前提推理过程结论
例7证明若R°RÍR,则R在A上传递.
证任取，
ÎRÙÎRÞÎR°RÞÎR
因此R在A上是传递的.
4.4关系的闭包
闭包定义
定义设R是非空集合A上的关系,R的自反（对称或传递）闭包是A上的关系R¢,使得R¢满足以下条件：
（1）R¢是自反的（对称的或传递的）
（2）RÍR¢
（3）对A上任何包含R的自反（对称或传递）关系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]=[6]={3,6}
以上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）ÆÏπ
（2）"x"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´A={<1,1>,<1,2>,<1,3>,<1,4>,<2,1>,<2,2>,
<2,3>,<2,4>,<3,1>,<3,2>,<3,3>,<3,4>,<4,1>,
<4,2>,<4,3>,<4,4>}
根据的x+y=2,3,4,5,6,7,8将A´A划分成7个
等价类：
（A´A）/R={{<1,1>},{<1,2>,<2,1>},
{<1,3>,<2,2>,<3,1>},
{<1,4>,<2,3>,<3,2>,<4,1>},
{<2,4>,<3,3>,<4,2>},
{<3,4>,<4,3>},{<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上的偏序关系≼一起叫做偏序集,记作.
实例：
整数集和小于等于关系构成偏序集，幂集P（A）和包含关系构成偏序集.
哈斯图：
利用偏序自反、反对称、传递性简化的关系图
特点：
每个结点没有环，两个连通的
升级会员 