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

《复旦大学 计算机院 赵一鸣 离散数学(中文课件) 3》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、四、投影运算在数据库中,用关系来描述数据时常用投影运算进行数据操作。定义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),

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

3、自反闭包,对称闭包和传递闭包分别记为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。自反的(对称的,传递的)；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是

4、A上的二元关系,R1R2则(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)=R∪IA。(IA={(a,a)

5、aA})证明：令R'=R∪IA。验证R'满足闭包的三个条件(1)自反(2)RR'，(3)假设有A上的

6、二元关系R''，R''自反且RR''，(目标是R'R'')定理2.8：设R是集合A上的二元关系,则s(R)=R∪R-1。证明：令R'=R∪R-1。验证R'满足闭包的三个条件(1)R'=R∪R-1对称(R是对称的当且仅当R=R-1)(2)RR∪R-1=R'，(3)假设有A上二元关系R''，R''对称且RR''，(目标R'R'')例：整数集上的“<”的对称闭包是“≠”<,>，少了=任一非空集A，其上的恒等关系的自反(对称)闭包就是恒等关系其上的空关系的自反闭包是恒等关系其上的空关系的对称闭包是空关系定理2.9：设R是集合A上的二元关系,则(1)传递：对任意(a

7、,b),(b,c)R'=R∪R2∪R3∪(a,c)R',(2)RR∪R2∪R3∪=R'，(3)假设有A上的二元关系R''，R''传递且RR''，(目标是R'R'')定理2.10：设R是有限集A上的二元关系,且

8、A

9、=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)对任意的aA,目标是(

10、a,a)s(R),(a,a)t(R)(3)对任意(a,b),(b,c)r(R)=R∪IA,目标是(a,c)R∪IAR是传递的,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:R1R2则t(R1)t(R2),s(R1)s(R2)定理2.11(2)(若R是对称的,则r(R)和t(R)都是对称的定理2.5(2)R是对称的当且仅当s(R)=Rts(R)是否与st(R)相等?2.6等价关系与划分一、等价关系