离散数学(第4.4)陈瑜

1、陈瑜Email：134028388008/8/2022离散数学计算机学院8/8/20221计算机科学与工程学院4.4二元关系的闭包设R是A上的关系，我们希望R具有某些有用的性质，比如自反性、对称性、传递性等。如果R不具有这些性质，可以通过在R中添加一些有序对来改造R，得到新关系R，使R具有上述性质，但又不希望R与R相差太多，即添加的有序对要尽可能的少，满足这些要求的R就称为R的闭包。8/8/20222计算机科学与工程学院定义4-4.1设R是定义在A上的二元关系，如果另有A上的关系R满足： 1)R是自反的(或对称的、或可传递的)， 2)R R， 3)对A上任何其它满足1）和2）的关系R，则： R

2、 R。（表明R的最小性） 则称R为R的自反闭包(或对称闭包、或传递闭包)，分别记为r(R)(s(R)或t(R)。8/8/20223计算机科学与工程学院例4.14设集合Aa,b,c,R,是定义在A上的二元关系，求r(R),s(R),t(R),并画出R，r(R),s(R),t(R)的关系图和求出相应的关系矩阵。解：r(R),；s(R),；t(R),。8/8/20224计算机科学与工程学院例4.14设集合Aa,b,c,R,是定义在A上的二元关系，求r(R),s(R),t(R),并画出R，r(R),s(R),t(R)的关系图和求出相应的关系矩阵。解：r(R),；s(R),；t(R),。8/8/2022

3、5计算机科学与工程学院例4.14设集合Aa,b,c,R,是定义在A上的二元关系，求r(R),s(R),t(R),并画出R，r(R),s(R),t(R)的关系图和求出相应的关系矩阵。解：r(R),；s(R),；t(R),。8/8/20226计算机科学与工程学院例4.14设集合Aa,b,c,R,是定义在A上的二元关系，求r(R),s(R),t(R),并画出R，r(R),s(R),t(R)的关系图和求出相应的关系矩阵。解：r(R),；s(R),；t(R),。8/8/20227计算机科学与工程学院例4.14（续）8/8/20228计算机科学与工程学院利用关系图和关系矩阵求闭包求一个关系的自反闭包，即将

4、图中的所有无环的节点加上环；关系矩阵中对角线上的值rij全变为“1”。求一个关系的对称闭包，则在图中，任何一对节点之间，若仅存在一条边，则加一条方向相反的另一条边；关系矩阵中则为：若有rij1(ij)，则令rji1(若rji1),即Ms(R)MRMR-1。求一个关系的传递闭包，则在图中，对任意节点a,b,c,若a到b有一条边，同时b到c也有一条边，则从a到c必增加一条边(当a到c无边时)；在关系矩阵中，若rij1，rjk1,则令rik1(若rik1)。8/8/20229计算机科学与工程学院利用关系图和关系矩阵求闭包求一个关系的自反闭包，即将图中的所有无环的节点加上环；关系矩阵中对角线上的值ri

5、j全变为“1”。求一个关系的对称闭包，则在图中，任何一对节点之间，若仅存在一条边，则加一条方向相反的另一条边；关系矩阵中则为：若有rij1(ij)，则令rji1(若rji1),即Ms(R)MRMR-1。求一个关系的传递闭包，则在图中，对任意节点a,b,c,若a到b有一条边，同时b到c也有一条边，则从a到c必增加一条边(当a到c无边时)；在关系矩阵中，若rij1，rjk1,则令rik1(若rik1)。8/8/202210计算机科学与工程学院利用关系图和关系矩阵求闭包求一个关系的自反闭包，即将图中的所有无环的节点加上环；关系矩阵中对角线上的值rij全变为“1”。求一个关系的对称闭包，则在图中，任何

6、一对节点之间，若仅存在一条边，则加一条方向相反的另一条边；关系矩阵中则为：若有rij1(ij)，则令rji1(若rji1),即Ms(R)MRMR-1。求一个关系的传递闭包，则在图中，对任意节点a,b,c,若a到b有一条边，同时b到c也有一条边，则从a到c必增加一条边(当a到c无边时)；在关系矩阵中，若rij1，rjk1,则令rik1(若rik1)。8/8/202211计算机科学与工程学院定理4-4.1(p100)证明: 3)可采用二种方法，一种是证明是传递闭包（按定义证明）；一种是直接证明 t(R)(书上采用的方法）。设R是集合A上的二元关系，则： 1)r(R)RIA。 2)s(R)RR-1。

7、 3)t(R)。8/8/202212计算机科学与工程学院定理4-4.1(p100)证明: 3)可采用二种方法，一种是证明是传递闭包（按定义证明）；一种是直接证明 t(R)(书上采用的方法）。设R是集合A上的二元关系，则： 1)r(R)RIA。 2)s(R)RR-1。 3)t(R)。8/8/202213计算机科学与工程学院方法一、设R1(1)显然R =R1 。(2)对任意a,b,cA，若R1，R1,(3)设R2是任何一个关系，且有RR2AA，R2是传递的。对任意R1，存在Rj(1j)，使得Rj，所以存在c1,c2,c3,cj-1A，使得：则由R1，必存在Rj,Rk(1j,k)，使得Rj，Rk，即

