关系及其表示PPT课件

1、2、前域、值域定义3-5.2：二元关系R中，所有序偶的第一元素的集合dom R称为R的前域，第二元素的集合ran R称为R的值域。R的前域和值域一起称作的域，记作FLD R。即dom R=x|( y) R ， ran R=y|( x) R，FLD R=dom R ran R例题例题1 1 设设A=1A=1，2 2，3 3，55，B=1B=1，2 2，44，H=1H=2，14，24，34，求求dom Hdom H，ran Hran H， FLD HFLD H。解：解： dom H=1dom H=1，2 2，33，ran H=2ran H=2，44，FLD H=1FLD H=1，2 2，3 3，4

2、4第1页/共23页3、X到Y的关系定义3-5.3：令令X X和和Y Y是任意两个集合，是任意两个集合，X X Y Y的子的子集集R R称作称作X X到到Y Y的关系。的关系。如果R是X到Y的关系，则dom R X，ran R Y。例题2 设X=1，2，3，4，求X上的关系及dom ，ran 。解：解：=， ，dom =2，3，4，ran =1，2，3第2页/共23页上周课程内容回顾上周课程内容回顾 序偶和笛卡尔积序偶和笛卡尔积 有序有序n元组元组 序偶序偶 笛卡尔积笛卡尔积 定义定义 性质性质 关系及其表示关系及其表示 关系的定义关系的定义 前域和值域前域和值域第3页/共23页4、特殊的关系(

3、1)全域关系：对于集合X和Y，称X Y为X到Y的全域关系。记作U。(2)空关系：称为空关系。(3)恒等关系：Ix称为X上的恒等关系。例题例题3 若若H=f，m，s，d，确定，确定H上的全域关系和空上的全域关系和空关系，另外再确定关系，另外再确定H上的一个关系，指出该关系的值上的一个关系，指出该关系的值域和前域。域和前域。解：设解：设H上的同一家庭成员的关系为上的同一家庭成员的关系为H1，H上的互不相上的互不相识的关系为识的关系为H2，则，则H1为全域关系，为为全域关系，为H2空关系，设空关系，设H上的长幼关系为上的长幼关系为H3 ， H3=，dom H3=f，m，ran H3=s，d第4页/共

4、23页解：H=， ，S=H S=， ，H S=X X=， ， H=， ，S-H=例题例题4 设设X=1，2，3，4，若，若H=|(x-y)/2是整数是整数，S=|(x-y)/3是正整数是正整数，求，求H S，H S， H，S-H。第5页/共23页5、定理3-5.1：若Z和S是集合X到Y的两个关系，则Z和S的并、交、补、差仍是X到Y的关系。第6页/共23页二、关系的表示1、集合为直观地表示为直观地表示A到到B的关系的关系,我们采用如下的我们采用如下的图示图示:用大圆圈表示集合用大圆圈表示集合A和和B,里面的小圆圈里面的小圆圈表 示 集 合 中 的 元 素表 示 集 合 中 的 元 素 ; 若若

5、a A , b B , 且且,则在图示中将表示则在图示中将表示a和和b的小圆圈的小圆圈用直线或弧线连接起来用直线或弧线连接起来,并加上从结点并加上从结点a到结到结点点b方向的箭头。方向的箭头。第7页/共23页此例中的1和2的图示如图1所示。例 设A A1,2,3,4,51,2,3,4,5, ,B Ba a, ,b,cb,c, ,则1 11, 是A A到B B的关系, ,而2 2 ,5是B B到A A的关系。其集合表示法如下：第8页/共23页图图1 上例用图上例用图 第9页/共23页2、关系矩阵：设给定两个有限集合X=x1，x2，xm， Y=y1，y2，yn，R是X到Y的关系，则R的关系矩阵MR

6、，其中rijm n， rij =1当 R， rij =0，当 R 。 如果R是X上的二元关系时，则其关系矩阵是一个方阵。第10页/共23页111102010310040005000M2010000000000011aMbc其关系矩阵表示为：其关系矩阵表示为：第11页/共23页 关系矩阵的写法也可以简化, 当约定了元素的次序后, 可以不写最左列和最上行的元素。 如2010000000000011M第12页/共23页说明：(1)空关系的关系矩阵的所有元素为0。(2)全关系的关系矩阵的所有元素为1。(3)恒等关系的关系矩阵的所有对角元为1，非对角元为0，此矩阵为单位矩阵。第13页/共23页例题5 设

7、X=x1,x2,x3,x4,Y=y1,y2,y3,R=, , , , , , ，写出关系矩阵MR。例题6 设A=1,2,3,4，写出集合A上大于关系的关系矩阵。第14页/共23页3、关系图：设有限集合X=x1，x2，xm， Y=y1，y2，yn，X到Y的一个关系为R，则R的关系图：做出m个结点分别记作x1，x2，xm， n个结点分别记作y1，y2，yn，如果 R ，则可自结点xi至yj作一有向弧，如果 R ，则xi至yj没有线段联结。第15页/共23页例 设A-2, -1, 0, 1, 写出A上的关系、 关系、 关系、 UA和IA, 并分别写出这些关系的前域和值域（这里、 、 分别表示通常的小

8、于、 小于等于和大于）。并画出关系图。 解解 , , , , , D-2, -1, 0 R-1, 0, 1, , , , , , , , DA RA第16页/共23页(-1, -2), (0, -1), (0, -2), (1, -2), (1, -1), (1, 0) D-1, 0, 1 R-2, -1, 0UA(-2, -2), (-2, -1), (-2,0), (-2,1), (-1,-2), (-1,-1), (-1, 0), (-1, 1), (0, -2), (0, -1), (0, 0), (0, 1), (1, -2), (1, -1), (1, 0), (1, 1)IA(-2, -2), (-1, -1), (0, 0), (1, 1)其关系图表示为：AAIIDARAAAUUDARA第17页/共23页图图 2 例题例题 用图用图 第18页/共23页109页例题7 设X=x1,x2,x3,x4,Y=y1,y2,y3,R=, , , , , , ，画出R的关系图。例题8 设A=1,2,3,4,5，在A上的二元关系R给定为：R=,画出R的关系图。第19页/共23页 X到Y有多少个不同的关系？ 如果|X|=m，|Y|=n，则|X Y|=m n，而关系是X