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

关系 ■关系的基本概念 口关系及其定义 ■对现实中关系的一种抽象描述 集合内元素之间或集合集合间元素之间 口例21: 设一个旅馆有n个房间,每个房间可住两个 旅客,因此一共可以住2n个客人; 的关系,该关系可描述为“某旅客住在某 ■则在旅馆内,旅客和房间之间就存在一定 房间”用R表示该关系

1 n 关系的基本概念 ¨ 关系及其定义 n 对现实中关系的一种抽象描述 n 集合内元素之间或集合集合间元素之间 ¨ 例2.1： n 设一个旅馆有n个房间，每个房间可住两个 旅客，因此一共可以住2n个客人； n 则在旅馆内，旅客和房间之间就存在一定 的关系，该关系可描述为“某旅客住在某 房间”用R表示该关系

设n=3,用1、2、3分别表示3个房间 用a、b、c、d、e、f分别表示6个旅客 则用如下示意图可表示: abcdef 2 由图可知: 旅客a与房间1之间存在关系R,记作aR1 旅客a与房间2之间不存在关系R,记作a2

2 设n=3， 用1、2、3分别表示3个房间 用a、b、c、d、e、f分别表示6个旅客 则用如下示意图可表示： a b 1 c d 2 e f 3 由图可知： 旅客a与房间1之间存在关系R，记作aR1 旅客a与房间2之间不存在关系R，记作aR2

■定义21:从集合A到集合B的二元关系R是笛卡尔 积AXB的一个子集; 口关系R中的有序偶的第一个客体可允许选取对象的集合 称为R的定义域,记作D(R),第二个客体可允许选取对 象的集合称为R的值域,记作C(R); 口当D(R)=C(R)=M(M为集合)时,称关系R为集合M上 的关系。 口说明:关系的元素是有序偶

3 n 定义2.1：从集合A到集合B的二元关系R是笛卡尔 积A×B的一个子集； ¨ 关系R中的有序偶的第一个客体可允许选取对象的集合 称为R的定义域，记作D(R)，第二个客体可允许选取对 象的集合称为R的值域，记作C(R)； ¨ 当D(R)=C(R)=M（M为集合）时，称关系R为集合M上 的关系。 ¨ 说明：关系的元素是有序偶

