摘要：傳遞關(guān)系是二元關(guān)系中比較難以掌握的部分，也是學(xué)生最容易出錯的地方。為使學(xué)生更好地掌握傳遞關(guān)系的判斷方法，本文將傳遞關(guān)系按關(guān)系有向圖分為1～3個節(jié)點，并結(jié)合謂詞公式法分析了11種情況的關(guān)系傳遞性。本文的內(nèi)容有助于學(xué)生掌握傳遞關(guān)系的判斷，并可有效提高傳遞關(guān)系的教學(xué)質(zhì)量。

關(guān)鍵詞：離散數(shù)學(xué)；二元關(guān)系；傳遞關(guān)系；有向圖

離散數(shù)學(xué)作為計算機科學(xué)領(lǐng)域最有效的一種數(shù)學(xué)工具，20世紀(jì)70年代初，國外就已經(jīng)將其作為計算機專業(yè)和一些工程學(xué)專業(yè)的學(xué)習(xí)課程［1］。離散數(shù)學(xué)的研究對象一般為有限個元素組成的集合，并以研究離散量的結(jié)構(gòu)和相互關(guān)系為主要目標(biāo)，因此它可以很好地描述計算機科學(xué)離散性的特點［23］。目前離散數(shù)學(xué)是計算機科學(xué)基礎(chǔ)理論的核心課程，也是許多計算機類專業(yè)課的必備基礎(chǔ)，包括數(shù)據(jù)結(jié)構(gòu)、算法原理、操作系統(tǒng)、編譯原理、數(shù)據(jù)庫原理、計算機網(wǎng)絡(luò)、人工智能和數(shù)字邏輯等［4］。離散數(shù)學(xué)對于培養(yǎng)學(xué)生的抽象思維能力和邏輯推理能力具有重要的作用［5］。學(xué)生通過對離散數(shù)學(xué)的學(xué)習(xí)，不但可以幫助學(xué)生在組合分析、算法設(shè)計以及應(yīng)用與建模等方面形成基本的離散思維方法，而且能夠培養(yǎng)學(xué)生嚴(yán)密的邏輯推理能力，從而為將來從事信息行業(yè)的理論研究和應(yīng)用開發(fā)打下堅實的基礎(chǔ)。

二元關(guān)系是離散數(shù)學(xué)集合論中的重要內(nèi)容，是兩個集合笛卡爾乘積的子集，研究的是一個集合內(nèi)部或兩個不同集合元素間關(guān)系。它與數(shù)理邏輯、集合論、布爾代數(shù)、組合數(shù)學(xué)和圖論等有密切的聯(lián)系，不但在數(shù)學(xué)領(lǐng)域中起著非常重要的作用，而且被廣泛應(yīng)用于計算機科學(xué)等領(lǐng)域。二元關(guān)系包括自反關(guān)系、反自反關(guān)系、對稱關(guān)系、反對稱關(guān)系以及傳遞關(guān)系，其中自反關(guān)系、反自反關(guān)系、對稱關(guān)系、反對稱關(guān)系的有向圖及關(guān)系矩陣具有十分鮮明和直觀的特點，而傳遞關(guān)系的特點比較隱蔽，有時往往很難從有向圖及關(guān)系矩陣中判斷一種關(guān)系是否為傳遞關(guān)系，因此傳遞關(guān)系的教學(xué)一直是二元關(guān)系的教學(xué)重點和難點，也是學(xué)生難以掌握的部分，而二元關(guān)系的學(xué)習(xí)又是后續(xù)關(guān)系閉包的基礎(chǔ)，二元關(guān)系的學(xué)習(xí)效果將直接影響后續(xù)學(xué)習(xí)的順利開展，為此對傳遞關(guān)系展開了大量的研究。杜衡吉研究了二元關(guān)系傳遞性的中途點及蘊涵式兩種判定方法［6］，李勁研究了傳遞關(guān)系的充分必要條件［7］，郭健等人研究了傳遞關(guān)系的幾種判定方法及適用條件［8］，張艷春利用關(guān)系矩陣以及關(guān)系圖研究二元關(guān)系的性質(zhì)［9］。

