【正文】 A B(或 A A)本身也是一個從 A到 B(或 A上 ) 的關(guān)系，稱之為完全關(guān)系。即含有全 部序偶的關(guān)系。它的矩陣中全是 1。 3. A上的 恒等關(guān)系 IA： IA?A A，且 IA ={x,x|x∈ A}稱之為 A 上的恒等關(guān)系。 例如 A={1,2,3}, 則 IA ={1,1,2,2,3,3} A上的 Φ、完全關(guān)系及 IA的關(guān)系圖及矩陣如 下： MIA = 1 0 0 0 1 0 0 0 1 3 3 1。 2。 。 3 1。 2。 。 3 1 1 1 1 1 1 1 1 1 3 3 1。 。 2。 3 0 0 0 0 0 0 0 0 0 3 3 MΦ= MA A= Φ A A IA 五 . 關(guān)系的集合運算 由于關(guān)系就是集合，所以集合的 ∩、 ∪ 、 、 ?和 ~運算對關(guān)系也適用。 例如， A是學(xué)生集合， R是 A上的同鄉(xiāng)關(guān)系， S是 A上的同姓關(guān)系，則 R∪ S：或同鄉(xiāng)或同姓關(guān)系 R∩S：既同鄉(xiāng)又同姓關(guān)系 RS ：同鄉(xiāng)而不同姓關(guān)系 R?S：同鄉(xiāng)而不同姓 ,或同姓而不同鄉(xiāng)關(guān)系 ~R：不是同鄉(xiāng)關(guān)系 , 這里 ~R=(A A)R 作業(yè) 第 109頁 ⑵、⑸ c)d) 43 關(guān)系的性質(zhì) 本節(jié)將研究關(guān)系的一些性質(zhì) ， 它們在關(guān)系的研究 中起著重要的作用 。 這是本章最重要的一節(jié) 。 本節(jié)中所討論的關(guān)系都是集合 A中的關(guān)系 。 關(guān)系的性質(zhì)主要有：自反性 、 反自反性 、 對稱 性 、 反對稱性和傳遞性 。 一 .自反性 定義 :設(shè) R是集合 A中的關(guān)系 ， 如果對于任意 x∈ A都有 x,x∈ R (xRx)， 則稱 R是 A中自反關(guān)系 。 即 R是 A中自反的 ??x(x?A?xRx) 例如在實數(shù)集合中 ,“?”是自反關(guān)系 ， 因為 ， 對任意實數(shù) x， 有 x ? x. 從關(guān)系有向圖看自反性 :每個結(jié)點都有環(huán)。 從關(guān)系矩陣看自反性：主對角線都為 1。 令 A={1,2,3}給定 A上八個關(guān)系如下： 1。 2。 。 1。 2。 。 1。 2。 。 1。 2。 。 3 3 3 3 1。 2。 。 1。 2。 。 1。 2。 。 1。 2。 。 3 3 3 3 R2 R1 R3 R4 R5 R6 R7 R8 可見這八個關(guān)系中 R R R4是自反的。 二 .反自反性 定義 ： 設(shè) R是集合 A中的關(guān)系，如果對于任 意的 x∈ A都有 x,x?R ，則稱 R為 A中的反 自反關(guān)系。即 R是 A中反自反的 ??x(x?A?x,x?R) 從關(guān)系有向圖看反自反性 :每個結(jié)點都無環(huán)。 從關(guān)系矩陣看反自反性：主對角線都為 0。 如實數(shù)的大于關(guān)系 ，父子關(guān)系是反自反的。 注意 ：一個不是自反的關(guān)系，不一定就是反 自反的，如前邊 R R7非自反 ,也非反自反。 下面 R R R均是反自反關(guān)系 。 1。 2。 。 1。 2。 。 1。 2。 。 1。 2。 。 3 3 3 3 1。 2。 。 1。 2。 。 1。 2。 。 1。 2。 。 3 3 3 3 R2 R1 R3 R4 R5 R6 R7 R8 三 .對稱性 定義 :R是集合 A中關(guān)系 ,若對任何 x, y∈ A,如 果有 xRy,必有 yRx,則稱 R為 A中的對稱關(guān)系。 R是 A上對稱的 ??x?y((x?A?y?A?xRy) ?yRx) 從關(guān)系有向圖看對稱性 :在兩個不同的結(jié)點 之間，若有邊的話，則有方向相反的兩條邊。 從關(guān)系矩陣看對稱性：以主對角線為對稱 的矩陣。 鄰居關(guān)系是對稱關(guān)系，朋友關(guān)系是對稱關(guān)系。 下邊 R R R6 、 R8均是對稱關(guān)系。 1。 2。 。 1。 2。 。 1。 2。 。 1。 2。 。 3 3 3 3 1。 2。 。 1。 2。 。 1。 2。 。 1。 2。 。 3 3 3 3 R2 R1 R3 R4 R5 R6 R7 R8 四 .反對稱性 定義 :設(shè) R為集合 A中關(guān)系 ,若對任何 x, y∈ A,如果有 xRy,和 yRx,就 有 x=y,則稱 R為 A中反對稱關(guān)系 。 R是 A上反對稱的 ??x?y((x?A?y?A?xRy?yRx) ?x=y) ??x?y((x?A?y?A?x?y?xRy)?y x) (P112) 由 R的關(guān)系圖看反對稱性： 兩個不同的結(jié)點之間 最多有一條邊。 從關(guān)系矩陣看反對稱性： 以主對角線為對稱的 兩個元素中最多有一個 1。 另外對稱與反對稱不是完全對立的， 有些關(guān)系 它既是對稱也是反對稱的 ，如空關(guān)系和恒等關(guān)系。 R 下邊 R R R R R8均是反對稱關(guān)系。 R R8既是對稱也是反對稱的。 1。 2。 。 1。 2。 。 1。 2。 。 1。 2。 。 3 3 3 3 1。 2。 。 1。 2。 。 1。 2。 。 1。 2。 。 3 3 3 3 R2 R1 R3 R4 R5 R6 R7 R8 五 . 傳遞性 定義 :R是 A中關(guān)系，對任何 x,y,z∈ A,如果有 xRy,和 yRz,就 有 xRz,則稱 R為 A中傳遞關(guān)系。 即 R在 A上傳遞 ??x?y?z((x?A?y?A?z?A?xRy?yRz)?xRz) 實數(shù)集中的 ≤、＜，集合 ?、 ?是傳遞的。 從關(guān)系關(guān)系圖和關(guān)系矩陣中不易看清是否有傳遞性。有 時，必須直接根據(jù)傳遞的定義來檢查。 檢查時要特別注意使得傳遞定義表達式的前件為 F的時候 此表達式為 T，即是傳遞的。 即若 x,y∈ R與 y,z∈ R有一個是 F時 (即定義的前件為 假 )， R是傳遞的。 例如 A={1,2},下面 A中關(guān)系 R是傳遞的 . 通過帶量詞的公式在論域展開式說明 R在 A上傳遞 ??x?y?z((x?A?y?A?z?A?xRy?yRz)?xRz) ??x?y?z((xRy?yRz)?xRz) (為了簡單做些刪改 ) ? ?y?z((1Ry?yRz)?1Rz)??y?z((2Ry?yRz)?2Rz) ? (?z((1R1?1Rz)?1Rz)??z((1R2?2Rz)?1Rz) ?(?z((2R1?1Rz)?2Rz) ?(?z((2R2?2Rz)?2Rz)) ?(((1R1?1R1)?1R1)?((1R1?1R2)?1R2)) ? (((1R2?2R1)?1R1)?((1R2?2R2)?1R2)) ? (((2R1?1R1)?2R1)? ((2R1?1R2)?2R2)) ? (((2R2?2R1)?2R1)) ? ((2R2?2R2)?2R2)) ? (((F?F)?F)?((F?T)?T))?(((T?F)?F)?((T?F)?T))? (((F?F)?F)? ((F?T)?F))?(((F?F)?F))?((F?F)?F))?T 1? ?2 下邊 R R R R R8均是傳遞的關(guān)系 。 1。 2。 。 1。 2。 。 1。 2。 。 1。 2。 。 3 3 3 3 1。 2。 。 1。 2。 。 1。 2。 。 1。 2。 。 3 3 3 3 R2 R1 R3 R4 R5 R6 R7 R8 本節(jié)要求 ： 。 。 R是 A中 自反 的 ??x(x?A?xRx) R是 A中 反自反 的 ??x(x?A?x,x?R) R是 A上 對稱 的 ??x?y((x?A?y?A?xRy) ?yRx) R是 A上 反對稱 的 ??x?y((x?A?y?A?xRy?yRx) ?x=y) ??x?y((x?A?y?A?x?y?xRy)?y x) R在 A上 傳遞 ??x?y?z((x?A?y?A?z?A?xRy?yRz)?xRz) 上述定義表達式都是 蘊涵式 ,所以判斷關(guān)系 R性質(zhì)時要特 別注意使得性質(zhì)定義表達式的前件為 F的時候此表達式 為 T，即 R是滿足此性質(zhì)的。 (自反和反自反性除外 ) R 自反性 反自反性 對稱性 傳遞性 反對稱性 每個結(jié)點都有環(huán) 主對角線全是 1 每個結(jié)點都無環(huán) 主對角線全是 0 不同結(jié)點間如果有邊 ,則有方向相反的兩條邊 . 是以對角線為對稱 的矩陣 不同結(jié)點間 ,最多有一條邊 . 以主對角線為對稱的位置不會同時為 1 如果有邊 a,b,b,c,則也有邊 a,c. 或者定義的前件為假 . 如果 aij=1,且 ajk=1,則 aik=1 從關(guān)系的矩 陣 從關(guān)系的有向 圖 性 質(zhì) 判定 : 下面歸納這八個關(guān)系的性質(zhì)： Y有 N無 1。 2。 。 1。 2。 。 1。 2。 。 1。 2。 。 3 3 3 3 R2 R1 R3 R4 自反性 反自反性 對稱性 反對稱性 傳遞性 R1 Y N N Y Y R2 N Y N Y N R3 Y N Y N Y R4 Y N Y Y Y 1。 2。 。 1。 2。 。 1。 2。 。 1。 2。 。 3 3 3 3 R5 R6 R7 R8 自反性 反自反性 對稱性 反對稱性 傳遞性 R5 N Y N Y Y R6 N N Y N N R7 N N N N N R8 N Y Y Y Y 練習(xí) 1:令 I是整數(shù)集合， I上關(guān)系 R定義為： R={x,y|xy可被 3整除 }，求證 R是自反、對稱和傳遞的。 證明 ： ⑴證自反性 ：任取 x∈ I, (要證出 x,x?R ) 因 xx=0, 0可被 3整除 ,所以有 x,x∈ R, 故 R自反。 ⑵證對稱性 ：任取 x,y∈ I,設(shè) x,y∈ R, (要證出 y,x?R ) 由 R定義得 xy可被 3整除 , 即 xy=3n(n∈ I)， yx=(xy)=3n=3(n), 因 n∈ I, ∴ y,x∈ R, 所以 R對稱。 ⑶ 證傳遞性 :任取 x,y,z∈ I,設(shè) xRy,