8、Rj+k(1j+k), Rj+kR1,所以R1，即R1是传递的。8/8/202214计算机科学与工程学院方法一、设R1(1)显然R =R1 。(2)对任意a,b,cA，若R1，R1,(3)设R2是任何一个关系，且有RR2AA，R2是传递的。对任意R1，存在Rj(1j)，使得Rj，所以存在c1,c2,c3,cj-1A，使得：则由R1，必存在Rj,Rk(1j,k)，使得Rj，Rk，即Rj+k(1j+k), Rj+kR1,所以R1，即R1是传递的。8/8/202215计算机科学与工程学院方法一、设R1(1)显然R =R1 。(2)对任意a,b,cA，若R1，R1,(3)设R2是任何一个关系，且有RR

9、2AA、R2是传递的。对任意R1，存在Rj(1j)，使得Rj，所以存在c1,c2,c3,cj-1A，使得： R,R,R,.,R。则由R1，必存在Rj,Rk(1j,k)，使得Rj，Rk，即Rj+k(1j+k), Rj+kR1,所以R1，即R1是传递的。8/8/202216计算机科学与工程学院因RR2，所以R2,R2,R2,R2。由R2是传递的，有：R2,R2,R2,R2。一直下去，最终有：R2。所以，R1R2。由(1),(2),(3)知：R1是R的传递闭包，即t(R)。8/8/202217计算机科学与工程学院因RR2，所以R2,R2,R2,R2。由R2是传递的，有：R2,R2,R2,R2。一直下

10、去，最终有：R2。所以，R1R2。由(1),(2),(3)知：R1是R的传递闭包，即t(R)。8/8/202218计算机科学与工程学院因RR2，所以R2,R2,R2,R2。由R2是传递的，有：R2,R2,R2,R2。一直下去，最终有：R2。所以，R1R2。由(1),(2),(3)知：R1是R的传递闭包，即t(R)。8/8/202219计算机科学与工程学院方法二、设t(R)是R的传递闭包，证明t(R)。 (1)证明t(R)， 是可传递，同时R 由传递闭包的定义知： t(R) 。(2)证明t(R)。只需证对任意的iN+,有Rit(R)。当i1时，因Rt(R),显然成立。设ik时，有Rkt(R)成立

11、。当ik+1时，对任意Rk+1，则存在cA，使得Rk，R由归纳假设有：t(R)，t(R)，由t(R)可传递，所以t(R)，即有：Rk+1t(R)。8/8/202220计算机科学与工程学院方法二、设t(R)是R的传递闭包，证明t(R)。 (1)证明t(R)， 是可传递，同时R 由传递闭包的定义知： t(R) 。(2)证明t(R)。只需证对任意的iN+,有Rit(R)。当i1时，因Rt(R),显然成立。设ik时，有Rkt(R)成立。当ik+1时，对任意Rk+1，则存在cA，使得Rk，R由归纳假设有：t(R)，t(R)，由t(R)可传递，所以t(R)，即有：Rk+1t(R)。8/8/202221计算

12、机科学与工程学院方法二、设t(R)是R的传递闭包，证明t(R)。 (1)证明t(R)， 是可传递，同时R 由传递闭包的定义知： t(R) 。(2)证明t(R)。只需证对任意的iN+,有Rit(R)。当i1时，因Rt(R),显然成立。设ik时，有Rkt(R)成立。当ik+1时，对任意Rk+1，则存在cA，使得Rk，R由归纳假设有：t(R)，t(R)，由t(R)可传递，所以t(R)，即有：Rk+1t(R)。8/8/202222计算机科学与工程学院 由(1)、(2)知：t(R) 。 由归纳法知，对任意有的iN+,有Rit(R)。所以 t(R)。8/8/202223计算机科学与工程学院 例：按照定理4

13、-4.1求r(R)、s(R)、t(R)。 （教材p101例4-4.1）8/8/202224计算机科学与工程学院定理4-4.2：设A是n个元素的集合，R是集合A上的二元关系，则正整数k，kn，使t(R) 。证明：（了解证明方法）对任何(x,y)R+=RR2，必存在最小正整数k，使得(x,y)Rk，即存在A的元素序列a1,a2,ak-1使得xRa1, a1Ra2,ak-1Ry。 不妨设x=a0,y=ak。若kn，那么序列a0,a1,ak中必有元素ai=aj，而ij导致a0Ra1，a1Ra2，ai-1Rai，aiRaj+1，ak-1Rak。很明显，这个序列比原序列短了j-i，且同时又有(x,y) R