由于傳遞關(guān)系涉及集合中的三個節(jié)點，本文針對傳遞關(guān)系的難點問題，將傳遞關(guān)系的判斷分為1個至3個節(jié)點的情況進(jìn)行分析和討論，涵蓋了傳遞關(guān)系判斷的所有基本情況，并將部分結(jié)論推廣到了空關(guān)系、恒等關(guān)系及全域關(guān)系的傳遞性的判斷。由于多元素的集合的關(guān)系判斷可拆分為局部節(jié)點的傳遞關(guān)系的判斷，因此本文的研究結(jié)果不僅適用于1至3個節(jié)點的傳遞關(guān)系的判斷，同時適用于多元素的集合的傳遞關(guān)系判斷。

1二元關(guān)系的特點

集合的二元關(guān)系包括自反關(guān)系、反自反關(guān)系、對稱關(guān)系、反對稱關(guān)系及傳遞關(guān)系5大類。每種關(guān)系的關(guān)系矩陣及關(guān)系圖都有自身的特征，其中自反性關(guān)系矩陣的主對角線上的元素均為1，關(guān)系圖的每個節(jié)點均有環(huán)；反自反性關(guān)系矩陣的主對角線上的元素均為0，關(guān)系圖的每個節(jié)點均沒有環(huán)；對稱性關(guān)系矩陣為對稱矩陣，關(guān)系圖的任意兩個節(jié)點之間均無單向邊，即如果兩個節(jié)點之間有邊，則一定是一對平行邊；反對稱性關(guān)系矩陣中如果rij=1，且i≠j，則rji=0，關(guān)系圖的任意兩個節(jié)點之間如果有邊，則一定是一條單向邊；傳遞性關(guān)系矩陣對M2中1所在的位置，M中相應(yīng)的位置為1。傳遞性關(guān)系圖中，如果節(jié)點ai到aj有邊連接，且aj到ak也有邊連接，則ai到ak也有邊連接。

顯然，二元關(guān)系中自反關(guān)系、反自反關(guān)系、對稱關(guān)系、反對稱關(guān)系的關(guān)系圖具有鮮明、直觀的特點，而傳遞性關(guān)系圖中節(jié)點數(shù)量如果低于3個則沒有明顯的特征，因此集合傳遞關(guān)系的判斷相對其他4種關(guān)系更加困難，如何使學(xué)生掌握集合傳遞關(guān)系的判斷是二元關(guān)系的教學(xué)難點。

2傳遞關(guān)系的判定

本文將通過集合中含有1至3個元素三種情況，分別分析二元關(guān)系中傳遞關(guān)系的傳遞性。

2.1含有1個元素集合的傳遞性

如圖1（a）所示，集合Φ中只含有一個元素a，對應(yīng)的關(guān)系圖只有一個無環(huán)孤立節(jié)點，圖1（a）所示的關(guān)系用R1表示。

傳遞關(guān)系的定義為蘊涵關(guān)系式，當(dāng)蘊涵關(guān)系式的前件為假時，蘊涵關(guān)系為真。由于圖1中只存在一個無環(huán)的孤立節(jié)點，傳遞關(guān)系的前件為假，則對應(yīng)的蘊涵關(guān)系為真，則傳遞關(guān)系成立。

含有1個無環(huán)孤立節(jié)點的結(jié)論可以推廣到含有多個無環(huán)孤立節(jié)點，即集合的空關(guān)系具有傳遞性。

如圖1（b）所示，集合中只含有一個元素a，對應(yīng)的關(guān)系圖只有一個有環(huán)孤立節(jié)點，圖1（b）所示的關(guān)系用R2表示。

圖1（b）中的節(jié)點A可以看作是三個節(jié)點A、B、C的重合節(jié)點，則A、B、C所代表的元素滿足a=b=c，由于該節(jié)點自帶環(huán)，則滿足如下關(guān)系：

