离散数学中二元关系的性质判定

【摘 要】 关系的性质是关系中的基本内容，对理解关系有着重要的意义。文中对二元关系性质的四种判定方法进行了分析和探讨，即，根据定义判定、根据定理判定、根据关系图判定、根据关系矩阵判定。以加深学生理解，方便灵活运用。

【关键词】 离散数学；二元关系；性质；判定

【中图分类号】G64【文献标识码】A【文章编号】2095-3089（2013）4-0-02

离散数学是现代数学的一个重要分支，是计算机科学的理论基础和核心课程。关系是离散数学中非常重要的一个基本概念，关系的概念在计算机科学是也是最基本的，它在形式语言、编译程序设计、信息检索、数据结构、算法分析、数据库和有限自动机等方面起着重要作用。

关系是一个使用得很频繁的词，如数集上大于关系、小于关系；平面集上的直线平行关系、三角形相似关系；人群集合上的父子关系、同乡关系等，这些都是离散数学中的关系研究的范畴。所以，离散数学中的关系是一个抽象的概念，定义为笛卡尔积A1×A2×…×An的任意一个子集。二元关系是我们讨论的重点内容，定义为笛卡尔积A1×A2的任意子集。关系的性质是关系的基本属性，是认识和分析关系的关键。关系的基本性质主要包括自反、反自反、对称、反对称以及传递性。如何判定关系的性质是我们必须要掌握的方法。关系基本性质的判定主要有四种方法：第一是直接根据定义判定；第二是根据定理判定；第三是根据关系图判定；第四是根据关系矩阵判定。本文将对这四种方法进行讨论。

1 根据定义判定

定义：设ρ是集合A上的二元关系，

1）若对于所有的a∈A，有（a，a）∈ρ，则称ρ是自反的。否则，称ρ是非自反的。

2）若对于所有的a∈A，有（a，a）∉ρ，则称ρ是反自反的。

3）对于所有的a，b∈A，若每当有（a，b）∈ρ时就有（b，a）∈ρ，则称ρ是对称的。否则，称ρ是非对称的。

4）对于所有的a，b∈A，若每当有（a，b）∈ρ和（b，a）∈ρ时，就必有a=b，则称ρ是反对称的。

5）对于所有的a，b，c∈A，若每当有（a，b）∈ρ和（b，c）∈ρ时，就必有（a，c）∈ρ，则称ρ是可传递的。否则，称ρ是不可传递的。

对于自反性，根据定义可以发现，当ρ包含了恒等关系IA时，它一定是自反的。由于IA中的序偶的个数刚好等于#A（A集合的基数），因此也可以得出这样的结论，若ρ是自反的，则ρ中序偶的个数大于或等于#A。即，当ρ中序偶的个数小于#A时，它一定不是自反的；当ρ中序偶的个数大于或等于#A时，它有可能是自反的。所以，根据关系中序偶数大于或等于#A，可以作为判断自反性的必要条件。

在判定对称、反对称和传递性时必须明确，如果指定了条件，那么不满足条件的一定不属于定义对象；满足条件的就肯定属于定义的对象；而“不违背”条件的，也属于定义对象。这符合逻辑学中蕴含式的规则，当蕴含式的前件为真，后件为假时，结论为假；当前件为真，后件为真时，结论为真；而当前件为假时，无论后件是真是假，结论均为真。

于是对于关系ρ，若当任意两个不同的元素a，b间不存在（a，b）∈ρ的问题时，也就没有必要再讨论（b，a）∈ρ或（b，a）∉ρ了，而此时ρ是满足对称性的。

对于所有的a，b∈A，若不存在（a，b）∈ρ和（b，a）∈ρ，则可以肯定ρ是反对称的。

对于反对称，我们还可以这样理解，即，若对于所有的a，b∈A且a≠b，若（a，b）∈ρ和（b，a）∈ρ不同时存在，也说明ρ是反对称的。这只是将上述定义中的第四条换了一种角度来理解，其实就是原定义的逆否命题，由于逆否命题与原命题等价，所以在某些情况下，当上述定义中的第四条不方便直接判定时，也可以用它来作为判定的依据。

对于所有的a，b，c∈A，若ρ中不存在（a，b）∈ρ和（b，c）∈ρ时，此时也不需要再讨论（a，c）∈ρ或（a，c）∉ρ了，可以断定此时ρ必定是可传递的。

如A上的恒等关系IA，根据以上讨论，可以判定IA是自反的、对称的、反对称的和可传递的。因为根据IA的定义及特点，首先可以判定它是自反的；再由于集合A中任意两个不同元素间均没有IA关系，所以，根据“不违背条件的，均属于定义对象”的原则，可以判定IA既是对称的，又是反对称的，并且是可传递的。并由此可以看出。对称与反对称是一对可以相兼容的性质。

