二元传递关系结构分析

石少俭, 曲志坚, 张艳华

(山东理工大学计算机科学与技术学院， 山东淄博 255049)

二元传递关系结构分析

石少俭, 曲志坚, 张艳华

(山东理工大学计算机科学与技术学院， 山东淄博 255049)

摘要：二元关系是离散数学的一个重要概念，传递性是二元关系的一个重要性质.文中定义了对称传递序偶、严格传递序偶、孤立序偶，给出了相应的计数公式，证明了满足传递性的关系的性质.

关键词：二元关系； 传递性； 孤立序偶； 对称传递序偶； 严格传递序偶

二元关系是离散数学的一个重要概念，传递性是二元关系的一个重要性质.传递关系的研究，主要是利用关系图或关系矩阵判断关系是否具有传递性上[1-3].关于传递关系的结构研究较少.文中定义了传递关系有关的概念，证明了满足传递性关系的性质.

1 基本概念

定义1[4]二元关系是集合A、B的笛卡尔积A×B的子集，A=B时，称为集合A上的二元关系.

定义2[4]R为集合A上的二元关系，对于任意a,b，c∈A，如果∈R,∈R时有∈R,称R为A上的传递关系.

定义3[4]R为定义在集合A上的二元关系，IA={|x∈A}，称IA为A上的恒等关系.IR={x,x>|x∈A,x∈R}

2传递关系的结构

定义4 R为定义在A上的二元关系，a,b∈A,a≠b,使∈R,∈R,∈R,∈R,称，，，为关系R一组对称传递序偶.

例1A={1,2,3,4,5}，R={<1,2>,<2,1>,<1,1>,<2,2>,<2,3>,<3,2>,<3,3>,<4,5> }.则<1,2>,<2,1>,<1,1>,<2,2>和<2,3>,<3,2>,<2,2>,<3,3>为对称传递序偶 .

定义5 R为定义在A上的二元关系，a,b,c∈A，a≠b≠c，∈R,∈R,∈R,称,,为关系R的一组严格传递序偶.

例2A={1,2,3,4,5}，R={<3,4>,<4,5>,<3,5>,<4,3>,<3,3>,}.则<3,4>,<4,5>,<3,5>和<4,3>,<3,5>,<4,5>是严格传递序偶， <3,4>,<4,3>,<3,3>不是严格传递序偶.

定理2R为n个元素的集合A上的二元关系，则R最多包含n(n-1)(n-2)组严格传递序偶.

证明由严格传递序偶的定义，考虑R的关系矩阵，不考虑主对角线元素.αik(k≠i)与αkl(k≠l),αil(l≠i)可组成一……