14、k+i-j，但k+i-jk，与k的最小性矛盾，即只能kn。因此， t(R) （k n）。8/8/202225计算机科学与工程学院通过课本P101例4-4.1可见，直接计算t(R)异常繁琐，通过Warshall算法可以较方便的计算t(R)。用矩阵计算传递闭包-Warshall(1962)算法(为计算机解决分类问题奠定了基础)8/8/202226计算机科学与工程学院Warshall算法算法见教材p102。（略）计算过程可以简述为：按列号顺序对R的关系矩阵MR的每一列中元素从上至下依次扫描。如果当前扫描的是第i列，那么当遇到1时，将1所对应的行加上第i行。8/8/202227计算机科学与工程学院例4

15、.15设R=,i:=1; i=1时,A的第一列中只有A(1,1)=1,将A的第一行上元素与本身作逻辑加,结果送该行,A不变。i:=i+1; i=2,A的第二列有两个1,即A(1,2)=A(3,2)=18/8/202228计算机科学与工程学院例4.15（续1）分别将A的第1行和第3行与第二行对应元素作逻辑加,将结果分别送1,3行得: (注：i=2) 8/8/202229计算机科学与工程学院例4.15（续2）i:=i+1; i=3,A的第3列有3个1,即A(1,3)=A(2,3)=A(3,3)=1,分别将A的第1,2,3行与第3行对应元素作逻辑加,将结果分别送1,2,3行得:8/8/202230计

16、算机科学与工程学院i:=i+1; i=4,A的第4行全为0,A不变。i:=i+1; i=54=n,停止,即得: 在关系矩阵中，每列（结点）的每个等于1的元素反映的是该元素所在行（结点）到该结点有一条有向边；每行（结点）的每个等于1的元素反映的是该结点到该元素所在列（结点）有一条有向边。8/8/202231计算机科学与工程学院i:=i+1; i=4,A的第4行全为0,A不变。i:=i+1; i=54=n,停止,即得: 在关系矩阵中，每列（结点）的每个等于1的元素反映的是该元素所在行（结点）到该结点有一条有向边；每行（结点）的每个等于1的元素反映的是该结点到该元素所在列（结点）有一条有向边。8/8

17、/202232计算机科学与工程学院闭包运算的性质定理4-4.3 设R1，R2是集合A上的关系，且R1R2，则：1)r(R1)r(R2)2)s(R1)s(R2)3)t(R1)t(R2)定理4-4.4 设R是集合A上的关系，则：1)若R是自反的，则s(R),t(R)也是自反的2)若R是对称的，则r(R),t(R)也是对称的3)若R是传递的，则r(R)也是传递的8/8/202233计算机科学与工程学院闭包运算的性质定理4-4.3 设R1，R2是集合A上的关系，且R1R2，则：1)r(R1)r(R2)2)s(R1)s(R2)3)t(R1)t(R2)定理4-4.4 设R是集合A上的关系，则：1)若R是自

18、反的，则s(R),t(R)也是自反的2)若R是对称的，则r(R),t(R)也是对称的3)若R是传递的，则r(R)也是传递的8/8/202234计算机科学与工程学院多重闭包定义4-4.2 1）集合A上的关系的自反对称闭包定义为: rs(R)r(s(R) 2）集合A上的关系的自反传递闭包定义为: rt(R)r(t(R) 3）集合A上的关系的对称传递闭包定义为: st(R)s(t(R)同理，我们还可定义sr(R),tr(R),ts(R),8/8/202235计算机科学与工程学院多重闭包定理4-4.5 设R是集合A上的关系，则： 1)rs(R)sr(R) 2)rt(R)tr(R) 3)st(R)ts(

19、R)证明： 1)sr(R)=s(RIA)=(RIA)(RIA)-1 = RIAR-1IA = (RR-1)IA =s(R)IA=rs(R)8/8/202236计算机科学与工程学院多重闭包定理4-4.5 设R是集合A上的关系，则： 1)rs(R)sr(R) 2)rt(R)tr(R) 3)st(R)ts(R)证明： 1)sr(R)=s(RIA)=(RIA)(RIA)-1 = RIAR-1IA = (RR-1)IA =s(R)IA=rs(R)8/8/202237计算机科学与工程学院多重闭包定理4-4.5 设R是集合A上的关系，则： 1)rs(R)sr(R) 2)rt(R)tr(R) 3)st(R)t

20、s(R)证明： 2)tr(R)=t(RIA) =(RIA)(RIA)2 =IARR2 =IAt(R)=rt(R) 。8/8/202238计算机科学与工程学院多重闭包定理4-4.5 设R是集合A上的关系，则： 1)rs(R)sr(R) 2)rt(R)tr(R) 3)st(R)ts(R)证明： 3)由定理4-4.3和4-4.4可得t（R）t（s（R），从而st（R）sts（R）;其次，ts（R）是对称的，所以s（ts（R）=ts（R），于是st（R） ts（R）。可以进一步证明该包含关系是严格的。 所以有：st（R） ts(R)。8/8/202239计算机科学与工程学院例4.16设A1,2,R,则：传递