三、关系、关系表示和性质.ppt

《三、关系、关系表示和性质.ppt》由会员分享，可在线阅读，更多相关《三、关系、关系表示和性质.ppt（19页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、35关系及其表示关系及其表示举例举例：“大于”关系，“同学”关系，“整除”关系，电影票和座位间“对号”关系记法：大于关系记法：大于关系“”：|x,yx,y|x,y是实数是实数 且且 xy xy 对号关系对号关系 R:R =|x|x是电影票号，是电影票号，y y是座位号，是座位号，且两者一致且两者一致定义：定义：关系（关系（Relation）任一任一序偶序偶的的集合集合确定了一个二元确定了一个二元关系关系。1.关系是一关系是一个集合；个集合；2.以以序偶序偶为为元素。元素。集合元素间的某种联系我们统称为集合元素间的某种联系我们统称为“关系关系”如果如果R R是一个关系，是一个关系，序偶序偶 R,

2、x,yR,则说则说 x x和和 y y具有关系具有关系R R，也可记为也可记为xRyxRy 序偶序偶 x,y R,R,则说则说x x和和y y没有关系没有关系R R，也可记为也可记为x R yx R y关系及其表示关系及其表示定义：定义：前域（前域（Domain）和值域（和值域（Range）由由 R的所有的所有 x 组成的集合组成的集合domR称为称为R的定义的定义域或前域，即域或前域，即 domRx|(y)(R)；由由R的所有的所有 y 组成的集合组成的集合 ranR称为称为R的的值域，值域，即即 ranRy|(x)(R)R的域的域 FLD R domR ranR 关系的前域、值域和域关系的

3、前域、值域和域定义定义:X X 到到 Y Y的的关系关系 令令 X X 和和 Y Y 是任意两个集合，直积是任意两个集合，直积XYXY的的子集子集R R称为称为 X X到到 Y Y 的的关系关系。例题：关系例题：关系R=,R=,则有：则有：2 2 R b,2 R BR b,2 R B domdom R=1,2,3,ran R=a,B,c,R=1,2,3,ran R=a,B,c,FLD R=1,2,3,a,B,c FLD R=1,2,3,a,B,c若若 R XY，则：则：R是从是从X到到Y的关系的关系 dom R X,ranR Y R domRranR XY注注意意关系及其表示关系及其表示关系及

4、其表示关系及其表示如如A=1,2,3A=1,2,3，则，则IA,说明说明:1:1、XYXY的两个平凡子集的两个平凡子集XY和和，分别为分别为X X到到Y Y的的 全域关系全域关系和和空关系空关系。2 2、当、当X XY Y时，称时，称R R为为X X上的关系。上的关系。(R X X)定义定义 恒等关系恒等关系 设设IX是是X上的二元关系且满足上的二元关系且满足 IX|xX，则称则称IX是是X上的恒等关系。上的恒等关系。定义定义 n元关系元关系(Relation)笛卡尔积笛卡尔积A A1 1AA2 2AAn n的的任一任一子集子集称为一个称为一个A A1 1,A A2 2,A An n上的上的

5、n n 元关系。元关系。例题：若例题：若H=f,m,s,d表示一个家庭中父，母，子，女四表示一个家庭中父，母，子，女四个人的集合，确定个人的集合，确定H上的全域关系和空关系，另外再确定上的全域关系和空关系，另外再确定H上的一个关系，指出该关系的值域和前域。上的一个关系，指出该关系的值域和前域。解解 设设H上的同一家庭成员关系为上的同一家庭成员关系为H1，H1=,H1为为全域关系全域关系 例题设设H上互不相识的关系为上互不相识的关系为H2,H2为为空关系空关系 设设H上的上的长幼关系长幼关系为为H3 H3=,domH3=f,m,ranH3=s,d关系的运算由于关系的本质仍然是由于关系的本质仍然是

6、集合集合，所以，所以集合的运算集合的运算、也也适用于关系。适用于关系。例：设例：设X X1,2,3,4，若若 H|(x-y)/2是整数是整数S|(x-y)/3是正整数，求是正整数，求HS，HS，H，SH。解：H=,S=HS=,HS=H=XXH=,SH=关系运算定理定理定理3-5.1:3-5.1:若若Z Z和和S S是从集合是从集合X X到集合到集合Y Y的两个关系，则的两个关系，则Z Z、S S的并、交、补、差仍是的并、交、补、差仍是X X到到Y Y的关系。的关系。提示提示：只要证明运算的结果仍然是：只要证明运算的结果仍然是XY的子集即可的子集即可证明 因为ZXY，SXY 故Z S XY,Z

