有限集上二元關(guān)系性質(zhì)的判定

摘 要： 離散數(shù)學(xué)中，二元關(guān)系自反、反自反、對稱、反對稱和傳遞性的判定是學(xué)習(xí)等價關(guān)系、相容關(guān)系和偏序關(guān)系的重要基礎(chǔ)知識，為使讀者靈活掌握二元關(guān)系五種性質(zhì)的判定，分別從關(guān)系性質(zhì)的定義、關(guān)系矩陣、關(guān)系圖和關(guān)系運算四方面對二元關(guān)系五種性質(zhì)的判定方法進行了探討。

關(guān)鍵詞： 二元關(guān)系性質(zhì)； 關(guān)系矩陣； 關(guān)系圖； 關(guān)系運算； 判定方法

中圖分類號：TP301 文獻(xiàn)標(biāo)志碼：A 文章編號：1006-8228（2013）04-51-02

Judgment on the properties of binary relation in a finite set

Zhang Songmin

（Department of Computer and Information Engineering， Luoyang Institute of Science and Technology， Luoyang， Henan 471023， China）

Abstract： In discrete mathematics， the judgment on the proprieties of binary relation including reflexive， anti-reflexive， symmetric， anti-symmetric and transitive is important basic knowledge in learning equivalence relation， compatible relation and partially ordered relation. In order to let the readers master the judgment methods easily， the methods are summarized and discussed from definition of the properties of binary relation， relation matrix， relation graph and relation operation.

Key words： binary relational properties； relational matrix； relational graph； relational operation； judgment method

0 引言

集合中的二元關(guān)系是離散數(shù)學(xué)中非常重要的內(nèi)容，在一個含有n個元素的有限集上，可以定義個關(guān)系。但真正有實際意義的關(guān)系，只有其中很少一部分，它們都是有著某些性質(zhì)的關(guān)系。一般離散數(shù)學(xué)課本中都介紹了關(guān)系的五種性質(zhì)—自反、反自反、對稱、反對稱和傳遞性，如何判別關(guān)系是否具有這五種性質(zhì)是學(xué)習(xí)等價關(guān)系、相容關(guān)系和序關(guān)系的重要基礎(chǔ)，因此，在離散數(shù)學(xué)學(xué)習(xí)中要求學(xué)生必須熟練掌握二元關(guān)系五種性質(zhì)的判別。筆者在多年離散數(shù)學(xué)教學(xué)中發(fā)現(xiàn)大多數(shù)學(xué)生不能靈活掌握二元關(guān)系性質(zhì)的判定。其實，在學(xué)習(xí)完集合與關(guān)系這一章內(nèi)容后，關(guān)系性質(zhì)的判定可以從關(guān)系性質(zhì)定義、關(guān)系矩陣、關(guān)系圖和關(guān)系運算四方面著手考慮，本文將詳細(xì)介紹有限集上二元關(guān)系性質(zhì)的判定方法。

1 利用關(guān)系性質(zhì)的定義判定

文獻(xiàn)[1]中給出了二元關(guān)系的五種性質(zhì)的定義：

定義 設(shè)R為集合X上的二元關(guān)系，則

⑴ 若對所有的x∈X，均有∈R，則稱R是自反的；

⑵ 若對所有的x∈X，均有?R，則稱R是反自反的；

⑶ 若對任意的x，y∈X，每當(dāng)∈R時，就有∈R，則稱R是對稱的；

⑷ 若對任意的x，y∈X，每當(dāng)∈R和∈R時，必有x=y，則稱R是反對稱的；

⑸ 若對任意的x，y，z∈X，每當(dāng)∈R和∈R時，就有∈R，則稱R是傳遞的。

根據(jù)這一定義，可以判斷給定的關(guān)系是否具有上述性質(zhì)。

例1 設(shè)集合A={a，b，c}，R1={，，}，R2={，}，R3={，，}，R4={，，，，}，分別是集合A上的二元關(guān)系，判斷這些關(guān)系是否具有上述性質(zhì)？

