中国科学技术大学：《离散数学》课程教学资源（PPT课件讲稿）关系

上例中 y3 Y2 1 R S 00 0000 01 1 Z R。S M。=001 1101「0101「011 M。=010|o001|=001 RoS 三M1R 0000011000 11

11 上例中： 1 1 0 0 1 0 0 0 0 MR        0 1 0 0 0 1 0 0 1 Ms        1 1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 1 MR S MR MS                      0 1 1 0 0 1 0 0 0       

定理21设R、S、T分别表示从X到Y、Y到Z、Z 到U的关系,则有:(RS)T=R(S7)结合律 证明:先证明(RoS)T≤Ro(SoT 设(x:)∈(ReS)7,则必然存在至少一个z∈Z, 有 x,z)∈RoS 且( z,l)∈T5 则必然至少存在一个 奶肯)∈S(al,则必有(01)E5eso Y 有 y∈ )∈R 因为 且(y,u)∈ST,则必有 即证明 y)∈R (x,)∈Ro(So7) 证明。(RS)7≤R(S7)yS2 的号法类秘(RS)TB 12

12 R S T   R  S T R  S T  R  S T  R  S T  R S T   x,uR  S T z Z  x,z R  S z,uT y Y  y,zS  y,z S z,uR  x, y R  x,uR S T  R  S T  R S T   x, y R 结合律

口关系的幂运算 由于关系中的复合运算满足结合律,所以复合运算 的括号可以省去,即:(RS)7=R(ST)=RoST 说明关系的幂运算是有意义的: R"=强9强9449 n个 容易证明: R"R"=R"(R")=Rn,mn均为正整数 i:R是相等关系,即: R0=X,X)|X∈A} ii: R=R 13

13 ¨关系的幂运算 由于关系中的复合运算满足结合律，所以复合运算 的括号可以省去，即： 说明关系的幂运算是有意义的： 容易证明： i: ，m,n均为正整数 ii: 是相等关系，即： R0 ={(x,x)|x∈A} iii: R  ST  R  S T  R  S T 0 R 1 R  R ,  n n m n m m m n R R R R R      n n R  1R4o44R42oL444o44R3 个

逆关系 由于关系中的元素是有序偶,则如果将该有序偶的顺 序颠倒,会得到一个新的关系,我们称之为逆关系。 口定义25设R是一个从X到Y的关系 R={(xy)x∈X,yey 则从Y到X的关系R称为R的逆关系 R={(yx)(xy)∈R 14

14 Ø逆关系 由于关系中的元素是有序偶，则如果将该有序偶的顺 序颠倒，会得到一个新的关系，我们称之为逆关系。 ¨ 定义2.5设R是一个从X到Y的关系 则从Y到X的关系 称为R的逆关系 ~R R   x, y | x X , y Y      ~R  y, x | x, y  R

■关于逆关系的一些说明 口空关系的逆关系是空关系; 口设关系R的关系矩阵为M2,则M的转置M,就是逆 关系R的关系矩阵; 即:M.=M 口将R的关系图每条有向边的箭头方向颠倒,就得到R的 关系图。 15

15 n 关于逆关系的一些说明： ¨ 空关系的逆关系是空关系； ¨ 设关系R的关系矩阵为 ，则 的转置 ，就是逆 关系 的关系矩阵； n 即： ¨ 将R的关系图每条有向边的箭头方向颠倒，就得到 的 关系图。 MR MR T MR ~R ~ T R R M  M ~R