《二元关系-1概念`合成》由会员分享，可在线阅读，更多相关《二元关系-1概念`合成（66页珍藏版）》请在金锄头文库上搜索。
1、第3章 二元关系,第三章 关 系,3.13.2,3.1 基本概念,例1 设 A = a，b，c，d 是某乒乓球队的男队员集合， B = e，f，g 是女队员集合。,R 表示具有混双配对关系的序偶集合,如果 A 和 B元素之间有混双配对关系的是 a 和 g，d 和 e。,R=a，g,d，e,可表达为:,所有可能,3.1.1 关系,=a，e,a，f,a，g,b，e,b，f,b，g, c，e,c，f,c，g,d，e,d，f,d，g,a 日 乙 b 法 甲 c 日 丙 d 法 乙,例2 设学生集合 A1 = a，b，c，d ，选修课集合 A2=日语，法语，成绩等级集合 A3 = 甲，乙，丙 。,可表达
2、为 S = a,日,乙,b,法,甲, c,日,丙,d,法,乙,如果四人的选修内容及成绩如下:,=a,日,甲,a,日,乙,a,日,丙,a,法,甲,a,法,乙, a,法,丙,b,日,甲,b,日,乙,b,日,丙,b,法,甲, b,法,乙,b,法,丙,c,日,甲,c,日,乙,c,日,丙, c,法,甲,c,法,乙,c,法,丙,d,日,甲,d,日,乙, d,日,丙,d,法,甲,d,法,乙,d,法,丙,关系是一个集合,其元素为n重组,定义 3.11 (1) AB的子集叫做 A 到 B的一个二元关系。,叫做 A 上的n元关系,(2) A1A2An(n1)的子集叫做 A1A2An上的一个 n 元关系。,一个谓词
3、 P ( x1，x2，xn ) 可以定义一个 n 元关系 R：,例如，实数 R 上的二元关系可定义如下：,反之，一个 n 元关系也可定义一个谓词：,R= x1，x2，xn | P ( x1，x2，xn ) , = x，y | x R y R x y ,例如，设P(x)表示“ x 是质数”，论述域是 N，则质数集合,当 n =1时，R = x | P( x ) ,称为一元关系,表示论述域上具有性质 P 的元素集合,可表示为, xP ( x ) N, x P( x ) ,或,其意义与 R = x | P ( x ) 相同,定义3.12 设 R 是 的子集，,如果 R = ，则称 R 为全域关系。,
4、如果 R = ，则称 R 为空关系，,并且 R1 和 R2 是相等的有序 n 重组集合。,定义3.13 设 R1 是 上的 n 元关系，R2 是 上的 m元关系，那么,当且仅当 n = m，,且对一切 i，1 i n，Ai = Bi，,R1 = R2,读做 x3 和 y1有关系 R,3.1.2 二元关系,设,A= x1，x2，x7 B= y1，y2，y6 R=x3，y1,x3，y2,x4，y4,x6，y2,A到B的二元关系 R 可如图表示。,中缀记法常用来表示诸如 “=”，“”，“” 等关系,x3，y1R，也可用中缀记法写成 x3 R y1，,例如3，5，通常写作 35,A叫做关系 R 的前域
5、,D(R) = x y (x，yR) 叫做关系 R 的定义域,B 叫做关系 R 的陪域,R(R) = y x (x，yR) 叫做关系 R 的值域,关系是序偶的集合，对它可进行集合运算，运算结果是一个新关系。,RS，RS，R-S， 等可分别定义如下：,x ( RS ) y,x (R S ) y,x ( ) y,x ( RS ) y,设 R 和 S 是给定集合上的两个二元关系，则,x R yx S y,x R y x S y,x R y x $ y,例3 平面上的几何图形是平面 R2 的子集，也是一种关系。,R1R2 = ,R1= x，y x，y R2 x2 + y2 9 ,设,R1R3= ,R1
6、-R3= ,= ,(1x30y3) ), x , y x , y R2( x2+y29, x , y x , y R2 (x2+y29), x2+y24, x , y x , y R2(x2+y29, x , y x , y R2,R2= x，y x，y R2 (1 x 3 ) (0 y 3) ,R3= x，y x，y R2 x2 + y2 4 ,A上的二元关系 R = | x A ,常记为 IA 或 EA,称为相等关系,3.1.3 关系矩阵和关系图,则称矩阵MR=rij是 R 的关系矩阵。,定义3.14 给定集合A = a1 , a2 , , am 和B= b1 , b2 , , bn ，及
7、一个 A 到 B 的二元关系 R， 使,适用于表示有限集之间的关系,m行n列,关系的其它表示法,例4 设A= a1，a2 ，B=b1，b2，b3 ，,b1 b2 b3a1a2,R=a1，b1,a2，b1,a1，b3,a2，b2,则其关系矩阵为,1 0 11 1 0,例5 设A = 1，2，3，4 ，A上的二元关系 R = x，yxy，试求出关系矩阵。,R =4,1,4,2,4,3,3,1,3,2,2,1,解,关系图,一个有限集合 A上的关系 R， 还可以用关系图直观地表示。画法如下：,（1）用小圆圈表示集合A中的每一个元素 ai结点。,（2）用一条从结点 ai 到结点 aj带箭头的弧线表示关系
8、中的序偶 ai， aj 弧或有向边。, ai， ai 对应的带箭头的弧线自回路。,这种图叫有向图Ch8讲,例6 设 A = 1，2，3，4，5 R=1，2,2，2,3，2,3，4,4，3,孤立点,空关系,0 0 0 0 0 0 0 0 0,全域关系,1 0 0 0 1 0 0 0 1,3.1.4 关系常见的特性,定义3.15 设 R 是 A 上的二元关系， (1)如果对A中每一 x，x R x，那么 R 是自反的。,A=1，2，3，R1=1，1,2，2,3，3,1,2,A上的关系 R 是自反的, x ( xA x R x ),即,每个结点上都有自回路,主对角线上的元素均为1,例如,IA R1,
9、(2)如果对A中每一x，x R x，那么 R 是反自反的。即,A上的关系 R 是反自反的,A=1，2，3，R2=2，1,1，3,3，2,例如,每个结点上都无自回路,主对角线上的元素均为0,0 0 1 1 0 0 0 1 0,IA R2=,有些关系既不是自反的，又不是反自反的,例如，R3=1,1,1,2,3,2,2,3,3,3,1 1 0 0 0 1 0 1 1,0 1 0,是否存在既是自反的，又是反自反的关系?,一般情况下，关系不能是自反的，又是反自反的,1 1 1,0 0 0, x ( x x R x ),自反的和反自反的,非空集合A上的空关系,反自反的, x ( xA x R x ),空集
10、上的空关系,整数集I上的关系“ ”,整数集I上的关系“ ”,是自反的，不是反自反的,是反自反的，不是自反的,IA,是自反的,是自反的,任何非空集合上的,自反与反自反,空关系,是反自反的,A2,(3)如果对每一 x，yA，x R y 蕴含着 y R x，那么 R 是对称的。, x y ( xAyA x R y y R x ),A=1，2，3，R4=1,2,2,1,1,3,3,1,1,1,例如,如果有a到b的弧，一定有b到a的弧,关于主对角线对称,1 1 1 1 0 0 1 0 0,如果没有b到 a的弧，一定没有a 到b的弧,IA,是对称的,是对称的,如果没有b到 a的弧，一定没有a 到b的弧,空
11、关系,是对称的,A2,(4)如果对每一 x，yA，x R y，y R x 蕴含着 x = y，那么R是反对称的。,A上的关系R是反对称的,x R y y R x x = y ,A上的关系R是反对称的也可以如下定义： ,xy ( xAyA x R y y R x x = y),A上的关系R是反对称的 xy ( xAyA x R y y R x x = y),例如，A=1，2，3，R5=1，2,2，3,如果有a到b的弧，不存在b到a的弧,如果aji1，则aij0，(ij),0 1 0 0 0 1 0 0 0,没有a到b的弧，也没有b到a的弧,A上的关系R是反对称的 xy ( xAyA x R y y R x x = y),是反对称的,是反对称的,整数集I上的关系“ ”,整数集I上的关系“ ”,是反对称的，不是对称的,是反对称的，不是对称的,不是反对称的,A2,有些关系既不是对称，也不是反对称。,有些关系既是对称，也是反对称。,如 空关系 和 IA其它还有吗?,是对称的与反对称的,是对称的不是反对称的,对称与反对称,空关系,是对称的与反对称的,A2,(5) 如果对每一 x，y，zA，xRy，yRz 蕴含着 xRz，那么 R是传递的。,A上的关系 R 是传递的 ,如果从 a 到 b 存在一条有向路径，则 a 到 b 也存在一条弧,