根据定义来判定关系的性质是最基本的方法，它几乎适用于所有的情况，不管是有限集上的关系还是无限集上的关系。但是，有时未免烦琐，特别是关系中列举了较多序偶对时，用定义来判定就不那么直观并且容易有遗漏。

2 根据定理判定

定理：设ρ是A上关系，IA为A上恒等关系，则

1）ρ是自反的当且仅当IA⊆ρ，

2）ρ是反自反的当且仅当IA∩ρ=φ，

3）ρ是对称的当且仅当ρ-1=ρ，

4）ρ是反对称的当且仅当ρ∩ρ-1⊆IA，

5）ρ是传递的当且仅当ρ°ρ⊆ρ。

如A上的恒等关系IA，由IA⊆IA，可知是自反的；由IA∩IA≠φ，可知不是反自反的；由IA-1=IA，可知是对称的；由IA-1∩IA⊆IA，可知是反对称的；由IA°IA⊆IA，可知是可传递的。

根据定理判定主要是将关系进行某种运算后再进行判断，这是一种简单且不易出错的方法。但是，当ρ关系中的序偶对是无限的，或者ρ关系只能用其具有的性质抽象描述而难以用列举法表示时，用定理来判断就不太容易了。

3 根据关系图判定

根據关系图判定关系的性质是一种简单、直观并且常用的方法。判定方法如下。

若ρ是自反的，则ρ关系的关系图中每个结点上必有一个环；若ρ是反自反的，则其关系图中的每个结点上都没有环。

若ρ是对称的，则在其关系图中若两不同结点间有边，必定有两条方向相反的边；若ρ是反对称的，则其关系图中若两不同结点间有边，必定是一条有向边，而不会同时有两条方向相反的边。

若ρ是可传递的，则在其关系图中，若有由结点ai指向aj的边，且又有由结点aj指向ak的边，就必有一条由结点ai指向ak的边。

如A上的恒等关系IA，其关系图就是仅在每个结点上都有一个单边环，于是可以判定为自反的；由于不同元素之间不存在边，所以属于不违背条件的情况，于是可以判定为对称的、反对称的和可传递的。

根据关系图判定是一种非常实用的方法，用來判定有限集上的关系的性质十分简便。对判断自反、反自反、对称以及反对称都是一目了然；判断传递性时，若边的条数较多，则容易有遗漏，需要谨慎仔细。而对于无限集上的关系，或者当集合中元素数目较多用图解表示很困难时，就不适合用关系图来进行判定了。

4 根据关系矩阵判定

关系矩阵是在计算机上描述关系时采用方法。通过关系矩阵可能直接判定出关系的某些性质，方法如下。

若ρ是自反的，则关系矩阵的主对角线上的元素全为1；若ρ是反自反的，则关系矩阵的主对角线上元素全为0。

若ρ是对称的，则其关系矩阵关于主对角线对称；若ρ是反对称的，则其关系矩阵中对i≠j，若rij=1，则rji=0。

传递关系的关系矩阵没有明显的特点，因而很少用关系矩阵来判定传递性。

如A上的恒等关系IA，其关系矩阵是除主对角线元素为1外，其他全为0的矩阵，所以是自反的；由于关于主对角线对称，所以是对称的；又由于当i≠j时，rij均不为1，所以是反对称的。

关系矩阵适合在计算机上表达，考虑到计算机的运算能力与效率，因此，当集合中元素数目较多时，用其他的方法来判定关系的性质需要的时间或计算量都很大，此时可以将大量的判断、计算工作交由计算机来完成，利用计算机通过关系矩阵的来判定就显得非常适宜了。

5 总结

本文讨论了判定关系基本性质的四种方法。其中，根据定义判定是最基本的，适用于所有的情况，特别是无限集上的关系；根据定理判定是很准确、不易出错的，但需要对集合的运算，关系的逆运算与复合运算比较熟练；根据关系图判定是最简便快捷的，但它仅适合于有限集上的关系，且在元素较少，用图解表示比较方便的情况下；根据关系矩阵判定也是较方便的，但它更适宜于用计算机来处理集合规模较大，计算量较多的情况。在实际运用中，具体采用哪种方法要依情况而定，但能灵活运用这些方法会帮助学生快速准确地对关系性质进行判定，对关系也能有更深入的理解。

参考文献

[1]洪凡.离散数学基础[M].第3版.武汉：华中科技大学出版社，2009.

[2]耿素云，屈婉玲.离散数学[M].北京：高等教育出版社，2004.

[3]屈婉玲，耿素云，张立昂.离散数学[M].北京：高等教育出版社，2008.

[4]傅彦，顾小丰，等.离散数学及其应用[M].北京：高等教育出版社，2007.