有限集上二元關系性質的判定

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

關鍵詞： 二元關系性質； 關系矩陣； 關系圖； 關系運算； 判定方法

中圖分類號：TP301 文獻標志碼：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 引言

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

1 利用關系性質的定義判定

文獻[1]中給出了二元關系的五種性質的定義：

定義 設R為集合X上的二元關系，則

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

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

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

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

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

根據這一定義，可以判斷給定的關系是否具有上述性質。

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

解：將這些關系性質列表如表1所示。

2 利用關系矩陣判定

2.1 關系矩陣的定義

設集合X={x1，x2，…，xn}，R是X上的一個關系，則定義MR=。

其中， 稱MR為關系R的關系矩陣[2]。

2.2 關系矩陣判定關系性質的方法

對于給定的關系，可以先作出其對應的關系矩陣，然后從關系矩陣中觀察：

⑴ R是自反的，當且僅當在關系矩陣中，對角線上的所有元素都是1；

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

⑶ R是對稱的，當且僅當關系矩陣是以主對角線對稱；

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

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

3 利用關系圖判定

3.1 關系圖的定義

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

3.2 利用關系圖判定關系性質的方法

對于給定的關系，可以先畫出其對應的關系圖，然后從關系圖中觀察：

⑴ R是自反的，當且僅當在關系圖上每個結點都有自回路；

⑵ R是反自反的，當且僅當在關系圖上每個結點都沒有自回路；

⑶ R是對稱的，當且僅當在關系圖上任兩個結點間若有定向弧，必是成對出現；

⑷ R是反對稱的，當且僅當在關系圖上兩個不同結點間的定向弧線不可能是成對出現；

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

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

例2 設R={<1，3>，<1，4>，<2，1>，<2，3>，<2，4>，<3，4>}集合A={1，2，3，4}上的關系。

解：⑴ R的關系矩陣為：

因為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，于是，該關系是傳遞的。

⑵ R的關系圖如圖1所示。

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

對于結點2：沒有入弧；

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

對于結點4：沒有出弧；

于是可以判斷該關系是傳遞的。

4 利用關系運算判定

學習了二元關系基本運算、復合運算、逆運算和閉包運算后，文獻[1，4]中基于關系運算給出了關系性質的判定方法，總結出定理如下。

定理 設R為集合A上的二元關系，則

⑴ R是自反的，當且僅當IA?R（根據恒等關系IA的性質）；

⑵ R是自反的，當且僅當自反閉包r（R）=R（根據自反閉包r（R）的運算公式）；

⑶ R是反自反的，當且僅當IA∩R=φ；

⑷ R是反自反的，當且僅當r（R）-R=IA；

⑸ R是對稱的，當且僅當R=RC；（根據逆關系RC的性質）；

⑹ R是對稱的，當且僅當對稱閉包s（R）=R（根據對稱閉包s（R）的運算公式）；

⑺ R是反對稱的，當且僅當R∩RC?IA；

⑻ R是傳遞的，當且僅當R?R?R（根據復合關系的性質）；

⑼ R是傳遞的，當且僅當t（R）=R（根據傳遞閉包t（R）的運算公式）。

上述定理的證明請參考文獻[1，4]。

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

解：設R為集合A上的二元關系，則

⑴ 證R為自反關系，可應用定理的⑴，⑵；

⑵ 證R為反自反關系，可應用定理的⑶，⑷；

⑶ 證R為對稱關系，可應用定理的⑸，⑹；

⑷ 證R為反對稱關系，可應定理的⑺；

⑸ 證R為傳遞關系，可應用定理的⑻，⑼。

5 結束語

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

參考文獻：

[1] 左孝凌，李為鑑，劉永才.離散數學[M].上海科學技術文獻出版社，2006.

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

[3] 陳中標.判定關系傳遞性的若干方法[J].南京工業職業技術學院學報，2009.9（2）：81-82

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