首页 理论教育 离散数学上册第五节:关系闭包运算

离散数学上册第五节:关系闭包运算

时间:2023-10-19 理论教育 版权反馈
【摘要】:如上所述,关系的合成和关系的逆都可以构成新的关系。我们还可以对给定的关系用扩充一些序偶的办法得到具有某些特殊性质的新关系,这就是闭包运算。则称关系R′为R的自反闭包,记作r。由定理2可以看出,若已知集合A上的二元关系R的关系图,只要在图上对没有自回路的结点都添加上自回路,便可以画成R的自反闭包r的关系图。例2 根据图1写出关系R和关系矩阵MR,并求出R的自反闭包r和对称闭包s。

离散数学上册第五节:关系闭包运算

如上所述,关系的合成和关系的逆都可以构成新的关系。我们还可以对给定的关系用扩充一些序偶的办法得到具有某些特殊性质的新关系,这就是闭包运算。

定义1 设R是A上的二元关系,如果另一个关系R′满足:

(1)R′是自反的(对称的、可传递的);

(2)R′⊇R;

(3)对于任何自反的(对称的、可传递的)关系R″,如果有R″⊇R,就有R″⊇R′。

则称关系R′为R的自反(对称、传递)闭包,记作r(R)(s(R),t(R))。

例1 设集合A={1,3,5,7}上的关系R={(1,3),(1,1),(5,7)},试求r(R),s(R),t(R)。

解 r(R)={(1,3),(1,1),(5,7),(3,3),(5,5),(7,7)};

s(R)={(1,3),(3,1),(1,1),(5,7),(7,5)};

t(R)={(1,3),(1,1),(5,7)}。

上面我们是根据定义利用添加元素的办法得到r(R),s(R)和t(R),下面介绍由已知关系R求r(R),s(R)和t(R)的方法。

注意到自反(对称、传递)闭包,应是包含的最小自反(对称、传递)关系,所以有:

定理1 设R是集合A上的二元关系,则

(1)R是自反的,当且仅当r(R)=R;

(2)R是对称的,当且仅当s(R)=R;

(3)R是传递的,当且仅当t(R)=R。

证明(1)若R是自反的,又有R⊇R,且对于任何包含R的自反关系R″,都有R″⊇R,所以R满足R′的全部条件,即r(R)=R。反之,若r(R)=R,由自反闭包的定义中的条件(1),可得R是自反的。

(2)、(3)可供读者作为练习自证。证毕。

定理2 设R是集合A上的二元关系,IA是集合A上的恒等关系,则r(R)=R∪IA

证明 设R′=R∪IA,则R′⊇R且R′⊇IA,R′是自反的,满足了自反闭包定义的前两个条件。

假设R″是A上的自反关系,且R″⊇R,必有R″⊇IA,所以R″⊇R∪IA,即R″⊇R′,满足了自反闭包定义的第三个条件,因此r(R)=R∪IA。证毕。

由定理2可以看出,若已知集合A上的二元关系R的关系图,只要在图上对没有自回路的结点都添加上自回路,便可以画成R的自反闭包r(R)的关系图。

定理3 设R是集合A上的二元关系,则s(R)=R∪R-1

