二元关系中“传递关系”的判断及其研究

摘要：传递关系是二元关系中比较难以掌握的部分，也是学生最容易出错的地方。为使学生更好地掌握传递关系的判断方法，本文将传递关系按关系有向图分为1～3个节点，并结合谓词公式法分析了11种情况的关系传递性。本文的内容有助于学生掌握传递关系的判断，并可有效提高传递关系的教学质量。

关键词：离散数学；二元关系；传递关系；有向图

离散数学作为计算机科学领域最有效的一种数学工具，20世纪70年代初，国外就已经将其作为计算机专业和一些工程学专业的学习课程［1］。离散数学的研究对象一般为有限个元素组成的集合，并以研究离散量的结构和相互关系为主要目标，因此它可以很好地描述计算机科学离散性的特点［23］。目前离散数学是计算机科学基础理论的核心课程，也是许多计算机类专业课的必备基础，包括数据结构、算法原理、操作系统、编译原理、数据库原理、计算机网络、人工智能和数字逻辑等［4］。离散数学对于培养学生的抽象思维能力和逻辑推理能力具有重要的作用［5］。学生通过对离散数学的学习，不但可以帮助学生在组合分析、算法设计以及应用与建模等方面形成基本的离散思维方法，而且能够培养学生严密的逻辑推理能力，从而为将来从事信息行业的理论研究和应用开发打下坚实的基础。

二元关系是离散数学集合论中的重要内容，是两个集合笛卡尔乘积的子集，研究的是一个集合内部或两个不同集合元素间关系。它与数理逻辑、集合论、布尔代数、组合数学和图论等有密切的联系，不但在数学领域中起着非常重要的作用，而且被广泛应用于计算机科学等领域。二元关系包括自反关系、反自反关系、对称关系、反对称关系以及传递关系，其中自反关系、反自反关系、对称关系、反对称关系的有向图及关系矩阵具有十分鲜明和直观的特点，而传递关系的特点比较隐蔽，有时往往很难从有向图及关系矩阵中判断一种关系是否为传递关系，因此传递关系的教学一直是二元关系的教学重点和难点，也是学生难以掌握的部分，而二元关系的学习又是后续关系闭包的基础，二元关系的学习效果将直接影响后续学习的顺利开展，为此对传递关系展开了大量的研究。杜衡吉研究了二元关系传递性的中途点及蕴涵式两种判定方法［6］，李劲研究了传递关系的充分必要条件［7］，郭健等人研究了传递关系的几种判定方法及适用条件［8］，张艳春利用关系矩阵以及关系图研究二元关系的性质［9］。

由于传递关系涉及集合中的三个节点，本文针对传递关系的难点问题，将传递关系的判断分为1个至3个节点的情况进行分析和讨论，涵盖了传递关系判断的所有基本情况，并将部分结论推广到了空关系、恒等关系及全域关系的传递性的判断。由于多元素的集合的关系判断可拆分为局部节点的传递关系的判断，因此本文的研究结果不仅适用于1至3个节点的传递关系的判断，同时适用于多元素的集合的传递关系判断。

1二元关系的特点

集合的二元关系包括自反关系、反自反关系、对称关系、反对称关系及传递关系5大类。每种关系的关系矩阵及关系图都有自身的特征，其中自反性关系矩阵的主对角线上的元素均为1，关系图的每个节点均有环；反自反性关系矩阵的主对角线上的元素均为0，关系图的每个节点均没有环；对称性关系矩阵为对称矩阵，关系图的任意两个节点之间均无单向边，即如果两个节点之间有边，则一定是一对平行边；反对称性关系矩阵中如果rij=1，且i≠j，则rji=0，关系图的任意两个节点之间如果有边，则一定是一条单向边；传递性关系矩阵对M2中1所在的位置，M中相应的位置为1。传递性关系图中，如果节点ai到aj有边连接，且aj到ak也有边连接，则ai到ak也有边连接。

显然，二元关系中自反关系、反自反关系、对称关系、反对称关系的关系图具有鲜明、直观的特点，而传递性关系图中节点数量如果低于3个则没有明显的特征，因此集合传递关系的判断相对其他4种关系更加困难，如何使学生掌握集合传递关系的判断是二元关系的教学难点。

2传递关系的判定

本文将通过集合中含有1至3个元素三种情况，分别分析二元关系中传递关系的传递性。

2.1含有1个元素集合的传递性

如图1（a）所示，集合Φ中只含有一个元素a，对应的关系图只有一个无环孤立节点，图1（a）所示的关系用R1表示。

