(第10講)二元關(guān)系

1、C CS S| |S SWWU US ST TXDCXDC1 14.1.4 4.1.4 關(guān)系的性質(zhì)關(guān)系的性質(zhì) 一、自反性和反自反性一、自反性和反自反性定義定義 設(shè)設(shè)A是一個(gè)集合，是一個(gè)集合， R是是A上的二元關(guān)系，上的二元關(guān)系，（1）若）若 aA，都有，都有R，則稱(chēng)，則稱(chēng)R是是自反的自反的，或稱(chēng)，或稱(chēng)R具有自反性。具有自反性。（2）若）若 aA，都有，都有 R，則稱(chēng)，則稱(chēng)R是是反自反的反自反的，或稱(chēng)，或稱(chēng)R具有反自反性。具有反自反性。 C CS S| |S SWWU US ST TXDCXDC2 2設(shè)設(shè)A=a,b,c,dA=a,b,c,d，例例1)1) R=,R=,。因?yàn)橐驗(yàn)锳 A中每個(gè)元素中

2、每個(gè)元素x x，都有，都有RR，所以，所以R R是是自反的。自反的。R R的關(guān)系圖的關(guān)系圖1001010100100001RMR R的關(guān)系矩陣的關(guān)系矩陣C CS S| |S SWWU US ST TXDCXDC3 32)2) S=,S=,。例例 ( (續(xù)續(xù)1 1) )S S的關(guān)系圖的關(guān)系圖0101001110000010SMS S的關(guān)系矩陣的關(guān)系矩陣因?yàn)橐驗(yàn)锳 A中每個(gè)元素中每個(gè)元素x x，都有，都有 S S，所以，所以S S是反自反的。是反自反的。C CS S| |S SWWU US ST TXDCXDC4 43)3) T=,T=,。例例 ( (續(xù)續(xù)2 2) )因?yàn)橐驗(yàn)锳 A中有元素中有元素

3、b b，使，使 T T，所以，所以T T不是不是自反的；因?yàn)樽苑吹模灰驗(yàn)锳 A中有元素中有元素a a，使，使TT，所，所以以T T不是反自反的。不是反自反的。T T的關(guān)系圖的關(guān)系圖1110000110100010TMT T的關(guān)系矩陣的關(guān)系矩陣C CS S| |S SWWU US ST TXDCXDC5 5有關(guān)說(shuō)明：有關(guān)說(shuō)明：（1）注意定義中注意定義中“任意任意”，“都都”這兩個(gè)詞。這兩個(gè)詞。（2）如果如果R不是自反的，則不是自反的，則R未必一定是反自未必一定是反自反的。一個(gè)關(guān)系可能既不是自反的，也不是反反的。一個(gè)關(guān)系可能既不是自反的，也不是反自反的。自反的。（3 3）表現(xiàn)在關(guān)系圖上：）表現(xiàn)在關(guān)

4、系圖上：關(guān)系關(guān)系R R是自反的，當(dāng)且是自反的，當(dāng)且僅當(dāng)其關(guān)系圖中每個(gè)結(jié)點(diǎn)都有環(huán)；關(guān)系僅當(dāng)其關(guān)系圖中每個(gè)結(jié)點(diǎn)都有環(huán)；關(guān)系R R是反自是反自反的，當(dāng)且僅當(dāng)其關(guān)系圖中每個(gè)結(jié)點(diǎn)都無(wú)環(huán)。反的，當(dāng)且僅當(dāng)其關(guān)系圖中每個(gè)結(jié)點(diǎn)都無(wú)環(huán)。（4 4）表現(xiàn)在關(guān)系矩陣上：）表現(xiàn)在關(guān)系矩陣上：關(guān)系關(guān)系R R是自反的，當(dāng)是自反的，當(dāng)且僅當(dāng)其關(guān)系矩陣的主對(duì)角線(xiàn)上全為且僅當(dāng)其關(guān)系矩陣的主對(duì)角線(xiàn)上全為1 1；關(guān)系；關(guān)系R R是反自反的當(dāng)且僅當(dāng)其關(guān)系矩陣的主對(duì)角線(xiàn)上是反自反的當(dāng)且僅當(dāng)其關(guān)系矩陣的主對(duì)角線(xiàn)上全為全為0 0。 C CS S| |S SWWU US ST TXDCXDC6 6例例1 R是是Z上的整除關(guān)系，則上的整除關(guān)系，則

