第6章二元關(guān)系2ppt課件

1、離離 散散 數(shù)數(shù) 學(xué)學(xué)電子科技大學(xué)電子科技大學(xué)數(shù)數(shù) 學(xué)學(xué) 科科 學(xué)學(xué) 學(xué)學(xué) 院院20222022年年2 2月月5 5日星期六日星期六2 26.4 6.4 關(guān)系的性質(zhì)關(guān)系的性質(zhì)-重點(diǎn)重點(diǎn) 本節(jié)涉及到的關(guān)系，如無特別聲明，都是假定本節(jié)涉及到的關(guān)系，如無特別聲明，都是假定其前域和后域相同。即都為定義在集合其前域和后域相同。即都為定義在集合A A上的關(guān)系，上的關(guān)系，且且A A是非空集合。對(duì)于前后域不相同的關(guān)系，其性是非空集合。對(duì)于前后域不相同的關(guān)系，其性質(zhì)無法加以定義。質(zhì)無法加以定義。6.4.1 6.4.1 關(guān)系性質(zhì)的定義關(guān)系性質(zhì)的定義1.1.關(guān)系性質(zhì)的定義關(guān)系性質(zhì)的定義3 3定義定義6.4.1-36

2、.4.1-3設(shè)設(shè)R R是集合是集合A A上的關(guān)系，上的關(guān)系， 1. 1. 如果對(duì)任意如果對(duì)任意xAxA，都有，都有RR，那么稱，那么稱R R在在A A上是自反上是自反的，或稱的，或稱R R具有自反性具有自反性. .2.2.如果對(duì)任意如果對(duì)任意xAxA，都有，都有 R R，那么稱，那么稱R R在在A A上是反自上是反自 反的，或稱反的，或稱R R具有反自反性。具有反自反性。3.3.對(duì)任意對(duì)任意x,yAx,yA，假設(shè)，假設(shè)RR，那么，那么 R R，則稱關(guān)，則稱關(guān)系系R R是對(duì)稱的，或稱是對(duì)稱的，或稱R R具有對(duì)稱性；具有對(duì)稱性；4.4.對(duì)任意對(duì)任意x,yAx,yA，假設(shè)，假設(shè)RR且且RR，那么，那

3、么x xy y或者或者, ,若若xy,xy,那么那么 與與不全屬于不全屬于R R），則），則稱關(guān)系稱關(guān)系R R是反對(duì)稱的，或稱是反對(duì)稱的，或稱R R具有反對(duì)稱性。具有反對(duì)稱性。5.5.對(duì)任意對(duì)任意x,y,zAx,y,zA，假設(shè)，假設(shè)RR且且RR，那么，那么RR，則稱關(guān)系，則稱關(guān)系R R是傳遞的，或稱是傳遞的，或稱R R具有傳遞性。具有傳遞性。4 4例例1 1：1.1.整數(shù)集整數(shù)集I I上的上的“等于關(guān)系是自反的、反對(duì)稱的、對(duì)等于關(guān)系是自反的、反對(duì)稱的、對(duì)稱的、傳遞的關(guān)系。稱的、傳遞的關(guān)系。 “ “小于等于關(guān)系是自反的、反對(duì)稱的、傳遞的關(guān)系；小于等于關(guān)系是自反的、反對(duì)稱的、傳遞的關(guān)系； “ “小

4、于關(guān)系是反自反的、反對(duì)稱的、傳遞的關(guān)系。小于關(guān)系是反自反的、反對(duì)稱的、傳遞的關(guān)系。 2. 2.冪集上的冪集上的“包含關(guān)系關(guān)系是自反的、反對(duì)稱的、傳遞包含關(guān)系關(guān)系是自反的、反對(duì)稱的、傳遞的關(guān)系。的關(guān)系。 3. 3.命題公式集合上的蘊(yùn)涵關(guān)系命題公式集合上的蘊(yùn)涵關(guān)系“”具有自反性、反對(duì)稱具有自反性、反對(duì)稱性和傳遞性。性和傳遞性。 4. 4.三角形的相似關(guān)系具有自反性、對(duì)稱性和傳遞性。三角形的相似關(guān)系具有自反性、對(duì)稱性和傳遞性。 5. 5.人的集合上的朋友關(guān)系具有自反性和對(duì)稱性人的集合上的朋友關(guān)系具有自反性和對(duì)稱性; ; 父子關(guān)系具有反自反性和反對(duì)稱性父子關(guān)系具有反自反性和反對(duì)稱性. .5 5例例2：