证明 设R′=R∪R-1,则R′⊇R,且R′⊇R-1。对于任意(a,b)∈R′,有(a,b)∈R或(a,b)∈R-1,于是(b,a)∈R-1或(b,a)∈(R-1-1=R,因此(b,a)∈R-1∪R=R′,故R′是对称的。

假设R″是对称关系,且R″⊇R。对于任意的(a,b)∈R′,有(a,b)∈R∪R-1,于是(a,b)∈R或者(a,b)∈R-1。若(a,b)∈R,由R″⊇R,则(a,b)∈R″;若(a,b)∈R-1,有(b,a)∈R,则(b,a)∈R″,再由R″是对称的,有(a,b)∈R″,所以R″⊇R′,故s(R)=R=R∪R-1。证毕。

由定理3可以得到,若已知集合A上的二元关系R的关系图,只要将图中所有单向弧都画为双向弧,便可以画成R的对称闭包s(R)的关系图。

例2 根据图1写出关系R和关系矩阵MR,并求出R的自反闭包r(R)和对称闭包s(R)。

所以,t(R)={(a,a),(a,b),(a,c),(a,d),(b,a),(b,b),(b,c),(b,d),(c,d)}。

例5 设R是集合A上的二元关系,试证:(www.xing528.com)

(1)若R是自反的,则s(R)和t(R)也是自反的;

(2)若R是对称的,则r(R)和t(R)也是对称的;

(3)若R是传递的,则r(R)也是传递的。

证明(1)由于s(R)=R∪R-1,所以R⊆s(R)。

又因为R是自反的,所以R=r(R)=R∪IA,于是IA⊆R,有IA⊆s(R),因此s(R)是自反的。

由于t(R)=R∪R2∪R3∪…,有R⊆t(R)。而R是自反的,于是IA⊆R,则IA⊆t(R),因此t(R)是自反的。

(2)由于r(R)=R∪IA,而R和IA都是对称的,所以r(R)是对称的。

由于t(R)=R∪R2∪R3∪…,下面用数学归纳法证明Ri(i=1,2,3,…)都是对称的。

因为R是对称的,所以i=1时命题成立。

假设Rk是对称的,下面证明Rk+1也是对称的。

由于Rk+1=Rk·R,对于任意(a,b)∈Rk+1,有(a,b)∈Rk·R,一定存在元素c,使(a,c)∈Rk,且(c,b)∈R,于是(c,a)∈Rk,且(b,c)∈R,从而(b,a)∈R·Rk,故Rk+1是对称的。

下面利用这个结论来证明t(R)的对称性。

任取(a,b)∈t(R),则一定存在k,使(a,b)∈Rk。因为Rk是对称的,有(b,a)∈Rk,从而(b,a)∈t(R),所以t(R)是对称的。

(3)对任意x,y,z∈A,若(x,y)∈r(R),且(y,z)∈r(R),则有(x,y)∈R,或(x,y)∈IA;(y,z)∈R或(y,z)∈IA。若(x,y),(y,z)∈R,则因为R传递,所以(x,z)∈R,(x,z)∈r(R);若(x,y)∈R,且(y,z)∈IA,则y=z,所以(x,z)∈R,(x,z)∈r(R);若(x,y)∈IA,且(y,z)∈R,则x=y,所以(x,z)∈R,即(x,z)∈r(R)。若(x,y)∈IA,且(y,z)∈IA,则x=y=z,故(x,z)∈IA,(x,z)∈r(R)。证毕。

例6 设R1和R2是集合A上的二元关系,且R1⊇R2,求证:

(1)r(R1)⊇r(R2);

(2)s(R1)⊇s(R2);

(3)t(R1)⊇t(R2)。

证明(1)因为R2⊆R1,所以R2⊆r(R1),又因为r(R1)是R1的自反闭包,故r(R1)是自反的,从而r(R2)⊆r(R1)。

(2)因为R2⊆R1,所以R2⊆s(R1),又因为s(R1)是R1的对称闭包,故s(R1)是对称的,从而s(R1)⊇s(R2)。

类似地可证明(3)。证毕。

例7 设R是集合A上的二元关系,则

(1)rs(R)=sr(R);

(2)rt(R)=tr(R);

(3)st(R)⊆ts(R)。

证明(1)方法1:R⊆r(R),由例6知有s(R)⊆sr(R),所以rs(R)⊆rsr(R),由例5知有sr(R)自反,由定理1知rsr(R)=sr(R),所以rs(R)⊆sr(R)。

反之,R⊆s(R),由例6知r(R)⊆rs(R),所以sr(R)⊆sr(s(R)),由例5知r(s(R))是对称的,由定理1知sr(s(R))=rs(R),所以sr(R)⊆rs(R)。因此,有:

sr(R)=rs(R)。

方法2:rs(R)=r(R∪R-1)=R∪R-1∪IA=R∪IA∪R-1∪IA=R∪IA∪(R∪IA-1=s(R∪IA)=sr(R)。

(2)因为R⊆r(R),由例5知tr(R)⊆tr(R),所以rt(R)⊆rtr(R)。由例5知tr(R)是自反的,由定理1知rtr(R)=tr(R),所以rt(R)⊆tr(R)。

类似地可证tr(R)⊆rt(R),故有

rt(R)=tr(R)

读者可自证(3)。证毕。

免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。

我要反馈