二元偏序關系結構的研究

石少儉

(山東理工大學 計算機科學與技術學院, 山東 淄博 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 結束語

偏序關系提供了一種比較集合元素間次序的工具。由于滿足傳遞性關系的結構較復雜，導致偏序關系的結構更為復雜。本文通過定義了有關的概念，給出了偏序關系的結構。