复旦大学计算机院赵一鸣离散数学(中文课件)3.ppt

四、投影运算 在数据库中, 用关系来描述数据时常用投影运算进行数据操作。 定义 2.10：设R是A1,A2,An的n元关系,定义R在Ai1,Ai2,Aim上的投影是一个m元关系,它是通过选取R中的每个有序n元组的第i1,第i2,第im个分量组成有序m元组作为m元关系中的元素,这个投影记为Ai1,Ai2,Aim(R)。,例：四元关系R和三元关系S定义如下:,关系R的投影的元素个数R的元素个数。,讨论了关系的性质:自反,反自反,对称,反对称,传递 通常一些关系不一定具有这些性质,但若在此关系基础之上适当增加一些元素,就可以使之具有所要的性质了。 例：R=(a,b),(b,a),(a,c),不对称。 若增加元素(c,a),得R=(a,b),(b,a),(a,c), (c,a)，而且R是一个包含R的不可减少任何元素的对称关系 闭包,2.5 关系的闭包,一、闭包的定义 从给定关系R出发构造一个新关系R,使得R包含R,并且R是具有某种性质的关系,同时R又是包含R的最小关系。 从关系R得到新关系R的运算通称为闭包运算。,定义 2.11：设R是A上的二元关系,定义R的自反(对称,传递)闭包记为R,满足下列三个条件： (1)R是自反的(对称的, 传递的)； (2) RR； (3)对任一自反(对称, 传递)关系R“,若RR“,则RR“。R的自反闭包,对称闭包和传递闭包分别记为r(R),s(R)和t(R)(t(R)又记为R+)。,例：若R对称，s(R)=? 也就是说，R对称当且仅当s(R)=R 定理 2.5：设R是A上的二元关系, 则 (1)R是自反的当且仅当r(R)=R； (2)R是对称的当且仅当s(R)=R； (3)R是传递的当且仅当t(R)=R。,自反的(对称的, 传递的)； RR；对任一自反(对称, 传递)关系R“,若RR“,则RR“。,定理 2.5：设R是A上的二元关系, 则 (1)R是自反的当且仅当r(R)=R； (2)R是对称的当且仅当s(R)=R； (3)R是传递的当且仅当t(R)=R。 定理 2.6：设R1和R2是A上的二元关系,R1R2则 (1)r(R1)r(R2)； (2)s(R1)s(R2)； (3)t(R1)t(R2)。,设A=1,2,3,R=(1,2),(1,3),则 r(R)=(1,1),(2,2),(3,3),(1,2),(1,3) s(R)=(1,2),(1,3),(2,1),(3,1) t(R)=(1,2),(1,3) 二、确定闭包的方法 定理 2.7：设R是集合A上的二元关系,IA是集合A上的恒等关系,则r(R)=RIA。(IA=(a,a)|aA) 证明：令R=RIA。验证R满足闭包的三个条件,(1) 自反 (2) RR， (3)假设有A上的二元关系R，R自反且RR，(目标是RR) 定理 2.8：设R是集合A上的二元关系, 则s(R)=RR-1。 证明：令R=RR-1。验证R满足闭包的三个条件 (1) R=RR-1对称(R是对称的当且仅当R=R-1) (2)RRR-1=R， (3)假设有A上二元关系R，R对称且RR，(目标RR),例：整数集上的“，少了= 任一非空集A，其上的恒等关系的自反(对称)闭包就是恒等关系 其上的空关系的自反闭包是恒等关系 其上的空关系的对称闭包是空关系 定理 2.9：设R是集合A上的二元关系, 则,(1)传递：对任意(a,b),(b,c)R=RR2R3 (a,c)R, (2)RRR2R3=R， (3)假设有A上的二元关系R，R传递且RR，(目标是RR),定理 2.10：设R是有限集A上的二元关系, 且|A|=n,则,例：A=a,b,c,d,R=(a,b),(b,a),(b,c),(c,d),求t(R),四、闭包的性质 定理 2.11：设R是A上的二元关系。 (1)若R是自反的,则s(R)和t(R)都是自反的 (2)若R是对称的,则r(R)和t(R)都是对称的 (3)若R是传递的,则r(R)是传递的。 证明(1)(3) 证明:(1)对任意的aA,目标是(a,a)s(R), (a,a)t(R) (3)对任意(a,b),(b,c)r(R)=RIA,目标是(a,c)RIA,R是传递的,s(R)是否传递？ 不一定 定理 2.12：设R是A上的二元关系, 则 (1)rs(R)=sr(R)(这里rs(R)读作R的对称自反闭包); (2)rt(R)=tr(R); (3)st(R)ts(R)。 定理 2.6:R1R2则t(R1)t(R2), s(R1)s(R2) 定理2.11(2)(若R是对称的,则r(R)和t(R)都是对称的 定理 2.5(2)R是对称的当且仅当s(R)=R ts(R)是否与st(R)相等?,2.6 等价关系与划分,一、等价关系 定义 2.13：设R是集合A上的二元关系,若R是自反的、对称的和传递的,则称R是A上的等价关系。若aRb,则称a与b等价。,例：设整数集I上的模m同余关系R是I上的等价关系。 证明:(1)自反(目标是证明对任意aI，有aRa) (2)对称(目标是证明若有aRb，则必有bRa) (3)传递(目标是证明若有aRb，bRc，则必有aRc) 因此整数集I上的模m同余关系R是I上的等价关系,例:设A=a,b,c,考察下列几个由A的子集所组成的集合： P=a,b,c,S=a,b,c,T=a,b,c,U=a,c,V=a,b,b,c,W=a,b,a,c,c, 对于P,由于a,bc=a,b,c，a,bc=，P是A的划分。 对于S,由于abc=a,b,c，ab=ac=bc=，S是A的划分。 对于T,显然是A的划分。 对于U, 由于aca,b,c，所以不是A的划分 对于V, 尽管a,bb,c=a,b,c，但a,bb,c=b,所以不是A的划分。 类似可知W也不是A的划