有限集上二元关系性质的判定

摘 要： 离散数学中，二元关系自反、反自反、对称、反对称和传递性的判定是学习等价关系、相容关系和偏序关系的重要基础知识，为使读者灵活掌握二元关系五种性质的判定，分别从关系性质的定义、关系矩阵、关系图和关系运算四方面对二元关系五种性质的判定方法进行了探讨。

关键词： 二元关系性质； 关系矩阵； 关系图； 关系运算； 判定方法

中图分类号：TP301 文献标志码：A 文章编号：1006-8228（2013）04-51-02

Judgment on the properties of binary relation in a finite set

Zhang Songmin

（Department of Computer and Information Engineering， Luoyang Institute of Science and Technology， Luoyang， Henan 471023， China）

Abstract： In discrete mathematics， the judgment on the proprieties of binary relation including reflexive， anti-reflexive， symmetric， anti-symmetric and transitive is important basic knowledge in learning equivalence relation， compatible relation and partially ordered relation. In order to let the readers master the judgment methods easily， the methods are summarized and discussed from definition of the properties of binary relation， relation matrix， relation graph and relation operation.

Key words： binary relational properties； relational matrix； relational graph； relational operation； judgment method

0 引言

集合中的二元关系是离散数学中非常重要的内容，在一个含有n个元素的有限集上，可以定义个关系。但真正有实际意义的关系，只有其中很少一部分，它们都是有着某些性质的关系。一般离散数学课本中都介绍了关系的五种性质—自反、反自反、对称、反对称和传递性，如何判别关系是否具有这五种性质是学习等价关系、相容关系和序关系的重要基础，因此，在离散数学学习中要求学生必须熟练掌握二元关系五种性质的判别。笔者在多年离散数学教学中发现大多数学生不能灵活掌握二元关系性质的判定。其实，在学习完集合与关系这一章内容后，关系性质的判定可以从关系性质定义、关系矩阵、关系图和关系运算四方面着手考虑，本文将详细介绍有限集上二元关系性质的判定方法。

1 利用关系性质的定义判定

文献[1]中给出了二元关系的五种性质的定义：

定义 设R为集合X上的二元关系，则

⑴ 若对所有的x∈X，均有∈R，则称R是自反的；

⑵ 若对所有的x∈X，均有∉R，则称R是反自反的；

⑶ 若对任意的x，y∈X，每当∈R时，就有∈R，则称R是对称的；

⑷ 若对任意的x，y∈X，每当∈R和∈R时，必有x=y，则称R是反对称的；

⑸ 若对任意的x，y，z∈X，每当∈R和∈R时，就有∈R，则称R是传递的。

根据这一定义，可以判断给定的关系是否具有上述性质。

例1 设集合A={a，b，c}，R1={，，}，R2={，}，R3={，，}，R4={，，，，}，分别是集合A上的二元关系，判断这些关系是否具有上述性质？

解：将这些关系性质列表如表1所示。

2 利用关系矩阵判定

2.1 关系矩阵的定义

设集合X={x1，x2，…，xn}，R是X上的一个关系，则定义MR=。

其中， 称MR为关系R的关系矩阵[2]。

2.2 关系矩阵判定关系性质的方法

对于给定的关系，可以先作出其对应的关系矩阵，然后从关系矩阵中观察：

⑴ R是自反的，当且仅当在关系矩阵中，对角线上的所有元素都是1；

⑵ R是反自反的，当且仅当在关系矩阵中，对角线上的所有元素都不是1；

⑶ R是对称的，当且仅当关系矩阵是以主对角线对称；

⑷ R是反对称的，当且仅当关系矩阵中以主对角线对称的元素不能同时为1；

⑸ R是传递的，从关系矩阵中判别，需逐行查看关系矩阵的元素，若rij=1（i≠j），再查看第j行，若rjk=1，再检查rik，如果rik=1，则关系为传递的。否则，该关系为非传递的[3]。

3 利用关系图判定

3.1 关系图的定义

设集合X={x1，x2，…，xn}，R是X上的一个关系，在平面上分别作出结点x1，x2，…，xn，若∈R，则可自结点xi至结点xj处作一有向弧（箭头指向xj），否则，结点xi至结点xj间没有弧联结。这样得到的图称为关系R的关系图[2]。

3.2 利用关系图判定关系性质的方法

对于给定的关系，可以先画出其对应的关系图，然后从关系图中观察：

⑴ R是自反的，当且仅当在关系图上每个结点都有自回路；

⑵ R是反自反的，当且仅当在关系图上每个结点都没有自回路；

⑶ R是对称的，当且仅当在关系图上任两个结点间若有定向弧，必是成对出现；

⑷ R是反对称的，当且仅当在关系图上两个不同结点间的定向弧线不可能是成对出现；

⑸ R是传递的，从关系图中判别，需逐个查看关系图的结点，对于任一结点，如果该结点有一条出弧同时又有一条入弧，并且从入弧的始点到出弧的终点有弧相连（弧的方向从入弧的始点指向出弧的终点），那么该关系是传递的。否则，该关系为非传递的[3]。

从关系矩阵和关系图中直接判别关系自反、反自反、对称和反对称性比较容易，但关系传递性的判别相对较复杂。这里举例说明：如何从关系矩阵和关系图判别关系传递性。

例2 设R={<1，3>，<1，4>，<2，1>，<2，3>，<2，4>，<3，4>}集合A={1，2，3，4}上的关系。

解：⑴ R的关系矩阵为：

因为m13=1，m34=1且m14=1；m14=1，而第4行元素全为0；m21=1，m13=1且m23=1；m23=1，m34=1且m24=1；m24=1，而第4行元素全为0；m34=1，而第4行元素全为0，于是，该关系是传递的。

⑵ R的关系图如图1所示。

对于结点1：入弧<2，1>，出弧<3，1>和<1，4>，且有弧<2，3>和<2，4>；

对于结点2：没有入弧；

对于结点3：入弧<1，3>和<2，3>，出弧<3，4>，且有弧<1，4>和<2，4>；

对于结点4：没有出弧；

于是可以判断该关系是传递的。

4 利用关系运算判定

学习了二元关系基本运算、复合运算、逆运算和闭包运算后，文献[1，4]中基于关系运算给出了关系性质的判定方法，总结出定理如下。

定理 设R为集合A上的二元关系，则

⑴ R是自反的，当且仅当IA⊆R（根据恒等关系IA的性质）；

⑵ R是自反的，当且仅当自反闭包r（R）=R（根据自反闭包r（R）的运算公式）；

⑶ R是反自反的，当且仅当IA∩R=φ；

⑷ R是反自反的，当且仅当r（R）-R=IA；

⑸ R是对称的，当且仅当R=RC；（根据逆关系RC的性质）；

⑹ R是对称的，当且仅当对称闭包s（R）=R（根据对称闭包s（R）的运算公式）；

⑺ R是反对称的，当且仅当R∩RC⊆IA；

⑻ R是传递的，当且仅当R

推荐访问:判定 性质 关系 有限