《離散數(shù)學(xué)》中二元關(guān)系傳遞性的判定

張振榮

摘 要 《離散數(shù)學(xué)》中二元關(guān)系性質(zhì)中傳遞性的判定是教學(xué)難點(diǎn)，本文列出傳遞性的真值表，利用真值表判斷傳遞性直觀有效，只有一種情形不滿足傳遞性，其余情形都滿足傳遞性。

關(guān)鍵詞 《離散數(shù)學(xué)》 二元關(guān)系

0引言

在《離散數(shù)學(xué)中》，二元關(guān)系的性質(zhì)包括自反性、反自反性、對(duì)稱性、反對(duì)稱性和傳遞性。其中前四個(gè)性質(zhì)可以由定義和關(guān)系圖直觀地表達(dá)，但是否滿足傳遞性僅從定義很難觀察出來。二元關(guān)系傳遞性的定義如下：

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

1利用真值表判斷傳遞性

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

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

從真值表判斷，第二種情形真值為假，即不滿足傳遞性。比如，沒有出現(xiàn)有序?qū)?，則為真，為真，為假，由真值表知，這是不滿足傳遞性的。

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

第四種、第六種、第七種情形都是包含一個(gè)有序?qū)Φ?，滿足傳遞性，以第四種情形為例，，為真，為假，為假，最后真值為真，故是傳遞的。

第八種情形是空關(guān)系，雖然沒有有序?qū)?，但是真值為真，故滿足傳遞性。

定義理解清楚后，是不是所有的二元關(guān)系都很容易判斷了呢？在二元關(guān)系中，包含很多組有序?qū)?，如果有一組有序?qū)Σ粷M足傳遞的定義，但其他組都滿足傳遞的定義，那這個(gè)二元關(guān)系仍然是不傳遞的，比如分三組有序?qū)紤]：（1）為真，為真，為真，則滿足傳遞性;（2）為真，為真，但為假，故不傳遞;（3）為真，為真，但為假，故不傳遞;因?yàn)椋?）（3）不傳遞，故不滿足傳遞性。

如果定義中的有兩個(gè)或三個(gè)相等，那么它仍然符合傳遞性的定義。如，將有序?qū)Ψ譃槿M考慮：（1）有序?qū)?，?）有序?qū)?，?）有序?qū)ΓM都滿足傳遞性的定義，故是傳遞的。

2總結(jié)

綜上所述，根據(jù)傳遞性的定義判斷二元關(guān)系是否具有傳遞性容易出錯(cuò)，而結(jié)合定義的真值表發(fā)現(xiàn)，只要二元關(guān)系中包含第二種情形，則就不是傳遞的，其余情形都是傳遞的。

參考文獻(xiàn)

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