離散數(shù)學(xué)第四章二元關(guān)系

1、第四章 二元關(guān)系第四章 二元關(guān)系本章討論的關(guān)系（主要是二元關(guān)系），它仍然是一種集合，但它是比前一章更為復(fù)雜的集合。關(guān)系是笛卡爾乘積的子集，它的元素是有序二元組的形式，這些有序二元組中的兩個(gè)元素來自于兩個(gè)不同或者相同的集合。因此，關(guān)系是建立在其它集合基礎(chǔ)之上的集合。關(guān)系中的有序二元組反映了不同集合中元素與元素之間的關(guān)系，或者同一集合中元素之間的關(guān)系。本章首先討論關(guān)系的基本表達(dá)形式，然后給出關(guān)系的運(yùn)算，最后討論幾種常用的關(guān)系。 回顧主要內(nèi)容關(guān)系的基本概念關(guān)系的性質(zhì)關(guān)系的表示關(guān)系的運(yùn)算合成關(guān)系的關(guān)系圖、關(guān)系矩陣特殊關(guān)系：等價(jià)關(guān)系和劃分，相容關(guān)系和覆蓋，偏序關(guān)系和哈斯圖等。 4.1關(guān)系的基本概念定義：

2、設(shè) 且 A1,A2,An為n個(gè)任意集合，(a) 稱R為A1,A2,An間的n元關(guān)系；(b) 若n=2，則稱R為A1到A2的二元關(guān)系；(c) 若 ，則稱R為空關(guān)系；若 ，則稱R為全關(guān)系；(d) 若A1=A2=An =A，則稱R為A上的n元關(guān)系。一、關(guān)系的定義一、關(guān)系的定義例：令則稱R1是N上的一元關(guān)系，R2是N上的二元關(guān)系，R3是N上的三元關(guān)系。如無特殊指定，“關(guān)系”概指二元關(guān)系。若序偶 屬于R，則記作 或 ，否則，記作 或 。一、關(guān)系的定義例：設(shè)集合A=a,b,B=2,5,8則令則 均是由A到B的關(guān)系。同理，則 是由B到A的關(guān)系。同理，則 是由B到B的關(guān)系。一、關(guān)系的定義例：設(shè)集合A=2,3,

3、5,9，試給出集合A上的小于或等于關(guān)系，大于或等于關(guān)系。解：令集合A上的小于或等于關(guān)系為R1，大于或等于關(guān)系為R2，根據(jù)定義有： 二、關(guān)系的相等定義：設(shè)R1為A1,A2,An間的n元關(guān)系，R2為B1, B2,Bm間的m元關(guān)系，如果：（1）n=m （2）若 1in，則Ai=Bi（3）把R1和R2作為集合看，R1=R2。則稱n元關(guān)系R1和m元關(guān)系R2相等，記作R1=R2二、關(guān)系的相等例：設(shè)R1為從Z到I+的二元關(guān)系，R2和R3都是I上的二元關(guān)系從集合的觀點(diǎn)來看，R1=R2=R3。但是就二元關(guān)系來說，R2=R3，不等于R1。三、關(guān)系的定義域和值域關(guān)系R(從A到B的關(guān)系)的定義域(簡(jiǎn)稱為域)定義為：關(guān)

4、系R的值域定義為：顯然，有例：設(shè)A=2,3,5,B=2,6,7,8,9，由A到B的關(guān)系R定義為：當(dāng)且僅當(dāng)a整除b時(shí)，有aRb?？傻?D(R)=2,3R(R)=2,6,8,9AB235268974.2關(guān)系的表示定義：設(shè)A和B為任意的非空有限集，R為任意一個(gè)從A到B的二元關(guān)系。以 中的每個(gè)元素為結(jié)點(diǎn)對(duì)每個(gè) 皆畫一條從x到y(tǒng)的有向邊，這樣得到的一個(gè)圖稱為關(guān)系R的關(guān)系圖。 一、關(guān)系圖例：A=1,2,4; B=3,5,6;關(guān)系R=,A124B356一、關(guān)系圖例：設(shè)A=2,3,4,5,6,B=6,7,8,12，從A到B的二元關(guān)系R為 ，畫出其關(guān)系圖。解：先求出R一、關(guān)系圖 對(duì)稱關(guān)系 反對(duì)稱關(guān)系二、關(guān)系矩陣