abc（a，b，c∈Φ∧〈a，b〉∈R2∧〈b，c〉∈R2→〈a，c〉∈R2）（1）

由公式（1）可知關(guān)系R2滿足傳遞性的要求，具有傳遞性。

含有1個有環(huán)孤立節(jié)點的結(jié)論可以推廣到含有多個有環(huán)孤立節(jié)點，即集合的恒等關(guān)系IA具有傳遞性。

2.2含有2個元素集合的傳遞性

2.2.1關(guān)系R3的傳遞性

如圖2（a）所示，集合Φ中含有兩個元素a和c，分別對應(yīng)關(guān)系圖中的有環(huán)節(jié)點A和無環(huán)節(jié)點C，圖2（a）所示的關(guān)系用R3表示。

由于節(jié)點A有環(huán)，可將其看作節(jié)點A和B的重合節(jié)點，其中節(jié)點B代表的元素為b，且滿足a=b。由圖2（a）所示，節(jié)點A經(jīng)過環(huán)到達(dá)節(jié)點B，節(jié)點B又可到達(dá)節(jié)點C，顯然節(jié)點A可到達(dá)節(jié)點C，公式（5）成立：

abc（a，b，c∈Φ∧〈a，b〉∈R3∧〈b，c〉∈R3→〈a，c〉∈R3）（2）

由公式（2）可知，關(guān)系R3滿足傳遞性的要求，具有傳遞性。

2.2.2關(guān)系R4的傳遞性

如圖2（b）所示，集合中含有兩個元素a和b，分別對應(yīng)關(guān)系圖中的有環(huán)節(jié)點A和無環(huán)節(jié)點B，圖2（b）所示的關(guān)系用R4表示。

由于節(jié)點B有環(huán)，可將其看作節(jié)點B和C的重合節(jié)點，其中節(jié)點C代表的元素為c，且滿足b=c。由圖2（b）所示，節(jié)點A經(jīng)過〈A，B〉到達(dá)節(jié)點B，節(jié)點B又經(jīng)過環(huán)可到達(dá)節(jié)點C，顯然節(jié)點A可到達(dá)節(jié)點C，公式（6）成立：

abc（a，b，c∈Φ∧〈a，b〉∈R4∧〈b，c〉∈R4→〈a，c〉∈R4）（3）

由公式（3）可知關(guān)系R4滿足傳遞性的要求，具有傳遞性。

2.2.3關(guān)系R5的傳遞性

如圖2（c）所示，集合中含有兩個元素a和b，分別對應(yīng)關(guān)系圖中的節(jié)點A和節(jié)點B，其中節(jié)點B看作節(jié)點B和C的重合節(jié)點，圖2（c）所示的關(guān)系用R5表示。

由圖2（c）可知，節(jié)點A可由路徑〈A，B〉到達(dá)節(jié)點B，但節(jié)點B沒有環(huán)，說明節(jié)點B并不可達(dá)節(jié)點C，即蘊涵關(guān)系式的前件為假時，蘊涵關(guān)系為真，R5滿足傳遞性的要求，具有傳遞性。

2.2.4關(guān)系R6的傳遞性

圖2（d）與圖2（c）不同的是，圖2（d）中含有雙向邊，而圖2（c）只含有單向邊，因此2（d）分別進(jìn)行如下兩種情況討論：

當(dāng)節(jié)點A看作節(jié)點A和C的重合節(jié)點時，節(jié)點A經(jīng)過〈A，B〉到達(dá)節(jié)點B，節(jié)點B又經(jīng)過〈B，C〉到達(dá)節(jié)點C，但節(jié)點A自身沒有環(huán)，即節(jié)點A不可達(dá)節(jié)點C，則

abc（a，b，c∈Φ∧〈a，b〉∈R5∧〈b，c〉∈R5→〈a，c〉R5）（4）

由公式（4）可知，關(guān)系R6不滿足傳遞性的要求。

