西南科技大学
5
计算机科学与技术学院
Discrete Mathematics
定义的有关说明:
1. R与S能进行合成的必要条件是R的后域B一定是 S的前域B，否则就不能合成。 2. <x,z>有合成关系的定义为：至少有一个做中间 桥梁的元素y属于B，使x,y有关系R，y,z有关系S。 例1 设A={1,2,3,4,5}，B={3,4,5}，C={1,2,3}
西南科技大学
15
计算机科学与技术学院
Discrete Mathematics 证明：(1)<x,z>∈R (S∪T) ⇔y(y∈B ∧<x,y>∈R∧<y,z>∈S∪T)
⇔y(y∈B ∧<x,y>∈R∧ (<y,z>∈S∨<y,z>∈T))
⇔ y(y∈B ∧ <x,y>∈R∧<y,z>∈S)∨ y(y∈B ∧ <x,y>∈R∧<y,z>∈T) ⇔ <x,z>∈R S∨<x,z>∈R T ⇔ <x,z>∈R S∪R T 从而有： R S∪R T= R (S∪T)
∵<3,3>R,<3,1>S,∴<3,1>RS
从而：RS={<1,3>,<2,2>,<3,1>}
用数学方法推导即为:
∵x+y=6，y-z=2，消去y得x+z=4
西南科技大学
7
计算机科学与技术学院
Discrete Mathematics
关系图为: 1 2 3 4 A → B 3 4 5 → C 1 2 3
西南科技大学
14
计算机科学与技术学院
Discrete Mathematics (3)合成关系的性质 ① 合成运算对∪,∩的分配律
定理 设R是从集合A到B的关系，S和T均为B到C 的关系。U是C到D的关系，则有
(1). R(S∪T)=R S∪R T； (2). R(S∩T) R S∩R T； (3). (S∪T) U=S U∪T U； (4). (S∩T) U S U∩T U；
S R= {<d,b> ,<c,b>}
R R= {<a,b>,<b,b>}
S S= {<d,e>}
从这个例子可以看出：
R SS R，即合成运算不成立交换律。
西南科技大学
9
计算机科学与技术学院
Discrete Mathematics 例3 设Z是整数集合，R，S是Z到Z的两个关系：
西南科技大学
16
计算机科学与技术学院
Discrete Mathematics (4)设A＝{a},B＝{b1,b2},C＝{c},关系S，T，U定 义为，S、T是A到B的关系，U是B到C的关系， S＝{<a,b1>}, T＝{<a,b2>}, U＝{<b1,c>,<b2,c>}。 则由于：S∩T＝Φ,所以： (S∩T)U＝ΦU＝Φ, 但：SU＝{<a,c>}，TU＝{<a,c>}， 所以：(SU)∩(TU)＝{<a,c>}， (S∩T)U(SU)∩(TU)， 即：(SU)∩(TU)≠(S∩T)U。
西南科技大学
17
计算机科学与技术学院
Discrete Mathematics
② 合成运算成立结合律
定理 设 R，S，T分别是A到B，B到C，C到D的关 系， 则有(R S) T = R (S T)。 证明：略
西南科技大学
18
计算机科学与技术学院
Discrete Mathematics (4)关系的幂 定义 设R是A上的二元关系，n∈N，则关系R的n次 幂Rn定义为： (1). R0 =A是A上的恒等关系，即R0={<x,x>|xA}； (2). R1=R (3). Rn+1=Rn R
西南科技大学
3
计算机科学与技术学院
Discrete Mathematics
2
关系的合成运算
引例：甲、乙、丙三人，设甲和乙是兄妹关系，乙
和丙是母子关系，则甲和丙是舅甥关系。
可利用“关系”的概念来表示以上联系：
如R表示兄妹关系，S表示母子关系，则舅甥关
系T是由关系R与S合成的。
再如： R 表示父子关系， R 与 R 合成则是祖孙关系。
则关系R的各次幂为：
R0 =A ={<1,1>，<2,2>，<3,3>，<4,4>，<5,5>}
R1=R
R2= R R={<1,1>，<2,2>，<1,3>，<2,4>，<3,5>} R3=R2 R={<1,2>，<2,1>，<1,4>，<2,3>，<2,5>} R4= R3 R={<1,1>，<2,2>，<1,5>，<2,4>，<1,3>} R5=R4 R={<1,2>，<1,4>，<2,1>，<2,3>，<2,5>}
0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0
MS=
0 0 0 0 0 0 1 0
0 0 1 0 0 0 0 0
0 0 0 1 1 1 0 0
1 0 0 0
0 1 0 0
则，MR S= MR ×MS =
Discrete Mathematics
第四章 二元关系
4.4 关系的运算
西南科技大学
1
计算机科学与技术学院
Discrete Mathematics
1
关系的交、并、补、差运算
设R，S都是集合A到B的两个关系，则： R∪S＝{<x,y>|(xRy)∨(xSy)} R∩S＝{<x,y>|(xRy)∧(xSy)} R-S＝{<x,y>|(xRy)∧(xSy)} R＝{<x,y>|(xRy)} 根 据 定 义 ， 由 于 A ×B 是 相 对 于 R 的 全 集 ， 所 以
R ＝A×B-R,且 R∪R＝A×B, R ∩R＝Φ。
西南科技大学
2
计算机科学与技术学院
Discrete Mathematics
例 设 A＝{a,b,c},B＝{1,2}，A上的关系 R＝{<a,1>,<b,2>,<c,1>}， S＝{<a,1>,<b,1>,<c,1>}， 则： R∪S＝{<a,1>,<b,2>,<c,1>，<b,1>}； R∩S＝{<a,1>,<c,1>}； R-S＝ {<b,2>}； R ＝{<a,2>,<b,1>,<c,2>}＝A×B-R。
R是A到B的关系，且R={<x,y>|x+y=6}，
S是B到C的关系，且S={<y,z>y-z=2} 。
求RS
西南科技大学
6
计算机科学与技术学院
Discrete Mathematics 只需从两个关系的二重组中搜索： ∵<1,5>∈R,<5,3>∈S,∴<1,3>∈RS
∵<2,4>R,<4,2>S,∴<2,2>RS
2n
2
都是A上的二元关系且有
2 +1个。
因此，R的这些幂中至少有两个是相等的。
n2
西南科技大学
23
计算机科学与技术学院
Discrete Mathematics 定理 设A是集合，R A×A，若有i，j∈N，i＜j，
使得Ri=Rj，则有
⑴. 对任何k∈N，有Ri+k=Rj+k;
⑵. 对任何k,m∈N，有Ri+md+k=Ri+k(d=j-i);
⑶. 对任意n∈N， Rn ∈{R0,R1,…,Rj-1}; 证明： (1) Ri+k＝Ri Rk＝Rj Rk＝Rj+k
10
计算机科学与技术学院
Discrete Mathematics (2)合成关系的关系矩阵 定理 设有集合
A={a1,…,am}，B={b1,…,bn}，C={C1,…, CP}
R是A到B的关系，其关系矩阵MR是m×n阶矩阵。
S是B到C的关系，其关系矩阵MS是n×p阶矩阵。
合成关系R S是A到C的关系，其关系矩阵
而 MS R = MS × M R = 验证：R S={<a,d>,<b,d>,<c,b>} S R={<a,d>,<c,b>,<d,b>}
西南科技大学
0 0 0 0
0 0 1 1
0 0 0 0
1 0 0 0
12
计算机科学与技术学院
Discrete Mathematics 例2 设 R＝{<1,2>,<3,4>,<2,2>} S＝{<4,2>,<2,3>,<3,1>}， 分别是定义为从A到B和从B到C的二元关系， 其中A＝B＝C＝{1,2,3,4}。 RS＝{<1,3>,<3,2>,<2,3>}；
西南科技大学
21
计算机科学与技术学院
Discrete Mathematics 从关系图来看关系的n次幂 R：
1 2 3 4 5
1
2
3
4
5
R2：
R2就是从R的关系图中的任何一个结点x出发，长 为2的路径，如果路径的终点是y，则在R2 的关系 图中有一条从x到y的有向边。其他以次类推： R3：
1 2 3 4 5
5 从而RS的关系图
1 2 3 4 1 2 3 8 计算机科学与技术学院
5
西南科技大学
Discrete Mathematics 例2 集合A={a,b,c,d,e}，A上的关系R、S分别为 R={<a,b>,<c,d>,<b,b>}，S={<d,b>,<b,e>,<c,a>}
则：R S= {<a,e>,<c,b>,<b,e>}
Rm Rk+1＝ Rm (Rk R)＝ (Rm Rk) R＝Rm+k+1， 所以对一切m,n∈N有： Rm Rn＝Rm+n。 西南科技大学 计算机科学与技术学院 20
Discrete Mathematics 例 设A={1,2,3,4,5}，A上关系R为 R={<1,2>，<2,1>，<2,3>，<3,4>，<4,5>}。
西南科技大学
4
计算机科学与技术学院
Discrete Mathematics (1)合成关系的定义
定义 设A,B,C是三个集合，R是A到B的关系，S是B
到C的关系，则R与S的合成关系是一个A到C的关
系，记作RS。定义为：
RS=
{<x,z>xA∧zC∧y(yB∧<x,y>R∧<y,z>S)}
R＝{<x,3x>|x∈Z}；
S＝{<x,5x>|x∈Z}。 则： RS＝{<x,15x>|x∈Z} SR＝{<x,15x>|x∈Z}
RR＝{<x,9x>|x∈Z} SS＝{<x,25x>|x∈Z}
(RR)R＝ {<x,27x>|x∈Z} (RS)R＝ {<x,45x>|x∈Z}
西南科技大学
3).用关系矩阵求RS。
MR S ＝ MR × MS
0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 × 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 Hale Waihona Puke Baidu 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0
1
2
3
4
5
R4：
西南科技大学
22
计算机科学与技术学院
Discrete Mathematics 定理 设|A|=n，R A×A，则必有i，j∈N，
0≤i＜j≤2n ，使得Ri=Rj。
证明：因为|A×A|=n2，则ρ(A×A)= 2
n2 n2
2
即A上有 2 个不同的二元关系。
而R0、R1、R2、„、R
1).用定义方法求RS，SR，RR，SS。则： SR＝{<4,2>,<2,4>,<3,2>}；
RR＝{<1,2>,<2,2>}；
SS＝{<4,3>,<2,1>}。
西南科技大学
13
计算机科学与技术学院
Discrete Mathematics
2).用关系图 求RS。 A 1。 2。 3。 4。 R B 。1 。2 。3 。4 S C 。1 。2 。3 。4 A 1。 2。 3。 4。 RS C 。1 。2 。3 。4
西南科技大学
19
计算机科学与技术学院
Discrete Mathematics 定理 设R是集合A上的关系，m,n∈N，则有 （1） Rm Rn=Rm+n
（2）(Rm)n=Rmn
此定理证明可以用数学归纳法来证明。
证明：(1)对于任意给定的m∈N。
若n=0，则有 Rm R0＝ Rm IA＝ Rm＝ Rm+0 假设Rm Rk=Rm+k，则有
MR S是m×p阶矩阵，且满足MR S=MR×MS
其中×是按布尔运算进行的矩阵乘法。
西南科技大学
11
计算机科学与技术学院
Discrete Mathematics 例1 设集合A={a,b,c,d}，R={<a,b>,<c,d>,<b,b>}， 0S={<d,b>,<b,d>,<c,a>,<a,c>}，则 MR =
