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

关系及其表示 定义： 前域（Domain）和值域（Range） 由x,y ∈R的所有 x 组成的集合domR称为R的定义域或前域，即 domR＝｛x | (? y) (x,y ∈R) ｝； 由x,y∈R的所有 y 组成的集合 ranR称为R的值域，即 ranR＝｛y | (? x) (x,y ∈R) ｝ R的域 FLD R＝ domR∪ ranR 关系及其表示 关系及其表示 关系的运算 由于关系的本质仍然是集合，所以集合的运算 ∩、∪、～、－、⊕也适用于关系。 关系运算定理 定理3-5.1: 若Z和S是从集合X到集合Y的两个关系，则Z、S的并、交、补、差仍是X到Y的关系。 关系的表达形式 1、序偶的集合 关系的表达形式 3、图形表示 3－6 关系的性质 定义1 自反（Reflexive）设R为定义在集合X上的二元关系，如果对于每个x∈X，有x,x ∈R ，则称二元关系R是自反的。 关系的性质2 定义2 对称（Symmetry）设R是X上的二元关系，如果对于每个x,y ∈X,每当x,y∈R,就有y,x∈R，则称关系R在集合X上是对称的。 关系的性质2 X={1,2,3} R={1,2, 2,1} X={1} R={1,1} X={1,2,3} R={1,1} 关系的性质 例6：设A＝{a,b,c},A上的关系R,S,T为R＝{a,a,b,b}, S＝｛a,b,a,c},T＝{a,b,b,a,a,c,c,a} 关系的证明方法： 要证明R在X上自反 假设?x∈X ，证出 x,x∈R 要证明R在X上对称 对?x,y ∈X,设x,y∈R ，证出 y, x ∈R 要证明R在X上传递 对?x,y,z∈X,设x,y∈R ∧ y, z ∈R ，证出 x,z∈R 要证明R在X上反自反 假设?x∈X，证出 x,x?R ） 要证明R在X上反对称 对?x,y∈X，设x,y∈R∧ y, x ∈R ，证出 x＝y * * 3－5关系及其表示 举例：“大于”关系，“同学”关系，“整除”关系，电影票和座位间“对号”关系 记法：大于关系“” ： ＝ {x,y| x,y是实数 且 xy } 对号关系 R: R = {x,y|x是电影票号，y是座位号， 且两者一致} 定义： 关系（Relation） 任一序偶的集合确定了一个二元关系。 关系是一个集合； 以序偶为元素。 集合元素间的某种联系我们统称为“关系” 如果R是一个关系， 序偶x,y∈R,则说 x和 y具有关系R，也可记为xRy 序偶x,y?R,则说x和y没有关系R，也可记为x R y 关系的前域、值域和域 定义: X 到 Y的关系 令 X 和 Y 是任意两个集合，直积X×Y的子集R称为 X到 Y 的关系 。 例题：关系R={1,a,2,B,3,c}, 则有： 2 R b, 2 R B dom R = {1,2,3}, ran R ={a, B, c}, FLD R ={1,2,3,a,B,c} 若 R ? X×Y，则： R是从X到Y的关系 dom R ? X, ranR ?Y R ? domR×ranR ?X×Y 注意 如A={1,2,3}，则IA＝｛1,1,2,2,3,3} 说明:1、X×Y的两个平凡子集X×Y和?，分别为X到Y的 全域关系和空关系。 2、当X＝Y时，称R为X上的关系。(R ? X× X) 定义 恒等关系 设IX是X上的二元关系且满足 IX ＝｛x,x | x∈X｝，则称IX是X上的恒等关系。 定义 n元关系(Relation) 笛卡尔积A1×A2×…×An的任一子集称为一个A1 , A2 , … , An上的 n 元关系。 例题：若H={f,m,s,d}表示一个家庭中父，母，子，女四个人的集合，确定H上的全域关系和空关系，另外再确定H上的一个关系，指出该关系的值域和前域。 解 设H上的同一家庭成员关系为H1， H1={f,m,f,s,f,d,m,f,m,s,m,d,s,f, s,m,s,d,d,f,d,md,s,f,f,m,m, s,s,d,d} H1为全域关系 例题 设H上互不相识的关系为H2,H2为空关系 设H上的长幼关系为H3 H3={f,s,f,d,m,s,m,d