二元關系閉包次序等價

1、二元關系閉包次序等價第1頁，共57頁，2022年，5月20日，8點2分，星期日3.3 關系上的閉包運算 3.3.1 逆關系定義 3.31 設 R 是從 A 到 B 的二元關系，關系 R 的逆是一個從 B 到 A 的二元關系，記為定義如下： 例1 (a) I 上的關系 相等關系的逆是相等關系空關系,第2頁，共57頁，2022年，5月20日，8點2分，星期日 z ( y , z R z , x S )定理3.31 設 R 是從 A 到 B 的關系，而 S 是從 B 到 C 的關系，則證 x , y y, x x , y z ( x , z z , y )第3頁，共57頁，2022年，5月20日，8

2、點2分，星期日定理3.32 設 R、R1 和 R2 都是從 A 到B 的二元關系，那么下列各式成立：(a)設 a , b 是 R 的任一元素。那么， b , a a , b a , b R(b) a , b b , a b , a b , a a , b a, b a, b (c)第4頁，共57頁，2022年，5月20日，8點2分，星期日(d) a , b 表示 ABR b , a b , a a, b a, b (e)(f) b , a R1 b , a R2 a , b R1 a , b R2第5頁，共57頁，2022年，5月20日，8點2分，星期日定理3.33 設 R是 A 上的二元關系

3、，那么 R 是對稱的當且僅當證設 ， b , a R R是對稱的設 R 是對稱的， b , a R a , b R a , b R 對于任意的元素對 a , b R 則對于任意的元素對 a , b 第6頁，共57頁，2022年，5月20日，8點2分，星期日3.3.2 關系的閉包運算定義3.32 設R是A上的二元關系, R的自反(對稱,傳遞)閉包是關系R,使 (i) R是自反的(對稱的,傳遞的) (ii) RR (iii)對任何自反的(對稱的,傳遞的)關系R,如果 RR,那么RRR的自反,對稱和傳遞閉包分別記為r(R),s(R)和t(R).R的自反(對稱,傳遞)閉包是包含R并且具有自反(對稱,傳

4、遞)性質的最小關系.第7頁，共57頁，2022年，5月20日，8點2分，星期日構造 R 的自反，對稱和傳遞閉包的方法給 R 補充必要的序偶，使它具有所希望的特性每個結點上都有自回路123自反關系的有向圖G123第8頁，共57頁，2022年，5月20日，8點2分，星期日 定理3.35 設 R 是集合 A 上的二元關系，那么，且 R Rr (R) = REE是 A上相等關系證設 R=RER是自反的，顯然，只需證明最小性假設R”是A上的自反關系，且R” RR”是自反因為 R” E R” RE= R R= r (R)第9頁，共57頁，2022年，5月20日，8點2分，星期日對稱關系的有向圖如果有a到b

5、的弧，一定有b到a的弧123G123第10頁，共57頁，2022年，5月20日，8點2分，星期日 定理3.36 設 R 是集合 A 上的二元關系，那么，R R證顯然，假設R”是對稱的，且R” R又R”是對稱的s (R) = R設 R=R R是對稱的設任 a , b R1) 如果 a , b R a , b R”那么 b , a R b, a R” a , b R”R R” 需證R” Rs (R) = RR 是對稱的當且僅當如果 a , b 2)第11頁，共57頁，2022年，5月20日，8點2分，星期日傳遞關系的有向圖如果從 a 到 b 存在一條有向路徑，則 a 到 b 也存在一條弧12341

6、234G這條弧出現在 Rn 的關系圖中第12頁，共57頁，2022年，5月20日，8點2分，星期日 a，ct (R) 和c，bt (R) Rn+1 t (R) a，bt (R)t (R)是傳遞的， 定理3.37 設 R 是集合 A 上的二元關系，那么 (1) n =1，證（a）(2) 假設 n 時 有 Rn t(R) 成立，設a，bRn+1，現證 n +1 時 Rn+1 t (R) 存在cA，使a，cRn 和c，bRRn+1=RnR若a，b是的任一元素，則存在一 n，使a，bRn，Rn t (R) a，bt (R)先用歸納法證明n 0， Rn t (R)從傳遞閉包定義，得到 R t (R)對一

