离散数学作业5_集合与关系_关系的闭包

闭包的求法 及性质
通过关系矩阵求闭包
设关系R, r(R), s(R), t(R)的关系矩阵分别为M, Mr(R), Ms(R), Mt(R), 则：
Mr(R) = M+E
Ms(R) = M+M', Mt(R) = M+M2+M3+…,
其中E是与M同阶的单位矩阵。M是M的转置 矩阵，矩阵元素相加时使用逻辑加(析取).
tr(R) = t( R∪IX) = IX∪R∪(IX∪R)2∪…∪(IX∪R)n∪… = IX∪R∪R2∪…∪Rn∪…
∴ rt(R)=tr(R)
注：以上证明引用了公式：（证明略） ( R∪IX)(n) = IX∪R∪R2∪…∪Rn∪…
证明 st(R) ts(R)
证：① 先证 R对称则t(R)对称 (t(R))c = (RR(2)R(3) …)c = Rc(R(2))c(R(3))c… = Rc(Rc)(2)(Rc)(3)… ((T◦S)c=Sc◦Tc，定理3-7.2 ) = R R(2) R(3) … = t(R) t(R)对称.
(4) 定理3-8.6 设R为集合X上的二元关系，那么 a) rs(R)=sr(R) 对称闭包的自反闭包 等于 自反闭包的对称闭包； b) tr(R)=rt(R) 自反闭包的传递闭包 等于 传递闭包的自反闭包； c) ts(R)st(R) 对称闭包的传递闭包 包含 传递闭包的对称闭包.
•
证明 rs(R)=sr(R)
<a,a>,<a,c>,<b,b>,<c,a>,<c,c>…} s(t(R))= s{ <a,b>,<c,b> }
= { <a,b>,<b,a>,<c,b>,<b,c> } t(s(R))

离散数学如何求r的传递闭包离散数学的传递闭包是指在一个关系 R 上，通过不断地迭代是否存在一些元素关系可以联通，扩展出一个新的关系闭包集合，使得 R 中任何两个元素之间都存在一条路径。

其中，R 是原始关系，而 R 的传递闭包是所有可以从 R 中的元素得到的路径的集合。

传递闭包是在关系上的一个重要属性，因为它可以表示元素之间的隐含关系，从而有助于更详细地分析和描述数据。

计算 R 的传递闭包有多种方法，其中最经典的是 Warshall 算法。

下面是使用Warshall 算法计算 R 的传递闭包的步骤。

1）建立一个大小为n × n 的布尔矩阵 T，其中 T[i][j] 表示从 i 到 j 是否存在一条路径。

2）将布尔矩阵 T 的初始值设置为 R 的布尔矩阵。

3）进行 n 次迭代，每次迭代更新布尔矩阵 T 的值。

具体地，对于 T 中的每一个元素 T[i][j]，如果存在一个 k 使得 T[i][k] 和 T[k][j] 均为 true，则将 T[i][j] 设为 true。

4）最终的 T 就是 R 的传递闭包。

下面是 Warshall 算法的详细代码实现：```int[][] transitiveClosure(int[][] R) {int n = R.length;int[][] T = new int[n][n];// 初始化 T 为 R 的布尔矩阵for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (R[i][j] == 1) {T[i][j] = 1;}}}// 根据 Warshall 算法进行迭代for (int k = 0; k < n; k++) {for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {T[i][j] |= (T[i][k] & T[k][j]);}}}return T;}```该算法的时间复杂度为 O(n^3)，其中 n 是 R 的大小。

1 3 1 3 1 3
2 r(R)s(R)t(R)
4
2
4
2
4
构造自反闭包r(R)的方法
定理3.3―5设R是集合A上的二元关系.那么, r(R)=R∪E(这里E是A上相等关系,在本节中均如此.) 证 设R′=R∪E.显然,R′是自反的且 是自反的 R⊆R′. 余下只需证明R′最小性, 现假设R″是A上的自反关系且R⊆R″. 因R″是自反的,所以E⊆R″, 所以R′=R∪E⊆R″. 这样,定义3.3―2都满足.所以,R′=r(R).证毕
2011-1-10
离散数学
14
例
设集合A={1,2,3,4}，R={<1,2>,<2,2>,<2,3>,<3,4>}是定义在A 上的二元关系。 上的二元关系。 （1）画出R的关系图； 的关系图； （2）求出r(R),s(R),t(R),并画出其相应的关系图。 并画出其相应的关系图。 解（1）R的关系图见下图； 的关系图见下图；
离散数学
4
性质
1. xRy⇔yR-1x 2. 将R的关系图中有向边的方向改变成相反方 有向边的方向改变成相反方 向即得R-1的关系图，反之亦然； 3. 将R的关系矩阵转置即得R-1的关系矩阵， 即R和R-1的关系矩阵互为转置矩阵。 的关系矩阵互为转置矩阵。 4. R-1的前域与后域正好是R的后域和前域， 即domR=ranR-1，domR-1=ranR； 5. (RoS)-1=S-1oR-1。
2011-1-10 离散数学 18
构造对称闭包t(R)的方法
定理3.3―7设R∞ 是集合A上的二元关系,那么 t ( R ) = U R i = R U R 2 U R 3 UL 证明分两部分

第一章集合论基础§ 1.1基本要求1.掌握集合、子集、超集、空集、幕集、集合族的概念。

懂得两个集合间相等和包含关系的泄义和性质，能够利用泄义证明两个集合相等。

熟悉常用的集合表示方法。

2.掌握集合的基本运算：并、交、余、差、直乘积、对称差的左义以及集合运算满足的基本算律，能够利用它们来证明更复杂的集合等式。

3.掌握关系、二元关系、空关系、全域关系、相等关系、逆关系的概念以及关系的性质：自反性、对称性、反对称性、传递性。

会做关系的乘积。

了解关系的闭包运算：自反闭包、对称闭包、传递闭包。

4.掌握等价关系、等价类、商集的概念，了解等价关系和划分的在联系。

5.掌握部分序关系、部分序集、全序关系、全序集的概念以及部分序集中的特殊元素：最大元、最小元、极大元、极小元、上确界、小确界的左义。

能画岀有限部分序集的Hasse 图，并根据图讨论部分序集的某些性质。

6.掌握映射、映像、1-1映射等概念，会做映射的乘枳。

了解可数集合的槪念，掌握可数集合的判定方法。

7.了解关系在数据库中的应用（数据的增、删、改）以及划分在计算机中的应用。

§ 1.2主要解题方法1.2.1证明集合的包含关系方法一.用泄义来证明集合的包含关系是最常用也是最基本的一种方法。

要证明ACB,首先任取xeA,再演绎地证出xeB成立。

由于我们选择的元素x是属于A的任何一个，而非特指的一个，故知给出的演绎证明对A中含有的每一个元素都成立。

当A是无限集时，因为我们不能对xwA,逐一地证明xeB成立，所以证明时的假设“x是任取的” 就特别重要。

例121设A, B, C, D是任意四个非空集合，若ACC, BCD,则AxBcCxDo证明：任取(x, y) e AxBt 往证(x, y) e CxD°由(x, y) e AxB 知，xe A, K ye Bo 又由AcC, BcD 知，xeC,且ye D,因此，(Xt y) e CxDo 故，AxBcCxDo方法二.还有一种证明集合包含关系的方法，基于集合的交和并运算的两个基本性质ACB<=> AnB=A <=> AuB=B以及一些已经证岀的集合等式。