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

35关系及其表示,举例：“大于”关系，“同学”关系，“整除”关系，电影票和座位间“对号”关系,记法：大于关系“” ： | x,y是实数 且 xy 对号关系 R: R = |x是电影票号，y是座位号， 且两者一致,定义： 关系（Relation） 任一序偶的集合确定了一个二元关系。,关系是一个集合； 以序偶为元素。,集合元素间的某种联系我们统称为“关系”,关系及其表示,定义： 前域（Domain）和值域（Range） 由 R的所有 x 组成的集合domR称为R的定义域或前域，即 domRx | ( y) ( R) ； 由R的所有 y 组成的集合 ranR称为R的值域，即 ranRy | ( x) ( R) R的域 FLD R domR ranR,关系的前域、值域和域,定义: X 到 Y的关系 令 X 和 Y 是任意两个集合，直积XY的子集R称为 X到 Y 的关系 。,例题：关系R=, 则有： 2 R b, 2 R B dom R = 1,2,3, ran R =a, B, c, FLD R =1,2,3,a,B,c,关系及其表示,关系及其表示,如A=1,2,3，则IA,说明:1、XY的两个平凡子集XY和，分别为X到Y的 全域关系和空关系。 2、当XY时，称R为X上的关系。(R X X),定义 恒等关系 设IX是X上的二元关系且满足 IX | xX，则称IX是X上的恒等关系。,定义 n元关系(Relation) 笛卡尔积A1A2An的任一子集称为一个A1 , A2 , , An上的 n 元关系。,例题：若H=f,m,s,d表示一个家庭中父，母，子，女四个人的集合，确定H上的全域关系和空关系，另外再确定H上的一个关系，指出该关系的值域和前域。,解 设H上的同一家庭成员关系为H1， H1=, , , H1为全域关系,例题,设H上互不相识的关系为H2,H2为空关系,设H上的长幼关系为H3 H3=, domH3=f,m, ranH3=s,d,关系的运算,由于关系的本质仍然是集合，所以集合的运算 、也适用于关系。,例：设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: 若Z和S是从集合X到集合Y的两个关系，则Z、S的并、交、补、差仍是X到Y的关系。,提示：只要证明运算的结果仍然是XY的子集即可,证明 因为ZXY， SXY 故Z S XY, Z S XY S = (XY-S) XY Z-S = Z S XY,关系的表达形式,1、序偶的集合,2、矩阵表示,Xx1，x2 ， ，xm，Yy1，y2 ， ，yn，R为从X到Y的一个二元关系。MRrijmn,例：设Aa1，a2，Bb1，b2，b3，R ,写出R的关系矩阵MR,关系的表达形式,3、图形表示,上例R ,的关系图：,关系图主要表达结 点与结点之间的邻接关系，故与结点位置和线段长短无关。,作图规则： X集上的节点 Y集上的节点 有向箭头与序偶对应,作业P109(1)、(2)、(5)c、(8),？从A到B的不同的关系共有多少？ 设|A|m ，|B|n,|AB|mn AB的子集个数为2mn,A到B上的不同关系有2mn种 。,36 关系的性质,定义1 自反（Reflexive）设R为定义在集合X上的二元关系，如果对于每个xX，有 R ，则称二元关系R是自反的。,R在X上自反（x）（xX R ）,例1：设A1,2,3，R,主对角线元素全为1,每个结点有自回路,比较自反 与恒等关系,关系矩阵：,关系图：,关系的性质2,定义2 对称（Symmetry）设R是X上的二元关系，如果对于每个x,y X,每当R,就有R，则称关系R在集合X上是对称的。,R在X上对称（x)(y)(xXyXRR）,判定定理：R在X上自反，当且仅当IX R,例：设A1,2,3,R为集合A上的二元关系， R,弧总是成对出现,矩阵关于主对角线对称,关系的性质2,X=1,2,3 R=, X=1 R= X=1,2,3 R=,对称的,既自反，又对称,对称而不自反,定理 R是对称的，当且仅当R = Rc,例 设 A=2,3,5,7,R=|(x-y)/2是整数，验证 R在A上是自反和对称的。,证明 因为对xA ，（x-x）/2=0,即 R,所以R是自反的。 对x, yA ，若 R,则有（x-y)/2是整数，那么 （y-x）/2也是整数，即 R,所以R是对称的。,R,定义3 传递（Transitive）设R是集合X上的二元关系,如果对于x,y,zX，若R，R，有R,则称R在X上是传递的。,R在X上是传递的(x)(y)(z)(xXyXzXRRR）,关系的性质3,关系图的特点：如果从a到b存在一条有向路径，则a到b也 存在一条有向弧。,如：实数集合中的大于关系，集合中的包含关系等都是传递的。,例：设B=1,2,3,4,5,6定义B上二元整除关系 R= a,bB,a能整除b,验证整除关系为传递的。,R=, , ,例：设X1,2,3，R1 =, R2 =, R3 =, , R1 、R2 、R3都是 传递的吗？,关系的性质3,解：R1 、R2都是传递的， R3不是传递的。,见书P111,注： 对于单个序偶构成的关系 认为是传递的。,关系的性质4,定义4 反自反（Antireflexive）设R为定义在集合X上的二元关系，如果对于 xX，都有R，则称二元关系R是反自反的。,R在X上反自反（x)(xXR ）,如： 父、子关系，数的大于关系等都是反自反的。,？ 一个关系不是自反的，一定是反自反的吗？ ？ 有没有既自反又反自反的二元关系,(1)例： A1,2,3，S, , S不是自反的，也不是反自反的。,主对角线元素全为0；每个结点都没有自回路,(2)空集上的任一二元关系既是自反的又是反自反的。,定义5 反对称（Antisymmetric）设R是X上的二元关系，如果对于每个x,yX,每当R和R，必有xy，则称R在X上的是反对称的。 或每当R和xy则必有R，则称R在X上的是反对称的。,关系的性质5,R在X上反对称 （x)(y)(xXyXRRxy) （x)(y)(xXyXR xyR),关于主对角线对称的元素不能同时为1； 弧总不是成对出现的。,例如实数集合中的关系、集合的关系等是反对称的。,关系的性质,例6：设Aa,b,c,A上的关系R,S,T为R, S,T,注意：有些关系既非对称，也非反对称； 有些关系既是对称的，又是反对称的。,则R、S是反对称的。而R、T是对称的。,例：设有三个人，组成集合AT，G，H, 在A上的朋友关系具有哪些性质？,具有反自反和对称性。,关系的性质在其表达形式上的体现,关系的证