《離散數學》中二元關系傳遞性的判定

張振榮

摘 要 《離散數學》中二元關系性質中傳遞性的判定是教學難點，本文列出傳遞性的真值表，利用真值表判斷傳遞性直觀有效，只有一種情形不滿足傳遞性，其余情形都滿足傳遞性。

關鍵詞 《離散數學》 二元關系

0引言

在《離散數學中》，二元關系的性質包括自反性、反自反性、對稱性、反對稱性和傳遞性。其中前四個性質可以由定義和關系圖直觀地表達，但是否滿足傳遞性僅從定義很難觀察出來。二元關系傳遞性的定義如下：

如果從定義來看，只能發現一種情形是滿足傳遞性的，即如，，，是傳遞的，但是，怎么用定義來判斷是否滿足傳遞性呢？

1利用真值表判斷傳遞性

我們不妨用真值表來分析這個定義，列出真值表如下：

真值表的第一種情形是我們熟悉的，從定義直接能判斷出來的。比如，為真，為真，為真，則滿足傳遞性。

從真值表判斷，第二種情形真值為假，即不滿足傳遞性。比如，沒有出現有序對，則為真，為真，為假，由真值表知，這是不滿足傳遞性的。

第三種情形和第五種情形看似不傳遞，但滿足傳遞性的定義。如，為真，為假，為真，由真值表知，這是滿足傳遞性的。再如，為假，為真，為真，滿足定義，是傳遞的。

第四種、第六種、第七種情形都是包含一個有序對的，滿足傳遞性，以第四種情形為例，，為真，為假，為假，最后真值為真，故是傳遞的。

第八種情形是空關系，雖然沒有有序對，但是真值為真，故滿足傳遞性。

定義理解清楚后，是不是所有的二元關系都很容易判斷了呢？在二元關系中，包含很多組有序對，如果有一組有序對不滿足傳遞的定義，但其他組都滿足傳遞的定義，那這個二元關系仍然是不傳遞的，比如分三組有序對考慮：（1）為真，為真，為真，則滿足傳遞性;（2）為真，為真，但為假，故不傳遞;（3）為真，為真，但為假，故不傳遞;因為（2）（3）不傳遞，故不滿足傳遞性。

如果定義中的有兩個或三個相等，那么它仍然符合傳遞性的定義。如，將有序對分為三組考慮：（1）有序對，（2）有序對，（3）有序對，三組都滿足傳遞性的定義，故是傳遞的。

2總結

綜上所述，根據傳遞性的定義判斷二元關系是否具有傳遞性容易出錯，而結合定義的真值表發現，只要二元關系中包含第二種情形，則就不是傳遞的，其余情形都是傳遞的。

參考文獻

[1] 屈婉玲.離散數學（第3版）[M].北京：清華大學出版社，2014.