【正文】 遞閉包。 必要性，已知 R反 對稱， (證出 R∩RC ? IA) 任取 x,y?R∩RC x,y?R∩RC?x,y?R∧ x,y?RC ?x,y?R∧ y,x?R ?x=y (因 R反對稱 ) ?x,y?IA 所以 R∩RC ?IA 。 必要性，已知 R 對稱， (證出 RC =R) 先證 RC?R， 任取 y,x∈ RC,則 x,y?R,因 R對稱 所以有 y,x∈ R，所以 RC?R。 5. R?S ? RC? SC 。如 三 .性質(zhì) 令 R、 S都是從 X到 Y的關系，則 1. (RC)C = R 2. (R∪ S)C = RC∪ SC 。 (x,y?A) a d b c R: 45 逆關系 逆關系 (反關系 )也是我們經(jīng)常遇到的概念，例 如 ≤與 ≥就是互為逆關系。 A B 4. 關系的乘冪 令 R是 A上關系，由于復合運算可結(jié)合，所以 關系的復合可以寫成乘冪形式。 B a b c 。 a b c 。 3。 。 2。 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 0 0 1 = 4 5 1 0 1 0 0 0 1 0 1 1 1 0 0 0 0 3 5 k=1 n ∨ k=1 n ∨ ⑷ 謂詞公式法 設 I是實數(shù)集合， R和 S都是 I上的關系，定義如下： R={x,y| y=x2+3x} S={x,y| y=2x+3} 所以 R?S ={x,y| y=2x2+6x+3} 三 .性質(zhì) 關系復合運算不滿足交換律，但是 : R?A B S?B C T?C D 則 TS)(RT)S(R ???? ?x x2+3x 2(x2+3x)+3 = 2x2+6x+3 R S 證明：任取 a,d∈ R (S T) ??b(b∈ B∧ a,b∈ R∧ b,d∈ S T) ??b(b∈ B∧ a,b∈ R∧ ?c(c∈ C∧ b,c∈ S∧ c,d∈ T)) ??b?c(b∈ B∧ a,b∈ R∧ (c∈ C∧ b,c∈ S∧ c,d∈ T)) ??c?b(c∈ C∧ (b∈ B∧ a,b∈ R∧ b,c∈ S∧ c,d∈ T)) ??c (c∈ C∧ ?b(b∈ B∧ a,b∈ R∧ b,c∈ S)∧ c,d∈ T) ??c (c∈ C∧ a,c∈ R S)∧ c,d∈ T) ?a,d∈ (R S) T TS)(RT)S(R ???? ?A B C D R T 所以 可以用下圖形象表示 : 2. R?A B S?B C T?B C ⑴ R (S∪ T)=(R S)∪ (R T) ⑵ R (S∩T)?(R S)∩(R T) 證明 ⑴ 任取 a,c∈ R (S∪ T) ? ?b(b∈ B∧ a,b∈ R∧ b,c∈ S∪ T) ??b(b∈ B∧ a,b∈ R∧ (b,c∈ S∨ b,c∈ T)) ??b((b∈ B∧ a,b∈ R∧ b,c∈ S)∨ (b∈ B∧ a,b∈ R∧ b,c∈ T)) ??b(b∈ B∧ a,b∈ R∧ b,c∈ S)∨ ?b(b∈ B∧ a,b∈ R∧ b,c∈ T) ?a,c∈ R S∨ a,c∈ R T ?a,c∈ (R S)∪ (R T) 所以 R (S∪ T)=(R S)∪ (R T) 證明⑵ 任取 a,c∈ R (S∩T) ? ?b(b∈ B∧ a,b∈ R∧ b,c∈ S∩T) ??b(b∈ B∧ a,b∈ R∧ (b,c∈ S∧ b,c∈ T)) ??b((b∈ B∧ a,b∈ R∧ b,c∈ S) ∧ (b∈ B∧ a,b∈ R∧ b,c∈ T)) ??b(b∈ B∧ a,b∈ R∧ b,c∈ S)∨ ?b(b∈ B∧ a,b∈ R∧ b,c∈ T) ?a,c∈ R S ∧ a,c∈ R T ?a,c∈ (R S)∩(R T) 所以 R (S∩T)?(R S)∩(R T) ?x(A(x)∧ B(x)) ??xA(x)∧ ?xB(x) 3. R是從 A到 B的關系，則 R IB=IA R=R 此式的證明很容易，從略。 。 。 2。 4 1。 。 則 a和 c間就是 舅舅和外甥 的關系 ,記作 R?S, 稱它是 R和 S的復合關系 。 (要證出 a,c?R ) 由 R是對稱的 ,得 b,a?R ，由 b,a?R且 b,c?R，根據(jù)已知條件得 a,c?R ， 所以 R是傳遞的。所以有如果 a,b和 a,c在 R中 ,則有 b,c也在 R中。 ⑶ 證傳遞性 :任取 x,y,z∈ I,設 xRy, yRz, (要證出 xRz) 由 R定義得 xy=3m, yz=3n (∈ I) xz= (xy)+(yz)=3m+3n=3(m+n), 因 m+n∈ I, 所以 xRz, 所以 R傳遞。 。 2。 1。 。 2。 1。 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) 上述定義表達式都是 蘊涵式 ,所以判斷關系 R性質(zhì)時要特 別注意使得性質(zhì)定義表達式的前件為 F的時候此表達式 為 T，即 R是滿足此性質(zhì)的。 2。 1。 。 2。 1。 。 即若 x,y∈ R與 y,z∈ R有一個是 F時 (即定義的前件為 假 )， R是傳遞的。 即 R在 A上傳遞 ??x?y?z((x?A?y?A?z?A?xRy?yRz)?xRz) 實數(shù)集中的 ≤、＜，集合 ?、 ?是傳遞的。 1。 。 2。 1。 。 2。 另外對稱與反對稱不是完全對立的， 有些關系 它既是對稱也是反對稱的 ，如空關系和恒等關系。 。 2。 1。 。 2。 1。 下邊 R R R6 、 R8均是對稱關系。 3 3 3 3 R2 R1 R3 R4 R5 R6 R7 R8 三 .對稱性 定義 :R是集合 A中關系 ,若對任何 x, y∈ A,如 果有 xRy,必有 yRx,則稱 R為 A中的對稱關系。 。 2。 3 3 3 3 1。 。 2。 1。 從關系矩陣看反自反性：主對角線都為 0。 。 2。 1。 。 2。 1。 從關系矩陣看自反性：主對角線都為 1。 本節(jié)中所討論的關系都是集合 A中的關系 。 2。 2。 例如 A={1,2,3}, 則 IA ={1,1,2,2,3,3} A上的 Φ、完全關系及 IA的關系圖及矩陣如 下： MIA = 1 0 0 0 1 0 0 0 1 3 3 1。 (全域關系 ) ： A B(或 A A)本身也是一個從 A到 B(或 A上 ) 的關系，稱之為完全關系。 。 。 3。 如 R?A A,即 R是集合 A中關系時 ,可能有 x,x?R,則從 x到 x畫一條有向環(huán) (自回路 )。如前的 R2 ={ 1,1,1,2,1,3, 1,4,2,2, 2,3, 2,4, 3,3, 3,4,4,4} 。如 :R={1,a,書 ,車 ,人 , 樹 } x,y?R ?xRy 也稱之為 x與 y有Ｒ關系。 一 .例子 1. 大寫英字母與五單位代碼的對應關系 R1: 令 α={A,B,C,D,…Z} β={30,23,16,22,…,21} 是 五單位代碼集合 β={11000, 10011, 01110, 10010,…, 10001} R1={A,30,B,23,C,16,...,Z,21}?α β ={1,2,3,4}, A中元素間的 ≤關系 R2 ： R2={ 1,1,1,2,1,3,1,4,2,2,2,3, 2,4, 3,3, 3,4,4,4}?A A 二 . 基本概念 定義 1:設 A、Ｂ是集合，如果Ｒ ?A B，則稱 R是一個 從 A到 B的二元關系。 1)令 A1={x|x是 學號 } A2={x|x是 姓名 } A3={男 ,女 } A4={x|x是 出生日期 } A5={x|x是 班級 } A6 ={x|x是 籍貫 } 則 A1?A2?A3 ?A4?A5 ?A6中一個元素： 001， 王強，男， 1981:02:16，計 20221，遼寧 這就是學生檔案數(shù)據(jù)庫的一條信息，所以學生 的檔案就是 A1?A2?A3 ?A4?A5 ?A6的一個子集。 2) A?Φ=Φ?B=Φ 3) ?對 ∪ 和 ∩滿足分配律。 解： A?B={0,a,0,b,1,a,1,b} B?A={a,0 ,b,0,a,1,b,1} A?A={0,0,0,1,1,0,1,1} 可見 A B≠B A 所以，集合的笛卡爾積運算不滿足交換律。且可以簡記成x1 , x2 ,? , xn1, xn。 ：設 x,y， u,v是兩個序偶，如果 x=u和 y=v，則稱 x,y和 u,v相等， 記作 x,y=u,v. 3 .定義 :有序 3元組是一個序偶 ,其第一個元素也是個序偶。例如，用序 偶表示平面直角坐標系中一個點 (a,b)。 41 序偶與集合的笛卡爾積 實際上“序偶”概念以前已經(jīng)用過。 注意，序偶 x,y與集合 {x,y}不同： 序偶 x,y：元素 x和 y有 次序； 集合 {x,y}：元素 x和 y的次序是無關緊要的。 :有序 n元組是一個序偶 ,其第一個元素本身是個有序 n1元組 ,記作 x1 , x2 ,? , xn1, xn。 A={紅 ,藍 } B={象 ,獅 ,虎 ,豹 ,狼 ,狗 ,貓 ,鼠 } 每個棋子可以看成一個序偶，斗獸棋可記成集合 A?B ： { 紅 ,象 ,紅 ,獅 ,紅 ,虎 ,紅 ,豹 ,紅 ,狼 ,紅 ,狗 ,紅 ,貓 ,紅 ,鼠 , 藍 ,象 ,藍 ,獅 ,藍 ,虎 ,藍 ,豹 ,藍 ,狼 ,藍 ,狗 ,藍 ,貓 ,藍 ,鼠 } 虎 象 獅 豹 狼 鼠 貓 狗 虎 象 獅 豹 狼 鼠 貓 狗 :設 A、 B是集合，由 A的元素為第一元素，B的元素為第二元素組成序偶的集合，稱為 A和 B的笛卡爾積，記作 A B，即 A?B={x,y|x?A∧ y?B} 例 1 設 A={0,1}， B={a,b}，求 A?B ， B?A， A?A 。 1) 如果 A、 B都是有限集，且 |A|=m, |B|=n，則 |A?B |=mn. 證明：由笛卡爾積的定義及排列組合中的乘法原 理，直接推得此定理。 4)若 C??,則 A?B?(A?C?B?C) ?(C?A?C?B). 證明 : 必要性： 設 A?B，求證 A?C?B?C 任取 x,y?A?C ?x?A?y?C ?x?B?y?C (因 A?B) ?x,y?B?C 所以 , A?C?B?C. 充分性： 若 C??, 由 A?C?B?C 求 證 A?B 取 C中元素 y, 任取 x?A?x?A?y?C ?x,y?A?C ?x,y?B?C (由 A?C?B?C ) ?x?B?y?C? x?B 所以 , A?B. 所以 A?B?(A?C?B?C) 類似可以證明 A?B ?(C?A?C?B). 5) 設 A、 B、 C、 D為非空集合，則 A?B?C?D?A?C∧ B?D. 證明 : 首先 ,由 A?