5、定義： 給定兩個(gè)有限集合X=x1,x2,xm和Y= y1,y2,yn，R是從X到Y(jié)的二元關(guān)系，如果有： 則稱 是R的關(guān)系矩陣，記作MR。 例：設(shè)A=1,2,3,4,R為定義在A上的二元關(guān)系，R=,，寫出關(guān)系矩陣。二、關(guān)系矩陣?yán)涸O(shè)A=1,2,3,B=a,b,c, R是A到B的二元關(guān)系，并且 ，試畫出R的關(guān)系圖，給出關(guān)系矩陣。二、關(guān)系矩陣如果關(guān)系矩陣主對(duì)角線上的記入值全為1，則R是自反的； 如果主對(duì)角線上的記入值全為0，則R是反自反的； 如果矩陣關(guān)于主對(duì)角線是對(duì)稱的，則R是對(duì)稱的；如果矩陣關(guān)于主對(duì)角線是反對(duì)稱的，(亦即rij=1時(shí)則一定有rji=0),則R是反對(duì)稱的；如果對(duì)于任意的i,j,k,

6、rij=1并且rjk=1時(shí)一定有rik=1 ，則R是可傳遞的； 如果存在i,j,k, rij=1并且rjk=1時(shí)，有rik 不等于1 ，則R是不可傳遞的；4.3關(guān)系的性質(zhì)定義：設(shè)R為A上的二元關(guān)系(1)若對(duì)每個(gè) ，皆有 ，則稱R為自反的。用式子來表述即是： R是自反的 (2)若對(duì)每個(gè) ，皆有 ，則稱R為反自反的。用式子來表述即是： R是反自反的 關(guān)系的性質(zhì)(3) 對(duì)任意的 ，若 ，則 ，就稱R為對(duì)稱的。用式子來表述即是： R是對(duì)稱的 (4) 對(duì)任意的 ，若 且 ， 則x=y，就稱R為反對(duì)稱的。用式子來表述即是： R是反對(duì)稱的 關(guān)系的性質(zhì)(5) 對(duì)任意的 ，若 且 ， 則 ，就稱R為可傳遞的。用

7、式子來表述即是： R是可傳遞的 (6) 存在 ，并且 而 ， 就稱R為不可傳遞的。用式子來表述即是： R是不可傳遞的 關(guān)系的性質(zhì)例1：考慮自然數(shù)集合上的普通相等關(guān)系“=”，大于關(guān)系“”和大于等于關(guān)系“ ”具有的性質(zhì)。 解：(1) “=”關(guān)系是自反的、對(duì)稱的、反對(duì)稱的、可傳遞的；(2)“”關(guān)系是反自反的、反對(duì)稱的、可傳遞的；(3)“ ”關(guān)系是自反的、反對(duì)稱的、可傳遞的。例2：空集上的二元關(guān)系的性質(zhì)。自反的、對(duì)稱的、反對(duì)稱的、反自反的、可傳遞的 區(qū)分概念：空關(guān)系vs空集上的關(guān)系空關(guān)系：對(duì)于任何集合A, 稱空集為A上的空關(guān)系.性質(zhì)：若A非空，空關(guān)系是反自反的，對(duì)稱的，反對(duì)稱的，可傳遞的；若A是空集，

8、該空關(guān)系是自反的，反自反的，對(duì)稱的，反對(duì)稱的，可傳遞的空集上的關(guān)系：自反的，反自反的，對(duì)稱的，反對(duì)稱的， 可傳遞的。在空集上可定義任意元關(guān)系。集合的壓縮和開拓定義：設(shè)R為集合A上的二元關(guān)系且SA ，則稱S上的二元關(guān)系R(SS)為R在S上的壓縮，記為R|S， 并稱R為R|S在A上的開拓。 定理：設(shè)R為A的二元關(guān)系且 ，那么：(1)若R是自反的，則 也是自反的； (2)若R是反自反的，則 也是反自反的； (3)若R是對(duì)稱的，則 也是對(duì)稱的； (4)若R是反對(duì)稱的，則 也是反對(duì)稱的； (5)若R是可傳遞的，則 也是可傳遞的； 4.4關(guān)系的運(yùn)算注意：由于關(guān)系也是特殊的集合，因此集合的運(yùn)算也適用于關(guān)系中

