离散数学

2023-09-24 20:06| 来源: 网络整理| 查看: 265

离散数学-二元关系、闭包的概念二元关系设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）。

posted on 2017-05-31 18:41 cynchanpin 阅读(12727) 评论(0) 编辑收藏举报

【本文地址】

公司简介

联系我们