如何判斷關係是否自反,反自反,對稱,反對稱,傳遞?

我們知道離散數學中,需要判斷關係是否為自反,反自反,對稱,反對稱,傳遞,完全,循環。這裡分享給大家如何使用關係矩陣,來判斷關係的性質。

方法/步驟

首先,求出關係的關係矩陣,即布爾邏輯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為全域關係

相關問題答案