5、設(shè)：設(shè)A是任意的非空集合，那么是任意的非空集合，那么 A上的全關(guān)系上的全關(guān)系A(chǔ)A是是 自反的、對(duì)稱的、傳遞的關(guān)系；自反的、對(duì)稱的、傳遞的關(guān)系； A上的空關(guān)系上的空關(guān)系是是 反自反的、反對(duì)稱的、對(duì)稱的、傳反自反的、反對(duì)稱的、對(duì)稱的、傳 遞的關(guān)系；遞的關(guān)系； A上的恒等關(guān)系上的恒等關(guān)系IA是是 自反的、對(duì)稱的、反對(duì)稱的、傳自反的、對(duì)稱的、反對(duì)稱的、傳 遞的關(guān)系。遞的關(guān)系。例例3 3：設(shè)：設(shè)A=1,2,3A=1,2,3，A A上的關(guān)系：上的關(guān)系：（1R=, 那么 R是自反的,反對(duì)稱的,傳遞的.（2S=, 那么 S是反自反的,對(duì)稱的.6 6（3U =, 那么 U 是對(duì)稱的,反對(duì)稱的,傳遞的.（4V =

6、, 那么 V 是反對(duì)稱的,傳遞的.（5T=, 那么 T 5個(gè)性質(zhì)都沒有.2.“2.“性質(zhì)在關(guān)系圖和關(guān)系矩陣上的反應(yīng)性質(zhì)在關(guān)系圖和關(guān)系矩陣上的反應(yīng)（1 1關(guān)系關(guān)系R R是自反的是自反的 關(guān)系圖中每個(gè)節(jié)點(diǎn)都有環(huán)關(guān)系圖中每個(gè)節(jié)點(diǎn)都有環(huán) 關(guān)系矩陣的主對(duì)角線上的元素全為關(guān)系矩陣的主對(duì)角線上的元素全為1 1（2 2關(guān)系關(guān)系R R是反自反的是反自反的 關(guān)系圖中每個(gè)節(jié)點(diǎn)都無環(huán)關(guān)系圖中每個(gè)節(jié)點(diǎn)都無環(huán) 關(guān)系矩陣的主對(duì)角線上的元素全為關(guān)系矩陣的主對(duì)角線上的元素全為0 07 7(3) 關(guān)系R是對(duì)稱的 關(guān)系圖中任何一對(duì)結(jié)點(diǎn)之間，要么有方向相反的兩條邊，要么無邊 關(guān)系矩陣為對(duì)稱矩陣(4) 關(guān)系R是反對(duì)稱的 關(guān)系圖中任何一

7、對(duì)結(jié)點(diǎn)之間，至多有一條邊； R的關(guān)系矩陣滿足 rijrji0，i,j=1,2,n，ij。(5) 關(guān)系R是傳遞的 圖中,任何三個(gè)節(jié)點(diǎn)x,y,z(可以相同)之間，若從x到y(tǒng)有一條邊存在,從y到z有一條邊存在,則從x到z一定有一條邊存在. 關(guān)系矩陣中關(guān)系矩陣中, ,如果如果rijrij1 1且且rjkrjk1,1,則則rikrik1 18 8S0 1 0M0 0 11 0 0有有: :反自反性和反對(duì)稱性反自反性和反對(duì)稱性132有有: :反自反性和反對(duì)稱性反自反性和反對(duì)稱性有有: :自反性自反性, ,反對(duì)反對(duì)稱性和傳遞性稱性和傳遞性312例例 A=1,2,3 A=1,2,3上關(guān)系上關(guān)系: :9 9設(shè)設(shè)

