二元傳遞關系結構分析

石少儉, 曲志堅, 張艷華

(山東理工大學計算機科學與技術學院， 山東淄博 255049)

二元傳遞關系結構分析

石少儉, 曲志堅, 張艷華

(山東理工大學計算機科學與技術學院， 山東淄博 255049)

摘要：二元關系是離散數學的一個重要概念，傳遞性是二元關系的一個重要性質.文中定義了對稱傳遞序偶、嚴格傳遞序偶、孤立序偶，給出了相應的計數公式，證明了滿足傳遞性的關系的性質.

關鍵詞：二元關系； 傳遞性； 孤立序偶； 對稱傳遞序偶； 嚴格傳遞序偶

二元關系是離散數學的一個重要概念，傳遞性是二元關系的一個重要性質.傳遞關系的研究，主要是利用關系圖或關系矩陣判斷關系是否具有傳遞性上[1-3].關于傳遞關系的結構研究較少.文中定義了傳遞關系有關的概念，證明了滿足傳遞性關系的性質.

1 基本概念

定義1[4]二元關系是集合A、B的笛卡爾積A×B的子集，A=B時，稱為集合A上的二元關系.

定義2[4]R為集合A上的二元關系，對于任意a,b，c∈A，如果∈R,∈R時有∈R,稱R為A上的傳遞關系.

定義3[4]R為定義在集合A上的二元關系，IA={|x∈A}，稱IA為A上的恒等關系.IR={x,x>|x∈A,x∈R}

2傳遞關系的結構

定義4 R為定義在A上的二元關系，a,b∈A,a≠b,使∈R,∈R,∈R,∈R,稱，，，為關系R一組對稱傳遞序偶.

例1A={1,2,3,4,5}，R={<1,2>,<2,1>,<1,1>,<2,2>,<2,3>,<3,2>,<3,3>,<4,5> }.則<1,2>,<2,1>,<1,1>,<2,2>和<2,3>,<3,2>,<2,2>,<3,3>為對稱傳遞序偶 .

定義5 R為定義在A上的二元關系，a,b,c∈A，a≠b≠c，∈R,∈R,∈R,稱,,為關系R的一組嚴格傳遞序偶.

例2A={1,2,3,4,5}，R={<3,4>,<4,5>,<3,5>,<4,3>,<3,3>,}.則<3,4>,<4,5>,<3,5>和<4,3>,<3,5>,<4,5>是嚴格傳遞序偶， <3,4>,<4,3>,<3,3>不是嚴格傳遞序偶.

定理2R為n個元素的集合A上的二元關系，則R最多包含n(n-1)(n-2)組嚴格傳遞序偶.

證明由嚴格傳遞序偶的定義，考慮R的關系矩陣，不考慮主對角線元素.αik(k≠i)與αkl(k≠l),αil(l≠i)可組成一組嚴格傳遞序偶， αik(k≠i)與第i行元素可組成n-2組嚴格傳遞序偶.第i行元素共有(n-1)(n-2)組嚴格傳遞序偶， R最多包含n(n-1)(n-2)組嚴格傳遞序偶.

定義6 R為定義在A上的二元關系，∈R, 且不存在c∈A,c≠a,使∈R，也不存在d∈A,d≠b,∈R,稱為關系R的孤立序偶.

例3A={1,2,3,4,5}，R={<1,2>,<2,2>,<3,4>,<4,5 >}，則<1,2>是孤立序偶.而<3,4>,<4,5 >不是孤立序偶.

R為集合A上的二元關系，記B1={關系R的對稱傳遞序偶}，B2={關系R的嚴格傳遞序偶}，B3={關系R的孤立序偶}，則有下面的性質：

定理4 R為集合A上的二元關系，關系S=IR∪B1∪B2∪B3一定是傳遞關系.

證明如果R為空集，則S為空集，由傳遞關系的定義，S是傳遞關系.

任∈S，如果∈IR，由傳遞關系的定義，滿足傳遞關系的定義.

