石少儉, 曲志堅(jiān), 張艷華

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

二元傳遞關(guān)系結(jié)構(gòu)分析

石少儉, 曲志堅(jiān), 張艷華

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

摘要：二元關(guān)系是離散數(shù)學(xué)的一個重要概念，傳遞性是二元關(guān)系的一個重要性質(zhì).文中定義了對稱傳遞序偶、嚴(yán)格傳遞序偶、孤立序偶，給出了相應(yīng)的計(jì)數(shù)公式，證明了滿足傳遞性的關(guān)系的性質(zhì).

關(guān)鍵詞：二元關(guān)系； 傳遞性； 孤立序偶； 對稱傳遞序偶； 嚴(yán)格傳遞序偶

二元關(guān)系是離散數(shù)學(xué)的一個重要概念，傳遞性是二元關(guān)系的一個重要性質(zhì).傳遞關(guān)系的研究，主要是利用關(guān)系圖或關(guān)系矩陣判斷關(guān)系是否具有傳遞性上[1-3].關(guān)于傳遞關(guān)系的結(jié)構(gòu)研究較少.文中定義了傳遞關(guān)系有關(guān)的概念，證明了滿足傳遞性關(guān)系的性質(zhì).

1 基本概念

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

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

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

2傳遞關(guān)系的結(jié)構(gòu)

定義4 R為定義在A上的二元關(guān)系，a,b∈A,a≠b,使∈R,∈R,∈R,∈R,稱，，，為關(guān)系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上的二元關(guān)系，a,b,c∈A，a≠b≠c，∈R,∈R,∈R,稱,,為關(guān)系R的一組嚴(yán)格傳遞序偶.

例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>是嚴(yán)格傳遞序偶， <3,4>,<4,3>,<3,3>不是嚴(yán)格傳遞序偶.

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

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

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

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

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

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

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

任∈S，如果∈IR，由傳遞關(guān)系的定義，滿足傳遞關(guān)系的定義.

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

如果∈B2，一定是某一組嚴(yán)格傳遞序偶中的一個，由嚴(yán)格傳遞序偶的定義，滿足傳遞關(guān)系的定義.

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

例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> }組成的關(guān)系S={<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<2,3>,<1,3>,<5,4>}是傳遞關(guān)系.

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

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

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

?R;

?B2, 一定不是任一組嚴(yán)格傳遞序偶中的一個序偶

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

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

所以∈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>}是傳遞關(guān)系.則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結(jié)束語

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

參考文獻(xiàn)：

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

[2] 何小亞,王洪山．利用關(guān)系矩陣求傳遞閉包的一種方法[J]．?dāng)?shù)學(xué)的實(shí)踐與認(rèn)識,2005,35(3)：172-175．

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

[4] 左孝凌,李為鑒,劉永才．離散數(shù)學(xué)[M]．上海：上?？茖W(xué)技術(shù)文獻(xiàn)出版社,1982．

(編輯：劉寶江)

收稿日期：2014-09-12

基金項(xiàng)目：山東省優(yōu)秀中青年科學(xué)家科研獎勵基金資助項(xiàng)目(BS2013DX032)

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

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

中圖分類號：O158

文獻(xiàn)標(biāo)志碼：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