9、。設(shè)R1和R2是從A到B的二元關(guān)系，那么R1R2， R1R2 ， R1-R2， R1R2也是從A到B的二元關(guān)系，它們分別被稱為二元關(guān)系R1和R2的交、并、差分和對(duì)稱差分。4.4關(guān)系的運(yùn)算例：設(shè)集合A=a,b,c，B=d,e，定義A到B的二元關(guān)系R1=,R2=,則4.4關(guān)系的運(yùn)算定義：設(shè)R是從X到Y(jié)的關(guān)系，S是從Y到Z的關(guān)系，于是可用RS表示從X到Z的關(guān)系，通常稱它是R和S的合成關(guān)系，用式子表示即是： 一、關(guān)系的合成例： 給定集合X=1,2,3,4，Y=2,3,4和Z=1,2,3。設(shè)R是從X到Y(jié)的關(guān)系，并且S是從Y到Z的關(guān)系，并且R和S給定成： 試求R和S的合成關(guān)系，并畫出合成關(guān)系圖給出合成關(guān)系

10、的關(guān)系矩陣。 一、關(guān)系的合成解：找出所有這樣的偶對(duì) x, z 對(duì)于某一個(gè)y來說，能有x+y=6和y-z=1，由上述的偶對(duì)就可構(gòu)成從X到Z的關(guān)系RS 。 一、關(guān)系的合成定義布爾運(yùn)算：0+0=0，1+0=0+1=1+1=111=1， 01= 10= 00=0對(duì)兩個(gè)關(guān)系矩陣求其合成時(shí)，其運(yùn)算法則與一般矩陣的乘法是相同的，但其中的加法運(yùn)算和乘法運(yùn)算應(yīng)改為布爾加和布爾乘。一、關(guān)系的合成注意：設(shè)R是從集合X到集合Y的關(guān)系，S是從集合Y到集合Z的關(guān)系，于是有：如果R關(guān)系的值域與S關(guān)系的定義域的交集是個(gè)空集，則合成關(guān)系RS也是個(gè)空關(guān)系；若至少有一個(gè)序偶 x, yR ，其中笫二個(gè)成員是S中的某一個(gè)序偶的笫一個(gè)成