如果∈B1，由對稱傳遞序偶的定義，存在∈S,∈S,∈S,滿足傳遞關系的定義.

如果∈B2，一定是某一組嚴格傳遞序偶中的一個，由嚴格傳遞序偶的定義，滿足傳遞關系的定義.

如果∈B3，?B1,?B2,孤立序偶滿足傳遞關系的定義.所以S一定是傳遞關系.

例4A={1,2,3,4,5}，R={<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<1,3>,<2,3>, <3,4>,<5,4> }.則{<1,1>,<2,2>,<3,3>}、{<1,1>,<2,2>,<1,2>,<2,1>}、{<1,2>,<2,3>,<1,3>}、{<5,4> }組成的關系S={<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<2,3>,<1,3>,<5,4>}是傳遞關系.

定理5 R為集合A上傳遞關系，則R=IR∪B1∪B2∪B3

證明任給∈R, 如果?IR∪B1∪B2∪B3

?IR, 則a≠b;?B1, 則

?R;

?B2, 一定不是任一組嚴格傳遞序偶中的一個序偶

?B3,由孤立序偶定義，存在c∈A,c≠a,使∈R,且

∈R,?R，和R為傳遞關系矛盾.或者存在d∈A,d≠b,d>∈R,且∈R,?R,和R為傳遞關系矛盾.

所以∈IR∪B1∪B2∪B3,而R?IR∪B1∪B2∪B3,R=IR∪B1∪B2∪B3.

例5A={1,2,3,4,5}，R={<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<2,3>,<1,3>,<4,5>}是傳遞關系.則IR={<1,1>,<2,2>,<3,3>}，B1={<1,2>,<2,1>,<1,1>,<2,2>}， B2={<1,2>,<2,3>, <1,3>}，B3={<4,5>}.

3結束語

不確定性度量是信息科學中人工智能和機器學習領域的研究熱點問題，其中，粗糙集理論作為一種新的處理不精確、不相容和不完全數據的數學工具，是處理不確定性問題的有效方法.在信息處理的許多領域，如特征選擇、機器學習，數據挖掘、進化算法等諸多方面得到了廣泛的應用.經典粗糙集理論研究的是離散型數據，以等價關系為基礎.傳遞關系是構成等價關系的重要基礎，文中定義了對稱序偶、嚴格遞增序偶、孤立序偶，給出了相應的計數公式.證明了二元傳遞關系的結構，為傳遞關系和等價關系的研究提供了理論依據，間接促進了粗糙集理論的進一步研究.

參考文獻：

[1]吳鵬.有限集上二元關系傳遞性的矩陣判別法[J]．成都大學學報：理科版,2009,28(2)：122-125.

[2] 何小亞,王洪山．利用關系矩陣求傳遞閉包的一種方法[J]．數學的實踐與認識,2005,35(3)：172-175．

[3] 汪小燕.二元關系中傳遞性的若干研究[J]．蘇州科技學院學報:自然科學版,2011,28(2)：37-39．

[4] 左孝凌,李為鑒,劉永才．離散數學[M]．上海：上海科學技術文獻出版社,1982．

(編輯：劉寶江)

收稿日期：2014-09-12

基金項目：山東省優秀中青年科學家科研獎勵基金資助項目(BS2013DX032)

作者簡介：石少儉，男，ssj05xy@sdut.edu.cn.

文章編號：1672-6197(2015)01-0020-02

中圖分類號：O158

文獻標志碼：A

Structureanalysisofbinarytransitiverelation

SHIShao-jian，QUZhi-jian，ZHANGYan-hua

(SchoolofComputerScienceandTechnology,ShandongUniversityofTechnology,Zibo255049,China)

Abstract:Binary relation is an important concept of discrete mathematics. Transmission is important in binary relation. This paper defines the symmetric transitive ordered pair, strictly transitive ordered pair,and isolated ordered pair, gives the corresponding count formula of each one and proves the property which meets transitive relation

Key words:binary relation； transitive relation； symmetric transitive ordered pair； strictly transitive ordered pair； isolated ordered pair