我們知道離散數學中,需要判斷關係是否為自反,反自反,對稱,反對稱,傳遞,完全,循環。這裡分享給大家如何使用關係矩陣,來判斷關係的性質。
方法/步驟
首先,求出關係的關係矩陣,即布爾邏輯0、1矩陣。
例如,集合A={1,2,5,8,12,16} R是整除關係。
那麼我們寫成關係矩陣。
關係矩陣 M=
1 1 1 1 1 1
0 1 0 1 1 1
0 0 1 0 0 0
0 0 0 1 0 1
0 0 0 0 1 0
0 0 0 0 0 1
R={<1,1>,<1,2>,<1,5>,<1,8>,<1,12>,<1,16>,<2,2>,<2,8>,<2,12>,<2,16>,<5,5>,<8,8>,<8,16>,<12,12>,<16,16>}
這時,我們要判斷是否為自反關係,只需檢查關係矩陣
對角線上的元素是否全為1。
全為1則關係是自反關係;
不全為1(只要對角線上有1個0),則不是自反關係。
顯然,整除關係是自反的。
要判斷是否為反自反關係,同樣只需檢查關係矩陣上的元素是否全為0
值得注意的是,如果集合A非空,則空關係滿足反自反,不滿足自反關係。
但集合A為空集,則空關係滿足自反關係,也滿足反自反。
從中我們可以看出,關係有可能既是自反關係,又是反自反關係。
同樣,關係有可能不是自反關係,也不是反自反關係。
這一點值得注意。
接下來,我們來看如何判斷關係的對稱性。
只需檢查關係矩陣的主對角線兩側的元素,是否一一對應,保持一致即可。
顯然,整除關係不是對稱關係。
如何判斷關係是反對稱關係呢?
同樣檢查關係矩陣的主對角線兩側的元素,是否一一對應,保持互補(有1的地方,對角線另一側的位置的元素為0)即可。
顯然,整除關係是反對稱關係。
注意,對稱關係與反對稱關係是互斥的,兩者只能最多出現一種情況。
而不像自反與反自反可以同時滿足。
下面來看如何通過關係矩陣,判斷是否是傳遞關係。
傳遞關係,在關係矩陣不能一眼直接看出,但是同樣可以按照步驟來檢查。
方法是:
按從上到下,從左到右,逐一檢查某行(例如a行)非對角線上的1元素,
定位到該1元素所在列,所對應的關係矩陣行,
檢查該行所有的1元素(或只檢查非對角線上的1元素),
將這些1元素所在列的a行元素找出,判斷是否都為1
都為1則,是傳遞關係;
但只要出現1個0,則不是傳遞關係。
顯然,整除關係滿足傳遞性。
下面我們來看,如何判斷關係是完全關係。
只需檢查關係矩陣中的對角線兩側相應的元素,都有元素1即可。
顯然整除關係,不是完全關係
最後,我們來看如何判斷關係是循環關係。
顧名思義,循環關係,就是aRb,bRc,則cRa
也就是說,關係矩陣中,第i行的第j列是1,以及第j行的第k列也為1的話,
則第k行的第i列,元素也是1,即滿足“循環”性質。
顯然,整除關係不滿足循環。
注意事項
關係矩陣元素全為0是空關係,全為1為全域關係