汪小燕，楊思春，申元霞

（安徽工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 馬鞍山 243032）

二元關(guān)系包括等價關(guān)系、相容關(guān)系、序關(guān)系等，它可以應(yīng)用于粒計(jì)算[1-2]、形式背景[3-4]、粗糙集[5]等相關(guān)問題研究，因此，有必要對二元關(guān)系的性質(zhì)進(jìn)行研究。二元關(guān)系的性質(zhì)一般包括自反、反自反、對稱、反對稱、傳遞，前四個性質(zhì)借助于關(guān)系圖或關(guān)系矩陣都能夠直接判斷，而傳遞性從關(guān)系圖或關(guān)系矩陣中不能直接反映出來，二元關(guān)系中包含序偶時，判斷反對稱性容易產(chǎn)生誤解。文獻(xiàn)[6]對傳遞性的前提條件進(jìn)行補(bǔ)充，給出一種傳遞性判斷的等價定義。文獻(xiàn)[7]利用二元關(guān)系的關(guān)系矩陣，通過行與行之間的布爾加運(yùn)算，判斷關(guān)系矩陣是否為衡平矩陣來判定二元關(guān)系的傳遞性。文獻(xiàn)[8]用數(shù)理邏輯方法和命題制作方法給出二元關(guān)系傳遞性的等價定義，并給出判斷二元關(guān)系傳遞性的幾個充分必要條件。文獻(xiàn)[9]對反對稱性進(jìn)行研究，給出一種反對稱性判斷的等價定義。文獻(xiàn)[10]通過對二元關(guān)系反對稱性定義的深入分析，給出兩種等價的定義形式。為了能夠直觀判斷二元關(guān)系的傳遞性，筆者定義了域矩陣和簡化域矩陣，將域矩陣和簡化域矩陣分別用于二元關(guān)系和其自身的復(fù)合運(yùn)算、判斷二元關(guān)系的傳遞性及反對稱性，基于兩種矩陣提出關(guān)于傳遞性、反對稱性判斷和關(guān)系復(fù)合運(yùn)算的相關(guān)理論。

1 相關(guān)概念

二元關(guān)系通常是由若干個序偶構(gòu)成的集合，序偶是二元關(guān)系的元素。若R是集合A上的二元關(guān)系，x，y∈A且xRy，也可以用序偶表示為：∈R。

定義1[11]R為集合A上的二元關(guān)系，對于任意a，b，c∈A，當(dāng)∈R且∈R時，有∈R，稱R為A上的傳遞關(guān)系，或者說R在A上具有傳遞性。

設(shè)R1，R2為集合{1，2，3}上的二元關(guān)系，R1={<1，2>，<1，3>}，R2={<1，2>}，這兩個二元關(guān)系都具有傳遞性，而使用定義1判斷這兩種類型的二元關(guān)系為什么具有傳遞性就不好理解。

定義2[11]R為集合A上的二元關(guān)系，如果對于任意∈R且a≠b，?R，則稱R在A上具有反對稱性。

定義3[11]設(shè)R是一個二元關(guān)系，由∈R的所有x組成的集合domR稱作R的前域，即domR={x|?y（∈R）}。

定義3指出前域是由二元關(guān)系中所有序偶的第一元素構(gòu)成的集合。

定義4[11]設(shè)R是一個二元關(guān)系，由∈R的所有y組成的集合ranR稱作R的值域，即ranR=｛y|?x（∈R）｝。

定義4指出值域是由二元關(guān)系中所有序偶的第二元素構(gòu)成的集合。任何一個非空的二元關(guān)系都具有非空的前域和值域。

定義5設(shè)R是集合A上的二元關(guān)系，x，y，z是A中的任意三個元素，若任意s，t∈R，且s=，t=，若以y為中間元素，則s和t可以形成新的序偶，將這一運(yùn)算稱為序偶的復(fù)合，記作s?t=。

定義6[12]設(shè)R是集合A上的二元關(guān)系，若IR={|x∈A且∈R}，則稱IR為R中的第一元素和第二元素相等的序偶的集合。

2 傳遞性質(zhì)的域矩陣判斷方法

為了方便表達(dá)判斷傳遞性質(zhì)的矩陣，現(xiàn)給出如下兩個定義。

定義7設(shè)R是集合A中的二元關(guān)系，稱（y）1={x|x∈A and y∈A and xRy}是y的R第一元素集合。

