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

1、复旦大学计算机院赵一鸣离散数学(中文课件) 四、投影运算四、投影运算 在数据库中在数据库中, 用关系来描述数据时常用投用关系来描述数据时常用投影运算进行数据操作。影运算进行数据操作。 定义定义 2.10：设：设R是是A1,A2,An的的n元关系元关系,定义定义R在在Ai1,Ai2,Aim上的投影是一个上的投影是一个m元关系元关系,它是通过选取它是通过选取R中的每个有序中的每个有序n元元组的第组的第i1,第第i2,第第im个分量组成有序个分量组成有序m元元组作为组作为m元关系中的元素元关系中的元素,这个投影记为这个投影记为 Ai1,Ai2,Aim(R)。复旦大学计算机院赵一鸣离散数学(中文课件)

2、 例：四元关系例：四元关系R和三元关系和三元关系S定义如下定义如下: R SA B C D D E Fa b c g b g ad a f h d a fa b d g ABD(R) EF(S)A B D E Fa b g g ad a h a fa b g ABD(R) EF(S)A B D E Fa b g g ad a h a f ABD(R) EF(S)A B D E Fa b g g ad a h a f复旦大学计算机院赵一鸣离散数学(中文课件) 关系关系R的投影的元素个数的投影的元素个数 R的元素个数。的元素个数。 AC(R)A Ca cd fa d复旦大学计算机院赵一鸣离散数学(

3、中文课件) 讨论了关系的性质讨论了关系的性质:自反自反,反自反反自反,对称对称,反反对称对称,传递传递 通常一些关系不一定具有这些性质通常一些关系不一定具有这些性质,但若但若在此关系基础之上适当增加一些元素在此关系基础之上适当增加一些元素,就就可以使之具有所要的性质了。可以使之具有所要的性质了。 例：例：R=(a,b),(b,a),(a,c),不对称。不对称。 若增加元素若增加元素(c,a),得得R=(a,b),(b,a),(a,c), (c,a)，而且而且R是一个包含是一个包含R的不可减少的不可减少任何元素的对称关系任何元素的对称关系 闭包闭包复旦大学计算机院赵一鸣离散数学(中文课件)2.5

4、 关系的闭包关系的闭包 一、闭包的定义一、闭包的定义 从给定关系从给定关系R出发构造一个新关系出发构造一个新关系R,使使得得R包含包含R,并且并且R是具有某种性质的关是具有某种性质的关系系,同时同时R又是包含又是包含R的最小关系。的最小关系。 从关系从关系R得到新关系得到新关系R的运算通称为闭包的运算通称为闭包运算。运算。复旦大学计算机院赵一鸣离散数学(中文课件) 定义定义 2.11：设：设R是是A上的二元关系上的二元关系,定义定义R的的自反自反(对称对称,传递传递)闭包闭包记为记为R,满足下列满足下列三个条件：三个条件： (1)R是自反的是自反的(对称的对称的, 传递的传递的)； (2) R

5、 R； (3)对任一自反对任一自反(对称对称, 传递传递)关系关系R,若若R R,则则R R。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)

6、=R。自反的自反的(对称的对称的, 传递的传递的)； R R；对任一自反对任一自反(对称对称, 传递传递)关系关系R,若若R R,则则R R。复旦大学计算机院赵一鸣离散数学(中文课件) 定理定理 2.5：设：设R是是A上的二元关系上的二元关系, 则则 (1)R是自反的当且仅当是自反的当且仅当r(R)=R； (2)R是对称的当且仅当是对称的当且仅当s(R)=R； (3)R是传递的当且仅当是传递的当且仅当t(R)=R。 定理定理 2.6：设：设R1和和R2是是A上的二元关上的二元关系系,R1 R2则则 (1)r(R1) r(R2)； (2)s(R1) s(R2)； (3)t(R1) t(R2)。复