8、A Aa,b,c,a,b,c,試判斷如下圖所示試判斷如下圖所示A A上關(guān)系的性質(zhì)：上關(guān)系的性質(zhì)：例例a ab bc c(a)(a)a ab bc c(b)(b)a ab bc c(c)(c)a ab bc c(d)(d)a ab bc c(e)(e)a ab bc c(f)(f)a ab bc c(g)(g)a ab bc c(h)(h)圖圖(a)(a)的關(guān)系是自反的、的關(guān)系是自反的、對(duì)稱的、反對(duì)稱的、傳對(duì)稱的、反對(duì)稱的、傳遞的關(guān)系遞的關(guān)系圖圖(b)(b)的關(guān)系是具備反自的關(guān)系是具備反自反的、對(duì)稱的、反對(duì)稱反的、對(duì)稱的、反對(duì)稱的、傳遞的關(guān)系的、傳遞的關(guān)系圖圖(c)(c)的關(guān)系是具備對(duì)稱的關(guān)系是

9、具備對(duì)稱的、反對(duì)稱的、傳遞的的、反對(duì)稱的、傳遞的關(guān)系關(guān)系圖圖(d)(d)的關(guān)系是不具備任的關(guān)系是不具備任何的性質(zhì)關(guān)系何的性質(zhì)關(guān)系圖圖(e)(e)的關(guān)系是具備自反的關(guān)系是具備自反的、對(duì)稱的、傳遞的關(guān)的、對(duì)稱的、傳遞的關(guān)系系圖圖(f)(f)的關(guān)系是具備反自的關(guān)系是具備反自反的、反對(duì)稱的、傳遞反的、反對(duì)稱的、傳遞的關(guān)系的關(guān)系圖圖(g)(g)的關(guān)系是具備反自的關(guān)系是具備反自反的、反對(duì)稱的關(guān)系反的、反對(duì)稱的關(guān)系圖圖(h)(h)的關(guān)系是具備反自的關(guān)系是具備反自反的、反對(duì)稱的、傳遞的反的、反對(duì)稱的、傳遞的關(guān)系關(guān)系1010注注: :(3) (3) 存在既是對(duì)稱也是反對(duì)稱的關(guān)系；存在既是對(duì)稱也是反對(duì)稱的關(guān)系；(

10、1) 非空集合非空集合A上的關(guān)系上的關(guān)系,若有自反性若有自反性,則一定沒有反自則一定沒有反自反性反性; 反知反知, 若有反自反性若有反自反性,則一定沒有自反性則一定沒有自反性;(2) 存在既不是對(duì)稱也不是反對(duì)稱的關(guān)系；存在既不是對(duì)稱也不是反對(duì)稱的關(guān)系；(4)(4)非空集合非空集合A A上的空關(guān)系具有反自反性、對(duì)稱性、上的空關(guān)系具有反自反性、對(duì)稱性、 反對(duì)稱性和傳遞性；反對(duì)稱性和傳遞性；(5)(5)空集上的空關(guān)系空集上的空關(guān)系5 5個(gè)性質(zhì)都具有個(gè)性質(zhì)都具有. .1111總結(jié)總結(jié)自反自反 反自反反自反對(duì)稱對(duì)稱反對(duì)稱反對(duì)稱傳遞傳遞定定義義 x,xRR x,x R R Rx,yRRR RRRxRx=y

11、x=y Rx,yRRRRR關(guān)關(guān)系系圖圖每個(gè)每個(gè)結(jié)點(diǎn)結(jié)點(diǎn)都有都有環(huán)環(huán)每個(gè)結(jié)每個(gè)結(jié)點(diǎn)都無點(diǎn)都無環(huán)環(huán)每對(duì)結(jié)點(diǎn)間每對(duì)結(jié)點(diǎn)間或有方向相或有方向相反的兩條邊，反的兩條邊，或無任何邊或無任何邊每對(duì)結(jié)點(diǎn)間至每對(duì)結(jié)點(diǎn)間至多有一條邊存多有一條邊存在在任三個(gè)結(jié)點(diǎn)任三個(gè)結(jié)點(diǎn)x,y,zx,y,z，若從若從x x到到y(tǒng) y有邊，從有邊，從y y到到z z有邊，則從有邊，則從x x到到z z一定有邊一定有邊關(guān)系關(guān)系矩陣矩陣對(duì)角對(duì)角線上線上全為全為1 1對(duì)角線對(duì)角線上全為上全為0 0對(duì)稱矩陣對(duì)稱矩陣r rijij r rjiji=0,=0,i,j=1,2,n, i,j=1,2,n, i ij j如如r rijij1 1且且r

