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