由例21可知: A={a、b、c、d、e、f B R={(a,1)(b,1),(C,2),(d,2),(e,3)、f,3) D(R=A C(R=B 设另一个关系为“某旅客和某旅客同房间”,用R表示 JIR'=(a, b ) (c, d), (e, ) (b, a), (d, c), (f, e)1 D(R)=C(R)=A,R为集合A上的关系 注意:在R中,(a,b)和(b,a)都要写出来

4 由例2.1可知： A={a、b、c、d、e、f} B={1、2、3} R={(a,1),(b,1),(c,2),(d,2),(e,3),(f,3)} D(R)=A C(R)=B 设另一个关系为“某旅客和某旅客同房间” ，用R’表示 则R’={(a,b),(c,d),(e,f),(b,a),(d,c),(f,e)} D(R’)=C(R’)=A， R’为集合A上的关系 注意：在R’中，(a,b)和(b,a)都要写出来

■几种特殊的关系(即为A×B的两个平凡子集) 口空关系: 口全关系:AXB 全域关系,所有的元素之间都存在关系 ■定义22:由集合X1,X2…,Mn可确定的n元关系是 X1X2×…×Xn的一个子集 注:本课程如果只说关系,则缺省为2元关系

5

关系的表示方法 ■图形法 口如例21中的示意图; 口用平面上的点来表示定义域和值域; 口如果(ab)∈R,则画一条从到b的有向边; 口如果同时存在(b)∈R(ba)∈R,则画两条边a→>bb→a 口如果(a,a)∈R,则画一个从a出发指向自身的环。 a R=(111223)}1 b 两个集合之间的关系

6 a,b R a,bR,b,aR ab,ba a,aR n 图形法 ¨ 如例2.1中的示意图； ¨ 用平面上的点来表示定义域和值域； ¨ 如果 ，则画一条从a到b的有向边； ¨ 如果同时存在 ，则画两条边 ¨ 如果 ，则画一个从a出发指向自身的环。 R={(1,1),(1,2),(2,3)} 两个集合之间的关系

矩阵表示法 ■该矩阵称为关系矩阵,关系R的关系矩阵用M2表示 ■在关系运算中广泛应用 110其中m取值0或,表示(aa)之间量的存在关系 R=001(R是A上的关系)或表示(a,b,)之间的存在关系 000(R是A到B的关系) 1.A=n,B=m时,M为nxm矩阵 2.当R为A上的关系时,M2为n×n方阵

7 矩阵表示法 n 该矩阵称为关系矩阵，关系R的关系矩阵用 表示 n 在关系运算中广泛应用 1. 2. MR     i,j i j i j m 0 1 a ,a R A a ,b R A B 其中 取值 或 ，表示 之间量的存在关系 （ 是 上的关系）或表示 之间的存在关系 （ 是 到 的关系） R A MR 当 为 上的关系时， 为n n方阵 A = R n，B =m时，M 为n  m矩阵 1 1 0 0 0 1 0 0 0 MR       

关系的运算 ■关系的交、并、补、差 口由于关系也是集合,是一些有序偶组成的集合,因而 集合的一些交、并、补、差等在关系中也适用,并且 集合的运算性质也同样适用。 口新运算:复合运算、逆运算 复合关系 口定义23:设R是一个从X到Y的关系,S是一个从Y到Z 的关系,则R与S的复合关系R。S可定义为 RoS={(x,)x∈X,∈Z至少存在一个y∈Y,有(x,y)∈R且(y,∈S 复合关系RoS是从X到Z的关系

8 R S 复合关系R S是从X到Z的关系 R S={ x,z|x X ,z Z,至少存在一个y Y ,有 x, y  R且 y,z S} n 关系的交、并、补、差 ¨ 由于关系也是集合，是一些有序偶组成的集合，因而 集合的一些交、并、补、差等在关系中也适用，并且 集合的运算性质也同样适用。 ¨ 新运算：复合运算、逆运算 n 复合关系 ¨ 定义2.3：设R是一个从X到Y的关系，S是一个从Y到Z 的关系，则R与S的复合关系 可定义为：

■图形说明: RoS 口在关系图中,两条相连的有向边,其中第一条有向边 的起始点和第二条有向边的终点组成的有序偶就是复 合关系的元素

9 n 图形说明： p 在关系图中，两条相连的有向边，其中第一条有向边 的起始点和第二条有向边的终点组成的有序偶就是复 合关系的元素

口关系复合运算的矩阵表示: 设X={x…xn},={y1…ym},Z={=1…=k} R是从X到Y的关系,关系矩阵为Mn; S是从Y到Z的关系,关系矩阵为M, 则复合关系RoS的关系矩阵 Ros R k 口说明: 布尔乘]设M=[4]-,则=∑ ■只要有、j之间有一个元素Z可以形成(2)和(z,就 能产生(]; ■这里用的是布尔加和布尔乘 10

10 ¨关系复合运算的矩阵表示： R是从X到Y的关系，关系矩阵为 ； S是从Y到Z的关系，关系矩阵为 。 则复合关系 的关系矩阵： ¨说明： n 只要有i、j之间有一个元素z可以形成(i,z)和(z,j)，就 能产生(i,j)； n 这里用的是布尔加和布尔乘。 R  S 1 , = R ij S ij n m m k m R S ij ij il lj n k l M r M s M t t r r                  设    ,则  设X=x1xn,Y  y1ym ,Z  z1zk  MRS  MR Ms  M R M s 布尔乘