當(dāng)節(jié)點B看作節(jié)點B和C的重合節(jié)點時，節(jié)點B經(jīng)過〈B，A〉到達(dá)節(jié)點A，節(jié)點A又經(jīng)過〈A，C〉到達(dá)節(jié)點C，但節(jié)點B自身無環(huán)，即節(jié)點B不可達(dá)節(jié)點C，則

abc（a，b，c∈Φ∧〈b，a〉∈R6∧〈a，c〉∈R6→〈b，c〉R6）（5）

由公式（5）可知，關(guān)系R6不滿足傳遞性的要求，不具有傳遞性。綜上所述，關(guān)系R6不具有傳遞性。

2.2.5關(guān)系R7的傳遞性

圖2（e）與圖2（d）相同的是也含有雙向邊，因此2（e）也分別進(jìn)行如下兩種情況討論：

當(dāng)節(jié)點A看作節(jié)點A和C的重合節(jié)點時，節(jié)點A經(jīng)過〈A，B〉到達(dá)節(jié)點B，節(jié)點B又經(jīng)過〈B，C〉到達(dá)節(jié)點C，但節(jié)點A自身有環(huán)，即節(jié)點A可達(dá)節(jié)點C，則

abc（a，b，c∈A∧〈a，b〉∈R7∧〈b，c〉∈R7→〈a，c〉∈R7）（6）

由公式（6）可知，關(guān)系R7滿足傳遞性的要求。

當(dāng)節(jié)點B看作節(jié)點B和C的重合節(jié)點時，節(jié)點B經(jīng)過〈B，A〉到達(dá)節(jié)點A，節(jié)點A又經(jīng)過〈A，C〉到達(dá)節(jié)點C，但節(jié)點B自身有環(huán)，即節(jié)點B可達(dá)節(jié)點C，則

abc（a，b，c∈Φ∧〈b，a〉∈R7∧〈a，c〉∈R7→〈b，c〉∈R7）（7）

由公式（7）可知，關(guān)系R7滿足傳遞性的要求，具有傳遞性。

綜上所述，關(guān)系R7具有傳遞性。

圖2（e）的結(jié)論可以推廣到含有多個節(jié)點的有向完全圖的情況，即集合的全域關(guān)系EA具有傳遞性。

2.3含有3個元素集合的傳遞性

2.3.1關(guān)系R8的傳遞性

如圖3（a）所示，集合Φ中含有三個元素a、b和c，分別對應(yīng)關(guān)系圖中的無環(huán)節(jié)點A、B和C，圖3（a）所示的關(guān)系用R8表示。

由圖3（a）可知，節(jié)點A可由路徑〈A，B〉到達(dá)節(jié)點B，但節(jié)點B和C之間沒有邊，說明節(jié)點B并不可達(dá)節(jié)點C，即如公式（2）所示的蘊涵關(guān)系式的前件為假時，蘊涵關(guān)系為真，R8滿足傳遞性的要求，R8具有傳遞性。

2.3.2關(guān)系R9的傳遞性

如圖3（b）所示，節(jié)點A可由路徑〈A，B〉到達(dá)節(jié)點B，節(jié)點B可由路徑〈B，C〉到達(dá)節(jié)點C，但節(jié)點A和C之間沒有邊，說明節(jié)點A并不可達(dá)節(jié)點C，則

abc（a，b，c∈Φ∧〈a，b〉∈R9∧〈b，c〉∈R9→〈a，c〉R9）（8）

由公式（8）可知，關(guān)系R9不滿足傳遞性的要求，不具有傳遞性。

2.3.3關(guān)系R10的傳遞性

如圖3（c）所示，節(jié)點A可由路徑〈A，B〉到達(dá)節(jié)點B，節(jié)點B可由路徑〈B，C〉到達(dá)節(jié)點C，同時節(jié)點A可由〈A，C〉到達(dá)節(jié)點C，說明節(jié)點A可達(dá)節(jié)點C，則

