[工学]二元关系ii

《[工学]二元关系ii》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、二元关系关系的闭包闭包的定义闭包的构造方法闭包的性质闭包的相互关系闭包的定义定义设R是非空集合A上的关系，R的自反（对称或传递）闭包是A上的关系R′，使得R′满足以下条件：（1）R′是自反的（对称的或传递的）（2）RR′（3）对A上任何包含R的自反（对称或传递）关系R″有R′R″。一般将R的自反闭包记作r(R)，对称闭包记作s(R)，传递闭包记作t(R)。设A={a,b,c,d},R={,,,},则R和r(R),s(R),t(R)分别是什么？闭包的构造方法定理设R为A上的关系，则有（1）r(R)＝R∪R0（2）s(R)＝R

2、∪R-1（3）t(R)＝R∪R2∪R3∪…证明思路(1)和(2)：证明右边的集合满足闭包定义的三个条件。(3)采用集合相等的证明方法。证明左边包含右边，即t(R)包含每个Rn。证明右边包含左边，即R∪R2∪…具有传递的性质。推论推论设R为有穷集A上的关系，则存在正整数r使得t(R)=R∪R2∪…∪Rr证明由定理7.6和7.10(3)得证。例题求整数集合Z上的关系R＝{

3、a

4、a

5、a＝b}＝{

6、a≤b}s(R)＝R∪R-1＝{

7、a

8、a

9、}＝{

10、a≠b}通过关系矩阵求闭包的方法设关系R，r(R)，s(R)，t(R)的关系矩阵分别为M，Mr，Ms和Mt，则Mr＝M＋E对角线上的值都改为1Ms＝M＋M′若aij＝1，则令aji＝1Mt＝M＋M2＋M3＋…沃舍尔算法其中E是和M同阶的单位矩阵，M′是M的转置矩阵。注意在上述等式中矩阵的元素相加时使用逻辑加。通过关系图求闭包的方法设关系R，r(R)，s(R)，t(R)的关系图分别记为G，Gr，Gs，Gt，则Gr，Gs，Gt的顶点集与G的顶点集相等。除了G的边以外，以下述方法添加新的边。1)考察G的每个顶点，如果没有环就加上一个环。最终得到的是Gr。

11、2)考察G的每一条边，如果有一条xi到xj的单向边，i≠j，则在G中加一条边xj到xi的反方向边。最终得到Gs。3)考察G的每个顶点xi，找出从xi出发的所有2步，3步，…，n步长的路径（n为G中的顶点数）。设路径的终点为。如果没有从xi到(l=1,2,…,k)的边，就加上这条边。当检查完所有的顶点后就得到图Gt。例设A={a,b,c,d}，R={,,,,}，则R和r(R)，s(R)，t(R)的关系图如下图所示。其中r(R)，s(R)，t(R)的关系图就是使用上述方法直接从R的关系图得到的。闭包的主要性质定理设R是

12、非空集合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。闭包的主要性质定理设R1和R2是非空集合A上的关系，且R1R2，则（1）r(R1)r(R2)（2）s(R1)s(R2)（3）t(R1)t(R2)证明：(1)任取，有∈r(R1)∈R1∪IA∈R1∨∈IA

13、∈R2∨∈IA∈R2∪IA∈r(R2)关系性质与闭包运算之间的联系定理设R是非空集合A上的关系，（1）若R是自反的，则s(R)与t(R)也是自反的。（2）若R是对称的，则r(R)与t(R)也是对称的。（3）若R是传递的，则r(R)是传递的。证明：略从这里可以看出，如果计算关系R的自反、对称、传递的闭包，为了不失去传递性，传递闭包运算应该放在对称闭包运算的后边，若令tsr(R)表示R的自反、对称、传递闭包，则tsr(R)=t(s(r(R)))自反性对称性传递性r(R)√√√s(R)√√×(反例)t(R)√√√反例A={1，2，

14、3}，R={<1,3>}是传递的s(R)={<1,3>,<3,1>}显然s(R)不是传递的。等价关系与划分定义设R为非空集合上的关系。如果R是自反的、对称的和传递的，则称R为A上的等价关系。设R是一个等价关系，若∈R，称x等价于y，记做x～y。举例(1)平面上三角形集合中，三角形的相似关系。(2)人群中的同性关系。例设A＝{1,2,…,8}，如下定义A上的关系R：R＝{

15、x，y∈A∧x≡y(mod3)}其中x≡y(mod3)叫做x与y模3相等，即x除以3的余数与y除以3的余数相等。不难验证R为A上的等价关系，因为x∈A，有x≡x(m