7、旦大学计算机院赵一鸣离散数学(中文课件) 设设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)|a A) 证明：令证明：令R=RIA。验证验证R满足闭包的满足闭包的三个条件三个条件复旦大学计算机院赵一鸣离散数学(中文课件) (1) 自反自反 (2)

8、 R R， (3)假设有假设有A上的二元关系上的二元关系R，R自反且自反且R R，(目标是目标是R R) 定理定理 2.8：设：设R是集合是集合A上的二元关系上的二元关系, 则则s(R)=RR-1。 证明：令证明：令R=RR-1。验证验证R满足闭包的三个条满足闭包的三个条件件 (1) R=RR-1对称对称(R是对称的当且仅当是对称的当且仅当R=R-1) (2)R RR-1=R， (3)假设有假设有A上二元关系上二元关系R，R对称且对称且R R，(目标目标R R)复旦大学计算机院赵一鸣离散数学(中文课件) 例：整数集上的例：整数集上的“”的对称闭包是的对称闭包是“” ，少了，少了= 任一非空集任

9、一非空集A，其上的恒等关系的自反其上的恒等关系的自反(对称对称)闭包就是恒等关系闭包就是恒等关系 其上的空关系的自反闭包是恒等关系其上的空关系的自反闭包是恒等关系 其上的空关系的对称闭包是空关系其上的空关系的对称闭包是空关系 定理定理 2.9：设：设R是集合是集合A上的二元关系上的二元关系, 则则1)(iiRRt证明：令证明：令 R R=1iiR。验证。验证 R R满足闭包满足闭包的三个条件的三个条件复旦大学计算机院赵一鸣离散数学(中文课件) (1)传递：对任意传递：对任意(a,b),(b,c) R=RR2R3 (a,c) R, (2)R RR2R3=R， (3)假设有假设有A上的二元关系上的

10、二元关系R，R传递且传递且R R，(目标是目标是R R)复旦大学计算机院赵一鸣离散数学(中文课件) 定理定理 2.10：设：设R是有限集是有限集A上的二元关系上的二元关系, 且且|A|=n,则则niiRRt1)(复旦大学计算机院赵一鸣离散数学(中文课件) 例：例：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

11、)和和t(R)都是对称的都是对称的 (3)若若R是传递的是传递的,则则r(R)是传递的。是传递的。 证明证明(1)(3) 证明证明:(1)对任意的对任意的a A,目标是目标是(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

12、(R); (3)st(R) ts(R)。 定理定理 2.6:R1 R2则则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上的等价关系。若上的等价

13、关系。若aRb,则称则称a与与b等价。等价。复旦大学计算机院赵一鸣离散数学(中文课件) 例：设整数集例：设整数集I上的模上的模m同余关系同余关系R是是I上的上的等价关系。等价关系。 证明证明:(1)自反自反(目标是证明对任意目标是证明对任意a I，有有aRa) (2)对称对称(目标是证明若有目标是证明若有aRb，则必有则必有bRa) (3)传递传递(目标是证明若有目标是证明若有aRb，bRc，则必则必有有aRc) 因此整数集因此整数集I上的模上的模m同余关系同余关系R是是I上的等上的等价关系价关系复旦大学计算机院赵一鸣离散数学(中文课件)二、集合的划分二、集合的划分定义定义 2.12 2.12

14、： 设： 设A A 是任意一个集合。是任意一个集合。 A Ai i A, AA, Ai i ,i=1,2,i=1,2,n,n, 若若,1AAnii且且 A Ai iA Aj j= =(i,j=1,2,(i,j=1,2, , ,n,in,i j),j), 则 称则 称 = =AA1 1,A,A2 2, ,A,An n 是是A A 的一个划分。其中每个的一个划分。其中每个 A Ai 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 , 由 于由 于 a b c = a , b , c ，ab=ac=bc=，S是是A的划分。的划分。 对于对于T,显然是显然是A的划分。的划分。 对于对于U, 由于由于aca,b,c，所以不是所以不是A的划分的划分 对 于对 于 V, 尽 管尽 管 a , b b , c = a