2.1 關(guān)系
序偶
- <x, y>: 兩個(gè)數(shù)值形成一個(gè)pair, 有順序;
- <x1,x2, ..., xn>: 有序n元組;
笛卡爾積
- 集合A<1, 2> X 集合B<a, b, c> = {<1,a>, <1,b>,<1,c>,<2,a>,<2,b>,<2,c>} (AXB)
- 是矩陣的創(chuàng)建運(yùn)算;
關(guān)系(二元關(guān)系為主)
- AXB的關(guān)系就是AXB的子集;
- A上的關(guān)系就是AXA的子集;
- 記號(hào): xRy;
恒等關(guān)系
- 記號(hào): Ix = {<x, x>|x∈X}; 換句話說(shuō), 所有X矩陣主對(duì)角線上的序偶的集合叫做X的恒等關(guān)系;
- X={a, b ,c}; then Ix = {<a,a>, <b,b>, <c,c>};
- 恒等關(guān)系必須遍歷整個(gè)對(duì)角線;
自反和反自反關(guān)系
- 所有的<x, x>都屬于R的話, R就是自反的; 換句話說(shuō), Ix是R的子集;
- 所有的<x, x>都不屬于R的話, R就是反自反的; 換句話說(shuō)對(duì)任意元素∈Ix, 都不在R中;
對(duì)稱和反對(duì)稱關(guān)系
- 對(duì)稱關(guān)系: 所有的xRy都有yRx, R就是對(duì)稱的;
- xRy and yRx coexists ==> R是對(duì)稱的;
- 可以是x==y也可以是x!=y
- {<1,2>, <2,1>, <3,3>}
- 反對(duì)稱關(guān)系: if (xRy && yRx), then {x==y must be true}; 換句話說(shuō), no (x!=y) && (xRy && yRx) shall exist;
- {<1, 1>, <1, 3>, <3, 2>}
- 反對(duì)稱和對(duì)稱關(guān)系的交集
- {<1,1>, <2,2>, <3,3>}, 也就是恒等關(guān)系Ix的一個(gè)子集;
傳遞關(guān)系
- 類似反對(duì)稱關(guān)系
- if (xRy && yRz) {xRz shall exists;} 換句話說(shuō): 不允許已經(jīng)出現(xiàn)xRy&&yRz 卻沒(méi)有xRz;
- e.g. R1 = {<1, 2>, <2, 3>, <1, 3>} R2 = {<1, 3>, <2, 3>}
2.2. 關(guān)系矩陣和關(guān)系圖
關(guān)系矩陣
- 把R中的序偶在矩陣中填上1, 其余XXY的其他位置填上0.
- 注意: XXY矩陣大小為|X|行|Y|列;
- 例如: X={1, 2, 3} Y={5,6,7} XXY矩陣(記住笛卡爾積可以創(chuàng)建矩陣)是3*3規(guī)模;
關(guān)系圖
2.3, 2.4 關(guān)系的運(yùn)算(連接, 逆, 閉包)
連接運(yùn)算
- 對(duì)于XXY, YXZ上的關(guān)系R和S, 生成一個(gè)包含所有滿足<x,y>&&<y,z>的<x, z>的集合;
- 記號(hào): R·S;
- 例如: R={<1,1>, <1,2>} S={<2,3>}, 那么R·S = {<1,3>}
- 關(guān)系的連接本質(zhì)上可以用邏輯門(mén)化的矩陣乘法來(lái)表示, 換句話說(shuō)矩陣上只有1 and 0;
- 矩陣運(yùn)算的規(guī)則, 矩陣左第一行逐個(gè)乘矩陣右第一列, 第二列, 第n列; 第二行逐個(gè)乘矩陣右第一列, 第二列, 第n列.......
逆運(yùn)算
- 對(duì)XXY的關(guān)系R, R的逆, R^(-1), 是YXX上的關(guān)系, 滿足R^(-1) = {<y,x>| <x,y>∈R};
- 相當(dāng)于矩陣的逆關(guān)系;
- 逆關(guān)系的類指數(shù)運(yùn)算性質(zhì)對(duì)交際, 并集和差集運(yùn)算起作用;
閉包運(yùn)算
設(shè)R是集合X上的二元關(guān)系(也就是R在X×X上)
- 自反閉包
- 包含R 最小的 自反關(guān)系 r(R)
- r(R) = R∪Ix;
- 對(duì)稱閉包
- 包含R 最小的 對(duì)稱關(guān)系 s(R)
- s(R) = R∪R逆
- 傳遞閉包
- 包含R 最小的 傳遞關(guān)系 t(R) R^+
- t(R) = ∪(1~無(wú)窮) R^i
- 總存在一個(gè)正整數(shù)k<=n (X為n元集), 使得t(R) = R∪R2∪...∪Rk;
2.5 等價(jià)關(guān)系和相容關(guān)系
覆蓋和劃分
- 覆蓋: ∪(1~n)A[i] = S, 則 集合{A[1], ..., A[n]}是集合S的一個(gè)覆蓋;
- A[1], A[2]等集合可能會(huì)有重疊, 交集的部分;
- 劃分: ∪(1~n)A[i] = S, 且A[1]∩A[2]∩...∩A[n]=?. 則集合{A[1], ..., A[n]}是集合S的一個(gè)劃分;
-
其中A[1]等單個(gè)子集會(huì)被叫做劃分塊.
這是一個(gè)劃分, 劃分屬于覆蓋的特殊形式
等價(jià)關(guān)系
- X上的關(guān)系R, R同時(shí)又自反性, 對(duì)稱性和傳遞性, 那么R是等價(jià)關(guān)系.
- 比如X={1, 2, 3} R1={<1,1>, <2,2>, <3,3>}是等價(jià)關(guān)系, R2={<1,1>, <2,2>, <3, 3>, <1,2>,<2,1> } 也是等價(jià)關(guān)系
- 若X×X上有R是等價(jià)關(guān)系, 那么其中屬于X的一個(gè)元素a, 和同樣屬于X的一個(gè)元素b, 有<a, b>∈R, 那么我們說(shuō)a等價(jià)于b, 即aRb等價(jià)于<a,b>∈R;
- [x][R]稱為x關(guān)于R的等價(jià)類, 也寫(xiě)作[x]; 舉例子, 上面例子R1中的[1] = {1}, R2中[1] = {1, 2};
- 同余類是等價(jià)關(guān)系;
等價(jià)產(chǎn)生劃分定理
- 如果R是X上的一個(gè)等價(jià)關(guān)系, 那么由R可以產(chǎn)生唯一的一個(gè)對(duì)X的劃分;
- 例子: 有一個(gè)動(dòng)物園, 有一個(gè)等價(jià)關(guān)系是貓科動(dòng)物, 那么動(dòng)物園的動(dòng)物們就自動(dòng)形成了一個(gè)劃分, 要么是貓科動(dòng)物, 要么不是貓科動(dòng)物. 一只動(dòng)物, 只能屬于或者不屬于;
相容關(guān)系
- X上的一個(gè)關(guān)系R, 如果只是自反的和對(duì)稱的, 而不能保證傳遞性, 那么則稱R是一個(gè)相容關(guān)系;
- 相容關(guān)系的實(shí)例化: the pair has something in common. compatible relation實(shí)際上顯示了兩個(gè)元素之間有一定的相同性質(zhì), 但是不能保證兩兩之間相同的屬性是一致的; 比如蘋(píng)果a, b都有屬性>500g, 而b, c都有屬性sweet, 我們說(shuō)a, b是相容的, b, c也是相容的; 但是我們不能確定 a,c相容, 也就是說(shuō)不能確定他們有交集;
偏序關(guān)系
偏序關(guān)系定義
- 集合X上的關(guān)系R, 具有自反性, 反對(duì)稱性, 傳遞性, 那么就叫做一個(gè)偏序關(guān)系(≤, Partial Order Relation).
- 注意≤是個(gè)特殊的記號(hào), 不等同于"小于等于", 盡管小于等于是一個(gè)例子.
- 稱呼R為一個(gè)偏序, 一個(gè)集合A與A上的偏序關(guān)系R一起叫作偏序集，記作<A,R>或<A, ≦>, 這么寫(xiě)是為了強(qiáng)調(diào)這個(gè)偏序關(guān)系集合是A的一個(gè)子集, 是建立在A集合上的, 區(qū)別于<B,≤>, <C,≤>。
- 舉例子: 整除關(guān)系. X = {3, 5, 6, 12} R = {<3,3>,<3,6>, <3,12>, <6, 12>}, 3能被3自己整除, 滿足自反性; 6能被3整除, 3反過(guò)來(lái)不能被6整除, 反對(duì)稱; 而6能被3整除, 12能被6整除, 那么12一定能被3整除, 傳遞性;
全序=線性序, 全序集=鏈
- <X, ≤>, 即建立在集合X上的偏序關(guān)系R, 對(duì)所有的, 任意的a, b∈X, 也就是C(2, n)都有a≤b or b≤a(即<a, b>∈R||<b,a>∈R 為true), 那么<X, ≤>是全序集, 此處的≤是X的一個(gè)全序/線性序.
上的一個(gè)全序; - 實(shí)例化: 實(shí)數(shù)關(guān)系中的大于等于關(guān)系 比如X={2,3,4} <X, ≤> = {<3,2>, <4,2>, <4,3>}.
- 全序在HASSE圖上自動(dòng)地體現(xiàn)為一條線;
蓋住
- 偏序關(guān)系中, 如果去掉自反性, 也就是R中刪掉所有<a, a>這種后所剩下的集合, 記作＜;
- 如果a<b且沒(méi)有間隙, 即不存在a<i且i<b; 稱作b蓋住a;
偏序關(guān)系畫(huà)HASSE圖
- 小圓圈表示集合X中的元;
- x<y, 那么x的小圓圈在下面, y的校園選在上面;
- 當(dāng)y蓋住x的是時(shí)候, x和y之間連一條線;
最小元, 最大元, 極小元, 極大元
- 最小, 最大元: 總是的故事: 集合X中若存在有一個(gè)元素z, 滿足所有的元素和其的序偶<e,z>都落在偏序關(guān)系R中, 即e≤z總是對(duì)所有e都成立, 那么稱z為最大元; 最小元同理;
- 極小, 極大元: 不存在的故事: 對(duì)元素a來(lái)說(shuō), 如果集合X中不存在元e, 使得a≤e, 那么我們稱a為一個(gè)極大元; 極小元同理;
- 顯然, 全序集中極大元和最大元是同一個(gè); 對(duì)不是全序的偏序來(lái)說(shuō), 沒(méi)有最大元, 最小元, 因?yàn)閄中存在著a,b無(wú)論如何無(wú)法組成偏序, 所以假設(shè)真的有最小元, 會(huì)出現(xiàn)最小元和其中某元素?zé)o法建立任何偏序關(guān)系的問(wèn)題, 導(dǎo)致矛盾;
上界, 下界, 最小上界(上確界), 最大上界(下確界)
- 集合X的子集A, 存在b∈X, 使得所有a∈A, 有a≤b, 那么b為A的一個(gè)上界; 在X的子集A的在所有上界的集合B中, 若有m滿足了m和任意B中的e組成的序偶<m,e>都是偏序, 也就是m≤e總是成立, 那么說(shuō)m是最小上界, 上確界.
良序
- 對(duì)X上的偏序關(guān)系R, 如果說(shuō)X的每個(gè)非空子集都有最小元, 那么說(shuō)R是一個(gè)良序關(guān)系, 簡(jiǎn)稱良序, 那么<X,≤>被稱為良序集, 良序集強(qiáng)調(diào)了良序關(guān)系集合(關(guān)系是一種集合)所在是X集合, 用來(lái)區(qū)別于<Y,≤>這種建立在Y集合上的良序關(guān)系;
說(shuō)人話: 偏序關(guān)系有最小元.