7、切 n 0， Rn t (R)第13頁，共57頁，2022年，5月20日，8點2分，星期日(b)首先證明是傳遞的。 設 a，b和b， c是 的任意元素，對某整數 s1和 t 1，a，bRs 和 b ，cRt那么a，cRs Rt =Rs+t a，c是傳遞的。t(R)包含于每一含有R的傳遞關系中第14頁，共57頁，2022年，5月20日，8點2分，星期日例2 (a) 整數集合 I 上的關系 (b) 整數集合 I 上的關系 (c) E對稱閉包是關系傳遞閉包是關系自反閉包是自反閉包是對稱閉包是傳遞閉包是自反閉包是對稱閉包是傳遞閉包是(d) 對稱閉包是自反閉包是傳遞閉包是自身自身全域關系自身EEE全域關

8、系自身全域關系傳遞反自反反對稱傳遞自反反對稱傳遞自反對稱 反對稱反自反對稱反自反第15頁，共57頁，2022年，5月20日，8點2分，星期日s (R)(f)設 R 是 I上的關系，xRy 當且僅當 y = x+1，(e)非空集合的空關系對稱閉包自反閉包傳遞閉包自身相等關系那么 t (R)是關系傳遞反自反對稱自身反對稱反自反反對稱r (R)第16頁，共57頁，2022年，5月20日，8點2分，星期日 定理3.37 設 R 是集合 A 上的二元關系，那么定理 3.38 設 R 是集合 A 上的二元關系，這里 |A|= n ， 那么 第17頁，共57頁，2022年，5月20日，8點2分，星期日 例3

9、 設 A = a，b，c，d ，R 如圖 (a)所示，t (R) =則RR2R3R4第18頁，共57頁，2022年，5月20日，8點2分，星期日 (1)如果 R 是自反的，那么s (R)t (R)R 是自反的當且僅當 EA R 若R 是自反的，則 必有EA Rs (R) = R必有EA R s (R) s (R)是自反的必有EA R t (R) t (R)是自反的是自反的證明：定理3.39第19頁，共57頁，2022年，5月20日，8點2分，星期日定理3.39(2)如果 R 是對稱的，那么 r ( R ) t ( R )R 是對稱的r (R) = REE 是對稱的r (R)是對稱的（理由：P9

10、8習題13表）證明：是對稱的第20頁，共57頁，2022年，5月20日，8點2分，星期日如果 R 是對稱的，那么t (R)是對稱的先證 對一切的 n ，R n 是對稱的1) n=1時，R是對稱的顯然成立2) 假設 n 時， R n是對稱的現證 n+1時， R n1也是對稱的 a, b R n1 = R nR 于是 c a, c R n c , b R a, b 是任意的，對一切的 n， R n是對稱的根據假設, 有R n是對稱的和 R 是對稱的 c, a R n , b , c R b, a R R n= R n1 R n+1是對稱的再證t ( R )是對稱的設 a, b t ( R )必存在

11、一 n, a, b R n R n是對稱的 b, a R n b, a t ( R ) a, b 是任意的， t ( R )是對稱的證明：第21頁，共57頁，2022年，5月20日，8點2分，星期日(3)如果 R 是傳遞的，那么 r (R) 是傳遞的證明：設 a, b r ( R ) b, c r ( R )只要能證明 a, c r ( R )即可r (R) = RE 若 a, b E (無論 b, c 屬于哪個集合 ) 則 a = b a, c r ( R ) 若 b, c E (無論 a, b 屬于哪個集合 ) 則 b = c a, c r ( R ) a, b 與 b, c 必在 R 或