12、 rjkjk1 1則則r rikik1 11212反自反反自反關(guān)系性質(zhì)的證明方法關(guān)系性質(zhì)的證明方法自反自反任取任取x xA A，中間過程中間過程任取任取x xA A，中間過程中間過程對(duì)稱對(duì)稱任取任取x,yx,yA A，假設(shè)假設(shè)R R，中間過程中間過程R R。R R。R R。1313關(guān)系性質(zhì)的證明方法關(guān)系性質(zhì)的證明方法( (續(xù)續(xù)) )反對(duì)稱反對(duì)稱任取任取x,yx,yA A，假設(shè)，假設(shè)R R，R R，中間過程中間過程x xy y?；蛘呋蛘呷稳∪稳,yx,yA A，xyxy，假設(shè)假設(shè)R R，中間過程中間過程R R。傳送傳送任取任取x,y,zx,y,zA A，假設(shè)，假設(shè)R R，R R，中間過程中間過

13、程R R。1414定理定理6.4.1 設(shè)設(shè)R是集合是集合A上的二元關(guān)系，那么：上的二元關(guān)系，那么：（1R是自反的是自反的IAR；（2R是反自反的是反自反的RIA；（3R是對(duì)稱的是對(duì)稱的RR-1；（4R是反對(duì)稱的是反對(duì)稱的RR-1IA；（5R是傳遞的是傳遞的RR R。6.4.2 6.4.2 關(guān)系性質(zhì)的判斷定理關(guān)系性質(zhì)的判斷定理1515證明證明4 4）“”設(shè)設(shè)R R是反對(duì)稱的。是反對(duì)稱的。對(duì)任意對(duì)任意RR-1RR-1，那么，那么RR且且R-1R-1，即：即： R R且且RR由于由于R R是反對(duì)稱的，那么是反對(duì)稱的，那么 a ab b 所以，所以，IAIA，即，即 RR-1 RR-1IAIA。“”設(shè)

14、設(shè)RR-1RR-1IAIA。 對(duì)任意對(duì)任意a,bAa,bA，假設(shè)，假設(shè)RR且且RR，則有：，則有：RR且且R-1R-1，即：，即：RR-1RR-1。又因又因RR-1RR-1IAIA，所以，所以，IAIA，即，即a ab b。即即R R是反對(duì)稱的。是反對(duì)稱的。1616“”設(shè)設(shè)R R是傳遞的。是傳遞的。 對(duì)任意對(duì)任意RRR R，根據(jù)，根據(jù)“”的定義，的定義，必存在必存在bAbA，使得，使得RR且且RR，由由R R的傳遞性，有：的傳遞性，有：RR。所以，。所以，R RR RR R?！啊痹O(shè)設(shè)R RR RR R。 對(duì)任意對(duì)任意a,b,cAa,b,cA，假設(shè)，假設(shè)RR并且并且RR，則有：則有：RRR R，

15、因因 R RR RR R，所以，所以，RR，即即R R是傳遞的。是傳遞的。證明證明5 5）1717定理定理6.4.2 6.4.2 設(shè)設(shè)R,SR,S是定義在是定義在A A上的二元關(guān)系，那么：上的二元關(guān)系，那么：(1)(1)若若R,SR,S是自反的，則是自反的，則R-1,RS,RS,RR-1,RS,RS,RS S也是自也是自反的；反的；(2)(2)若若R,SR,S是反自反的，則是反自反的，則R-1,RS,RSR-1,RS,RS也是反自也是反自反的。反的。(3)(3)若若R,SR,S是對(duì)稱的，則是對(duì)稱的，則R-1,RS,RSR-1,RS,RS也是對(duì)稱的。也是對(duì)稱的。(4)(4)若若R,SR,S是反對(duì)

