【正文】 1,1,1,2,1,3, 1,4,2,2, 2,3, 2,4, 3,3, 3,4,4,4} 。 例 3. R是實數集合， R上的幾個熟知的關系： 從例 3中可以看出 關系是序偶 (點 )的集合 (構成線、面 )。如 :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的二元關系。 作業(yè) 第 105頁 ⑵ 42 關系及其表示法 關系是一個非常普遍的概念，如數值的大于關 系、整除關系，人類的父子關系、師生關系、同 學關系等。 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，遼寧 這就是學生檔案數據庫的一條信息，所以學生 的檔案就是 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 所以，集合的笛卡爾積運算不滿足交換律。? , yn ?( x1= y1)? ( x2= y2) ?? ?( xn= yn) 二 .集合的 笛卡爾積 例如“斗獸棋”的 16顆棋子， 可看成是由兩種顏色的集合 A和 8種動物的集合 B組成的。且可以簡記成x1 , x2 ,? , xn1, xn。 但 a,b,c不是 有序 3元組。 ：設 x,y， u,v是兩個序偶，如果 x=u和 y=v，則稱 x,y和 u,v相等， 記作 x,y=u,v. 3 .定義 :有序 3元組是一個序偶 ,其第一個元素也是個序偶。 一 .序偶與有序 n元組 :由兩個對象 x、 y組成的序列稱為有序二元組，也稱之為序偶，記作 x,y；稱 x、 y分別為序偶 x,y的第一，第二元素。例如，用序 偶表示平面直角坐標系中一個點 (a,b)。第四章 二元關系 二元關系是一個很重要的概念 ， 它在很多數學領域中 都有應用 ， 在計算機科學的如下理論都離不開關系 ： 邏輯設計 、 數據結構 、 編譯原理 、 軟件工程 數據庫理論 、 計算理論 、 算法分析 、 操作系統(tǒng) 等 本章主要介紹： 關系的概念及表示方法 關系的性質 關系的運算 :關系的復合 , 求逆關系 , 關系的閉包 . 三種關系 : 等價關系， 相容關系 , 次序關系。 41 序偶與集合的笛卡爾積 實際上“序偶”概念以前已經用過。設 x表示 上衣 ,y表示褲子 ,(x,y)可以表示一個人的著裝。 注意，序偶 x,y與集合 {x,y}不同： 序偶 x,y：元素 x和 y有 次序； 集合 {x,y}：元素 x和 y的次序是無關緊要的。 有序 3元組 a,b, c可以簡記成 a,b,c。 :有序 n元組是一個序偶 ,其第一個元素本身是個有序 n1元組 ,記作 x1 , x2 ,? , xn1, xn。 5. 定義 ： x1, x2 ,? , xn=y1 , y2 , 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 。 另外 (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)。 1) 如果 A、 B都是有限集，且 |A|=m, |B|=n，則 |A?B |=mn. 證明：由笛卡爾積的定義及排列組合中的乘法原 理，直接推得此定理。 設 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) 所以⑴式成立。 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?B?C?D 證明 A?C∧ B?D. 任取 x?A，任取 y?B，所以 x?A?y?B ?x,y?A B ?x,y?C D (由 A?B?C?D ) ?x?C?y?D 所以 , A?C∧ B?D. 其次 , 由 A?C， B?D. 證明 A?B?C?D 任取 x,y?A B x,y?A B ? x?A?y?B ? x?C?y?D (由 A?C， B?D) ?x,y?C D 所以 , A?B?C?D 證畢 . 6)約定 (…(A 1?A2)?… ?An1)?An)=A1?A2?… ?An 特別 A?A?… ?A = An 設 R是實數集合，則 R2表示 笛卡爾坐標平面， R3表示 三維空間， Rn表示 n維空間。 n 個 2) 令A={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 的一個子集。下面討論如何從中抽象出關系的定義 和如何表示關系。如果 R?A A，則稱 R是 A上 的二元 關系。 定義 2:任何序偶的集合，都稱之為一個二元關系。 后綴表示 中綴表示 x,y?R ?xRy 也稱之為 x與 y沒有Ｒ關系。 x2+y2=4 ≤ ≥ = x y 定義域 (domain) ： 設 R?A B，由所有 x,y?R的第一個元素組成的集合，稱為 R的定義域，記作 dom R，即 dom R={x|?y(x,y?R)} 值域 (range) ： 設 R?A B，由所有 x,y?R的第二個元素組成的集合，稱為 R的值域， 記作 ran R，即 ran R={y|?x(x,y?R)} 上述 R2={ 1,1,1,2,1,3,1,4,2,2,2,3, 2,4, 3,3, 3,4,4,4} dom R2 ={1,2,3,4} ran R2 ={1,2,3,4} 三 . 關系的表示方法 1. 枚舉法 : 即將關系中所有序偶一一列舉出，寫在大括號 內。 ： 即用謂詞公式表示序偶的第一元素與第二元素間的關系。這樣得到的圖形稱為 R的關系圖。 例 設 A={1,2,3,4},B={a,b,c}， R3 ?A B， R3={ 1,a,1,c,2,b,3,a,4,c} 則 R3的關系圖如下： 例 設 A={1,2,3,4}, R4 ?A A， R4={ 1,1,1,4,2,3,3,1,3,4,4,1,4,2} 則 R4的關系圖如右上圖。 2。 4。 。 A B a b c 1。 4。 2 3 R4 : R3 : ： 有限集合之間的關系也可以用矩陣來表示，這種表示 法便于用計算機來處理關系。即無任何元素的關系，它的關系圖 中只有結點 ,無任何邊；它的矩陣中全是 0。即含有全 部序偶的關系。 3. A上的 恒等關系 IA： IA?A A，且 IA ={x,x|x∈ A}稱之為 A 上的恒等關系。 2。 3 1。 。 。 3 0 0 0 0 0 0 0 0 0 3 3 MΦ= MA A= Φ A A IA 五 . 關系的集合運算 由于關系就是集合，所以集合的 ∩、 ∪ 、 、 ?和 ~運算對關系也適用。 這是本章最重要的一節(jié) 。 關系的性質主要有：自反性 、 反自反性 、 對稱 性 、 反對稱性和傳遞性 。 即 R是 A中自反的 ??x(x?A?xRx) 例如在實數集合中 ,“?”是自反關系 ， 因為 ， 對任意實數 x， 有 x ? x. 從關系有向圖看自反性 :每個結點都有環(huán)。 令 A={1,2,3}給定 A上八個關系如下： 1。 。 2。 1。 。 2。 3 3 3 3 1。 。 2。 1。 。 2。 3 3 3 3 R2 R1 R3 R4 R5 R6 R7 R8 可見這八個關系中 R R R4是自反的。即 R是 A中反自反的 ??x(x?A?x,x?R) 從關系有向圖看反自反性 :每個結點都無環(huán)。 如實數的大于關系 ，父子關系是反自反的。 下面 R R R均是反自反關系 。 2。 1。 。 2。 1。 。 2。 1。 。 2。 1。 。 R是 A上對稱的 ??x?y((x?A?y?A?xRy) ?y