二元偏序关系结构的研究

石少俭

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

在计算机科学中，关系的概念十分重要。偏序关系是比较典型和重要的一种关系，主要应用于粗糙集理论研究[1-2]。偏序关系主要研究盖住问题和偏序集的特殊元素及其与格的联系等[3-6]。关于偏序关系的结构研究较少，本文定义有关的概念，证明偏序关系的性质。

1 基本概念

定义1[7]R为定义在集合A上的二元关系，如果R满足自反性、反对称性和传递性，则称R是A上的一个偏序关系，记作≤，称作偏序集。

定义2[7]设给定集合A={a1，a2，…，am}，R为定义在集合A上的二元关系，则R的关系矩阵MR=[rij]nn，rij=1当R；rij=0，当R。

定义3[7]IA={x|,xA}，IA称为集合A上的恒等关系。

2 二元偏序关系的性质

定义4R为定义在A上的二元关系，x∈A，∈R且不存在y，x≠y，使∈R，或者∈R。x称为二元关系R的独立元素。由独立元素的定义知，独立元素就是偏序关系的哈斯图上的孤立点。

定理1R为n个元素集合A上的二元偏序关系，则其独立元素最多为n个。

证明恒等关系IA满足自反的、反对称的和传递的，所以也是偏序关系。恒等关系哈斯图的结点都是孤立点，所以偏序关系的独立元素最多为n个。

定义5R为定义在集合A上的二元关系，x≠y，∈R，且不存在a，a≠x≠y使∈R；也不存在b，b≠x≠y，∈R，称为关系R的孤立序偶或者孤立边。

定理2R为n个元素的集合A上的二元偏序关系，孤立序偶最多有n-1个。

证明由偏序关系R的孤立序偶的定义，考虑关系矩阵，对角元素全为1。孤立序偶可以是某一行元素全为1，但其他元素必须全部为0，所以孤立序偶最多有n-1个。

定义6R为定义在A上的二元关系，x≠y≠z,∈R,∈R,∈R称,,为关系R的一组单调传递序偶。

例1A={1,2,3,4,5，6，7}，R={<1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<6,6>,<7,7>,<1,2>,<2,3 >,<1,3>,<4,6>,<5,6>}，由上面的定义，7是偏序关系的独立元素，<4,6>和<5,6>是孤立序偶，而<1,2>,<2,3 >,<1,3>是一组单调传递序偶。

3 二元偏序关系的结构

R为集合A上的二元关系，记B1={关系R的孤立序偶}，B2={关系R的单调传递序偶}，则有下面的性质：

定理4R为集合A上的二元关系，关系S=IA∪B1∪B2一定是偏序关系。

证明：

1)关系S显然是满足自反的。

2)由B1和B2的定义可知，是满足反对称的，满足反对称关系的并集也是满足反对称的，所以关系S是满足自反的。

3)任∈S，如果∈IA，由传递关系的定义，满足传递关系的定义。如果∈B1，孤立序偶满足传递关系的定义。如果∈B2，一定是某一组单调传递序偶中的一个，由单调传递序偶的定义，满足传递关系的定义。S是满足自反的、反对称的、传递的，所以S是偏序关系。

定理5R为定义在集合A上二元偏序关系，则R=IA∪B1∪B2。

证明任给∈R，如果∉IA∪B1∪B2，∉IA，则a≠b；∉B2，一定不是某一组单调传递序偶中的一个；∉B1，由孤立序偶定义，存在c∈A，c≠a,使∈R，且∈R，∉R，和R为传递关系矛盾。或者存在d∈A,d≠b,∈R，且∈R，∉R，和R为传递关系矛盾。

所以∈IA∪B1∪B2，而R⊇IA∪B1∪B2，R=IA∪B1∪B2。

例2上面例1中IA={<1,1>,<2,2>,<3,3>，<4,4>,<5,5>,<6,6>,<7,7>}，B1={<4,6>,<5,6>},B2={<1,2>,<1,3>,<2,3>}，R=IA∪B1∪B2。

例3A={1,2,3,4,5，6，7}，R={<1,1>,<3,4>,<4,3> ,<1,2>,<2,3 >,<1,3>,<4,6> ,<5,6>}，不是偏序关系。IA={<1,1>,<2,2>,<3,3>，<4,4>,<5,5>,<6,6>,<7,7>}，B1={<4,6>,<5,6>},B2={<1,2>,<1,3>,<2,3>}，R1=IA∪B1∪B2是偏序关系。

4 结束语

偏序关系提供了一种比较集合元素间次序的工具。由于满足传递性关系的结构较复杂，导致偏序关系的结构更为复杂。本文通过定义了有关的概念，给出了偏序关系的结构。