二元關(guān)系傳遞性的等價定義及其判別法

孫鳳芝

(大慶師范學(xué)院 教師教育學(xué)院，黑龍江 大慶163712)

0 引言

二元關(guān)系是離散數(shù)學(xué)中重要的基本概念，實際判定某個二元關(guān)系性質(zhì)時，自反性、反自反性、對稱性的判定比較容易，而傳遞性的判定有時則較困難，是學(xué)習(xí)的重點，也是難點。一方面，本文給出二元關(guān)系傳遞性的等價定義，得到解決途徑:從邏輯蘊(yùn)涵式的角度，給出一種等價的定義形式，該定義把判斷集合A 上的二元關(guān)系R 是否具有傳遞性問題轉(zhuǎn)化為判斷蘊(yùn)涵式的真假問題;另一方面，本文利用二元關(guān)系與其關(guān)系矩陣是一一對應(yīng)的結(jié)論，給出矩形判別法，這樣就突破了難點，使對二元關(guān)系傳遞性的判定準(zhǔn)確而又迅速。

1 二元關(guān)系傳遞性的定義及其局限性

在現(xiàn)有的離散數(shù)學(xué)教材文獻(xiàn)［1］［2］中，對二元關(guān)系反對稱性和傳遞性分別定義如下:

定義1 :設(shè)R 為集合A 上的二元關(guān)系，對于(x，y，z ∈A，當(dāng)＜x，y ＞∈R 且＜y，z ＞∈R 時，有＜x，z ＞∈R，則稱R 在A 上具有傳遞性。

例1:設(shè)集合A={1，2，3，4}，R 是A 上的二元關(guān)系，R={＜1，2 ＞，＜3，4 ＞}，問R 在A 上是否可傳遞?

分析:正確答案為“R 在A 上是可傳遞的。”許多同學(xué)對此感到困惑，提出疑問:他們認(rèn)為在A 中找不到元素x，y，z，使得＜x，y ＞∈R，＜y，z ＞∈R，當(dāng)然也更談不到＜x，z ＞∈R 了，所以他們認(rèn)為R 在A 上是不可傳遞的?？梢?，直接根據(jù)傳遞性的定義不好判定二元關(guān)系的傳遞性。

2 二元關(guān)系傳遞性的等價定義及應(yīng)用

在課程安排的先后順序上考慮，把數(shù)理邏輯安排在二元關(guān)系(集合論)之前講，把定義用邏輯部分的符號語言等價地表示出來，即得第二等價定義。

傳遞性等價定義 對于集合A 上的關(guān)系R，若

為真，則稱R 在A 上具有傳遞性。

從上述定義中可以看出，定義的表達(dá)形式是蘊(yùn)涵式，從而可以把判斷集合A 上的二元關(guān)系R 是否具有傳遞性問題轉(zhuǎn)化為判斷定義中蘊(yùn)涵式(1)式的真假問題。

應(yīng)用傳遞性第二等價定義可以很快地判定前面例1 的傳遞性

例2:設(shè)集合A={1，2，3，4}，R 是A 上的二元關(guān)系，R={＜1，2 ＞，＜3，4 ＞}，問R 在A 上是否可傳遞?

解:對R 中的有序?qū)Γ?，2 ＞，不存在＜2，x ＞∈R，即＜2，x ＞(R(－ x ∈A)，蘊(yùn)涵式的前件為假，蘊(yùn)涵式為真;

對R 中的有序?qū)Γ?，4 ＞，不存在＜4，x ＞∈R，即＜4，x ＞(R(－ x ∈A)，蘊(yùn)涵式的前件為假，蘊(yùn)涵式為真;

因此，R 中的每一個有序?qū)Χ际箓鬟f性定義等價形式中的蘊(yùn)涵式為真，該二元關(guān)系是傳遞的。

3 二元關(guān)系的判別法及其應(yīng)用

3.1 有關(guān)定義、定理及其證明

定義2:對于A 是有窮集合時，設(shè)A={x1，x2，…，xn}，R 是A 上的關(guān)系，

是R 的關(guān)系矩陣，記做MR。

定義3:設(shè)F，G 為二元關(guān)系，G 對F 的右復(fù)合記作F °G，其中

由傳遞的關(guān)系的定義1 及右復(fù)合運算的定義3，我們有以下的定理。

引理:設(shè)R 為A 上的關(guān)系，則R 在A 上傳遞當(dāng)且僅當(dāng)R°R ?R

由引理與關(guān)系矩陣定義2 及右復(fù)合運算的定義3，我們有以下的定理。

