二元關(guān)系中“傳遞關(guān)系”的判斷及其研究

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

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

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

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

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

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

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

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

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

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

2.1含有1個(gè)元素集合的傳遞性

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

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

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

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

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

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

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

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

2.2含有2個(gè)元素集合的傳遞性

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

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

由于節(jié)點(diǎn)A有環(huán)，可將其看作節(jié)點(diǎn)A和B的重合節(jié)點(diǎn)，其中節(jié)點(diǎn)B代表的元素為b，且滿足a=b。由圖2（a）所示，節(jié)點(diǎn)A經(jīng)過環(huán)到達(dá)節(jié)點(diǎn)B，節(jié)點(diǎn)B又可到達(dá)節(jié)點(diǎn)C，顯然節(jié)點(diǎn)A可到達(dá)節(jié)點(diǎn)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）所示，集合中含有兩個(gè)元素a和b，分別對(duì)應(yīng)關(guān)系圖中的有環(huán)節(jié)點(diǎn)A和無(wú)環(huán)節(jié)點(diǎn)B，圖2（b）所示的關(guān)系用R4表示。

由于節(jié)點(diǎn)B有環(huán)，可將其看作節(jié)點(diǎn)B和C的重合節(jié)點(diǎn)，其中節(jié)點(diǎn)C代表的元素為c，且滿足b=c。由圖2（b）所示，節(jié)點(diǎn)A經(jīng)過〈A，B〉到達(dá)節(jié)點(diǎn)B，節(jié)點(diǎn)B又經(jīng)過環(huán)可到達(dá)節(jié)點(diǎn)C，顯然節(jié)點(diǎn)A可到達(dá)節(jié)點(diǎn)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）所示，集合中含有兩個(gè)元素a和b，分別對(duì)應(yīng)關(guān)系圖中的節(jié)點(diǎn)A和節(jié)點(diǎn)B，其中節(jié)點(diǎn)B看作節(jié)點(diǎn)B和C的重合節(jié)點(diǎn)，圖2（c）所示的關(guān)系用R5表示。

由圖2（c）可知，節(jié)點(diǎn)A可由路徑〈A，B〉到達(dá)節(jié)點(diǎn)B，但節(jié)點(diǎn)B沒有環(huán)，說明節(jié)點(diǎn)B并不可達(dá)節(jié)點(diǎn)C，即蘊(yùn)涵關(guān)系式的前件為假時(shí)，蘊(yù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é)點(diǎn)A看作節(jié)點(diǎn)A和C的重合節(jié)點(diǎn)時(shí)，節(jié)點(diǎn)A經(jīng)過〈A，B〉到達(dá)節(jié)點(diǎn)B，節(jié)點(diǎn)B又經(jīng)過〈B，C〉到達(dá)節(jié)點(diǎn)C，但節(jié)點(diǎn)A自身沒有環(huán)，即節(jié)點(diǎn)A不可達(dá)節(jié)點(diǎn)C，則

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

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

當(dāng)節(jié)點(diǎn)B看作節(jié)點(diǎn)B和C的重合節(jié)點(diǎn)時(shí)，節(jié)點(diǎn)B經(jīng)過〈B，A〉到達(dá)節(jié)點(diǎn)A，節(jié)點(diǎn)A又經(jīng)過〈A，C〉到達(dá)節(jié)點(diǎn)C，但節(jié)點(diǎn)B自身無(wú)環(huán)，即節(jié)點(diǎn)B不可達(dá)節(jié)點(diǎn)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é)點(diǎn)A看作節(jié)點(diǎn)A和C的重合節(jié)點(diǎn)時(shí)，節(jié)點(diǎn)A經(jīng)過〈A，B〉到達(dá)節(jié)點(diǎn)B，節(jié)點(diǎn)B又經(jīng)過〈B，C〉到達(dá)節(jié)點(diǎn)C，但節(jié)點(diǎn)A自身有環(huán)，即節(jié)點(diǎn)A可達(dá)節(jié)點(diǎn)C，則

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

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

當(dāng)節(jié)點(diǎn)B看作節(jié)點(diǎn)B和C的重合節(jié)點(diǎn)時(shí)，節(jié)點(diǎn)B經(jīng)過〈B，A〉到達(dá)節(jié)點(diǎn)A，節(jié)點(diǎn)A又經(jīng)過〈A，C〉到達(dá)節(jié)點(diǎn)C，但節(jié)點(diǎn)B自身有環(huán)，即節(jié)點(diǎn)B可達(dá)節(jié)點(diǎn)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é)論可以推廣到含有多個(gè)節(jié)點(diǎn)的有向完全圖的情況，即集合的全域關(guān)系EA具有傳遞性。

2.3含有3個(gè)元素集合的傳遞性

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

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

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

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

如圖3（b）所示，節(jié)點(diǎn)A可由路徑〈A，B〉到達(dá)節(jié)點(diǎn)B，節(jié)點(diǎn)B可由路徑〈B，C〉到達(dá)節(jié)點(diǎn)C，但節(jié)點(diǎn)A和C之間沒有邊，說明節(jié)點(diǎn)A并不可達(dá)節(jié)點(diǎn)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é)點(diǎn)A可由路徑〈A，B〉到達(dá)節(jié)點(diǎn)B，節(jié)點(diǎn)B可由路徑〈B，C〉到達(dá)節(jié)點(diǎn)C，同時(shí)節(jié)點(diǎn)A可由〈A，C〉到達(dá)節(jié)點(diǎn)C，說明節(jié)點(diǎn)A可達(dá)節(jié)點(diǎn)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é)點(diǎn)A可由路徑〈A，B〉到達(dá)節(jié)點(diǎn)B，節(jié)點(diǎn)B可由路徑〈B，C〉到達(dá)節(jié)點(diǎn)C，但節(jié)點(diǎn)A不可由有向邊〈A，C〉到達(dá)節(jié)點(diǎn)C，說明節(jié)點(diǎn)A不可達(dá)節(jié)點(diǎn)C，則

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

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

結(jié)語(yǔ)

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

參考文獻(xiàn)：

［1］吳明芬，瞿赟昀.離散數(shù)學(xué)中的閉包概念及應(yīng)用［J］，鄭州大學(xué)學(xué)報(bào)（工學(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］，計(jì)算機(jī)時(shí)代，2021（02）：9395+98.

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

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

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

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

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

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

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

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

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