孫鳳芝
(大慶師范學(xué)院 教師教育學(xué)院,黑龍江 大慶163712)
二元關(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)確而又迅速。
在現(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)系的傳遞性。
在課程安排的先后順序上考慮,把數(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)系是傳遞的。
定義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 是可傳遞的。
由上述定理,在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)系。
通過給出二元關(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.