【正文】 自反性 反自反性 對稱性 傳遞性 反對稱性 每個結(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。 例如 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)系 。 從關(guān)系關(guān)系圖和關(guān)系矩陣中不易看清是否有傳遞性。 2。 1。 。 2。 1。 。 R 下邊 R R R R R8均是反對稱關(guān)系。 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)系 。 。 2。 3 3 3 3 1。 。 2。 1。 R是 A上對稱的 ??x?y((x?A?y?A?xRy) ?yRx) 從關(guān)系有向圖看對稱性 :在兩個不同的結(jié)點 之間，若有邊的話，則有方向相反的兩條邊。 1。 。 2。 1。 。 2。 如實數(shù)的大于關(guān)系 ，父子關(guān)系是反自反的。 3 3 3 3 R2 R1 R3 R4 R5 R6 R7 R8 可見這八個關(guān)系中 R R R4是自反的。 。 2。 3 3 3 3 1。 。 2。 令 A={1,2,3}給定 A上八個關(guān)系如下： 1。 關(guān)系的性質(zhì)主要有：自反性 、 反自反性 、 對稱 性 、 反對稱性和傳遞性 。 3 0 0 0 0 0 0 0 0 0 3 3 MΦ= MA A= Φ A A IA 五 . 關(guān)系的集合運算 由于關(guān)系就是集合，所以集合的 ∩、 ∪ 、 、 ?和 ~運算對關(guān)系也適用。 。 2。即含有全 部序偶的關(guān)系。 2 3 R4 : R3 : ： 有限集合之間的關(guān)系也可以用矩陣來表示，這種表示 法便于用計算機來處理關(guān)系。 A B a b c 1。 4。 例 設(shè) A={1,2,3,4},B={a,b,c}， R3 ?A B， R3={ 1,a,1,c,2,b,3,a,4,c} 則 R3的關(guān)系圖如下： 例 設(shè) A={1,2,3,4}, R4 ?A A， R4={ 1,1,1,4,2,3,3,1,3,4,4,1,4,2} 則 R4的關(guān)系圖如右上圖。 ： 即用謂詞公式表示序偶的第一元素與第二元素間的關(guān)系。 后綴表示 中綴表示 x,y?R ?xRy 也稱之為 x與 y沒有Ｒ關(guān)系。如果 R?A A，則稱 R是 A上 的二元 關(guān)系。 n 個 2) 令A(yù)={a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v, w,x,y,z} 是英文字母表 一個 英文單詞可以看成有序 n元組：如 at=a,t, boy=b,o,y, data=d,a,t,a, puter=c,o,m,p,u,t,e,r 于是可以說： at?A2 ,boy?A3,data?A4,puter?A8,… 于是英文詞典中的 單詞集合 可以看成是 A∪ A2∪ … ∪ An 的一個子集。 設(shè) A,B,C是任意集合，則 ⑴ A?(B∪ C)= (A?B)∪ (A?C)； ⑵ A?(B∩C)= (A?B)∩(A?C)； ⑶ (A∪ B)?C= (A?C)∪ (B?C)； ⑷ (A∩B)?C= (A?C)∩(B?C) 證明⑴ ：任取 x,y?A?(B∪ C) ?x?A ?y?B∪ C ?x?A ?(y?B∨ y?C) ?( x?A ?y?B)∨ (x?A?y?C) ?x,y?A?B∨ x,y?A?C ?x,y?(A?B)∪ (A?C) 所以⑴式成立。 另外 (A?B)?C={a,b,c|a,b?A?B ?c?C} A?(B?C)={a,b,c|a?A ?b,c?B?C}, 因 a,b,c不是有序三元組 , 所以 (A?B)?C?A?(B?C)。 5. 定義 ： x1, x2 ,? , xn=y1 , y2 , 有序 3元組 a,b, c可以簡記成 a,b,c。設(shè) x表示 上衣 ,y表示褲子 ,(x,y)可以表示一個人的著裝。第四章 二元關(guān)系 二元關(guān)系是一個很重要的概念 ， 它在很多數(shù)學領(lǐng)域中 都有應(yīng)用 ， 在計算機科學的如下理論都離不開關(guān)系 ： 邏輯設(shè)計 、 數(shù)據(jù)結(jié)構(gòu) 、 編譯原理 、 軟件工程 數(shù)據(jù)庫理論 、 計算理論 、 算法分析 、 操作系統(tǒng) 等 本章主要介紹： 關(guān)系的概念及表示方法 關(guān)系的性質(zhì) 關(guān)系的運算 :關(guān)系的復(fù)合 , 求逆關(guān)系 , 關(guān)系的閉包 . 三種關(guān)系 : 等價關(guān)系， 相容關(guān)系 , 次序關(guān)系。 一 .序偶與有序 n元組 :由兩個對象 x、 y組成的序列稱為有序二元組，也稱之為序偶，記作 x,y；稱 x、 y分別為序偶 x,y的第一，第二元素。 但 a,b,c不是 有序 3元組。? , yn ?( x1= y1)? ( x2= y2) ?? ?( xn= yn) 二 .集合的 笛卡爾積 例如“斗獸棋”的 16顆棋子， 可看成是由兩種顏色的集合 A和 8種動物的集合 B組成的。 故 ?也不滿足結(jié)合律。 其余可以類似證明。 作業(yè) 第 105頁 ⑵ 42 關(guān)系及其表示法 關(guān)系是一個非常普遍的概念，如數(shù)值的大于關(guān) 系、整除關(guān)系，人類的父子關(guān)系、師生關(guān)系、同 學關(guān)系等。 二元 關(guān)系簡稱為關(guān)系。 例 3. R是實數(shù)集合， R上的幾個熟知的關(guān)系： 從例 3中可以看出 關(guān)系是序偶 (點 )的集合 (構(gòu)成線、面 )。例如 R={x,y|xy} ： R?A B,用兩組小圓圈 (稱為 結(jié)點 )分別表示 A和 B的元素，當 x,y?R時，從 x到 y引一條有向弧 (邊 )。 1。 。 。 設(shè) A={a1, a2, ? , am}， B={b1, b2, ? , bn}是個有限集， R?A B，定義 R的 m n階 矩陣 MR=(rij)m n，其中 rij= R3={ 1,a,1,c,2,b,3,a,4,c} R4={ 1,1,1,4,2,3,3,1,3,4,4,1,4,2} 上例中 MR = MR4= 1 若 ai,bj∈ R 0 若 ai,bj∈ R (1≤i≤m,1≤j≤n) 3 1 0 1 0 1 0 1 0 0 0 0 1 4 3 1 2 3 4 a b c 1 0 0 1 0 0 1 0 1 1 0 0 1 0 0 1 4 4 1 2 3 4 1 2 3 4 四 .三個特殊關(guān)系 Φ： 因為 Φ?A B， (或 Φ?A A)，所以 Φ也 是一個從 A到 B(或 A上 )的關(guān)系，稱之為 空 關(guān)系 。它的矩陣中全是 1。 。 3 1 1 1 1 1 1 1 1 1 3 3 1。 例如， A是學生集合， 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)系的研究 中起著重要的作用 。 一 .自反性 定義 :設(shè) R是集合 A中的關(guān)系 ， 如果對于任意 x∈ A都有 x,x∈ R (xRx)， 則稱 R是 A中自反關(guān)系 。 2。 。 1。 2。 。 1。 二 .反自反性 定義 ： 設(shè) R是集合 A中的關(guān)系，如果對于任 意的 x∈ A都有 x,x?R ，則稱 R為 A中的反 自反關(guān)系。 注意 ：一個不是自反的關(guān)系，不一定就是反 自反的，如前邊 R R7非自反 ,也非反自反。 。 1。 2。 。 1。 2。 從關(guān)系矩陣看對稱性：以主對角線為對稱 的矩陣。 2。 。 1。 2。 。 1。 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é)點之間 最多有一條邊。 R R8既是對稱也是反對稱的。 1。 2。 。 1。 2。 。有 時，必須直接根據(jù)傳遞的定義來檢查。 1。 2。 。 3 3 3 3 1。 2。 。 3 3 3 3 R2 R1 R3 R4 R5 R6 R7 R8 本節(jié)要求 ： 。 2。 。 1。 2。 。 1。 證明 ： ⑴證自反性 ：任取 x∈ I, (要證出 x,x?R ) 因 xx=0, 0可被 3整除 ,所以有 x,x∈ R, 故 R自反。 證明 ： 必要性 : 已知 R是對稱和傳遞的。 先證 R對稱 ：任取 a,b?A 設(shè) a,b?R， (要證出 b,a?R ) 因 R是自反的 ,所以 a,a?R，由 a,b?R且 a,a?R，根據(jù)已知條件得 b,a?R ， 所以 R是對稱的。 例如，有 3個人 a,b,c， A={a,b,c}， R是 A上 兄妹 關(guān)系， S是 A上 母子 關(guān)系， a,b∈ R∧ b,c∈ S 即 a是 b的哥哥 , b是 a的妹妹 。定義為： R?S ={x,z|x?X?z?Z??y(y?Y ?x,y?R?y,z?S)} 顯然， R?S 是從 X到 Z的關(guān)系。 。 3。 A 。 4 R S 5 。 C 1 2 3 。 令 A={1,2,3}, B={a,b,c,d} 從這兩個圖看出它們的復(fù)合都等于 R。 A IA 。 d R 1。 。 。 2。a,d?R3,表明在 R圖上有從 a到 d有三條 邊的