5、R具有自反性。具有自反性。證明：證明： xN，x能整除能整除x，R， R具有自反性。具有自反性。例例2 R是是Z上的同余關(guān)系，則上的同余關(guān)系，則R具有自反性。具有自反性。證明：證明： xZ，(x-x)/k=0Z, x與與x同余，同余， R，R具有自反性。具有自反性。其它其它，關(guān)系，倍數(shù)關(guān)系，人與人的同名關(guān)關(guān)系，倍數(shù)關(guān)系，人與人的同名關(guān)系、集合的系、集合的 關(guān)系，均是關(guān)系，均是自反的自反的。 C CS S| |S SWWU US ST TXDCXDC7 7例例3 Z上的大于關(guān)系是反自反關(guān)系。上的大于關(guān)系是反自反關(guān)系。證明：證明： xZ，x不大于不大于x， R， N上的大于關(guān)系是上的大于關(guān)系是反自

6、反的反自反的。其他的如實(shí)數(shù)上的，關(guān)系其他的如實(shí)數(shù)上的，關(guān)系, ,人與人的父子關(guān)人與人的父子關(guān)系系, ,均是均是反自反反自反關(guān)系。關(guān)系。C CS S| |S SWWU US ST TXDCXDC8 8二、對(duì)稱(chēng)性二、對(duì)稱(chēng)性定義定義 設(shè)設(shè)R是是A上的關(guān)系，上的關(guān)系， a,bA，如果，如果R，則必有，則必有R，則稱(chēng)，則稱(chēng)R是是對(duì)稱(chēng)的對(duì)稱(chēng)的，或稱(chēng)或稱(chēng)R具有對(duì)稱(chēng)性。具有對(duì)稱(chēng)性。例如，例如，A=1，2，3，4 R1，則，則R1是對(duì)稱(chēng)的；是對(duì)稱(chēng)的； R2，則，則R2也是對(duì)稱(chēng)的；也是對(duì)稱(chēng)的； R3， 則則R3不是對(duì)稱(chēng)的不是對(duì)稱(chēng)的，因，因R，而，而 R。 C CS S| |S SWWU US ST TXDCXDC

7、9 9有關(guān)說(shuō)明有關(guān)說(shuō)明: 由對(duì)稱(chēng)性的定義可知，如果由對(duì)稱(chēng)性的定義可知，如果R是是對(duì)稱(chēng)對(duì)稱(chēng)的，的，則當(dāng)則當(dāng) R時(shí)，時(shí)， 必有必有 R。 對(duì)于像對(duì)于像，這種序偶是否屬于這種序偶是否屬于R R對(duì)對(duì)R R的對(duì)稱(chēng)性沒(méi)有影響。的對(duì)稱(chēng)性沒(méi)有影響。 R R1 1的關(guān)系圖的關(guān)系圖1101000100RMR R1 1的關(guān)系矩陣的關(guān)系矩陣是對(duì)稱(chēng)的是對(duì)稱(chēng)的例例 設(shè)設(shè)A=A=a,b,ca,b,c ， 1)1) R R1 1=,=,C CS S| |S SWWU US ST TXDCXDC例例 R R是是Z Z上的模上的模5 5同余關(guān)系同余關(guān)系, ,則則R R是對(duì)稱(chēng)關(guān)系是對(duì)稱(chēng)關(guān)系 ；證明：證明：R|x,yZ，(x-y)/

8、5Z x,yZ，如果，如果R， 則則(x-y)/5 Z 所以，所以， (y-x)/5 - (x-y)/5 Z R，故，故R具有對(duì)稱(chēng)性。具有對(duì)稱(chēng)性。 1010C CS S| |S SWWU US ST TXDCXDC11113)3) R R3 3=,=,例例 ( (續(xù)續(xù)1 1) )4)4) R R4 4=,=,既不是對(duì)稱(chēng)的，也不是反對(duì)稱(chēng)的既不是對(duì)稱(chēng)的，也不是反對(duì)稱(chēng)的R R3 3的關(guān)系圖的關(guān)系圖3111000100RMR R3 3的關(guān)系矩陣的關(guān)系矩陣既是對(duì)稱(chēng)的，也是反對(duì)稱(chēng)的既是對(duì)稱(chēng)的，也是反對(duì)稱(chēng)的R R3 3的關(guān)系圖的關(guān)系圖4100000001RMR R3 3的關(guān)系矩陣的關(guān)系矩陣C CS S| |