11、員，則合成關(guān)系就是個(gè)非空關(guān)系。對(duì)于合成關(guān)系RS來說，它的定義域是集合X的子集，而它的值域則是Z的子集，事實(shí)上，它的定義域是關(guān)系R的定義域的子集，它的值域是關(guān)系S的值域的子集。 一、關(guān)系的合成定理：給定集合X,Y,Z和W，設(shè)R1是從 X到Y(jié)的關(guān)系，R2和R3是Y到Z的關(guān)系，R4是從Z到W的關(guān)系，于是有：一、關(guān)系的合成證明：當(dāng)且僅當(dāng)存在某一個(gè)yY，能使 R1和 R2 R3 ，才有 R1 (R2 R3)，而 對(duì)任意的x,zR1o(R2R3)y(x,yR1y,zR2R3)y(x,yR1(y,zR2 y,zR3) y(x,yR1y,zR2) (x,yR1 y,zR3) y(x,yR1y,zR2) y(x

12、,yR1y,zR3) x,zR1oR2 x,zR1oR3 x,z（R1oR2）（R1oR3） 得證一、關(guān)系的合成證明：當(dāng)且僅當(dāng)存在某一個(gè)yY ，能使 R1和 R2 R3 ，才有 R1 (R2 R3) ，而 對(duì)以上證明過程(a)式使用的是存在量詞對(duì)滿足分配律對(duì)(b)存在量詞對(duì)不滿足分配律，但它滿足蘊(yùn)涵式x(A(x) B(x)xA(x) x B(x)這里應(yīng)注意是一、關(guān)系的合成合成運(yùn)算是對(duì)關(guān)系的二元運(yùn)算，使用這種運(yùn)算，能夠由兩個(gè)關(guān)系生成一個(gè)新的關(guān)系，對(duì)于這個(gè)新的關(guān)系又可進(jìn)行合成運(yùn)算，從而生成其它關(guān)系。 定理：設(shè)R1是從X到Y(jié)的關(guān)系，R2是從Y到Z的關(guān)系，R3是從Z到W的關(guān)系，于是有一、關(guān)系的合成一、

13、關(guān)系的合成例：給定關(guān)系R和S，并且則關(guān)系的冪定義：如果R1是從X1到X2的關(guān)系，R2是從X2到的X3關(guān)系，Rn是從Xn到Xn+1的關(guān)系，則無括號(hào)表達(dá)式 表達(dá)了從X1到Xn+1的關(guān)系。當(dāng)X1=X2=Xn+1和R1=R2 =Rn時(shí)，也就是說當(dāng)集合X中的所有Ri都是同樣的關(guān)系時(shí)，X中的合成關(guān)系 可表達(dá)成Rn，并稱作關(guān)系R的冪。 定義：給定集合X，R是X中的二元關(guān)系。設(shè) ，于是R的n次冪Rn可定義成 (a) R0是集合X中的恒等關(guān)系IX，亦即(b) 關(guān)系的冪定理：給定集合X，R是X中的二元關(guān)系。設(shè) ，于是可有 例：給定集合X=a,b,c，R1,R2,R3,R4是X中的關(guān)系，并給定給出這些關(guān)系的各次冪關(guān)

14、系的冪解：關(guān)系的冪定理：設(shè)X是含有n個(gè)元素的有限集合，R是X中的二元關(guān)系。于是存在這樣的s和t，能使 ， 證明：集合X中的每一個(gè)二元關(guān)系都是 的子集，X有n個(gè)元素， 有n2個(gè)元素， 有 個(gè)元素，每一個(gè)元素都是 的一個(gè)子集，也是一種二元關(guān)系，因而，在X中有 個(gè)不同的二元關(guān)系。所以，不同的二元關(guān)系R的冪不會(huì)多于個(gè) 。但是序列 中有 項(xiàng)，因此這些的方冪中至少有兩個(gè)是相等的。證畢。 二、合成關(guān)系的矩陣表達(dá)和圖解設(shè)集合X=x1,x2,xm,Y=y1,y2 ,yn,Z=z1,z2,zp, R是從X到Y(jié)的關(guān)系，S是從Y到Z的關(guān)系，MR和MS第i行第j列的元素分別是aij和bij，它們是0或者1。則合成關(guān)系

15、關(guān)系矩陣上的元素為定義布爾運(yùn)算：0+0=0，1+0=0+1=1+1=111=1， 01= 10= 00=0對(duì)兩個(gè)關(guān)系矩陣求其合成時(shí)，其運(yùn)算法則與一般矩陣的乘法是相同的，但其中的加法運(yùn)算和乘法運(yùn)算應(yīng)改為布爾加和布爾乘。二、合成關(guān)系的矩陣表達(dá)和圖解例：求合成關(guān)系 的關(guān)系矩陣二、合成關(guān)系的矩陣表達(dá)和圖解當(dāng)用 表示這些矩陣的合成矩陣二、合成關(guān)系的矩陣表達(dá)和圖解例：設(shè)集合X=0,1,2,3，R是X中的關(guān)系，并且畫出 和 的關(guān)系圖解：0231(a)0231(b)0231(c)三、關(guān)系的求逆運(yùn)算關(guān)系R的逆關(guān)系 定義如下：對(duì)于所有的 和 來說，逆關(guān)系的關(guān)系矩陣：原關(guān)系矩陣轉(zhuǎn)置逆關(guān)系的關(guān)系圖：原關(guān)系圖中顛倒弧線上箭頭的方向。區(qū)分 ：逆關(guān)系vs補(bǔ)關(guān)系 在關(guān)系圖和關(guān)系矩陣上的體現(xiàn)？三、合成關(guān)系的求逆運(yùn)算定理：設(shè)R是從集合X到Y(jié)的關(guān)系。S是從集合Y到Z的關(guān)系。于是有 證明：對(duì)于任何 ， 和 來說，如果xRy和ySz，則會(huì)有 和 ，因?yàn)檫€有 和 ，所以又有 。因此可有 。利用關(guān)系矩陣也可以理解， 的轉(zhuǎn)置和 是一樣的。三、合成關(guān)