定理:設(shè)R(A×A，其中A 為有限集合(不妨設(shè)為n 元素集合)，MR是R 的關(guān)系矩陣，則R 是可傳遞的當(dāng)且僅當(dāng)在MR中，對于任意的k，若有aik=akj=1(1 ≤i，j ≤n)，則必有aij=1.

證明:不妨設(shè)A={a1，a2，…，an}。對于任意的i，j(1 ≤i，j ≤n)，若存在＜ai，aj＞∈R，則在MR中有aij=1;否則aij=0.反之亦然。

必要性:R 是可傳遞的，即若對于任意ai，aj，ak∈X，每當(dāng)(＜ai，ak＞∈R)∧(＜ak，aj＞∈R)時必有＜ai，aj＞∈R，則有在MR中，對于任意的k，若有aik=aki=1，則必有aij=1。

充分性:已知在MR中，對于任意的k，若有aik=akj=1(1 ≤i，j ≤n)，則必有aij=1。進(jìn)而有對于任意ai，aj，ak∈X，每當(dāng)(＜ai，ak＞∈R)∧(＜ak，aj＞∈R)時，必有＜ai，aj＞∈R。故證得R 是可傳遞的。

3.2 矩形判別方法與應(yīng)用

由上述定理，在R 是可傳遞的等價條件中所涉及的關(guān)系矩陣MR中元素aik、akj及aij再加上主對角上元素akk，如果將這四個點用直線分別沿所在的行和列連起來，則恰好構(gòu)成一個矩形，由此可以得到傳遞關(guān)系R 的矩形判別法:

(1)依次選取MR中主對角線上元素akk(k=1，2，3，...，n)(并以此元素為中心點劃橫、縱線各一條，即在第k 行與第k 列上各劃一條線，可用實線表示);

(2)對第k 行元素中依次找出所有非零元素，設(shè)為akj(1 ≤j ≤n)，(并在此元素所在的第j 列上劃一條線，可用虛線表示)，顯然，akj=1;

(3)對(2)中的每個元素akj，在第k 列元素中依次找出所有非零元素，設(shè)為aik(并在此元素所在的第i行上劃一條線，可用虛線表示)，顯然，aik=1;

(4)判別:若對于(2)、(3)中所有非零元素aik、akj，元素aij非零(即(2)、(3)中兩條虛線的交點處的元素非零)，則可以判別關(guān)系R 是可傳遞的(見圖1)。

圖1 傳遞關(guān)系R 的矩形判別法

注:1)在中，akk只是提供了判別的一個順序號，使思路清晰，不重不漏，而akk=0 還是akk=1，對判別沒有影響;

2)在判別方法中，亦可將(2)、(3)中的“行”“列”互換;

3)若要驗證或判別關(guān)系R 是可傳遞的，則須在MR中對于每一個k(k=1，2，3，...，n)驗證出對于所有的i，j(1 ≤i，j ≤n)，或者aik與akj至少有一個為零，或者aik、akj或者aij都等于1.=0

例3 設(shè)A={a1，a2，a3，a4，a5，a6}，

R={(a1，a2)，(a1，a3)，(a1，a4)，(a2，a3)，(a2，a4)，(a3，a4)，(a1，a6)，(a5，a4)，(a6，a2)，(a6，a3)，(a6，a4)}，

試判斷R 是傳遞關(guān)系嗎?

方法一:用矩形判別法判別R 是傳遞的:

當(dāng)k=1 時，由于在第1 列中元素均為0，故進(jìn)行下一步;

當(dāng)k=2 時，第2 行中有兩個元素a23=1，a24=1，而在第2 列中有兩個元素a12=1，a62=1，由此只須進(jìn)行四次判別:

在a23=1 且a12=1 的情況下判別是否有a13=1;

在a23=1 且a62=1 的情況下判別是否有a63=1;

在a24=1 且a12=1 的情況下判別是否有a14=1;

在a24=1 且a62=1 的情況下判別是否有a64=1;

由MR知a13=1，a63=1，a14=1，a64=1。

當(dāng)k=3 時，情況與k=2 時類似，……

當(dāng)k ＞3 時，讀者可類似地討論。

例2 已知

A={a，b，c，d，e，f}，R={＜a，a ＞，＜a，b ＞，＜a，c ＞，＜a，f ＞，＜b，b ＞，＜b，c ＞，＜b，f ＞，＜d，a ＞，＜d，b ＞，＜d，c ＞，＜d，d ＞.＜d，f ＞，＜e，a ＞，＜e，b ＞，＜e，c ＞，＜e，d ＞，＜e，e ＞，＜e，f ＞，＜f，a ＞，＜f，b ＞}，試判斷R 是否是傳遞關(guān)系。

方法二:

圖4 傳遞關(guān)系R 的矩形判別法

由矩形判別法，如圖4，因為a62=1，a23=1，而交叉點a63=0，所以，R 不是傳遞關(guān)系。

4 結(jié) 語

通過給出二元關(guān)系傳遞性的等價定義和矩形判別法，并通過實例對它們進(jìn)行了應(yīng)用，使對二元關(guān)系傳遞性的判斷直觀、高效。

［1］左孝凌，李為鑒，劉永才.離散數(shù)學(xué)［M］.上海:上海科學(xué)技術(shù)文獻(xiàn)出版社，1982.

［2］耿素云，屈婉玲，張立昂.離散數(shù)學(xué)［M］.北京:清華大學(xué)出版社，1991:75－86.

［3］耿素云，屈婉玲.離散數(shù)學(xué)［M］.北京:高等教育出版社，1997:1－105，132－156.

［4］Kolman B，Busby R C，Ross S C.Discrete Mathematical Structures［M］.Beijing:Higher Education press，2001.

［5］楊思春，王小林.二元關(guān)系傳遞性研究［J］.微機(jī)發(fā)展，2003，13(10):88－89.