7、S XY S=(S=(XY-S)XY Z-S=Z S S XY关系的表达形式关系的表达形式1、序偶的集合、序偶的集合2、矩阵表示、矩阵表示Xx1，x2，xm，Yy1，y2，yn，R为从X到Y的一个二元关系。MRrijmn 例：设Aa1，a2，Bb1，b2，b3，R ,写出R的关系矩阵MR 1 当R rij 0 当R关系的表达形式关系的表达形式3、图形表示、图形表示上例上例R ,的关系图：的关系图：关系图主要表达结关系图主要表达结 点与结点之间的点与结点之间的邻邻接关系接关系，故与，故与结点结点位置位置和和线段长短线段长短无无关。关。作图规则：作图规则：X集上的节点集上的节点 Y集上的节点集上的

8、节点 有向箭头与序偶对应有向箭头与序偶对应作业作业P109(1)、(2)、(5)c、(8)？从从A A到到B B的不同的关系共有多少？的不同的关系共有多少？设设|A|A|m m，|B|B|n n|AB|mn AB的子集个数为的子集个数为2mn A到到B上的不同关系有上的不同关系有2mn种种。36 关系的性质关系的性质定义定义1 1 自反自反（Reflexive）设设R为定义在集合为定义在集合X上的二元关系，上的二元关系，如果对于每个如果对于每个xX，有有 R，则称二元关系则称二元关系R是自反的。是自反的。R R在在X X上自反上自反（x x）（）（x xX X R ）例1：设A1,2,3，R,

9、主对角线元主对角线元素素全全为为1每个结点每个结点有自回路有自回路比较比较自反自反与与恒等恒等关系关系关系矩阵：关系矩阵：关系图：关系图：关系的性质关系的性质2定义定义2 2 对称（对称（Symmetry）设设R是是X上的二元关系，如上的二元关系，如果对于每个果对于每个x,y X,每当每当R,就有就有R，则则称关系称关系R R在集合在集合X X上是上是对称对称的。的。R R在在X X上对称上对称（x)(x)(y)(y)(x xX Xy yX XRR）判定定理判定定理：R在在X上自反，当且仅当上自反，当且仅当I IX X R 例例：设A1,2,3,R为集合A上的二元关系，R R,弧总是成弧总是成

10、对出现对出现矩阵关于矩阵关于主对角线主对角线对称对称关系的性质关系的性质21.X=1,2,3 R=,2.X=1 R=3.X=1,2,3 R=对称的对称的既自反，又对称既自反，又对称对称而不自反对称而不自反定理定理 R是对称的，当且仅当是对称的，当且仅当R=Rc 例例 设设 A=2,3,5,7,R=|(x-y)/2是整数是整数，验证，验证 R在在A上是自反和对称的。上是自反和对称的。证明证明 因为对因为对 x A A，（，（x-x）/2=0,即即 R,R,所以所以R R是自反的。是自反的。对对 x,y A A，若若 R,R,则有（则有（x-y)/2x-y)/2是整数，那么是整数，那么 （y-xy