12、 E 中 若 a, b R ， b, c RR是傳遞的 a, c r ( R ) a, c r ( R )第22頁，共57頁，2022年，5月20日，8點2分，星期日補充：(3)如果 R 是傳遞的，那么 s (R) 是不一定是傳遞的例如：A = 1，2，3，4 R= 1, 2 ， 2, 3 ， 1, 3 s ( R ) = 1, 2 ， 2, 3 ， 1, 3 ， 2, 1 ， 3, 2 ， 3, 1 不是傳遞的是傳遞的第23頁，共57頁，2022年，5月20日，8點2分，星期日 作業(yè) P109 4. 證自反、對稱、傳遞 8 9 (2) 14(1)第24頁，共57頁，2022年，5月20日，8

13、點2分，星期日注 意：3.4 次序關系 定義3.41 如果集合 A 上的二元關系 R 是自反的， 反對稱的和傳遞的，那么稱 R 為 A 上的偏序。 3.4.1 偏序集合序偶A，R稱為偏序集合如果 R 是偏序,A，R常記為 A， 讀做“小于或等于” R是偏序時，aRb 就記成如果R是集合 A上的偏序，則是 A上的偏序；如果用 表示 R ，可用 表示數集上的小于等于關系是偏序 A， 和A， 都是偏序集合，并互為對偶。a b第25頁，共57頁，2022年，5月20日，8點2分，星期日例1(1) I， 是偏序集合 表示整數中的“小于或等于”關系(2)(A)， 是偏序集合第26頁，共57頁，2022年，

14、5月20日，8點2分，星期日D= M= 例1(3) A=2,4,6,8，D代表整除關系，M代表整倍數關系，則A，D是偏序集合，且互為對偶2,2,4,4,6,6,8,8,2,4,2,6,2,8,4,82,2,4,4,6,6,8,8,4,2,6,2,8,2,8,4A，M第27頁，共57頁，2022年，5月20日，8點2分，星期日x y, xy, 且不存在元素 zA， 使得 x z 且 z y對偏序關系的關系圖作簡化偏序關系自反， 各結點處均有環(huán)，可全部略去。偏序關系反對稱， 任何兩個不同結點之間沒有相互到達的邊， 若把點按從下小上大層次排列，則邊的箭頭方向都是向上，可省略全部箭頭。偏序關系傳遞，

15、可將由傳遞關系可推出的邊省去。D=2,2,4,4,6,6,8,8,2,4,2,6,2,8,4,82468哈斯（Hasse）圖第28頁，共57頁，2022年，5月20日，8點2分，星期日例2(1) P=1，2，3，4，P， 的哈斯圖 = 1, 1,2, 2,3, 3,4, 4,1 , 2 ,1, 3,1, 4,2, 3,2, 4,3, 42431第29頁，共57頁，2022年，5月20日，8點2分，星期日(2) A=2，3，6，12，24，36，A，整除的哈斯圖。D=2, 2,3, 3,6, 6,12, 12,24, 24,36, 36,2, 6, 2, 12, 2, 24, 2, 36, 3,

16、 6 3, 12, 3, 24, 3, 36, 6, 12, 6, 24, 6, 36, 12, 24, 12, 36236122436第30頁，共57頁，2022年，5月20日，8點2分，星期日(3) A=1，2，12，A，整除的哈斯圖。D=1,1,2,2, ,6,6,12,12,1,2,1,3,1,4,1,5,1,6,1,7,1,8,1,9,1,10,1,11,1,12,2,4,2,6, 2,8,2,10,2,12, 3,6,3,9,3,12,4,8,4,12,5,10,6,12第31頁，共57頁，2022年，5月20日，8點2分，星期日A=a,b,c, (A)， 的哈斯圖。補充例第32頁

17、，共57頁，2022年，5月20日，8點2分，星期日由圖所示的哈斯圖， 寫出對應的偏序關系、 關系矩陣。 關系矩陣 A=a, b, c, d, e 偏序關系 = 解:a, a, b, b,c, c, d, d, e, e, 補充例c, a, c, b, d,c，d, a, d,b第33頁，共57頁，2022年，5月20日，8點2分，星期日定義3.42 設A， 是一偏序集合，B是A的子集(1)元素bB是 B 的最大元素，如果對每一元素 xB，xb例3(2)元素bB是 B 的最小元素，如果對每一元素 xB，bx在偏序“整除”下整數1到6的集合(1) B = 1，2，3，6B的最大元素B的最小元素是

