二元偏序關(guān)系結(jié)構(gòu)的研究

石少儉

(山東理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 山東 淄博 255049)

在計(jì)算機(jī)科學(xué)中，關(guān)系的概念十分重要。偏序關(guān)系是比較典型和重要的一種關(guān)系，主要應(yīng)用于粗糙集理論研究[1-2]。偏序關(guān)系主要研究蓋住問(wèn)題和偏序集的特殊元素及其與格的聯(lián)系等[3-6]。關(guān)于偏序關(guān)系的結(jié)構(gòu)研究較少，本文定義有關(guān)的概念，證明偏序關(guān)系的性質(zhì)。

1 基本概念

定義1[7]R為定義在集合A上的二元關(guān)系，如果R滿足自反性、反對(duì)稱性和傳遞性，則稱R是A上的一個(gè)偏序關(guān)系，記作≤，稱作偏序集。

定義2[7]設(shè)給定集合A={a1，a2，…，am}，R為定義在集合A上的二元關(guān)系，則R的關(guān)系矩陣MR=[rij]nn，rij=1當(dāng)R；rij=0，當(dāng)R。

定義3[7]IA={x|,xA}，IA稱為集合A上的恒等關(guān)系。

2 二元偏序關(guān)系的性質(zhì)

定義4R為定義在A上的二元關(guān)系，x∈A，∈R且不存在y，x≠y，使∈R，或者∈R。x稱為二元關(guān)系R的獨(dú)立元素。由獨(dú)立元素的定義知，獨(dú)立元素就是偏序關(guān)系的哈斯圖上的孤立點(diǎn)。

定理1R為n個(gè)元素集合A上的二元偏序關(guān)系，則其獨(dú)立元素最多為n個(gè)。

證明恒等關(guān)系IA滿足自反的、反對(duì)稱的和傳遞的，所以也是偏序關(guān)系。恒等關(guān)系哈斯圖的結(jié)點(diǎn)都是孤立點(diǎn)，所以偏序關(guān)系的獨(dú)立元素最多為n個(gè)。

定義5R為定義在集合A上的二元關(guān)系，x≠y，∈R，且不存在a，a≠x≠y使∈R；也不存在b，b≠x≠y，∈R，稱為關(guān)系R的孤立序偶或者孤立邊。

定理2R為n個(gè)元素的集合A上的二元偏序關(guān)系，孤立序偶最多有n-1個(gè)。

證明由偏序關(guān)系R的孤立序偶的定義，考慮關(guān)系矩陣，對(duì)角元素全為1。孤立序偶可以是某一行元素全為1，但其他元素必須全部為0，所以孤立序偶最多有n-1個(gè)。

定義6R為定義在A上的二元關(guān)系，x≠y≠z,∈R,∈R,∈R稱,,為關(guān)系R的一組單調(diào)傳遞序偶。

例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是偏序關(guān)系的獨(dú)立元素，<4,6>和<5,6>是孤立序偶，而<1,2>,<2,3 >,<1,3>是一組單調(diào)傳遞序偶。

3 二元偏序關(guān)系的結(jié)構(gòu)

R為集合A上的二元關(guān)系，記B1={關(guān)系R的孤立序偶}，B2={關(guān)系R的單調(diào)傳遞序偶}，則有下面的性質(zhì)：

定理4R為集合A上的二元關(guān)系，關(guān)系S=IA∪B1∪B2一定是偏序關(guān)系。

證明：

1)關(guān)系S顯然是滿足自反的。

2)由B1和B2的定義可知，是滿足反對(duì)稱的，滿足反對(duì)稱關(guān)系的并集也是滿足反對(duì)稱的，所以關(guān)系S是滿足自反的。

3)任∈S，如果∈IA，由傳遞關(guān)系的定義，滿足傳遞關(guān)系的定義。如果∈B1，孤立序偶滿足傳遞關(guān)系的定義。如果∈B2，一定是某一組單調(diào)傳遞序偶中的一個(gè)，由單調(diào)傳遞序偶的定義，滿足傳遞關(guān)系的定義。S是滿足自反的、反對(duì)稱的、傳遞的，所以S是偏序關(guān)系。

定理5R為定義在集合A上二元偏序關(guān)系，則R=IA∪B1∪B2。

證明任給∈R，如果?IA∪B1∪B2，?IA，則a≠b；?B2，一定不是某一組單調(diào)傳遞序偶中的一個(gè)；?B1，由孤立序偶定義，存在c∈A，c≠a,使∈R，且∈R，?R，和R為傳遞關(guān)系矛盾?；蛘叽嬖赿∈A,d≠b,∈R，且∈R，?R，和R為傳遞關(guān)系矛盾。

所以∈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>}，不是偏序關(guān)系。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是偏序關(guān)系。

4 結(jié)束語(yǔ)

偏序關(guān)系提供了一種比較集合元素間次序的工具。由于滿足傳遞性關(guān)系的結(jié)構(gòu)較復(fù)雜，導(dǎo)致偏序關(guān)系的結(jié)構(gòu)更為復(fù)雜。本文通過(guò)定義了有關(guān)的概念，給出了偏序關(guān)系的結(jié)構(gòu)。