11、-x）/2/2也是整数，即也是整数，即 y,x R,R,所以所以R R是对称的。是对称的。R R,定义定义3 传递传递（Transitive）设设R是是集合集合X上的二元关系上的二元关系,如如果对于果对于 x,y,zX，若若R，R，有有R,则则称称R在在X上是传递的。上是传递的。R在在X上是传递的上是传递的(x)x)(y)y)(z)(z)(xXxXyXyXzXzXRRR）关系的性质关系的性质3关系图的特点关系图的特点：如果从a到b存在一条有向路径，则a到b也 存在一条有向弧。如如：实数集合中的大于关系，集合中的包含关系等都是传递的。例例：设：设B=1,2,3,4,5,6B=1,2,3,4,5,

12、6定义定义B B上二元上二元整除整除关系关系 R=R=a,ba,b B,B,a a能整除能整除b b,验证整除关系为传递验证整除关系为传递的。的。R=,1,R=,4,6,6,例例：设：设X X1,2,31,2,3，R R1 1=,R,R2 2=,R R3 3=,R,R1 1、R R2 2、R R3 3都是都是 传递的吗？传递的吗？关系的性质关系的性质3解：解：R R1 1、R R2 2都是传递的，都是传递的，R R3 3不是传递的不是传递的。见书见书P111注：注：对于单个序偶构成的关系对于单个序偶构成的关系 认为是传递的。认为是传递的。关系的性质关系的性质4定义定义4 反自反反自反（Anti

13、reflexive）设设R为定义在集合为定义在集合X上的二元关系，上的二元关系，如果对于如果对于 xX，都有都有 R，则称二元关系则称二元关系R是是反自反的。反自反的。R R在在X X上反自反上反自反（x)(x)(x xX X R ）如：如：父、子关系，数的大于关系等都是反自反的。父、子关系，数的大于关系等都是反自反的。？一个关系不是自反的，一定是反自反的吗？一个关系不是自反的，一定是反自反的吗？有没有既自反又反自反的二元关系有没有既自反又反自反的二元关系(1)(1)例：例：A A1,2,31,2,3，S S,S,S不是自反不是自反的，也不是反自反的。的，也不是反自反的。主对角线元主对角线元素

14、素全为全为0；每个结点都每个结点都没有自回路没有自回路(2)(2)空集空集上的任一二元关系既是上的任一二元关系既是自反自反的又是的又是反自反反自反的。的。定义定义5 5 反对称反对称（AntisymmetricAntisymmetric）设设R是是X上的二元关系，如上的二元关系，如果对于果对于每个每个x,yX,每当每当R和和R，必有必有xy，则称则称R R在在X X上的是反对称的。上的是反对称的。或或每当每当R和和xy则必有则必有 R，则称则称R R在在X X上的是反对称上的是反对称的。的。关系的性质5R R在在X X上反对称上反对称（x)(x)(y)(y)(x xX Xy yX XRRx x

15、y y)（x)(x)(y)(y)(x xX Xy yX XR xyy,x R R)关于主对角关于主对角线对称的元线对称的元素不能同时素不能同时为为1；弧总不是成弧总不是成对出现的。对出现的。例如实数集合中的例如实数集合中的 关系、集合的关系、集合的 关关系等是反对称的。系等是反对称的。关系的性质例例6 6：设设A Aa,b,c,Aa,b,c,A上的关系上的关系R,S,TR,S,T为为R R,S S,T,T,注意：有些关系注意：有些关系既非对称既非对称，也，也非反对称非反对称；有些关系既是有些关系既是对称对称的，又是的，又是反对称反对称的。的。则则R R、S S是反对称的。而是反对称的。而R R

16、、T T是对称的。是对称的。例：设有三个人，组成集合例：设有三个人，组成集合A AT T，G G，H H,在在A A上的上的朋友关系朋友关系具有哪些性质？具有哪些性质？具有反自反和对称性。具有反自反和对称性。关系的性质在其表达形式上的体现关系的性质在其表达形式上的体现关系的性质关系的性质关系矩阵关系矩阵关系图关系图自反自反主对角线上的所有元素都是主对角线上的所有元素都是1每个结点都有自回路每个结点都有自回路反自反反自反主对角线上的所有元素都为主对角线上的所有元素都为0每个结点都没有自回路每个结点都没有自回路对称对称关系矩阵是对称的关系矩阵是对称的有向弧线成对出现有向弧线成对出现反对称反对称以主

17、对角线对称的元素不能同以主对角线对称的元素不能同时为时为1任意两个结点间的弧线任意两个结点间的弧线不可能成对出现不可能成对出现关系的证明方法：关系的证明方法：要要证明证明R R在在X X上上自反自反 假设假设 x xX X，证出证出 R 要要证明证明R R在在X X上对称上对称 对对 x,x,y y X,X,设设R ，证出证出 R 要证明要证明R R在在X X上传递上传递 对对 x,y,zX,x,y,zX,设设R R，证出证出 R 要证明要证明R R在在X X上反自反上反自反 假设假设 x xX X，证出证出 R ）要证明要证明R R在在X X上反对称上反对称 对对 x,x,y yX X，设设RR ，证证出出 x xy y 作业作业:P113(4),(6)