18、1是6(2) B=2，3B 沒有最小元素和最大元素(3) B =4B的最大元素B的最小元素是4最大(小)元素要求它與其它元素都可比第34頁，共57頁，2022年，5月20日，8點2分，星期日定理3.41 設A, 是一偏序集合，且 B A，如果B有最大(最小)元素，那么它是唯一的。證：那么 a b b a假設 a 和 b 都是 B 的最大元素當 a 和 b 都是 B 的最小元素時，證明是類似的 是反對稱的a = b結論：最大(最小)元素未必存在，若存在則必唯一。第35頁，共57頁，2022年，5月20日，8點2分，星期日例(A)= 定義3.43 設A， 是一偏序集合，B是 A 的子集 (1) 如

19、果 bB，且 B 中不存在元素 x，使 bx 且 b x，那么元素 bB 叫做 B 的極大元素。 (2) 如果 bB，且 B 中不存在元素 x，使 bx 且 x b，那么元素 bB 叫做 B 的極小元素。集合A =a, b, c的冪集 , a, b, c a , b, a , c,b , c, a , b , c“”關系是一個偏序關系設 B = a , b ,b , c , b, c, 極大元素：a , b ,b , c極小元素最大元素：無最小元素：極大(小)元素不要求它與其它元素都可比，只要沒有比它更大（?。┑脑鼐涂梢缘?6頁，共57頁，2022年，5月20日，8點2分，星期日 如果 a

20、是一下界并且對每一 B 的下界 a有a a，那么元素 aA 叫做 B 的最大下界。定義3.44 設A， 是一偏序集合，B 是 A 的子集(1) 如果對每一 bB，b a，那么元素 aA 叫做 B 的上界；如果對每一 bB，a b，那么元素 aA 叫做 B 的下界。(2) 如果 a 是一上界并且對每一 B 的上界 a有 a a，那么元素 aA 叫做 B 的最小上界。記為glb記為lub注意：第37頁，共57頁，2022年，5月20日，8點2分，星期日例4 (3)考慮偏序集合2,5,6,10,15,30, 整除,其哈斯圖如圖。設B=2,5,6,10,15,30, 那么極小元素：2、5 ；沒有最小元

21、素、下界、最大下界；30是 最大元素、極大元素、上界、最小上界。設B=2,6,10,設B=6,10,15,設B=2,5,設B=2,5,10,第38頁，共57頁，2022年，5月20日，8點2分，星期日結論： 設A， 為偏序集，B A（1）若 b為B的最大(小)元，則 b為B的極大(小)元和最小上(大下)界。 （2）最大(最小)元 未必存在，若存在，則唯一。 （3）若B為非空有限集，則 B 的極大(小)元 恒存在； 但不唯一，若有多個，它們之間不可比。（4）最大(小)元與極大(小)元都必須是子集B中的元素。（6）若b是B的一個上(下)界且bB，那么b是B的最大(小)元。定理3.4-2 3.4-4

22、（5）最小上(大下)界未必存在，若存在，則唯一。 第39頁，共57頁，2022年，5月20日，8點2分，星期日 3.4.2 擬序集合 定義3.45 如果集合A上的二元關系R是傳遞的和反自反的, 那么R叫做A上的擬序.A,R稱為擬序集合. 常借用符號表示擬序。擬序是反對稱的。 證明： 如果xRy和yRx, 由R的傳遞性得xRx, 但這與R的反自反性矛盾, 所以xRyyRx常假,于是 xRyyRxx=y 常真, 【無義證明法】即R是反對稱的.第40頁，共57頁，2022年，5月20日，8點2分，星期日 例5 (1) 實數集合中的是擬序關系 (2) 集合族中的真包含是擬序關系 擬序集合和偏序集合是緊