9、S SWWU US ST TXDCXDC1212對(duì)稱(chēng)關(guān)系的關(guān)系矩陣和關(guān)系圖的特點(diǎn)對(duì)稱(chēng)關(guān)系的關(guān)系矩陣和關(guān)系圖的特點(diǎn)1. 對(duì)稱(chēng)關(guān)系的關(guān)系矩陣是對(duì)稱(chēng)關(guān)系的關(guān)系矩陣是對(duì)稱(chēng)矩陣對(duì)稱(chēng)矩陣，即，即rijrji；因?yàn)橐驗(yàn)?rij1 R R rji1一切一切i,j，rijrji=1 2. 對(duì)稱(chēng)關(guān)系的對(duì)稱(chēng)關(guān)系的關(guān)系圖的特點(diǎn)關(guān)系圖的特點(diǎn)是任何兩個(gè)不同的結(jié)點(diǎn)是任何兩個(gè)不同的結(jié)點(diǎn)之間，或者是一來(lái)一回兩條邊（弧），或者是沒(méi)有之間，或者是一來(lái)一回兩條邊（?。蛘呤菦](méi)有邊（?。?。而邊（?。?。而是否有自回路，對(duì)對(duì)稱(chēng)性沒(méi)有影響。是否有自回路，對(duì)對(duì)稱(chēng)性沒(méi)有影響。顯然顯然, ,全域關(guān)系全域關(guān)系U UA A，空關(guān)系，空關(guān)系，恒等關(guān)系

10、，恒等關(guān)系 A A，都是對(duì)，都是對(duì)稱(chēng)的。稱(chēng)的。C CS S| |S SWWU US ST TXDCXDC1313三、反對(duì)稱(chēng)性三、反對(duì)稱(chēng)性定義定義 如果如果R是是A上的關(guān)系，上的關(guān)系， a,bR如果如果R且且R，則必有，則必有ab，稱(chēng)，稱(chēng)R是是反反對(duì)稱(chēng)的對(duì)稱(chēng)的。 有關(guān)說(shuō)明有關(guān)說(shuō)明:該定義的等價(jià)說(shuō)法是：該定義的等價(jià)說(shuō)法是： a,bA，如，如ab，R，則必有，則必有 R。即兩個(gè)不同點(diǎn)結(jié)點(diǎn)間不允許有兩條邊（?。?。即兩個(gè)不同點(diǎn)結(jié)點(diǎn)間不允許有兩條邊（?。?。該定義的否命題說(shuō)法并不成立。即該定義的否命題說(shuō)法并不成立。即“ab， R，則，則R”并不成立，即反對(duì)稱(chēng)關(guān)并不成立，即反對(duì)稱(chēng)關(guān)系的關(guān)系圖允許兩個(gè)不同點(diǎn)間沒(méi)

11、有弧。系的關(guān)系圖允許兩個(gè)不同點(diǎn)間沒(méi)有弧。 C CS S| |S SWWU US ST TXDCXDC1414例例2 2 R R是是N N上的整除關(guān)系上的整除關(guān)系, ,即即 R R|x,yN,y/xN,|x,yN,y/xN,顯然，如果顯然，如果x x能整除能整除y y，且，且xyxy，則則y y不能整除不能整除x x。所以所以R R是反對(duì)稱(chēng)是反對(duì)稱(chēng)的。的。 例例1 1 設(shè)設(shè)A=A=a,b,ca,b,c ，R R2 2=, R R2 2的關(guān)系圖的關(guān)系圖2101000000RMR R2 2的關(guān)系矩陣的關(guān)系矩陣是反對(duì)稱(chēng)的是反對(duì)稱(chēng)的C CS S| |S SWWU US ST TXDCXDC1515例例3

