等价关系与等价关系矩阵.pdf

维普资讯 第12卷 第 1期 兰州工业高等专科学校学报 V_01．12．No．1 2005年 3月 JournalofLanz~uPolytechnicCollege Mar．．2005 文章编号：1009-2269(2005)01—0039—04 等价关系与等价关系矩阵 王志龙 (兰州工业高等专科学校 基础学科部，甘肃 兰州 730050) 摘要：首先对关系与关系矩阵进行了探讨，得出一个关系具有对称、反身及传递性的充要条件是 其关系矩阵有对称、主对角线元素为 1等性质；然后重点讨论 了等价关系和等价关系矩阵之间的 关系及如何确定等价关系矩阵；最后论述 了它们的运算性质． 关 键 词：等价关系；等价关系矩阵；布尔矩阵；布尔积 中图分类号：O151．21 文献标识码：A 1 关系与关系矩阵 设A，B是两个集合，R表示A与B之间的一个关系，对 Va∈A及 Vb∈B，若a与b有关系R，记 作aRb；若 口与b没有关系R，记作aRb． 定义 1．1 给定集合A= {a1，a2，…，a)和B： {b1，b2，…，b)及一个A到B的关系R，令 f1， 如果a,R．bj 10， 如果口f ，其中口∈A，∈B， 则称矩阵MR= [] 是关系R的关系矩阵． 定义 1．2 如果矩阵M 中的元素都是0或1，则称M 是布尔矩阵． 下文中用 ll·lI表示集合中的元素个数，如 IlAII=m，IlBIl=71表示集合A和B中分别有优和 71个元素；用 表示给某元 “赋值”或确定其意义用U／R表示集合u关于R的商集；用[aT】表示商集U／R 中aT所在的等价类． 定理 1．1 矩阵M 是一个关系矩阵的充要条件是M 是一个布尔矩阵． 证明：若M 是一个关系矩阵，显然M 中的元素都是0或 1，则M 是布尔矩阵． 若M ：[] 是布尔矩阵，给定集合A、B，且 IlAIl=m，IlBIl=71，可以定义一个A到B的关 系R：即对 V口∈A， ∈B，i：1，2，…，m；j=1，2，…，．若 =1，规定 口炳 ；若ro=0，规定ai ， 则R是一个A到B的关系．证毕． 定义 1．3 设矩阵A l= [口] 和B』 ：[bo] 都是布尔矩阵，C埘 全 [co] ，其中 = m ax min{aik，6}，i=1，2，…，m，=1，2，…，，称 。为矩阵A f与B』 的布尔积，记作A *Bf ． … ， ． 1≤女≤ 。 。 。 ’ ’ 一 定义 1．4 设A =[ao] 和B =[bd】 都是布尔矩阵，对A 与B 定义如下运算(将 A 和B 简记为A与B)： 1)AUB [cO] ，其中 =瑚x{口d，bo．)； ·收稿 日期：20O4一l2一l1 基金项目：甘肃省自然科学基金资助项目(32S041一A25—0O4) 作者简介：王志龙(1965一)，男，甘肃正宁人。副教授． 维普资讯 · 40 · 兰 州 工 业 高 等 专 科 学 校 学 报 第 l2卷 2)AnB [ ] ，其中f=rain{ao，bo}； 3)A 【1一aljJ ． 定理 1．2 若A、B是布尔矩阵，则A*B、AUB、AnB和A 都是布尔矩阵． 定理显然成立，这也说明两个关系进行上述运算的结果还是关系． 以上内容主要来 自文献[1]，但在文献[1]及其它相关文献中给出关系矩阵的定义和运算后．对如何 用关系矩阵确定关系R的性质未作讨论，定理 1