离散数学(第11讲)关系2

《离散数学(第11讲)关系2》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、栾新成四川大学软件学院luanxch@sina.com8599782213808024081第5章二元关系(2)主要内容二元关系的闭包2021年7月26日2二元关系的闭包设R是A上的关系，我们希望R具有某些有用的性质，比如自反性、对称性、传递性等。如果R不具有这些性质，可以通过在R中添加一些有序对来改造R，得到新关系R′，使R′具有上述性质，但又不希望R′与R相差太多，即添加的有序对要尽可能的少，满足这些要求的R′就称为R的闭包。2021年7月26日3二元关系的闭包定义4-4.1设R是定义在A上的二元关

2、系，若存在A上的关系R′满足：R′是自反的(或对称的、或可传递的)，RR′，对A上任何其它满足1）和2）的关系R〞，则：R′R〞。（表明R′的最小性）则称R′为R的自反闭包(或对称闭包、或传递闭包)。R的自反闭包、对称闭包、传递闭包分别记为r(R)、s(R)和t(R)。2021年7月26日4二元关系的闭包例4.14设集合A＝{a,b,c},R＝{,,}是定义在A上的二元关系，求r(R),s(R),t(R),并画出R,r(R),s(R),t(R)的关系图和求出相应的关系矩

3、阵。解：r(R)＝{,,,,}；s(R)＝{,,,,}；t(R)＝{,,,}。2021年7月26日5二元关系的闭包2021年7月26日6二元关系的闭包例求下列关系的r(R)、s(R)、t(R)：(1)整数集Z上的“<”关系(2)整数集Z上的“=”关系解:(1)Z上的“<”关系的r(R)为“≤”；s(R)为“≠”；t(R)为“＜”(2)Z上的“=”关系的r(R)为“=

4、”；s(R)为“=”；t(R)为“=”2021年7月26日7利用关系图和关系矩阵求闭包求一个关系的自反闭包，即将图中的所有无环的节点加上环；关系矩阵中对角线上的值rij全变为“1”。求一个关系的对称闭包，则在图中，任何一对节点之间，若仅存在一条边，则加一条方向相反的另一条边；关系矩阵中则为：若有rij＝1(i≠j)，则令rji＝1(若rji≠1),即Ms(R)＝MR∨MR-1。求一个关系的传递闭包，则在图中，对任意节点a,b,c,若a到b有一条边，同时b到c也有一条边，则从a到c必增加一条边(当a到c

5、无边时)；在关系矩阵中，若rij＝1，rjk＝1,则令rik＝1(若rik≠1)。2021年7月26日8利用关系运算求闭包定理4-4.1设R是集合A上的二元关系，则：1)r(R)＝R∪IA。2)s(R)＝R∪R-1。3)t(R)＝证明3）可采用二种方法，一种是证明是传递闭包（按定义证明）；一种是直接证明t(R)＝(书上采用的方法）。2021年7月26日9利用关系运算求闭包方法一、设R1＝(1)显然R=R1。(2)对任意a,b,c∈A，若∈R1，∈R1,则由R1＝

6、，必存在Rj,Rk(1≤j,k≤)，使得∈Rj，∈Rk，即∈Rj+k(1≤j+k≤),∵Rj+kR1,所以∈＝R1，即R1是传递的。(3)设R2是R的任何一个关系，且有RR2A×A，R2是传递的。对任意∈R1，存在Rj(1≤j≤)，使得∈Rj，所以存在c1,c2,c3,…,cj-1∈A，使得：2021年7月26日10利用关系运算求闭包∈R,∈R,∈R,....,∈R

7、。因RR2，所以∈R2,∈R2,∈R2,…,∈R2。由R2是传递的，有：∈R2,∈R2,∈R2,…,∈R2。一直下去，最终有：∈R2。所以，R1R2。由(1),(2),(3)知：R1是R的传递闭包，即t(R)＝2021年7月26日11利用关系运算求闭包方法二、设t(R)是R的传递闭包，证明t(R)＝。(1)证明t(R)，∵是可传递，同时R∴由传递闭包的定义知：t(

8、R)。(2)证明t(R)。只需证对任意的i∈N+,有Rit(R)。当i＝1时，因Rt(R),显然成立。设i＝k时，有Rkt(R)成立。当i＝k+1时，对任意∈Rk+1，则存在c∈A，使得∈Rk，∈R，由归纳假设有：∈t(R)，∈t(R)，由t(R)可传递，所以∈t(R)，即有：Rk+1t(R)。2021年7月26日12利用关系运算求闭包由归纳法知，对任意有的i∈