定義8設(shè)R是集合A中的二元關(guān)系，稱（x）2={y|x∈A and y∈A and xRy}是x的R第二元素集合。

根據(jù)以上相關(guān)概念，提出域矩陣的定義。

定義9設(shè)R是集合A中的二元關(guān)系，定義域矩陣為：矩陣的每一行對應(yīng)一個元素的R第二元素集合，即（x）2，每一列對應(yīng)一個元素的R第一元素集合，即（y）1，矩陣中元素取值表示如下

其中x∈domR，y∈ranR。

文獻(xiàn)[11]指出R是集合A上的二元關(guān)系，設(shè)R1=R-IR，如果R1具有傳遞的性質(zhì)，則二元關(guān)系R也一定具有傳遞性質(zhì)。所以，研究二元關(guān)系R的傳遞性質(zhì)，可以借助刪減后的二元關(guān)系R1來判斷。這樣可以降低矩陣的規(guī)模，提高判斷的速度。改進(jìn)的簡化域矩陣定義如下。

定義10設(shè)R是集合A中的二元關(guān)系，R1=R-IR，定義簡化域矩陣為：矩陣的每一行對應(yīng)一個元素的R1第二元素集合，即（x）2，每一列對應(yīng)一個元素的R1第一元素集合，即（y）1，矩陣中元素取值表示如下

其中x∈domR1，y∈ranR1。

根據(jù)簡化域矩陣，下面研究判斷二元關(guān)系傳遞性質(zhì)的相關(guān)理論。

定理1設(shè)R是集合A中的二元關(guān)系，R1=R-IR，M為簡化域矩陣，（x）2和（y）1分別為元素的R1第二元素集合和R1第一元素集合。對?x∈domR1，?y∈ranR1，若（x）2∩（y）1=?或者（x）2∩（y）1≠?且∈R，則R具有傳遞性質(zhì)。

證明當(dāng)（x）2∩（y）1=?時，也就是∈R1，不存在∈R1。而當(dāng)（x）2∩（y）1≠?且∈R時，也就是對∈R1，存在∈R1且∈R，根據(jù)定義1可知R在A上具有傳遞性。

根據(jù)簡化域矩陣和定理1，可得如下推論。

推論1設(shè)R是集合A中的二元關(guān)系，R1=R-IR，M為簡化域矩陣。若矩陣中的元素為1或?，則R具有傳遞性質(zhì)。

推論2設(shè)R是集合A中的二元關(guān)系，R1=R-IR，M為簡化域矩陣。若矩陣中至少有一個元素為0，則R不具有傳遞性質(zhì)。

定理2設(shè)R是集合A中的二元關(guān)系。若簡化域矩陣不存在，則R具有傳遞性質(zhì)。

證明設(shè)R是集合A中的二元關(guān)系，R1=R-IR，若R1=?時，則domR1=?，ranR1=?，簡化域矩陣不存在，在定理1中，前提條件不滿足，即前提為假，根據(jù)命題邏輯的條件聯(lián)結(jié)詞運(yùn)算可知，關(guān)于定理1的命題為真。所以R具有傳遞性質(zhì)。

R1無論是非空集合上的空關(guān)系還是空集上的空關(guān)系，只要關(guān)于R1的簡化域矩陣不存在，R就一定具有傳遞性質(zhì)。

定理3設(shè)R是集合A中的二元關(guān)系，R1=R-IR，M為簡化域矩陣，（x）2和（y）1分別為元素的R1第二元素集合和R1第一元素集合。對?x∈domR1，?y∈ranR1，若x=y，對應(yīng)矩陣元素為?，則R具有反對稱性質(zhì)。

證明對?x∈domR1，?y∈ranR1，當(dāng)x=y時，對應(yīng)矩陣元素為?，則（x）2∩（y）1=?，也就是對∈R1，不存在∈R1，根據(jù)定義2可知R在A上具有反對稱性質(zhì)。

定理4設(shè)R是集合A中的二元關(guān)系，R1=R-IR，M為簡化域矩陣，（x）2和（y）1分別為元素的R1第二元素集合和R1第一元素集合，?x∈domR1，?y∈ranR1。若x=y時，對應(yīng)矩陣元素為0或1，則R不具有反對稱性質(zhì)。

