石少儉
(山東理工大學(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[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)
定義3[7]IA={x|
定義4R為定義在A上的二元關(guān)系,x∈A,
定理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,
定理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,
例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)傳遞序偶。
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,使
所以∈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)系。
偏序關(guān)系提供了一種比較集合元素間次序的工具。由于滿足傳遞性關(guān)系的結(jié)構(gòu)較復(fù)雜,導(dǎo)致偏序關(guān)系的結(jié)構(gòu)更為復(fù)雜。本文通過(guò)定義了有關(guān)的概念,給出了偏序關(guān)系的結(jié)構(gòu)。