23、密相關的,唯一區(qū)別是相等關系E. 定理3.45 在集合A上, (1) 如果R是一擬序, 那么r(R)=RE是偏序. (2) 如果R是一偏序, 那么R-E是一擬序.證明：習題12。第41頁，共57頁，2022年，5月20日，8點2分，星期日 3.4.3 線序集合 如果是一偏序, 若ab或ba,我們說a和b是可比較的.偏序集合中的元素不一定都可比較, 所以叫“偏”序. 定義3.46 在偏序集合A,中. 如果每一a,bA, 或者ab,或者ba. 那么叫做A上的線序(或全序), A,叫做線序集合或鏈.第42頁，共57頁，2022年，5月20日，8點2分，星期日 例6 (1)P= ,a,a,b,a,b,

24、c,P,是線序集合,其哈斯圖如圖3.48所示 (2)I,是線序集合,其哈斯圖(不完全)如圖3.49所示 (4)1,2,3,6,整除不是線序集合; 如果A是多于一個元素的集合, 那么(A),不是線序集合. 圖3.48 圖3.49 第43頁，共57頁，2022年，5月20日，8點2分，星期日作業(yè) P1191. (3) (5)5. 良序集合改為等價關系610.(2) 提示R含義，保持R所有性質12第44頁，共57頁，2022年，5月20日，8點2分，星期日3.5 等價關系和劃分 定義3.51如果集合A上的二元關系 R 是自反的，對稱的和傳遞的，那么稱 R 是等價關系。 3.5.1 等價關系設 R 是

25、 A上的等價關系， a，b，c 是 A 的任意元素如果 aRb記作 a b讀做“ a 等價于 b ”第45頁，共57頁，2022年，5月20日，8點2分，星期日等價關系：自反的，對稱的和傳遞的(1) 自反性(2) 對稱性(3) 傳遞性有向圖上，每一結點都有自回路有向圖上，如果有從 a 到 b 的弧，那么也有從 b 到 a 的弧有向圖上，如果從 a 到 c 有一條路徑，則從 a 到 c 有一條弧每一元素都和自己等價如果 a 等價于 b，則 b 也等價于a如果 a 等價于b，b 等價于c，則 a 等價于c第46頁，共57頁，2022年，5月20日，8點2分，星期日R= 例1 (1) 同學集合A =

26、 a，b，c，d，e，f R：“住在同一房間”等價關系現假設 a 和 b 同住一間，d，e，f 同住一間，c 住一間則 a,a, b,b,c,c,d,d,e,e,f,f, a,b,b,a, d,e,e,d,e,f,f,e,d,f,f,d 每個連通分圖是完全圖每一結點都有自回路，每兩結點間有兩條不同方向的邊第47頁，共57頁，2022年，5月20日，8點2分，星期日(iii) x y zx y z xRyyRzxRz (2) 數中的相等關系集合中的相等關系命題演算中的 關系等價關系(3) 空集合 中的二元關系 R(i) x (x xRx)(ii) x yx y xRy yRx自反的等價關系對稱的

27、傳遞的(4) 集合 A 上的全域關系 R= AA等價關系第48頁，共57頁，2022年，5月20日，8點2分，星期日定義3.52 設 k 是一正整數而 a，b I。如果對某整數 m，a-b = mk，那么 a 和 b 是模 k 等價。 整數 k 叫做等價的模數 ab ( mod k )寫成第49頁，共57頁，2022年，5月20日，8點2分，星期日 (iii) 設 a b(mod k) 和 b c (mod k)，定理3.51 模 k 等價是任何集合 A I上的等價關系(1) 如果 A =，證:是等價關系(2) 如果 A 則(i) 對任一a，a - a = 0k，自反的(ii) a b (mod k)時，那么存在 m1，m2I，使 a-b = m1k 和 b-c =m2k，將兩等式兩邊相加，a-c = (m1+m2)k， a c(mod k) a a (mod k) b a (mod k)存在某 mI，使 a-b = mk， b-a = -mk，對稱的傳遞的第50頁，共57頁，2022年，5月20日，8點2分，星期日定義3.53 設 R 是集合 A上等價關系，對每一a A，a 關于R 的等價類是集合對每一 a A，等價類 aR 非空aR xxRa 簡記為aa 為等價類a的表示元素 a a R