證明若?x∈domR1，?y∈ranR1，當(dāng)x=y時，對應(yīng)矩 陣元 素為0或1，則（x）2∩（y）1≠?，也就是對∈R1，存在∈R1，根據(jù)定義2可知R在A上不具有反對稱性質(zhì)。

推論3設(shè)R是集合A中的二元關(guān)系。若簡化域矩陣不存在，則R具有反對稱性質(zhì)。

根據(jù)定義9建立的域矩陣既可以用于傳遞性質(zhì)的判斷，還可以用于二元關(guān)系與其自身的復(fù)合運(yùn)算。

定理5設(shè)R是集合A中的二元關(guān)系，M為域矩陣，則矩陣中取值為0或1的元素所對應(yīng)的序偶∈R?R。

證明當(dāng)矩陣中元素取值為0或1時，根據(jù)定義9知：（x）2∩（y）1≠?，也就是對∈R，存在∈R，根據(jù)復(fù)合運(yùn)算的定義知：∈R?R。

定理6設(shè)R是集合A中的二元關(guān)系，M為域矩陣，則矩陣中取值為0或1的元素所對應(yīng)的序偶集合為R2，則R?R=R2。

證明由復(fù)合運(yùn)算的定義和定理5可證。

推論4設(shè)R是集合A中的二元關(guān)系，M為域矩陣。若矩陣中所有元素都是?，則R?R=?。

根據(jù)簡化域矩陣，判斷二元關(guān)系傳遞性的步驟如下：（1）計(jì)算R1=R-IR；（2）分別計(jì)算出二元關(guān)系R1的前域domR1和值域ranR1；（3）對?x∈domR1，?y∈ranR1，分別計(jì)算（x）2和（y）1；（4）按照定義10給出R1的簡化域矩陣；（5）檢查矩陣中是否有0元素存在，若不存在0元素，則R具有傳遞性質(zhì)，否則R不具有傳遞性質(zhì)。

若根據(jù)簡化域矩陣，判斷二元關(guān)系反對稱性質(zhì)，只需要將上述步驟（5）改為：檢查矩陣中對?x∈domR1（R1的前域），?y∈ranR1（R1值域），若x=y時，對應(yīng)矩陣元素為?，則R具有反對稱性質(zhì)。

根據(jù)域矩陣，計(jì)算一個二元關(guān)系和其自身復(fù)合的步驟如下：（1）分別計(jì)算出二元關(guān)系R的前域domR和值域ranR；（2）對?x∈domR，?y∈ranR，分別計(jì)算（x）2和（y）1；（3）按照定義9給出R的域矩陣；（4）R?R為矩陣中所有取值為0或1的元素所對應(yīng)的序偶集合。

下面通過實(shí)例來說明判斷二元關(guān)系傳遞性質(zhì)、反對稱性質(zhì)和二元關(guān)系與其自身復(fù)合的過程。

例1設(shè)集合A={1，2，3，4，5}，R是A上的一個二元關(guān)系，

判斷過程如下

根據(jù)定義10，所得到的簡化域矩陣為

該矩陣中有0元素存在，則二元關(guān)系R不具有傳遞性質(zhì)，該矩陣中第二行第一列以及第三行第二列所對應(yīng)的元素都是?，故二元關(guān)系R具有反對稱性質(zhì)。

同理，根據(jù)定義9，所得到的域矩陣為

由定理5可得：R?R={<1，1>，<1，2>，<1，3>，<1，5>，<2，2>，<2，3>，<2，5>，<4，4>}。

3 結(jié)語

結(jié)合二元關(guān)系的前域和值域，提出域矩陣和簡化域矩陣，簡化域矩陣降低了矩陣規(guī)模，更適合二元關(guān)系傳遞性和反對稱性的判斷。將域矩陣用于二元關(guān)系與其自身的復(fù)合運(yùn)算，運(yùn)算過程中不會產(chǎn)生重復(fù)的序偶。利用兩種矩陣，提出了傳遞性質(zhì)和反對稱性質(zhì)判斷的相關(guān)理論和判斷方法以及復(fù)合運(yùn)算的理論與方法。利用新的方法進(jìn)行關(guān)系的復(fù)合運(yùn)算和判斷傳遞性、反對稱性，計(jì)算和判斷過程直觀，步驟清晰，而且容易理解。接下來將研究適合不同二元關(guān)系復(fù)合的域矩陣和適合數(shù)據(jù)挖掘領(lǐng)域的域矩陣。