【正文】 ， x與 y都是可比的， x覆蓋 x1。為成立，則稱若的極小元；為成立，則稱若的最大元；為成立，則稱若的最小元；為成立，則稱若ByxyxyBxxByxyyxBxxByyxBxxByxyBxx)()4()()3()()2()()1(????????????????????52/57 次序關(guān)系 ?如果最小元存在，最小元唯一，但極小元可以有多個； ?b是 B的最小元 =b是 B中的唯一極小元； ?反之，極大元亦然。 Ayx ?? ,57/57 次序關(guān)系 ?定義 ： 設 A, ≤ 是一個偏序集，若 A的任何一個非空子集有最小元，則稱“ ≤ ”為良序關(guān)系(Well Order Relation)，簡稱良序，此時 A, ≤ 稱為良序集。 例： (1)集合 A={a， b， c}，上定義的關(guān)系 ≤={a ，a， b， b， c， c， a， b， b， c， a， c}是一個全序關(guān)系； (2)實數(shù)集合 R上定義的“ ≤ ”是全序關(guān)系， R, ≤ 是全序集。 ?例 417： 設集合 A={a}， B={a， b}， C={a， b， c}分別畫出集合 A， B， C之冪集上定義的“ ”的哈斯圖。 ? ?Ayx ?? ,Az?48/57 次序關(guān)系 例： (1)集合 A={a， b， c}，則偏序集 ρ (A), ?中， {a}與 {a， b}是可比的； {a}與 {b， c}是不可比的； {a， b}覆蓋 {a}； {a， b， c}不覆蓋 {a}。 證明：必要性：若 R是等價關(guān)系； (1)R等價 =R自反 (2) ， R等價 ∴ R對稱 ∴ ，即 R是循環(huán)關(guān)系； 充分性：若 R自反且循環(huán) ： (1)自反性顯然； (2) ， R是自反，得 ，因 R是循環(huán)的 ，即 R是對稱的； ?RcbRcaRba ????????? , ，則有且RcaRbaAcba ???????? , 若RcbRcaRab ?????????? ,R, 傳遞，而Aba ?? , Raa ??? ,RabRba ?????? , 則若45/57 等價關(guān)系與劃分 (3) ，則由 R對稱得 ，由 R循環(huán)， ， ∴ R是傳遞的； ∴R 等價。][,).1(AxyxyRxAyxyxxR yAyxxAxRAxRRRRR??????????????????則則Ax?? Rxx ??? ,????? RR xxx ][][RxzRzxxzz ?????????? ,][,RRRR yxyzxzRzyRyzRyxRxz][][][][,?????????????????????40/57 等價關(guān)系與劃分 同理： (3)若 ，則存在 ，即： ?定義 ： 設 R是集合 A上的等價關(guān)系，由 R確定的一切等價類的集合，稱為集合 A上關(guān)于 R的商集(Quotient Set)，記為 A/R，即 RRRR yxxy ][][][][ ??????RR yx ][][ ? RR yzxz ][][ ???矛盾與 yRxRyxRzyRzx ???????????? ,AxxAxxAxxxxxxRxxAxxAxAxAxxRAxRAxRAxRAxRRAxR???????????????????????????][][][,][][,][][,)4(?????即}|]{[/ AxxRA R ??41/57 等價關(guān)系與劃分 ?定理 ： 設 R是非空集合 A上的等價關(guān)系，則 A上的關(guān)于 R的商集 A/R是 A的一個劃分，稱之為由 R導出的等價劃分。 Ryx ??? ,AAI A ?,?36/57 等價關(guān)系與劃分 ?例 412： 設 m為正整數(shù)，整數(shù)集合上的關(guān)系 證明關(guān)系 R是等價關(guān)系。 (3)集合 A上的關(guān)系 R的對稱傳遞閉包定義為 st(R)=s(t(R))。 R?R?RR ?? R?RR ????30/57 關(guān)系的閉包 例：定義在 N上的“ ”關(guān)系的自反閉包 r(R)為“ ≤ ”，對稱閉包 s(R)為“ ≠ ”，傳遞閉包 t(R)為“ ”； 定義在 N上的“ =”關(guān)系的自反閉包 r(R)為“ =”，對稱閉包 s(R)為“ =”，傳遞閉包 t(R)為“ =”。)1(11RRRRIRRRRRRIRRRIRAAA?????????????????傳遞的是反對稱的是對稱的是反自反的是自反的27/57 關(guān)系的性質(zhì) ? ?定理 ： 設 R， S是 A上的二元關(guān)系，則 ?例 410： 設 R={a, b， b, c， a, c}， S={b, a， c, b， c, a}是定義在 A={a, b, c}上的兩個二元關(guān)系。 ?例 48： 設 A={a, b, c} 稱的。對任意的 ，則由“” 的定義知：存在 ，使得： .),20(, 2 jin RRjiji ???? 使iniiiRR11 ???? ??iiiniRR ????11?? iniiiRR11 ???? ??iniiniiiRRR ???????111????inik RR1?? ?kRba ??? , ?Aaaa k ?? 121 , ?),(, 012110 baaaRaaRaaRaa kkk ??????????? ? 令?19/57 關(guān)系的運算 由于 |A|=n，所以由鴿巢原理； k+1個元素 中至少有兩個元素相同，不妨設為 ，則可 在 中刪去 后仍有 由關(guān)系的復合運算得： ，其中 ，此時：若 ，則 ；若 ，則重復上述做法，最終總能找到 ，使 得 ，即有 ，由此 有 ，由 k的任意性 ， ∴ kaa ,0 ?)( jiaa ji ??RaaRaaRaa kk ????????? ? , 12110 ?RaaRaaRaa jjiiii ????????? ???? , 1211 ?RaaRaaRaaRaaRaa kkjjii ??????????????? ??? , 1112110 ?39。)(,)(,)) . (3(。 ?2. 關(guān)系圖法 ?定義 ： 設集合 A={ }到 B={ }上的二元關(guān)系 R，以集合 A， B中的元素為頂點，在圖中用“ ο ”表示頂點，若 則可自頂點 向頂點 引有向邊 ，其箭頭指向 ，用這種方法畫出的圖稱為關(guān)系圖 (Graph of Relation)。 對于二元關(guān)系 F，若 ，常記作 ，反之 ；規(guī)定 為 n元空關(guān)系，也是二元空關(guān)系，簡稱空關(guān)系。 例如：平面上的坐標 x, y， x, y R； 操作碼，地址碼 等都是序偶。 ?性質(zhì) ： (1). | A B |=|A| |B|(A, B為有限集合 )； (2). ； (3). 不適合交換律，即 A B ≠B A(除非 A， B= 或 A=B)； (4). 不適合結(jié)合律， (A B) C ≠A (B C)(除非 )； (5). 對 ∪ 和 ∩ 運算滿足分配律， }|,{ ByAxyxBA ??????????????????? AA ，??????????? CBA??3/57 二元關(guān)系及其表示法 證明： (6). ，且當 或 時，逆命題成立。 ?一般來說，若 |A|=m， |B|=n， A到 B上的二元關(guān)系共有 個， A上的共有 個二元關(guān)系； ?