离散数学闭包证明(离散数学-二元关系)

二元关系 设S是一个非空集合,R是关于S的元素的一个条件.如果对S中任意一个有序元素对(a,b),我们总能确定a与b是否满足条件R,就称R是S的一个关系(relation).如果a与b满足条件R,则称a与b满足条件R,则称a与b有关系R,记做aRb;否则称a与b无关系R.关系R也成为二元关系.,现在小编就来说说关于离散数学闭包证明?下面内容希望能帮助到你,我们来一起看看吧!

离散数学闭包证明(离散数学-二元关系)

离散数学闭包证明

二元关系

设S是一个非空集合,R是关于S的元素的一个条件.如果对S中任意一个有序元素对(a,b),我们总能确定a与b是否满足条件R,就称R是S的一个关系(relation).如果a与b满足条件R,则称a与b满足条件R,则称a与b有关系R,记做aRb;否则称a与b无关系R.关系R也成为二元关系.

定义:

集合 X 与集合 Y 上的二元关系是 R=(X, Y, G(R)) 当中 G(R),称为R 的图,是笛卡儿积 X × Y的子集.若 (x,y) ∈ G(R) 则称 x 是 R-关系於 y 并记作 xRy 或 R(x,y).

但经常地我们把关系与其图等价起来,即若 R ⊆ X × Y 则 R 是一个关系.

闭包

关系的闭包运算时关系上的一元运算,它把给出的关系R扩充成一新关系R’,使R’具有一定的性质,且所进行的扩充又是最“节约”的。 比如自反闭包,相当于把关系R对角线上的元素全改成1,其他元素不变,这样得到的R’是自反的,且是改动次数最少的,即是最“节约”的。

一个关系R的闭包,是指加上最小数目的有序偶而形成的具有自反性,对称性或传递性的新的有序偶集,此集就是关系R的闭包。

设R是集合A上的二元关系,R的自反(对称、传递)闭包是满足以下条件的关系R':

(i)R'是自反的(对称的、传递的);

(ii)R'⊇R;

(iii)对于A上的任何自反(对称、传递)关系R",若R"⊇R,则有R"⊇R'。

R的自反、对称、传递闭包分别记为r(R)、s(R) 和t(R)。

性质1

集合A上的二元关系R的闭包运算可以复合,例如:

ts(R)=t(s(R))

表示R的对称闭包的传递闭包,通常简称为R的对称传递闭包。而tsr(R)则表示R的自反对称传递闭包。

性质2

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

(a)如果R是自反的,那么s(R)和t(R)也是自反的;

(b)如果R是对称的,那么r(R)和t(R)也是对称的;

(c)如果R是传递的,那么r(R)也是传递的。

性质3

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

(a)rs(R)=sr(R);

(b)rt(R)=tr(R);

(c)ts(R)⊇ st(R)。

,

免责声明:本文仅代表文章作者的个人观点,与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺,请读者仅作参考,并自行核实相关内容。文章投诉邮箱:anhduc.ph@yahoo.com

    分享
    投诉
    首页