传递关系的定义为蕴涵关系式，当蕴涵关系式的前件为假时，蕴涵关系为真。由于图1中只存在一个无环的孤立节点，传递关系的前件为假，则对应的蕴涵关系为真，则传递关系成立。

含有1个无环孤立节点的结论可以推广到含有多个无环孤立节点，即集合的空关系具有传递性。

如图1（b）所示，集合中只含有一个元素a，对应的关系图只有一个有环孤立节点，图1（b）所示的关系用R2表示。

图1（b）中的节点A可以看作是三个节点A、B、C的重合节点，则A、B、C所代表的元素满足a=b=c，由于该节点自带环，则满足如下关系：

abc（a，b，c∈Φ∧〈a，b〉∈R2∧〈b，c〉∈R2→〈a，c〉∈R2）（1）

由公式（1）可知关系R2满足传递性的要求，具有传递性。

含有1个有环孤立节点的结论可以推广到含有多个有环孤立节点，即集合的恒等关系IA具有传递性。

2.2含有2个元素集合的传递性

2.2.1关系R3的传递性

如图2（a）所示，集合Φ中含有两个元素a和c，分别对应关系图中的有环节点A和无环节点C，图2（a）所示的关系用R3表示。

由于节点A有环，可将其看作节点A和B的重合节点，其中节点B代表的元素为b，且满足a=b。由图2（a）所示，节点A经过环到达节点B，节点B又可到达节点C，显然节点A可到达节点C，公式（5）成立：

abc（a，b，c∈Φ∧〈a，b〉∈R3∧〈b，c〉∈R3→〈a，c〉∈R3）（2）

由公式（2）可知，关系R3满足传递性的要求，具有传递性。

2.2.2关系R4的传递性

如图2（b）所示，集合中含有两个元素a和b，分别对应关系图中的有环节点A和无环节点B，图2（b）所示的关系用R4表示。

由于节点B有环，可将其看作节点B和C的重合节点，其中节点C代表的元素为c，且满足b=c。由图2（b）所示，节点A经过〈A，B〉到达节点B，节点B又经过环可到达节点C，显然节点A可到达节点C，公式（6）成立：

abc（a，b，c∈Φ∧〈a，b〉∈R4∧〈b，c〉∈R4→〈a，c〉∈R4）（3）

由公式（3）可知关系R4满足传递性的要求，具有传递性。

2.2.3关系R5的传递性

如图2（c）所示，集合中含有两个元素a和b，分别对应关系图中的节点A和节点B，其中节点B看作节点B和C的重合节点，图2（c）所示的关系用R5表示。

由图2（c）可知，节点A可由路径〈A，B〉到达节点B，但节点B没有环，说明节点B并不可达节点C，即蕴涵关系式的前件为假时，蕴涵关系为真，R5满足传递性的要求，具有传递性。

2.2.4关系R6的传递性

图2（d）与图2（c）不同的是，图2（d）中含有双向边，而图2（c）只含有单向边，因此2（d）分别进行如下两种情况讨论：

当节点A看作节点A和C的重合节点时，节点A经过〈A，B〉到达节点B，节点B又经过〈B，C〉到达节点C，但节点A自身没有环，即节点A不可达节点C，则

abc（a，b，c∈Φ∧〈a，b〉∈R5∧〈b，c〉∈R5→〈a，c〉R5）（4）

由公式（4）可知，关系R6不满足传递性的要求。

当节点B看作节点B和C的重合节点时，节点B经过〈B，A〉到达节点A，节点A又经过〈A，C〉到达节点C，但节点B自身无环，即节点B不可达节点C，则

abc（a，b，c∈Φ∧〈b，a〉∈R6∧〈a，c〉∈R6→〈b，c〉R6）（5）

由公式（5）可知，关系R6不满足传递性的要求，不具有传递性。综上所述，关系R6不具有传递性。

2.2.5关系R7的传递性

图2（e）与图2（d）相同的是也含有双向边，因此2（e）也分别进行如下两种情况讨论：

当节点A看作节点A和C的重合节点时，节点A经过〈A，B〉到达节点B，节点B又经过〈B，C〉到达节点C，但节点A自身有环，即节点A可达节点C，则

abc（a，b，c∈A∧〈a，b〉∈R7∧〈b，c〉∈R7→〈a，c〉∈R7）（6）

由公式（6）可知，关系R7满足传递性的要求。

当节点B看作节点B和C的重合节点时，节点B经过〈B，A〉到达节点A，节点A又经过〈A，C〉到达节点C，但节点B自身有环，即节点B可达节点C，则

