二元偏序关系结构的研究

2020-09-16 14:29石少俭
关键词:单调定理定义

石少俭

(山东理工大学 计算机科学与技术学院, 山东 淄博 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 结束语

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

猜你喜欢
单调定理定义
J. Liouville定理
单调任意恒成立,论参离参定最值
聚焦二项式定理创新题
严昊:不定义终点 一直在路上
怎样判断函数的单调性
A Study on English listening status of students in vocational school
成功的定义
世界正在变得单调
修辞学的重大定义
一个简单不等式的重要应用