离散数学关系的闭包论文

离散数学关系的闭包论文

“关系”的闭包（Closure)离散数学中，一个关系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）。

离散数学当中的"闭包"有什么实际应用，能否举例？

一个关系不具有自反, 对称, 传递这3种基本性质之一,但均可以通过对该关系的扩充(在关系中增添序偶),使扩充后的关系具有这种性质,这种包含该关系的最小扩充称为该关系关于这种性质的闭包.下面给出闭包的定义.
设R是X上的关系,R的自反(对称,传递)闭包R1是这样的包含R(或R包含于R1)的自反(对称,传递)关系,对任意的自反(对称,传递) 关系S,如果R包含于S,则必有R1包含于S.
关系闭包在数学中，在日常生活中均有广泛的应用，比如在数学中，小于(<)或大于(>)关系均没有自反性，但它们的的自反闭包是小于等于(≤)或大于等于((≥)，却有自反性，在数学中经常要用到小于关系表示量之间的关系，但是有时感到用小于关系不方便，而用小于等于关系，实际上是将量之间的关系进行扩大，不自觉地用了小于的自反闭包，日常生活中我们按同龄或同班或同乡关系将人分组，一般来说同龄，同班，同乡关系指两个不同的人之间的一种关系，这种关系就不具有自反性，如果我们约定了自已与自已同龄，同班，同乡，此时它们就有了自反性，如果仅有一个人和其他人年龄均不同，此时他自已就可构成一组。
小于关系是不对称，它的逆关系大于关系也是不对称，但将两者关系并起来(将关系看成集合)，得不等关系却是的对称的，不等关系是小于或大于关系的对称闭包，夫对妻的关系是不对称的，妻对夫的关系也是不对称的，但对称闭包婚姻关系却是对称的(考虑到男女平等，即对称性)。大于1的关系是不传递的，大于2的关系也是不传递的，…将大于1，大于2，大于3,…全部并起来得到大于关系却是传递的，大于关系是大于1的关系的传递闭包，父子关系是不传递的，但它的传递闭包是长辈对后辈关系却是传递的。
总而言之，我们经常不自觉的用到了关系闭包的概念，在数学中随着人们的对关系的深入认识，自觉地使用闭包的概念，比如在数学中严格偏序关系的自反闭包是偏序关系，偏序集利用所谓盖住关系的关系图(哈斯图)，来描述该偏序集十分简单明了，盖住关系的自反传递闭包就是偏序集上的偏序关系。

离散数学闭包证明

t(R)=∪Rⁿ
t(S)=∪Sⁿ
t(R∪S)=∪(R∪S)ⁿ
=(R∪S)∪(R∪S)∪⋯(R∪S)
=Rⁿ∪Sⁿ 反复利用集合并的交换律、结合律

下面来证明子集关系
针对∀x∈t(R)∪t(S)，显然x∈t(R)或者x∈t(S)
不妨设x∈t(R)（因为x∈t(S)可以类似证明）
则x∈Rⁿ, 其中n是自然数

显然x∈Rⁿ∪Sⁿ
由于x的任意性，得到
t(R)∪t(S) ⊆ t(R∪S)

即 t(R∪S)⊇ t(R)∪t(S)