16、稱的，則是反對(duì)稱的，則R-1,RSR-1,RS也是反對(duì)稱的。也是反對(duì)稱的。(5)(5)若若R,SR,S是傳遞的，則是傳遞的，則R-1,RSR-1,RS也是傳遞的。也是傳遞的。6.4.3 6.4.3 關(guān)系性質(zhì)的保守性關(guān)系性質(zhì)的保守性留意：留意：（1 1逆運(yùn)算與交運(yùn)算具有較好的保守性；逆運(yùn)算與交運(yùn)算具有較好的保守性；（2 2并運(yùn)算、差運(yùn)算和復(fù)合運(yùn)算的保守性較差。并運(yùn)算、差運(yùn)算和復(fù)合運(yùn)算的保守性較差。1818例例 試舉例說明試舉例說明: :（1 1R R和和S S是反自反、反對(duì)稱和傳遞的，但是，是反自反、反對(duì)稱和傳遞的，但是，RoSRoS不一定具備反自反性，反對(duì)稱性；不一定具備反自反性，反對(duì)稱性；R

17、SRS不一定具有不一定具有反對(duì)稱性和傳遞性；反對(duì)稱性和傳遞性；（2 2R R和和S S是自反、對(duì)稱和傳遞的，但是是自反、對(duì)稱和傳遞的，但是RoSRoS不一定不一定是對(duì)稱和傳遞的，是對(duì)稱和傳遞的，R-SR-S不一定是自反和傳遞的。不一定是自反和傳遞的。1919解續(xù)）解續(xù)）那么那么 RoS=, RoS=,， 不具備反自反性和反對(duì)稱性；不具備反自反性和反對(duì)稱性；RS=,RS=,， 不具備傳遞性和反對(duì)稱性；不具備傳遞性和反對(duì)稱性；（2 2） “ “不的例：設(shè)不的例：設(shè)A=1,2,3, AA=1,2,3, A上關(guān)系上關(guān)系 R=, , R=, , S=, S=,顯然顯然R,SR,S都是自反的、對(duì)稱的、傳遞

18、的。此時(shí)，都是自反的、對(duì)稱的、傳遞的。此時(shí)，RoS=, RoS=, 不具備對(duì)稱性和傳遞性；不具備對(duì)稱性和傳遞性；R-S=,R-S=,不具備自反性和傳遞性；不具備自反性和傳遞性；20201. 1. 閉包的定義閉包的定義定義定義6.5.1 設(shè)設(shè)R是定義在是定義在A上的關(guān)系，若存在上的關(guān)系，若存在A上的另一上的另一個(gè)關(guān)系個(gè)關(guān)系R，滿足：，滿足：（1R是自反的是自反的(對(duì)稱的、或傳遞的對(duì)稱的、或傳遞的)；（2對(duì)任何自反的對(duì)任何自反的(對(duì)稱的、或傳遞的對(duì)稱的、或傳遞的)關(guān)系關(guān)系R，如果，如果R R，就有，就有R R，則稱為，則稱為R的自反閉包的自反閉包(對(duì)稱閉對(duì)稱閉包、或傳遞閉包包、或傳遞閉包)，分別記

19、為，分別記為r(R) (s(R)或或t(R)。 從定義可以看出，關(guān)系的閉包是增加最少元素，使從定義可以看出，關(guān)系的閉包是增加最少元素，使其具備所需性質(zhì)的擴(kuò)充。其具備所需性質(zhì)的擴(kuò)充。6.5 6.5 關(guān)系的閉包運(yùn)算關(guān)系的閉包運(yùn)算21212. 2. 閉包的簡單性質(zhì)閉包的簡單性質(zhì)關(guān)系R有自反性 r(R) = R關(guān)系R有對(duì)稱性 S(R) = R關(guān)系R有傳遞性 t(R) = R3. 3. 閉包的計(jì)算閉包的計(jì)算定理定理6.5.1 設(shè)設(shè)R是集合是集合A上的二元關(guān)系，那么：上的二元關(guān)系，那么：（1r(R)RIA。（2s(R)RR-1。Ri1i （3t(R) ，假設(shè)，假設(shè)|A|n，則，則t(R) 。Rin1i 2222例例: 設(shè)集合設(shè)集合A=1,2,3,4， A上關(guān)系上關(guān)系 R=, （1畫出畫出R的關(guān)系圖；的關(guān)系圖；（2求出求出r(R),s(R),t(R), 并畫出其相應(yīng)的關(guān)系圖。并畫出其相應(yīng)的關(guān)系圖。解解:（1R的關(guān)系圖見下圖；的關(guān)系圖見下圖；2 24 41 13 32323（續(xù)）（續(xù)）（2 2）r(R)=,r(R)=,；s(R)