《关系的闭包运算》ppt课件

《《关系的闭包运算》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、3-8关系的闭包运算关系的闭包概念闭包的求法闭包的闭包1一、关系的闭包概念引列：设A={1,2,3}，R为A上的二元关系，R={<1,2>,<2,3>,<3,1>}，求包含关系R且有自反性的新关系，这种关系是唯一的吗？解：根据自反性的定义，可知A上的自反关系都包含恒等关系IA，所以含有R且有自反性的关系为：R1=R∪IA={<1,1>,<2,2>,<3,3>,<1,2>,<2,3>,<3,1>}在R1上继续添加序偶，还可得到含有R且有自反性的关系：R2=R1∪{<2,1>}，R3=R1∪{<3,2

2、>}，……其中：R1是满足“含有R且有自反性”要求的最小关系，R1就是关系R的自反闭包。类似方法可得到对称闭包和传递闭包。2定义：R是非空集合A上的关系,若A另外有一个关系R’满足如下三条：1）R’是自反的(对称的，传递的）2）RR’3）对A上任何一个满足以上两条的关系R’’，均有R’R’’则称关系R’为R的自反(对称,传递)闭包,记作r(R),(s(R),t(R))。自反(对称、传递)闭包是包含R的最小自反(对称、传递)关系。3例：设集合A={a,b,c},A上的关系R={,<

3、a,b>,}，求r(R),s(R),t(R)abcRabcr(R)abcs(R)abct(R)解:自反闭包r(R)={,,,,}对称闭包s(R)={,,,,}传递闭包t(R)={,,,}关系图如下：4r(R)：是在R的基础上添加自回路，使得每点均有自回路；s(R)：是在R中两点间只有一条弧的情况下，再添一条反向弧，使两点间或是0条弧，或是两条弧，原

4、来两点间没有弧不能添加；t(R)：是在R中如结点a通过有向路能通到x，则添加一条从a到x的有向弧，其中包括如a能达到自身，则必须添从a到a的自回路。例：R={,,,,}求t(R)。R的关系图：abcde从关系图中可以看出：a能到达a,c,d,e,则要加,,,；b能到达b,d,e,则要加,,；c能到达e,则要加，这些加入后才成为t(R)。5定理：设R是非空集合A上的关系,

5、则1)R是自反的充要条件是R=r(R)2)R是对称的充要条件是R=s(R)3)R是传递的充要条件是R=t(R)（证明略）6二、闭包的求法定理：设R是非空集合A上的关系,则r(R)=RA。证明：RRA，IARA，∴RA是自反的。满足定义中的前两条。下面证对A上任何一个满足以上两条的关系R’’，均有RAR’’。设R”满足RR”,且R”是自反的,∴IxR’’∴RIxR’’，满足定义第三条。∴r(R)=RA7定理：设R是非空集合A上的关系,则s(R)=RR-

6、1证明：1）(RR-1)-1=R-1(R-1)-1=R-1R=RR-1∴RR-1是对称的，满足定义的第1条；2）显然RRR-1，满足定义第2条；3）假设R”,使得RR”且R”是对称的，R-1，则R，∵RR”，∴R”，又∵R”对称，∴R”,∴R-1R”∴RR-1R”，则满足定义第三条；∴s(R)=RR-18定理：设R是非空集合A上的关系,则t(R)=Ri=RR2…=R+(证明过程略)1)利用归纳法证明右左；2)证明左

7、右，即证明右为传递的即可。U∞i=19例：集合A={a,b,c}，A上的关系R={,,}求r(R)，s(R)，t(R)解：r(R)=RIA={,,,,,}s(R)=RRc={,,,,,}R={,,}R2={,,}R3={,,}=IAR4=R3R=IAR

8、=RR5=R4R=RR=R2继续算，可得以下规律：R=R4=R7=…、R2=R5=R8=…、R3=R6=R9=…∴t(R)=RR2R3...=RR2R3={,,,,,,,}10推论：设R是非空有限集合A上的关系,

9、A

10、=n，则存在一个正整数k≤n，使得t(R)=RR2…Rk证明：由定理已知t(R)=RR2…∴若t(R)，则存在一个正整数m，使得R