离散数学-3-7 复合关系和逆关系

证： 1)<x, y>∈(S∪T)C⇔<y, x>∈S∪T ⇔<y, x>∈S∨<y, x>∈T ⇔<x, y>∈S C ∨<x, y>∈ T c ⇔<x, y>∈S C ∨T C 4)<x, y>∈(∼R) C⇔<y, x>∈∼R ⇔<y, x>∉R⇔<x, y>∉R C ⇔<x, y>∈(∼R) C 5)因S－T＝S∩∼T，故 (S-T) C =( S∩∼T) C =S C ∩(∼T) C =S C ∩∼T C =S C -T C
13
例
例 设X=1,2,3,4，Y=a,b,c，X到Y二元关系
R=<1,a>,<2,b>,<4,c>， ⑴试求RC，写出MR和 M R C ，验证 M R C =MRT ⑵画出R和RC 的关系图，验证将R关系图中的弧线的箭 头反置可得到RC关系图。 解：RC=<a,1>,<b,2>,<c,4> R和RC的关系矩阵是： 1 0 0 1 0 0 0 0 1 0 M R C = 0 1 0 0 MR= 0 0 0 0 0 0 1 0 0 1 显然， M R C =MRT
12
二、关系的逆
*关于R C的图形，是R的图形中将其弧线的箭头反置 即得，而R C的关系矩阵是R的关系矩阵的转置。
例：X={a, b, c}其上二元关系R关系阵为
1 0 1 1 1 0 1 1 1
C
则R 的关系阵为
1 1 1 0 1 1 1 0 1
10
二、关系的逆
定理3.7.3 定理3.7.3 设R为X上的二元关系，则： 1）R是对称的，当且仅当R＝R C； 2）R是反对称的，当且仅当R∩R C ⊆IX。 证：1）∵R对称，故 <x, y>∈R⇔<y, x>∈R⇔<x, y>∈R C, 故R＝R C 反之R C＝R，则 <x, y>∈R⇔<y, x>∈R C⇔<y, x>∈R，即R对 称。
0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0
5
例
0 0 MR ∘ MS= 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 ∘ 1 0 0
第三章 集合与关系
3-7 复合关系和逆关系 授课人：李朔 Email:chn.nj.ls@
1
一．关系的复合
二元关系是以序偶为元素的集合，可以进行集合运算，产 生新的集合，本课介绍关系的一种新的运算，关系的复合。 定义3.7.1 定义3.7.1 设R为X到Y的关系，S为从Y到Z的关系，则 RоS称为R和S的复合关系 复合关系，表示为 复合关系 RоS＝ z> ∃∧y(y y(y∈ y>∈ z>∈ RоS＝{<x, z>x∈X∧z∈Z∃∧y(y∈Y∧<x, y>∈R∧<y, z>∈S) 易见RоS是从X到Z的关系。 *从R和S，求RоS称为关系的合成运算 关系的合成运算。 关系的合成运算 合成运算由两个关系生成一个新的关系 P114例如 例如： 是关系“ 是 兄弟 兄弟” 是关系“ 是 *P114例如：R1是关系“…是…兄弟”，R2是关系“…是… 父亲” 那么R 是关系“ 是 的叔伯” 父亲”，那么 1оR2是关系“…是……的叔伯” 的叔伯 R1是关系 是关系“ 是 的父亲” 那么R 是关系“ 若R1是关系“…是……的父亲”，那么 1оR2是关系“… 的父亲 的祖父” 是…的祖父” 的祖父
0 1 0 0 0 0 0 0 1 0 0 0 0 0 = 0 1 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0
所以MR ∘ S=MR ∘ MS
6
二、关系的逆
关系是序偶的集合，由于序偶的有序性， 关系是序偶的集合，由于序偶的有序性，关系还 有一些特殊的运算。 有一些特殊的运算。 定义3.7.2 P117 定义3.7.2 设R为X到y的二元关系，如将R 中每一序偶的元素顺序互换，所得的集称为R的逆 R 关系，记为Rc，即：Rc={<y, x><x, y>∈R} 关系 例如：R={<1,a>,<2,b>,<3,c>} 则 Rc ={<a,1>,<b,2>,<c,3>} 易见 (Rc)c = R 又如集合Z上，关系“<”的逆关系是“>”
7
二、关系的逆
定理3.7.1 P117 定理3.7.1 设R，S，T都是从A到B的 二元关系，则 1）(S∪T)C=SC∪TC 2）(S∩T)C =SC∩TC 3）(A×B)C =B×A 4）(∼R)C =∼RC (∼R=A×B-R, ∼RC=B×A-RC) 5）(S-T)C =SC－TC

8
二、关系的逆
11
二、关系的逆
定理3.7.3 定理3.7.3 设R为X上的二元关系，则： 1）R是对称的，当且仅当R＝R C； 2）R是反对称的，当且仅当R∩R C ⊆IX。 证：2）设R反对称 ∀<x,y>∈R∩R C 则 <x,y>∈R且<x,y>∈ R C 故有<y,x>∈R ∴x=y 即 <x,y>∈IX ∴R∩RC ⊆IX, 反之设R∩R C ⊆IX ∀<x,y>∈R且<y,x>∈R 则 <x,y>∈ R C ∴<x,y>∈R∩R C 即有<x,y>∈IX ∴x=y ∴ R是反对称的。
2
一．关系的复合
例题1：R={<1,2>,<3,4>,<2,2>},S={<4,2>,<2,5>,<3,1>} 则 RоS={<1,5>,<3,2>,<2,5>} SоR={<4,2>,<3,2>} (RоS)оR=? Rо(SоR)=? SоS={<4,5>} RоR={<1,2>,<2,2>} RоRоR={<1,2>,<2,2>} 可以证明，关系的复合运算满足结合律，即： （RоS）оT＝Rо（SоT） 故可记为 ＝RоSоT P115 例题2 *当R与自己复合时，记RоR＝R2。 记RоR＝ 一般定义 Rn+1=RnоR
3
一．关系的复合
例：设X={0,1,2,3}, 则 R={<0,1>,<1,2>,<2,3>,<0,0>,<2,1>} R2=RоR=? {<0,2>,<1,3>,<1,1>,<0,1>,<0,1>,<0,0>,<2,2>} R3= R2оR =? {<0,3>,<0,1>,<1,2>,<0,2>,<0,0>,<2,3>,<2,1>}
14
例
R和RC 的关系图分别是图1和图2，它们中的弧线的方 向是相反的。
15
本课小结
关系的复合 关系的逆
16
作业
P119 (6)(7)
17
0 0 MR=0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 MS= 1 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0
0 0 MR ∘ S= 0 0 0
*关系可用矩阵表示，故复合关系亦可用矩阵表示。 （类似矩阵乘法，但采用逻辑加）P115
4
例
A=1,2,3,4,5，A上的二元关系R和S定义如下： R=<1,2>,<2,2>,<3,4> S=<1,3>,<2,5>,<3,1>,<4,2> 试求MR ∘ S和MR ∘ MS，它们是否相等 ? 解：按照R 和S的定义，求出 R∘S=<1,5>,<2,5> ,<3,2> 写出R 、S和R ∘ S关系矩阵如下： 例题3 例题
9
二、关系的逆
定理3.7.2 P117 定理3.7.2 设T为从X到Y的关系，S为从Y 到Z的关系，则（TоS）C＝S CоT C （TоS） 证：<z, x>∈（TоS）C ⇔<x, z>∈TоS ⇔∃y(y∈Y∧<x, y>∈T∧<y, z>∈S) ⇔∃y(y∈Y∧<y, x>∈T C ∧<z, y>∈S C) ⇔<z, x>∈S CоT C