《35关系及其表示.ppt》由会员分享，可在线阅读，更多相关《35关系及其表示.ppt（24页珍藏版）》请在三一办公上搜索。
1、3-5 关系及其表示,1.掌握关系的概念2.会用关系矩阵和关系图表示关系,1、关系定义3-5.1：任一序偶的集合确定了一个二元关系R，R记作aRb，称a与b有关系，R记作aRb，称a与b没有关系。这种记法称为中缀记法。例如，=|x，y是实数且xy说明：(1)把关系R这种无形的联系用集合这种“有形”的实体来描述，为今后的描述和论证带来方便。(2)序偶是讲究次序的，如果有R未必有R，即a与b有关系R，未必b与a有关系R。例：甲与乙有父子关系，但乙与甲没有父子关系。,一、关系（Relation）,2、前域、值域定义3-5.2：二元关系R中，所有序偶的第一元素的集合dom R称为R的前域，第二元素的集
2、合ran R称为R的值域。R的前域和值域一起称作的域，记作FLD R。即dom R=x|(y)R，ran R=y|(x)R，FLD R=dom Rran R例题1 设A=1，2，3，5，B=1，2，4，H=，求dom H，ran H，FLD H。,解：dom H=1，2，3，ran H=2，4，FLD H=1，2，3，4,3、X到Y的关系定义3-5.3：令X和Y是任意两个集合，XY的子集R称作X到Y的关系。如果R是X到Y的关系，则dom RX，ran RY。例题2 设X=1，2，3，4，求X上的关系及dom，ran。,解：=，dom=2，3，4，ran=1，2，3,上周课程内容回顾,序偶和笛卡
3、尔积有序n元组序偶笛卡尔积定义性质关系及其表示关系的定义前域和值域,4、特殊的关系(1)全域关系：对于集合X和Y，称XY为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,解：H=，S=HS=，HS=XX=，H=，S-H=,例题4 设X=1，2，3，4，若H=|(x-y)
4、/2是整数，S=|(x-y)/3是正整数，求HS，HS，H，S-H。,5、定理3-5.1：若Z和S是集合X到Y的两个关系，则Z和S的并、交、补、差仍是X到Y的关系。,二、关系的表示1、集合,为直观地表示A到B的关系,我们采用如下的图示:用大圆圈表示集合A和B,里面的小圆圈表示集合中的元素;若aA,bB,且,则在图示中将表示a和b的小圆圈用直线或弧线连接起来,并加上从结点a到结点b方向的箭头。,此例中的1和2的图示如图1所示。,例 设A1,2,3,4,5,Ba,b,c,则1,是A到B的关系,而2,是B到A的关系。其集合表示法如下：,图1 上例用图,2、关系矩阵：设给定两个有限集合X=x1，x2，
5、xm，Y=y1，y2，yn，R是X到Y的关系，则R的关系矩阵MR，其中rijmn，rij=1当R，rij=0，当R。如果R是X上的二元关系时，则其关系矩阵是一个方阵。,其关系矩阵表示为：,关系矩阵的写法也可以简化,当约定了元素的次序后,可以不写最左列和最上行的元素。如,说明：(1)空关系的关系矩阵的所有元素为0。(2)全关系的关系矩阵的所有元素为1。(3)恒等关系的关系矩阵的所有对角元为1，非对角元为0，此矩阵为单位矩阵。,例题5 设X=x1,x2,x3,x4,Y=y1,y2,y3,R=,，写出关系矩阵MR。例题6 设A=1,2,3,4，写出集合A上大于关系的关系矩阵。,3、关系图：设有限集合
6、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没有线段联结。,例 设A-2,-1,0,1,写出A上的关系、关系、关系、UA和IA,并分别写出这些关系的前域和值域（这里、分别表示通常的小于、小于等于和大于）。并画出关系图。,解,D-2,-1,0 R-1,0,1,DA RA,(-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)
7、,(-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)其关系图表示为：,图 2 例题 用图,109页例题7 设X=x1,x2,x3,x4,Y=y1,y2,y3,R=,，画出R的关系图。例题8 设A=1,2,3,4,5，在A上的二元关系R给定为：R=,画出R的关系图。,X到Y有多少个不同的关系？如果|X|=m，|Y|=n，则|XY|=mn，而关系是XY的子集，XY的子集共有2mn个，所以，X到Y的关系共有2mn个。,可定义n元关系。若S Ai，则称S为 Ai上的n元关系。特别A1=A2=An时，称S为A上的n元关系。,作业110页(5)，(6)，(8),
