【正文】 1 離散數(shù)學(xué) 西安交通大學(xué) 電子與信息工程學(xué)院 計(jì)算機(jī)軟件所 劉國(guó)榮 2 等價(jià)關(guān)系 叉積 關(guān)系 幺關(guān)系 元組 全關(guān)系 傳遞閉包 逆關(guān)系 復(fù)合關(guān)系 關(guān)系冪 自反傳遞閉包 自反關(guān)系 對(duì)稱關(guān)系 反對(duì)稱關(guān)系 傳遞關(guān)系 半序關(guān)系 空關(guān)系 余關(guān)系 并關(guān)系 差關(guān)系 交關(guān)系 3 離散數(shù)學(xué) 第二章 關(guān)系 (relation) 167。 1 . 集合的叉積 n元組 167。 2 .關(guān)系 167。 3 .關(guān)系的 表示 關(guān)系的性質(zhì) 167。 4 .關(guān)系的運(yùn)算 167。 5. 等價(jià)關(guān)系 167。 6. 半序關(guān)系 4 離散數(shù)學(xué) 167。 1 . 集合的叉積 n元組 定義 ，笛卡爾積 (cross product ,Cartesian product(1637)) ? n個(gè)集合 A1， A2， ? ， An的 n 維叉積定義為 =A1 A2 ? An ={(a1, a2, ? , an): ai? Ai(1?i ? n)} ； ? n 維叉積 A1 A2 ? An的每個(gè)元素 (a1, a2, ? , an)都稱為一個(gè) n元組（ ntuple）；即，叉積是元組的集合； ?每個(gè) n元組 (a1, a2, ? , an)的第 i個(gè)位置上的元素 ai稱為該 n元組的第 i個(gè)分量（坐標(biāo)或投影）；元組各分量的順序不能改變； ? n 稱為該叉積及其元組的維數(shù)； ?兩個(gè) 元組相等 ?它們的 維數(shù)相同且對(duì)應(yīng)的分量相等。 1nii A??5 離散數(shù)學(xué) 即 (a1, a2, ? , an)= (b1, b2, ? , bm) ?n=m?(?i?N)(1?i ? n)(ai = bi)； 注： 笛卡爾 (15961650 )，法國(guó)數(shù)學(xué)家， 1637年發(fā)表 《 方法論 》 之一 《 幾何學(xué) 》 ，首次提出坐標(biāo)及變量概念。這里是其概念的推廣。 定義 2. ? 二個(gè)集合 A， B的 (二維或二重 )叉積定義為 A B ={(a, b): a? A ?b?B} ； ?其元素 —— 二元組 (a, b)通常稱為序偶或偶對(duì) (ordered pair) ； ?二元組 (a, b)的 第一分量上的元素 a稱為前者； 第二分量上的元素 b稱為后者； ?二重叉積的 A? B第一 集合 A稱為前集； 第二 集合 B稱為后集。 6 離散數(shù)學(xué) 例 1 . A={ a,b,c }, B={0,1} A B={(a,0), (a,1), (b,0), (b,1), (c,0), (c,1)} B A={(0,a), (0,b), (0,c), (1,a), (1,b), (1,c)} 例 2 . A={張三 ,李四 }， B={白狗 ,黃狗 } A B={(張三 ,白狗 ),(張三 ,黃狗 ),(李四 ,白狗 ),(李四 ,黃狗 )} B A={(白狗 ,張三 ),(白狗 ,李四 ),(黃狗 ,張三 ),(黃狗 ,李四 )} 一般地說(shuō)，關(guān)于叉積和元組我們有： (1) (a, b)? (b, a)； (2) A B ? B A ； (3)二元組不是集合，因?yàn)槎M中的分量計(jì)較順 7 離散數(shù)學(xué) 序 ,而集合中的元素是不講順序的。但是我們?yōu)榱藢⑺械母拍疃冀y(tǒng)一于集合概念，我們可采用克亞托斯基(Kazimierz Kurafowski)在 1921年給出的定義 (a, b)={{a},{a, b}} 將二元組定義為比其元素高二層的集合； (4)我們也可用二元組來(lái)遞歸的定義 n元組如下： (a,b,c)=((a,b),c) ? ? ? (a1, a2, ? , an1 , an)= ((a1, a2, ? , an1) , an) (5)這樣，我們也就可用二重叉積來(lái)遞歸的定義 n維叉積如下： A B C=(A B) C ? ? ? A1 A2 ? An1 An= (A1 A2 ? An1) An 8 離散數(shù)學(xué) (6)利用 (5)所給的定義，我們可以遞歸的定義集合的叉積冪如下： A2= A A A3 = A2 A ? An = An1 A (7)我們 規(guī)定空集 ?與任何 集合 A的叉積是空集 ? 。 即 A ? = ? = ? A 由于若偶對(duì)的第一分量或第二分量不存在就沒有偶對(duì)存在，故規(guī)定它們的叉積集合為空集是合理的。 定理 A,B,C,D是四個(gè)非空的集合。那么 A B = C D ? A = C ? B = D 。 9 離散數(shù)學(xué) [證 ].?):顯然。 ?)： （采用邏輯法） 對(duì)任何的元素 a,b a?A?b?B ?(a,b)?A B ?(a,b)?C D (條件： A B = C D ） ? a?C?b?D 所以 A = C ? B = D 。 定理 2 . 設(shè) A,B,C是三個(gè)集合。則 (1)左分配律： A (B∪ C) = (A B)∪ (A C) (叉積對(duì)并的 )； (2)左分配律： A (B∩C) = (A B)∩(A C) (叉積對(duì)交的 )； (3)右分配律： (A∪ B) C = (A C)∪ (B C) 10 離散數(shù)學(xué) (叉積對(duì)并的 )； (3)右分配律： (A∩B) C = (A C)∩(B C) (叉積對(duì)交的 )。 [證 ].只證 (1)（采用邏輯法） 對(duì)任何的元素 a,b (a,b)?A (B∪ C) ?a?A?b? B∪ C ? a?A?(b?B?b?C) ? (a?A?b?B)?(a?A?b?C) (分配律： p?(q?r)?(p?q)?(p?r)) ? (a,b)?A B?(a,b)?A C ? (a,b)?(A B)∪ (A C) 所以 A (B∪ C) = (A B)∪ (A C) 。 11 離散數(shù)學(xué) 167。 2 .關(guān)系 一 .關(guān)系的基本概念 定義 1 .二元關(guān)系 (binary relation) 設(shè) A,B是兩個(gè)非空的集合。 ?二重叉集 A B 的任何一個(gè)子集 R都稱為是從集合 A到集合 B的一種二元關(guān)系。即 R?A B ； ?當(dāng) (a,b)?R 時(shí)，稱 a與 b有關(guān)系 R ，記為 aRb ； ?當(dāng) (a,b)?R 時(shí)，稱 a與 b沒有關(guān)系 R ，記為 或 ； ?當(dāng) A=B時(shí)， 即 R?A A，則 稱 R是 A上的一個(gè)二元關(guān)系 。 例 1 . 設(shè) A是西安交通大學(xué)全體同學(xué)組成的集合 。 aRbaRb aRb12 離散數(shù)學(xué) R={(a,b) : a?A?b?A?a與 b是同鄉(xiāng) }?A A 于是， R是西安交通大學(xué)同學(xué)之間的同鄉(xiāng)關(guān)系。 例 2 . 設(shè) A是某一大家庭。 R1 = {(a,b) : a?A?b?A?a是 b的父親或母親 }?A A R2 = {(a,b) : a?A?b?A?a是 b的哥哥或姐姐 }?A A R3 = {(a,b) : a?A?b?A?a是 b的丈夫或妻子 }?A A 于是， R1是父母與兒女之間的關(guān)系，即父母子女關(guān)系； R2是兄弟姐妹之間的關(guān)系，即兄弟姊妹關(guān)系； R3是夫妻之間的關(guān)系，即夫妻關(guān)系。 例 3 . 設(shè) N是自然數(shù)集合。 13 離散數(shù)學(xué) R= { (a,b) : a?N?b?N?a|b }? N N 則 R就是自然數(shù)集合上的整除關(guān)系。 例 4 . 設(shè)Ｉ是整數(shù)集合。 R= { (a,b) : a?I?b?I?(?k?I)(ab =k?m)}? I?I 則 R就是整數(shù)集合上的 (模 m)同余關(guān)系。 例 5 . 設(shè) A是某一大型 FORTRAN程序中諸程序塊的集合。 R= { (a,b) : a?A?b?B?a調(diào)用 (call)b }?A?A 則 R就是程序塊集合上的 調(diào)用 關(guān)系。 例 6 . 設(shè) A = {風(fēng)，馬，牛 }， R = { (風(fēng) ,馬 )， (馬 ,牛 ) }?A?A 則 R是 A上的一個(gè)二元關(guān)系。 14 離散數(shù)學(xué) 關(guān)于關(guān)系概念，我們還有如下的幾個(gè)定義和說(shuō)明： 1176。 全關(guān)系 (full relation)： 關(guān)系 R=A?B稱為全關(guān)系； 2176。 空關(guān)系 (empty relation)： 關(guān)系 R= ?稱為空關(guān)系； ?空關(guān)系和全關(guān)系都是平凡關(guān)系； 3176。 幺關(guān)系或單位關(guān)系 (identical relation)： 關(guān)系 R= {(a, a): a?A}? A?A稱為 A上的幺關(guān)系； 例 7 . 設(shè) A={1,2,3,4}，則 R1 = {(1,1) , (2,2) , (3,3) , (4,4) }是 幺關(guān)系； R2 = {(1,1) , (2,3) , (3,4) , (4,4) }不是； R3 = {(1,1) , (2,2) , (3,3) , (4,4) ,(1,2) }也不是； 15 離散數(shù)學(xué) 4176。 關(guān)系的交，并，余運(yùn)算： ?叉積是一種（新型的）集合；關(guān)系是叉積的子集；因此，關(guān)系也是一種（新型的）集合； ? 從而，有關(guān)集合論的一切概念、論述、運(yùn)算也都適合于關(guān)系； ?尤其是 集合的交，并，余，差運(yùn)算也都適合于關(guān)系；因此，關(guān)系也有交，并，余，差運(yùn)算； 例 8 . 設(shè) N是自然數(shù)集合。 R=小于關(guān)系 ={(m,n) : m?N?n?N?m?n}?N?N S=整除關(guān)系 ={(m,n) : m?N?n?N?m|n}?N ?N 則 R? =大于等于關(guān)系 (?)； R?S=小于等于關(guān)系 (?) ； 16 離散數(shù)學(xué) R?S=不相等的 整除關(guān)系 (???)； R\S=小于又 不 整除關(guān)系 (? ??)； S\R=相等 關(guān)系 (=) 。 5176。 關(guān)系的擴(kuò)充 (expansion)： 若 R1 ? R2 ，則稱關(guān)系 R2 是關(guān)系 R1的一個(gè)擴(kuò)充； 6176。 n元關(guān)系： n元關(guān)系 R是 n 維叉積的一個(gè)子集；即 R? A1?A2? ? ?An R1 R2 17 定義 (domain) 后域 (codomain) 設(shè) A,B是兩個(gè)非空集合， R ?A B是一關(guān)系。則關(guān)系R的 ?前域： ? (R) = { a : a ?A?(?b?B)(aRb)}?A ； ?后域： ? (R) = { b : b?B?(?a?A)(aRb) }?B 。 例 9 .設(shè) A={1,2,3,4} ， B={2,4,6,8,10} 。 R={(1,2),(2,4),(3,6)}。 則 ? (R) = {1,2,3}?A ， ? (R) = {2,4,6}?B 。 二 .關(guān)系的一些關(guān)聯(lián)性質(zhì) 離散數(shù)學(xué) A ? (R) B ? (R) a b R 18 離散數(shù)學(xué) 定理 1. 設(shè) R1,R2 ? A B是兩個(gè)關(guān)系。若 R1 ? R2 ，則 (1)保序性： ? (R1