abc（a，b，c∈Φ∧〈b，a〉∈R7∧〈a，c〉∈R7→〈b，c〉∈R7）（7）

由公式（7）可知，关系R7满足传递性的要求，具有传递性。

综上所述，关系R7具有传递性。

图2（e）的结论可以推广到含有多个节点的有向完全图的情况，即集合的全域关系EA具有传递性。

2.3含有3个元素集合的传递性

2.3.1关系R8的传递性

如图3（a）所示，集合Φ中含有三个元素a、b和c，分别对应关系图中的无环节点A、B和C，图3（a）所示的关系用R8表示。

由图3（a）可知，节点A可由路径〈A，B〉到达节点B，但节点B和C之间没有边，说明节点B并不可达节点C，即如公式（2）所示的蕴涵关系式的前件为假时，蕴涵关系为真，R8满足传递性的要求，R8具有传递性。

2.3.2关系R9的传递性

如图3（b）所示，节点A可由路径〈A，B〉到达节点B，节点B可由路径〈B，C〉到达节点C，但节点A和C之间没有边，说明节点A并不可达节点C，则

abc（a，b，c∈Φ∧〈a，b〉∈R9∧〈b，c〉∈R9→〈a，c〉R9）（8）

由公式（8）可知，关系R9不满足传递性的要求，不具有传递性。

2.3.3关系R10的传递性

如图3（c）所示，节点A可由路径〈A，B〉到达节点B，节点B可由路径〈B，C〉到达节点C，同时节点A可由〈A，C〉到达节点C，说明节点A可达节点C，则

abc（a，b，c∈Φ∧〈a，b〉∈R10∧〈b，c〉∈R10→〈a，c〉∈R10）（9）

由公式（9）可知，关系R10满足传递性的要求，具有传递性。

2.3.4关系R11的传递性

如图3（d）所示，节点A可由路径〈A，B〉到达节点B，节点B可由路径〈B，C〉到达节点C，但节点A不可由有向边〈A，C〉到达节点C，说明节点A不可达节点C，则

abc（a，b，c∈Φ∧〈a，b〉∈R11∧〈b，c〉∈R11→〈a，c〉R11）（10）

由公式（10）可知，关系R11不满足传递性的要求，不具有传递性。

结语

传递关系相对于自反关系、反自反关系、对称关系以及反对称关系不具有直观的几何特征，因此是二元关系教学中的难点。本文利用关系有向图并结合谓词公式法分析了11种关系的传递性，并将分析结果扩展到空关系、恒等关系及全域关系，这些结论对多元素集合的传递性分析同样具有指导意义。本文的内容可以帮助教师突破传递关系判断的教学难点，同时有助于学生理解和掌握传递关系。

参考文献：

［1］吴明芬，瞿赟昀.离散数学中的闭包概念及应用［J］，郑州大学学报（工学版），2012，33（5）：133137.

［2］左孝凌，李为监，刘永才.离散数学［Ｍ］.上海：上海科技文献出版社，2001.

［3］傅彦.离散数学基础及应用［Ｍ］.成都：电子科技大学出版社.2000.

［4］惠康华，李春利.离散数学教学改革研究［J］，计算机时代，2021（02）：9395+98.

［5］李海侠.离散数学中二元关系的教学模式改革探讨——基于信息与计算科学专业［J］，高教学刊，2020（06）：129131.

［6］杜衡吉.二元关系传递性的两种等价判定［J］.曲靖师范学院学报，2015，34（06）：4547.

［7］李劲.判断二元关系传递性的充分必要条件［J］.河西学院学报，2016，32（2）：1116.

［8］郭键，赵明茹.判定二元关系传递性的几种方法［J］.大庆师范学院学报，2008，28（5）：4548.

［9］张艳春.二元关系的性质及其研究［J］.时代教育，2009（6）：121122.

［10］屈婉玲，耿素云，张立昂.离散数学［M］.北京：高等教育出版社，2015.

基金项目：河北省首批省级研究生教育教学改革研究项目（YJG2023028）

作者简介：邹成业（1982—），男，汉族，辽宁人，博士，讲师，主要从事DNA计算、复杂网络及图像加密方面的研究；张炳（1989—），男，汉族，湖北人，博士，副教授，主要从事软件测试课程教育方面的研究。

*通讯作者：吴培良（1981—），男，汉族，河北人，博士，教授，主要从事家庭服务机器人环境工具和服务对象认知、家庭服务机器人操作技能学习等方面的研究。