12、 A是某集合，是某集合，R是是(A)上的包含關(guān)系。上的包含關(guān)系。因因u、v(A)，如，如uv，且，且u v，則必有，則必有v u,所以，包含關(guān)系所以，包含關(guān)系R是是反對(duì)稱(chēng)的反對(duì)稱(chēng)的。換一種理解，如果換一種理解，如果u,v(A)，有，有u v，v u，則必，則必有有uv。集合集合A A上的包含關(guān)系上的包含關(guān)系R R是是反對(duì)稱(chēng)的反對(duì)稱(chēng)的。其它例如其它例如、 關(guān)系，人與人的父子關(guān)系，關(guān)系，人與人的父子關(guān)系，領(lǐng)導(dǎo)領(lǐng)導(dǎo)與被領(lǐng)導(dǎo)關(guān)系均是與被領(lǐng)導(dǎo)關(guān)系均是反對(duì)稱(chēng)反對(duì)稱(chēng)的的。 C CS S| |S SWWU US ST TXDCXDC1616反對(duì)稱(chēng)關(guān)系的關(guān)系矩陣和關(guān)系圖特點(diǎn)反對(duì)稱(chēng)關(guān)系的關(guān)系矩陣和關(guān)系圖特點(diǎn)關(guān)系矩

13、陣：關(guān)系矩陣：R是反對(duì)稱(chēng)的，則其關(guān)系矩陣如果在是反對(duì)稱(chēng)的，則其關(guān)系矩陣如果在非對(duì)角元上非對(duì)角元上rij1，則在其對(duì)稱(chēng)位置上，則在其對(duì)稱(chēng)位置上rji0，即，即rij和和rji(ij)這兩個(gè)數(shù)至多一個(gè)是這兩個(gè)數(shù)至多一個(gè)是1，但允許兩個(gè)，但允許兩個(gè)均為均為0。關(guān)系圖關(guān)系圖：任何兩個(gè)不同的結(jié)點(diǎn)之間，至多有一：任何兩個(gè)不同的結(jié)點(diǎn)之間，至多有一條邊（弧），或者沒(méi)有邊（弧）。條邊（?。?，或者沒(méi)有邊（弧）。 C CS S| |S SWWU US ST TXDCXDC1717四、傳遞性四、傳遞性定義定義 設(shè)設(shè)R是是A上的關(guān)系，上的關(guān)系， a,b,cA，如果，如果R，R，則必有，則必有R。則稱(chēng)。則稱(chēng)R是是傳遞的傳

14、遞的，或稱(chēng)，或稱(chēng)R具有傳遞性。具有傳遞性。 設(shè)設(shè)A=A=a,b,c,da,b,c,d ， 1)1) R R1 1=,=, 是傳遞的是傳遞的R R1 1的關(guān)系圖的關(guān)系圖11110001000000000RMR R1 1的關(guān)系矩陣的關(guān)系矩陣C CS S| |S SWWU US ST TXDCXDC1818設(shè)設(shè)A=a,b,c,dA=a,b,c,d， 例（續(xù)）例（續(xù)）2)2) R R2 2= 是傳遞的是傳遞的R R2 2的關(guān)系圖的關(guān)系圖20100000000000000RMR R2 2的關(guān)系矩陣的關(guān)系矩陣C CS S| |S SWWU US ST TXDCXDC19193)3) R R3 3=,=,例

15、例 ( (續(xù)續(xù)) )4)4) R R4 4=,=,不是傳遞的不是傳遞的R R3 3的關(guān)系圖的關(guān)系圖31100001000000000RMR R3 3的關(guān)系矩陣的關(guān)系矩陣不是傳遞的不是傳遞的R R3 3的關(guān)系圖的關(guān)系圖40110001000010000RMR R3 3的關(guān)系矩陣的關(guān)系矩陣C CS S| |S SWWU US ST TXDCXDC20201)1) 表現(xiàn)在關(guān)系圖上：表現(xiàn)在關(guān)系圖上：關(guān)系關(guān)系R R是傳遞的當(dāng)且僅當(dāng)其是傳遞的當(dāng)且僅當(dāng)其關(guān)系圖中，任何三個(gè)結(jié)點(diǎn)關(guān)系圖中，任何三個(gè)結(jié)點(diǎn)x,y,zx,y,z（可以相同）（可以相同）之間，若從之間，若從x x到到y(tǒng) y有一條邊存在，從有一條邊存在，從