abc（a，b，c∈Φ∧〈a，b〉∈R10∧〈b，c〉∈R10→〈a，c〉∈R10）（9）

由公式（9）可知，關(guān)系R10滿足傳遞性的要求，具有傳遞性。

2.3.4關(guān)系R11的傳遞性

如圖3（d）所示，節(jié)點A可由路徑〈A，B〉到達(dá)節(jié)點B，節(jié)點B可由路徑〈B，C〉到達(dá)節(jié)點C，但節(jié)點A不可由有向邊〈A，C〉到達(dá)節(jié)點C，說明節(jié)點A不可達(dá)節(jié)點C，則

abc（a，b，c∈Φ∧〈a，b〉∈R11∧〈b，c〉∈R11→〈a，c〉R11）（10）

由公式（10）可知，關(guān)系R11不滿足傳遞性的要求，不具有傳遞性。

結(jié)語

傳遞關(guān)系相對于自反關(guān)系、反自反關(guān)系、對稱關(guān)系以及反對稱關(guān)系不具有直觀的幾何特征，因此是二元關(guān)系教學(xué)中的難點。本文利用關(guān)系有向圖并結(jié)合謂詞公式法分析了11種關(guān)系的傳遞性，并將分析結(jié)果擴(kuò)展到空關(guān)系、恒等關(guān)系及全域關(guān)系，這些結(jié)論對多元素集合的傳遞性分析同樣具有指導(dǎo)意義。本文的內(nèi)容可以幫助教師突破傳遞關(guān)系判斷的教學(xué)難點，同時有助于學(xué)生理解和掌握傳遞關(guān)系。

參考文獻(xiàn)：

［1］吳明芬，瞿赟昀.離散數(shù)學(xué)中的閉包概念及應(yīng)用［J］，鄭州大學(xué)學(xué)報（工學(xué)版），2012，33（5）：133137.

［2］左孝凌，李為監(jiān)，劉永才.離散數(shù)學(xué)［Ｍ］.上海：上海科技文獻(xiàn)出版社，2001.

［3］傅彥.離散數(shù)學(xué)基礎(chǔ)及應(yīng)用［Ｍ］.成都：電子科技大學(xué)出版社.2000.

［4］惠康華，李春利.離散數(shù)學(xué)教學(xué)改革研究［J］，計算機時代，2021（02）：9395+98.

［5］李海俠.離散數(shù)學(xué)中二元關(guān)系的教學(xué)模式改革探討——基于信息與計算科學(xué)專業(yè)［J］，高教學(xué)刊，2020（06）：129131.

［6］杜衡吉.二元關(guān)系傳遞性的兩種等價判定［J］.曲靖師范學(xué)院學(xué)報，2015，34（06）：4547.

［7］李勁.判斷二元關(guān)系傳遞性的充分必要條件［J］.河西學(xué)院學(xué)報，2016，32（2）：1116.

［8］郭鍵，趙明茹.判定二元關(guān)系傳遞性的幾種方法［J］.大慶師范學(xué)院學(xué)報，2008，28（5）：4548.

［9］張艷春.二元關(guān)系的性質(zhì)及其研究［J］.時代教育，2009（6）：121122.

［10］屈婉玲，耿素云，張立昂.離散數(shù)學(xué)［M］.北京：高等教育出版社，2015.

基金項目：河北省首批省級研究生教育教學(xué)改革研究項目（YJG2023028）

作者簡介：鄒成業(yè)（1982—），男，漢族，遼寧人，博士，講師，主要從事DNA計算、復(fù)雜網(wǎng)絡(luò)及圖像加密方面的研究；張炳（1989—），男，漢族，湖北人，博士，副教授，主要從事軟件測試課程教育方面的研究。

*通訊作者：吳培良（1981—），男，漢族，河北人，博士，教授，主要從事家庭服務(wù)機器人環(huán)境工具和服務(wù)對象認(rèn)知、家庭服務(wù)機器人操作技能學(xué)習(xí)等方面的研究。