发布时间 : 星期一 文章离散数学中二元关系的性质判定-最新教育文档更新完毕开始阅读
离散数学中二元关系的性质判定
离散数学是现代数学的一个重要分支，是计算机科学的理论基础和核心课程。关系是离散数学中非常重要的一个基本概念，关系的概念在计算机科学是也是最基本的，它在形式语言、编译程序设计、信息检索、数据结构、算法分析、数据库和有限自动机等方面起着重要作用。
关系是一个使用得很频繁的词，如数集上大于关系、小于关系；平面集上的直线平行关系、三角形相似关系；人群集合上的父子关系、同乡关系等，这些都是离散数学中的关系研究的范畴。所以，离散数学中的关系是一个抽象的概念，定义为笛卡尔积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 根据关系图判定
根据关系图判定关系的性质是一种简单、直观并且常用的方法。判定方法如下。
若ρ是自反的，则ρ关系的关系图中每个结点上必有一个