解：將這些關(guān)系性質(zhì)列表如表1所示。

2 利用關(guān)系矩陣判定

2.1 關(guān)系矩陣的定義

設(shè)集合X={x1，x2，…，xn}，R是X上的一個關(guān)系，則定義MR=。

其中， 稱MR為關(guān)系R的關(guān)系矩陣[2]。

2.2 關(guān)系矩陣判定關(guān)系性質(zhì)的方法

對于給定的關(guān)系，可以先作出其對應(yīng)的關(guān)系矩陣，然后從關(guān)系矩陣中觀察：

⑴ R是自反的，當(dāng)且僅當(dāng)在關(guān)系矩陣中，對角線上的所有元素都是1；

⑵ R是反自反的，當(dāng)且僅當(dāng)在關(guān)系矩陣中，對角線上的所有元素都不是1；

⑶ R是對稱的，當(dāng)且僅當(dāng)關(guān)系矩陣是以主對角線對稱；

⑷ R是反對稱的，當(dāng)且僅當(dāng)關(guān)系矩陣中以主對角線對稱的元素不能同時為1；

⑸ R是傳遞的，從關(guān)系矩陣中判別，需逐行查看關(guān)系矩陣的元素，若rij=1（i≠j），再查看第j行，若rjk=1，再檢查rik，如果rik=1，則關(guān)系為傳遞的。否則，該關(guān)系為非傳遞的[3]。

3 利用關(guān)系圖判定

3.1 關(guān)系圖的定義

設(shè)集合X={x1，x2，…，xn}，R是X上的一個關(guān)系，在平面上分別作出結(jié)點x1，x2，…，xn，若∈R，則可自結(jié)點xi至結(jié)點xj處作一有向弧（箭頭指向xj），否則，結(jié)點xi至結(jié)點xj間沒有弧聯(lián)結(jié)。這樣得到的圖稱為關(guān)系R的關(guān)系圖[2]。

3.2 利用關(guān)系圖判定關(guān)系性質(zhì)的方法

對于給定的關(guān)系，可以先畫出其對應(yīng)的關(guān)系圖，然后從關(guān)系圖中觀察：

⑴ R是自反的，當(dāng)且僅當(dāng)在關(guān)系圖上每個結(jié)點都有自回路；

⑵ R是反自反的，當(dāng)且僅當(dāng)在關(guān)系圖上每個結(jié)點都沒有自回路；

⑶ R是對稱的，當(dāng)且僅當(dāng)在關(guān)系圖上任兩個結(jié)點間若有定向弧，必是成對出現(xiàn)；

⑷ R是反對稱的，當(dāng)且僅當(dāng)在關(guān)系圖上兩個不同結(jié)點間的定向弧線不可能是成對出現(xiàn)；

⑸ R是傳遞的，從關(guān)系圖中判別，需逐個查看關(guān)系圖的結(jié)點，對于任一結(jié)點，如果該結(jié)點有一條出弧同時又有一條入弧，并且從入弧的始點到出弧的終點有弧相連（弧的方向從入弧的始點指向出弧的終點），那么該關(guān)系是傳遞的。否則，該關(guān)系為非傳遞的[3]。

從關(guān)系矩陣和關(guān)系圖中直接判別關(guān)系自反、反自反、對稱和反對稱性比較容易，但關(guān)系傳遞性的判別相對較復(fù)雜。這里舉例說明：如何從關(guān)系矩陣和關(guān)系圖判別關(guān)系傳遞性。

例2 設(shè)R={<1，3>，<1，4>，<2，1>，<2，3>，<2，4>，<3，4>}集合A={1，2，3，4}上的關(guān)系。

解：⑴ R的關(guān)系矩陣為：

因為m13=1，m34=1且m14=1；m14=1，而第4行元素全為0；m21=1，m13=1且m23=1；m23=1，m34=1且m24=1；m24=1，而第4行元素全為0；m34=1，而第4行元素全為0，于是，該關(guān)系是傳遞的。