16、y y到到z z有一有一條邊存在，則從條邊存在，則從x x到到z z一定有一條邊存在。一定有一條邊存在。2)2) 表現(xiàn)在關(guān)系矩陣上：表現(xiàn)在關(guān)系矩陣上：關(guān)系關(guān)系R R是傳遞的當(dāng)且僅當(dāng)是傳遞的當(dāng)且僅當(dāng)其關(guān)系矩陣中，對(duì)任意其關(guān)系矩陣中，對(duì)任意i,j,k1,2,3,i,j,k1,2,3,n,n，若若r rijij=1=1且且r rjkjk=1=1，必有，必有r rikik=1=1。結(jié)論結(jié)論C CS S| |S SWWU US ST TXDCXDC2121例例 整除關(guān)系整除關(guān)系DN是是N上的傳遞關(guān)系。上的傳遞關(guān)系。證明：證明： x,y,zN，如，如DN，DN，即即x能整除能整除y，且，且y能整除能整除z

17、，則必有，則必有x能整除能整除z，即即DN，所以整除關(guān)系具有傳遞性。，所以整除關(guān)系具有傳遞性。例例 (A)上的包含關(guān)系上的包含關(guān)系 ，具有傳遞性。，具有傳遞性。因?yàn)槿粢驗(yàn)槿魎 v，v w，則必有，則必有u w。例例 實(shí)數(shù)集上的實(shí)數(shù)集上的關(guān)系也具有傳遞性。關(guān)系也具有傳遞性。因?yàn)槿粢驗(yàn)槿魓y，yz，必有，必有xz。其它如全域關(guān)系其它如全域關(guān)系UA，空關(guān)系，空關(guān)系，恒關(guān)系，恒關(guān)系 A均是均是傳遞的傳遞的。 C CS S| |S SWWU US ST TXDCXDC關(guān)系性質(zhì)的邏輯表示關(guān)系性質(zhì)的邏輯表示設(shè)設(shè)R R是集合是集合A A上的二元關(guān)系，上的二元關(guān)系，1)1) R R是自反的是自反的)Rx, x(

18、)Ax)(x( 是永真的是永真的2)2) R R不不是自反的是自反的)Rx, x()Ax)(x( 是永真的是永真的3)3) R R是是反反自反的自反的)Rx, x()Ax)(x( 是永真的是永真的4)4) R R不不是是反反自反的自反的)Rx, x()Ax)(x( 是永真的是永真的5)5) R R是是對(duì)稱(chēng)對(duì)稱(chēng)的的)Rx, y()Ry, x)(y)(x( 是永真的是永真的6)6) R R不不是是對(duì)稱(chēng)對(duì)稱(chēng)的的)Rx, y()Ry, x)(y)(x( 是永真的是永真的C CS S| |S SWWU US ST TXDCXDC2323關(guān)系性質(zhì)的邏輯表示關(guān)系性質(zhì)的邏輯表示( (續(xù)續(xù)) )7)7) R R

19、是是反反對(duì)稱(chēng)對(duì)稱(chēng)的的9)9) R R是是傳遞傳遞的的)Rz, x()Rz, y()Ry, x)(z)(y)(x( 是永真的是永真的10)10)R R不不是是傳遞傳遞的的)Rz, x()Rz, y()Ry, x)(z)(y)(x( 是永真的是永真的)Rx, y()Ry, x()yx)(y)(x()yx()Rx, y()Ry, x)(y)(x( 是永真的是永真的8)8) R R不不是是反對(duì)稱(chēng)反對(duì)稱(chēng)的的)Rx, y()Ry, x()yx)(y)(x( 是永真的是永真的C CS S| |S SWWU US ST TXDCXDC2424設(shè)設(shè)A A1,2,3,1,2,3,試判斷如下圖所示試判斷如下圖所示A A上關(guān)系的性質(zhì)：上關(guān)系的性質(zhì)：1)1) 圖圖a)a)的關(guān)系是自反的、的關(guān)系是自反的、對(duì)稱(chēng)的、反對(duì)稱(chēng)的、傳對(duì)稱(chēng)的、反對(duì)稱(chēng)的、傳遞的關(guān)系；遞的關(guān)系；2)2) 圖圖b)b)的關(guān)系是具備反自的關(guān)系是具備反自反的、對(duì)稱(chēng)的、反對(duì)稱(chēng)反的、對(duì)稱(chēng)的、反對(duì)稱(chēng)的、傳遞的關(guān)系；的、傳遞的關(guān)系；圖圖c)c)的關(guān)系是具備對(duì)