⑵ R的關(guān)系圖如圖1所示。

對于結(jié)點1：入弧<2，1>，出弧<3，1>和<1，4>，且有弧<2，3>和<2，4>；

對于結(jié)點2：沒有入弧；

對于結(jié)點3：入弧<1，3>和<2，3>，出弧<3，4>，且有弧<1，4>和<2，4>；

對于結(jié)點4：沒有出弧；

于是可以判斷該關(guān)系是傳遞的。

4 利用關(guān)系運算判定

學(xué)習(xí)了二元關(guān)系基本運算、復(fù)合運算、逆運算和閉包運算后，文獻(xiàn)[1，4]中基于關(guān)系運算給出了關(guān)系性質(zhì)的判定方法，總結(jié)出定理如下。

定理 設(shè)R為集合A上的二元關(guān)系，則

⑴ R是自反的，當(dāng)且僅當(dāng)IA?R（根據(jù)恒等關(guān)系IA的性質(zhì)）；

⑵ R是自反的，當(dāng)且僅當(dāng)自反閉包r（R）=R（根據(jù)自反閉包r（R）的運算公式）；

⑶ R是反自反的，當(dāng)且僅當(dāng)IA∩R=φ；

⑷ R是反自反的，當(dāng)且僅當(dāng)r（R）-R=IA；

⑸ R是對稱的，當(dāng)且僅當(dāng)R=RC；（根據(jù)逆關(guān)系RC的性質(zhì)）；

⑹ R是對稱的，當(dāng)且僅當(dāng)對稱閉包s（R）=R（根據(jù)對稱閉包s（R）的運算公式）；

⑺ R是反對稱的，當(dāng)且僅當(dāng)R∩RC?IA；

⑻ R是傳遞的，當(dāng)且僅當(dāng)R?R?R（根據(jù)復(fù)合關(guān)系的性質(zhì)）；

⑼ R是傳遞的，當(dāng)且僅當(dāng)t（R）=R（根據(jù)傳遞閉包t（R）的運算公式）。

上述定理的證明請參考文獻(xiàn)[1，4]。

例3 證明一個二元關(guān)系是否具有自反性、反自反性、對稱性、反對稱性或傳遞性的方法。

解：設(shè)R為集合A上的二元關(guān)系，則

⑴ 證R為自反關(guān)系，可應(yīng)用定理的⑴，⑵；

⑵ 證R為反自反關(guān)系，可應(yīng)用定理的⑶，⑷；

⑶ 證R為對稱關(guān)系，可應(yīng)用定理的⑸，⑹；

⑷ 證R為反對稱關(guān)系，可應(yīng)定理的⑺；

⑸ 證R為傳遞關(guān)系，可應(yīng)用定理的⑻，⑼。

5 結(jié)束語

對于集合X上的一個二元關(guān)系R，要判定其性質(zhì)，本文所述的四種方法均可使用。一般來講，只能從定義出發(fā)，當(dāng)關(guān)系R包含的序偶較多時，從定義出發(fā)比較難判定，用關(guān)系矩陣或關(guān)系圖來判定相對簡便實用，同時可以借助于計算機編程來實現(xiàn)。利用關(guān)系運算判定的方法更適合借助于計算機編程來實現(xiàn)。讀者可根據(jù)具體情況來選擇判定方法。

參考文獻(xiàn)：

[1] 左孝凌，李為鑑，劉永才.離散數(shù)學(xué)[M].上海科學(xué)技術(shù)文獻(xiàn)出版社，2006.

[2] 耿素云，屈婉玲，張立昂.離散數(shù)學(xué)[M].清華大學(xué)出版社，2004.

[3] 陳中標(biāo).判定關(guān)系傳遞性的若干方法[J].南京工業(yè)職業(yè)技術(shù)學(xué)院學(xué)報，2009.9（2）：81-82

[4] 左孝凌，李為鑑，劉永才.離散數(shù)學(xué)理論·分析·題解[M].上海科學(xué)技術(shù)文獻(xiàn)出版社，2004.