《離散數(shù)學(xué)二元關(guān)系.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)二元關(guān)系.ppt（48頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、1 定義 7.1 由兩個(gè)元素 x 和 y，按照一定的順序組成的 二元組稱為有序?qū)蛐蚺?，記?，其中 x是它 的第一元素， y是它的第二元素 . 注：有序?qū)哂腥缦滦再|(zhì)： （ 1）有序性 （當(dāng) xy 時(shí)） （ 2） 與 相等的充分必要條件是 x=u且 y=v. 這些性質(zhì)是二元集 x,y所不具備的 .例如當(dāng) xy 時(shí) 有 x,y=y,x. 第一節(jié) 有序?qū)εc笛卡兒 一、有序?qū)?第七章 二元關(guān)系 2 二、笛卡兒積 定義 7.2 設(shè) A,B 為集合，用 A中元素為第一元素 ,B中 的元素為第二元素構(gòu)成有序?qū)?.所有這樣的有序?qū)M 成的集合叫做 A 與 B 的笛卡兒積 ,記作 A B. 笛卡兒積的符號(hào)化
2、表示為 A B = | x A y B 例 A=1,2,3, B=a,b,c A B = , , B A = , , 3 注 :笛卡兒積的性質(zhì) （ 1）不適合交換律 A B B A (AB, A, B) （ 2）不適合結(jié)合律 (A B) C A (B C) (A, B, C) （ 3）對(duì)于并或交運(yùn)算滿足分配律 A (B C) = (A B) (A C) (B C) A = (B A) (C A) A (BC) = (A B)(A C) (BC) A = (B A)(C A) （ 4）若 A 或 B 中有一個(gè)為空集，則 A B 就是空集 . A = B = （ 5）若 |A| = m, |B|
3、= n, 則 |A B| = mn 4 例 7.2 設(shè) 2,1A , 求 AAP )( . 解 AAP )( 2,2,1,1,2,1 ,2,2,1,2,2,1,1,1,2,1, 2,12,1,2,1, 5 例 7.3 （ 1) 證明 A=B,C=D A C=B D （ 2） A C = B D 是否推出 A=B,C=D? 為什么？ 解 （ 1）任取 A C x A y C x B y D B D （ 2) 不一定 .反例如下： A=1， B=2, C = D = , 則 A C = B D 但是 A B. 6 第二節(jié) 二元關(guān)系 一、二元關(guān)系的定義 定義 7.3 如果一個(gè)集合滿足以下條件之一：
4、（ 1）集合非空 , 且它的元素都是有序?qū)?（ 2）集合是空集 則稱該集合為一個(gè)二元關(guān)系 , 簡稱為關(guān)系，記作 R. 如果 R, 可記作 xRy；如果 R, 則記作 x y. 例： R=, S=,a,b.則 R 是二 元關(guān)系 , 當(dāng) a,b 不是有序?qū)r(shí)， S 不是二元關(guān)系 .根據(jù) 上面的記法，可以寫 1R2, aRb, a c 等 . 7 二、從 A到 B的關(guān)系與 A上的關(guān)系 定義 7.4 設(shè) A,B 為集合 ,A B 的任何子集所定義的二 元關(guān)系叫做從 A 到 B 的二元關(guān)系 ,當(dāng) A=B 時(shí)則叫做 A 上 的二元關(guān)系 . 例 A=0,1, B=1,2,3, 那么 R1=, R2=A B,
5、 R3=, R4= R1, R2, R3, R4 是從 A 到 B 的二元關(guān)系 , R3和 R4同時(shí) 也是 A 上的二元關(guān)系 . 8 三、 A 上重要關(guān)系的實(shí)例 定義 7.5 設(shè) A 為任意集合 ,是 A 上的關(guān)系，稱為空 關(guān)系 ,EA ,IA分別稱為全域關(guān)系與恒等關(guān)系 ,其中 EA = | x A y A = A A, IA = | x A. 例如 , A=1,2, 則 EA = , , IA = , . 9 特定集合上的小于等于關(guān)系 LA、整除關(guān)系 DA、包 含關(guān)系 R定義如下： LA = | x,y A xy, 這里 AR， R 為實(shí) 數(shù)集合 , DA = | x,y B x 整除 y,
6、 這里 AZ* , Z* 為非 0 整數(shù)集合 , R = | x,y A xy, 這里 A 是集合族 . 10 四 、關(guān)系的表示 表示一個(gè)關(guān)系的方式有三種：關(guān)系的集合表達(dá)式、關(guān)系 矩陣、關(guān)系圖 . 關(guān)系矩陣和關(guān)系圖的定義 (1) 關(guān)系矩陣 若 , 2121 nm yyyBxxxA ， R 是從 A 到 B 的關(guān) 系， R 的 關(guān) 系 矩 陣 是 布 爾 矩 陣 nmijR rM , 其中 RyxrRyxr jiijjiij ,0,1 . 11 (2) 關(guān)系圖 , 21 nxxxA ， R 是從 A 上的關(guān)系， R 的關(guān)系圖是 RAG R , , 其中 A 為結(jié)點(diǎn)集， R 為邊集 . 如果 ji
7、 yx , 屬于 關(guān)系 R ，在圖中就有一條從 ix 到 jx 的有向邊 . 注： (1) 關(guān)系矩陣適合表示從 A 到 B 的關(guān)系或者 A 上 的關(guān) 系（ A , B 為有窮集） (2) 關(guān)系圖適合表示有窮集 A 上的關(guān)系 12 例 A =1,2,3,4, R =, R 的關(guān)系矩陣 RM 和關(guān)系圖 RG 如下： 0010 0000 1100 0011 R M , 13 第三節(jié) 關(guān)系的運(yùn)算 一、關(guān)系的基本運(yùn)算定義 1 定義域、值域與域 定義 7.6 設(shè) R 是二元關(guān)系 . (1) R 中所有的有序?qū)Φ牡谝辉貥?gòu)成的集合稱為 R 的定義域 , 記作 domR, 即 dom R = x | y (
8、R ) (2) R 中所有的有序?qū)Φ牡诙貥?gòu)成的集合稱為 R 的值域 , 記 作 ranR, 即 ran R = y | x ( R ) (3) R 的定義域和值域的并集稱為 R 的域 , 記作 fldR, 即 fld R = dom R ran R 14 例 R =, 則 dom R =1, 2, 4 ran R =2, 3, 4 fld R =1, 2, 3, 4 2 逆與合成 定義 7.7 設(shè) R 是二元關(guān)系 ,R 的逆關(guān)系 , 簡稱 R 的逆 , 記作 R 1 , 其中 R 1 = | R 定義 7.8 設(shè) F,G 為二元關(guān)系， G 對(duì) F 的右復(fù)合 記作 F G, 其中 F G =
9、 | t ( F G ) 15 3 限制與像 定義 7.9 設(shè) R 為二元關(guān)系 , A 是集合 （ 1 ） R 在 A 上的限制記作 R A , 其中 R A = | xRy x A （ 2 ） A 在 R 下的像記作 R A , 其中 R A =ran( R A ) 注 ： R 在 A 上的限制 R A 是 R 的子關(guān)系，即 R A R ， 而 A 在 R 下的像 R A 是 ran R 的子集，即 R A ran R . 例 設(shè) R =, 則 R 1=, , R = , R 2,3=, , R 1=2,3 , R = , R 3=2 . 16 二、關(guān)系運(yùn)算的性質(zhì) 定理 7.1 設(shè) F 是任
10、意的關(guān)系 , 則 (1) (F 1 ) 1 =F (2) dom F 1 = ran F , ran F 1 = dom F 證 （ 1 ）任取 , 由逆的定義有 (F 1 ) 1 F 1 F . 所以有 (F 1 ) 1 =F . （ 2 ）任取 x , x dom F 1 y ( F 1 ) y ( F ) x ran F 所以有 dom F 1 = ran F . 同理可證 ran F 1=dom F . 17 定理 7.2 設(shè) F , G , H 是任意的關(guān)系 , 則 (1) ( F G ) H = F ( G H ) (2) ( F G ) 1 = G 1 F 1 證 (1) 任取
11、, ( F G ) H t ( F G H ) t ( s ( F G ) H ) t s ( F G H ) s ( F t ( G H ) s ( F G H ) F ( G H ) 所以 ( F G ) H = F ( G H ) . 18 （ 2 ）任取 , ( F G ) 1 F G t ( F G ) t ( G 1 F 1 ) G 1 F 1 所以 ( F G ) 1 = G 1 F 1 . 定理 7.3 設(shè) R 為 A 上的關(guān)系 , 則 R I A = I A R = R . 19 定理 7.4 (1) F ( G H ) = F G F H (2) ( G H ) F = G
12、 F H F (3) F ( G H ) F G F H (4) ( G H ) F G F H F 證 (3) 任取 , F ( G H ) t ( F G H ) t ( F G H ) t ( F G ) ( F H ) t ( F G ) t ( F H ) F G F H F G F H 所以有 F ( G H )= F G F H . 20 定理 7.5 設(shè) F 為關(guān)系 , A , B 為集合 , 則 (1) F ( A B ) = F A F B (2) F A B = F A F B (3) F ( A B ) = F A F B (4) F A B F A F B 證 (1)
13、 任取 F ( A B ) F x A B F ( x A x B ) ( F x A ) ( F x B ) F A F B F A F B 所以有 F ( A B ) = F A F B . 21 三、 A 上關(guān)系的冪運(yùn)算 定義 7.10 設(shè) R 為 A 上的關(guān)系 , n 為自然數(shù) , 則 R 的 n 次 冪定義為： （ 1 ） R 0 =| x A = IA （ 2 ） R n +1 = R n R 注 ： 對(duì)于 A 上的任何關(guān)系 R 1 和 R 2 都有 AIRR 0 2 0 1 . 關(guān)系的冪的計(jì)算： 給定 A 上的關(guān)系 R 和自然數(shù) n ，怎樣計(jì)算 n R 呢？若 n 是 0 或 1
14、 ，結(jié)果是很簡單的 . 下面考慮 2n 的情況 . 如果 R 是用 集合表達(dá)式 給出的，可以通過 1n 次合成計(jì)算得到 nR . 22 如果 R 是用 關(guān)系矩陣 M 給出的，則 n R 的關(guān)系矩陣 是 n M ，即 n 個(gè)矩陣 M 之積 . 與普通矩陣乘法不同的是， 其中的相加是邏輯加，即 1 1 1 , 1 0 0 1 1 , 0 0 0 . 如果 R 是用 關(guān)系圖 G 給出的，可以直接由圖 G 得到 n R 的 關(guān)系圖 G . G 的頂點(diǎn)集與 G 相同 . 考察 G 的每個(gè)頂點(diǎn) i x ，如果在 G 中從 i x 出發(fā)經(jīng)過 n 步長的路徑到達(dá)頂點(diǎn) j x ， 則在 G 中加一條從 i x
15、到 j x 的邊 . 當(dāng)把所有這樣的邊都找 到以后，就得到圖 G . 23 例 7.2.3 設(shè) , , , A a b c d ， , , , , , , , R a b b a b c c d ， 求 R 的各次冪，分別用矩陣和關(guān)系圖表示 . 解 R 的關(guān)系矩陣為 0 1 0 0 1 0 1 0 0 0 0 1 0000 M ，則 234,R R R 的關(guān)系矩陣分別 是 2 1 0 1 0 0 1 0 1 0000 0000 M M M ， 32 0 1 0 1 1 0 1 0 0000 0000 M M M ， 43 1 0 1 0 0 1 0 1 0000 0000 M M M . 24
16、 因此 42 MM ， 53 RR ， . 所以可以得到 2 4 6 RRR ， 3 5 7 R R R ，而 0 R ，即 為 A I 的關(guān)系矩 陣 . 至此， R 各次冪的關(guān)系矩陣都得到了 . 用關(guān)系圖的方法得到 0 1 2 3 , , , ,R R R R 的關(guān)系圖如下圖所示 . 25 第四節(jié) 關(guān)系的性質(zhì) 一、五種性質(zhì)的定義 1 自反性與反自反性 定義 7.11 設(shè) R 為 A 上的關(guān)系 , （ 1 ）若 x ( x A R ), 則稱 R 在 A 上是自反的 . （ 2 ）若 x ( x A R ), 則稱 R 在 A 上是反自反的 . 例如： 自反關(guān)系：全域關(guān)系 EA , 恒等關(guān)系
17、IA , 小于等于關(guān)系 LA , 整除關(guān)系 DA ； 反自反關(guān)系：實(shí)數(shù)集上的小于關(guān)系、冪集上的真包含 關(guān)系 . 例 設(shè) A =1,2,3, R 1 , R 2 , R 3 是 A 上的關(guān)系 , 其中 R 1 , , R 2 , , R 3 則 R 2 是自反的， R 3 是反自反的， R 1 既不是自反的也不是反自反的 . 26 2 對(duì)稱性與反對(duì)稱性 定義 7.12 設(shè) R 為 A 上的關(guān)系 , （ 1 ）若 x y ( x , y A R R ), 則稱 R 為 A 上 對(duì)稱的關(guān)系 . （ 2 ）若 x y ( x , y A R R x = y ), 則稱 R 為 A 上的反對(duì)稱關(guān)系 .
18、例如： 對(duì)稱關(guān)系： A 上的全域關(guān)系 EA , 恒等關(guān)系 IA 和空關(guān)系 反對(duì)稱關(guān)系：恒等關(guān)系 IA 和空關(guān)系也是 A 上的反對(duì)稱關(guān)系 . 例 設(shè) A 1,2,3, R 1 , R 2 , R 3 和 R 4 都是 A 上的關(guān)系 , 其中 R 1 , ， R 2 , R 3 , ， R 4 , 則 R 1 既是對(duì)稱也是反對(duì)稱的 , R 2 是對(duì)稱的但不是反對(duì)稱的 , R 3 是反 對(duì)稱的但不是對(duì)稱的 , R 4 既不是對(duì)稱的也不是反對(duì)稱的 . 27 3 傳遞性 定義 7.13 設(shè) R 為 A 上的關(guān)系 , 若 x y z ( x , y , z A R R R ), 則稱 R 是 A 上的傳遞
19、關(guān)系 . 例如 : A 上的全域關(guān)系 E A , 恒等關(guān)系 I A 和空關(guān)系 , 小于等于 和小于關(guān)系，整除關(guān)系，包含與真包含關(guān)系 . 例 設(shè) A 1,2,3, R 1 , R 2 , R 3 是 A 上的關(guān)系 , 其中 R 1 , , R 2 , , R 3 , 則 R 1 和 R 3 是 A 上的傳遞關(guān)系 , R 2 不是 A 上的傳遞關(guān)系 . 28 二關(guān)系性質(zhì)的等價(jià)描述 下面給出這五種性質(zhì)成立的充分必要條件 . 定理 7.9 設(shè) R 為 A 上的關(guān)系 , 則 （ 1 ） R 在 A 上自反當(dāng)且僅當(dāng) I A R （ 2 ） R 在 A 上反自反當(dāng)且僅當(dāng) R I A = （ 3 ） R 在
20、A 上對(duì)稱當(dāng)且僅當(dāng) R = R 1 （ 4 ） R 在 A 上反對(duì)稱當(dāng)且僅當(dāng) R R 1 I A （ 5 ） R 在 A 上傳遞當(dāng)且僅當(dāng) R R R 29 三、關(guān)系性質(zhì)的三種等價(jià)條件 自反性 反自反性 對(duì)稱性 反對(duì)稱性 傳遞性 邏 輯 表 達(dá) 式 ( ) x x A x Rx ( ) x x A x Rx ( ) x y x A y A xR y yR x ( ) x y x A y A xR y yR x x y ( ) x y z x A y A z A xR y yR z xR z 集 合 表 達(dá) 式 AIR ARI 1RR 1 AR R I R R R 關(guān) 系 矩 陣 主對(duì)角線 元素全
21、是 1 主對(duì)角線 元素全是 0 矩陣是對(duì)稱 矩陣 若 1ijr ，且 ij ， 則 0jir 對(duì) 2 M 中 1 所 在位置， M 中 相應(yīng)的位置都 是 1 關(guān) 系 圖 每個(gè)頂點(diǎn) 都有環(huán) 每個(gè)頂點(diǎn) 都沒有環(huán) 如果兩個(gè)頂 點(diǎn)之間有邊， 一定是一對(duì) 方向相反的 邊 ( 無單邊 ) 如果兩點(diǎn)之間 有邊，一定是 一條有向邊 ( 無雙向邊 ) 如果頂點(diǎn) ix 到 jx 有邊， jx 到 kx 有邊，則從 ix 到 kx 也有邊 30 例 判斷下圖中關(guān)系的性質(zhì) , 并說明理由 . （ 1 ） （ 2 ） （ 3 ） 解 : （ 1 ）不是自反也不是反自反的；對(duì)稱的 , 不是反對(duì)稱的； 不是傳遞的 . （
22、2 ）是反自反但不是自反的；是反對(duì)稱的但不 是對(duì)稱的；是傳遞的 . （ 3 ）是自反但不是反自反的；是反對(duì) 稱的但不是對(duì)稱的；不是傳遞的 . 31 第五節(jié) 關(guān)系的閉包 一、閉包定義 定義 7.14 設(shè) R 是非空集合 A 上的關(guān)系 , R 的自反（對(duì) 稱或傳遞）閉包是 A 上的關(guān)系 R , 使得 R 滿足以下條 件： （ 1 ） R 是自反的（對(duì)稱的或傳遞的） （ 2 ） R R （ 3 ）對(duì) A 上任何包含 R 的自反（對(duì)稱或傳遞）關(guān)系 R 有 R R . 一般將 R 的自反閉包記作 r ( R ), 對(duì)稱閉包記作 s ( R ), 傳 遞閉包記作 t ( R ). 32 二、閉包的構(gòu)造方法
23、 1 集合表示 定理 設(shè) R 為 A 上的關(guān)系 , 則有 （ 1 ） r ( R )= R R 0 （ 2 ） s ( R )= R R 1 （ 3 ） t ( R )= R R 2 R 3 說明：對(duì)于有窮集合 A (| A |= n ) 上的關(guān)系 ,(3) 中的并最 多不超過 R n . 證明思路：（ 1 ）和（ 2 ）證明右邊的集合滿足閉包定義 的三個(gè)條件 . （ 3 ）采用集合相等的證明方法 . 證明左邊包 含右邊，即 t ( R ) 包含每個(gè) R n . 證明右邊包含左邊，即 R R 2 R 3 具有傳遞的性質(zhì) . 33 2. 矩陣表示和圖表示 設(shè)關(guān)系 R , r ( R ), s (
24、 R ), t ( R ) 的關(guān)系矩陣分別為 M , M r , M s 和 M t , 則 M r = M + E ， M s = M + M ， M t = M + M 2 + M 3 + ， 其中 E 是和 M 同 階的單位矩陣 , M 是 M 的轉(zhuǎn)置矩陣 . 注意在上述等式中矩 陣的元素相加時(shí)使用邏輯加 . 設(shè)關(guān)系 R , r ( R ), s ( R ), t ( R ) 的關(guān)系圖分別記為 G , G r , G s , G t , 則 G r , G s , G t 的頂點(diǎn)集與 G 的頂點(diǎn)集相等 . 除了 G 的邊以 外 , 以下述方法添加新的邊 . 考察 G 的每個(gè)頂點(diǎn) , 如果
25、沒 有環(huán)就加上一個(gè)環(huán) . 最終得到的是 G r . 考察 G 的每一條邊 , 如果有一條 x i 到 x j 的單向邊 , i j , 則在 G 中加一條 x j 到 x i 的反方向邊 . 最終得到 G s . 考察 G 的每個(gè)頂點(diǎn) x i , 找從 x i 出 發(fā)的所有 2 步 , 3 步 , , n 步長的路徑（ n 為 G 中的頂 點(diǎn)數(shù)） . 設(shè)路徑的終點(diǎn)為 x j1 ,x j2 ,x jk , 如果沒有從 x i 到 x jl ( l =1,2, k ) 的邊 , 就加上這條邊 . 當(dāng)檢查完所有的頂點(diǎn) 后就得到圖 G t . 34 例 設(shè) A = a , b , c , d , R
26、=, R 和 r ( R ), s ( R ), t ( R ) 的關(guān)系圖如下圖所示 . 35 三、閉包的主要性質(zhì) 定理 7.11 設(shè) R 是非空集合 A 上的關(guān)系 , 則 （ 1 ） R 是自反的當(dāng)且僅當(dāng) r ( R )= R . （ 2 ） R 是對(duì)稱的當(dāng)且僅當(dāng) s ( R )= R . （ 3 ） R 是傳遞的當(dāng)且僅當(dāng) t ( R )= R . 定理 7.12 設(shè) R 1 和 R 2 是非空集合 A 上的關(guān)系 , 且 R 1 R 2 , 則 （ 1 ） r ( R 1 ) r ( R 2 ) （ 2 ） s ( R 1 ) s ( R 2 ) （ 3 ） t ( R 1 ) t ( R
27、2 ) 定理 7.13 設(shè) R 是非空集合 A 上的關(guān)系 , （ 1 ）若 R 是自反的 , 則 s ( R ) 與 t ( R ) 也是自反的 . （ 2 ）若 R 是對(duì)稱的 , 則 r ( R ) 與 t ( R ) 也是對(duì)稱的 . （ 3 ）若 R 是傳遞的 , 則 r ( R ) 是傳遞的 . 36 第六節(jié) 等價(jià)關(guān)系與劃分 一、 等價(jià)關(guān)系的定義與實(shí)例 定義 7.15 設(shè) R 為非空集合上的關(guān)系 . 如果 R 是自反 的、對(duì)稱的和傳遞的 , 則稱 R 為 A 上的等價(jià)關(guān)系 . 設(shè) R 是 一個(gè)等價(jià)關(guān)系 , 若 R , 稱 x 等價(jià)于 y , 記做 x y . 例 設(shè) A =1,2,8,
28、如下定義 A 上的關(guān)系 R ： R =| x , y A x y (mod 3) 其中 x y (mod 3) 叫做 x 與 y 模 3 相等 , 即 x 除以 3 的 余數(shù)與 y 除以 3 的余數(shù)相等 . 37 不難驗(yàn)證 R 為 A 上的等價(jià)關(guān)系 , 因?yàn)?x A , 有 x x (mod 3) x , y A , 若 x y (mod 3), 則有 y x (mod 3) x , y , z A , 若 x y (mod 3), y z (mod 3), 則有 x z (mod 3) 模 3 等價(jià)關(guān)系的關(guān)系圖 38 二、等價(jià)類及其性質(zhì) 1 等價(jià)類 定義 7.16 設(shè) R 為非空集合 A 上
29、的等價(jià)關(guān)系 , x A ， 令 x R = y | y A xRy 稱 x R 為 x 關(guān)于 R 的等價(jià)類 , 簡稱為 x 的等價(jià)類 , 簡記 為 x 或 x . 例如 A=1, 2, , 8 上模 3 等價(jià)關(guān)系的等價(jià)類： 1 = 4 = 7 = 1, 4, 7 2 = 5 = 8 = 2, 5, 8 3 = 6 = 3, 6 39 2 等價(jià)類的性質(zhì) 定理 7.14 設(shè) R 是非空集合 A 上的等價(jià)關(guān)系 , 則 （ 1 ） x A , x 是 A 的非空子集 . （ 2 ） x , y A , 如果 xRy , 則 x = y . （ 3 ） x , y A , 如果 x y , 則 x 與
30、y 不交 . （ 4 ） x | x A = A . 三、商集與集合的劃分 1. 商集 定義 7.17 設(shè) R 為非空集合 A 上的等價(jià)關(guān)系 , 以 R 的 所有等價(jià)類作為元素的集合稱為 A 關(guān)于 R 的商集 , 記做 A / R , 即 A / R = x R | x A . 40 2 集合的劃分 定義 7.18 設(shè) A 為非空集合 , 若 A 的子集族 ( P ( A ) 滿足下面條件： （ 1 ） （ 2 ） x y ( x , y x y x y = ) （ 3 ） = A 則稱 是 A 的一個(gè)劃分 , 稱 中的元素為 A 的劃分塊 . 例 設(shè) A a , b , c , d , 給定
31、 1 , 2 , 3 , 4 , 5 , 6 如下： 1 = a , b , c , d ， 2 = a , b , c , d 3 = a , a , b , c , d ， 4 = a , b , c 5 = , a , b , c , d ， 6 = a , a , b , c , d 則 1 和 2 是 A 的劃分 , 其他都不是 A 的劃分 . 41 四、商集與劃分的對(duì)應(yīng)關(guān)系 商集 A / R 就是 A 的一個(gè)劃分 , 不同的商集對(duì)應(yīng)于不同 的劃分 . 任給 A 的一個(gè)劃分 , 如下定義 A 上的關(guān)系 R ： R =| x , y A x 與 y 在 的同一劃分塊中 則 R 為 A
32、上的等價(jià)關(guān)系 , 且該等價(jià)關(guān)系所確定的商集就 是 . 注 : A 上的等價(jià)關(guān)系與 A 的劃分是一一對(duì)應(yīng)的 . 42 第七節(jié) 偏序關(guān)系 一、偏序關(guān)系 1 定義 7.19 偏序關(guān)系：非空集合 A 上的自反、反對(duì)稱和傳遞的關(guān) 系，記作 . 設(shè) 為偏序關(guān)系 , 如果 , 則記作 x y , 讀作 x “ 小于或等于 ” y . 2. 實(shí)例 集合 A 上的恒等關(guān)系 I A 是 A 上的偏序關(guān)系 . 小于或等于關(guān)系 , 整除關(guān)系和包含關(guān)系也是相應(yīng)集合上 的偏序關(guān)系 . 43 3 相關(guān)概念 定義 7.20 設(shè) R 為非空集合 A 上的偏序關(guān)系 , x , y A , x 與 y 可比 x y y x . 任
33、取兩個(gè)元素 x 和 y , 可能有下述幾種情況發(fā)生： x y ( 或 y x ), x y , x 與 y 不是可比的 . 定義 7.21 R 為非空集合 A 上的偏序關(guān)系 , x , y A , x 與 y 都是可比的，則稱 R 為全序（或線序） 例 如 ：數(shù)集上的小于或等于關(guān)系 是全序關(guān)系 , 整除關(guān)系 不是正整數(shù)集合上的全序關(guān)系 定義 7.22 x , y A , 如果 x y 且不存在 z A 使得 x z y , 則稱 y 覆蓋 x . 例如 : 1,2,4,6 集合上的整除關(guān)系 , 2 覆蓋 1, 4 和 6 覆 蓋 2. 但 4 不覆蓋 1. 44 二、偏序集與哈斯圖 1 偏序集
34、 定義 7.23 集合 A 和 A 上的偏序關(guān)系 一起叫做偏序集 , 記作 . 例如 ：整數(shù)集合 Z 和數(shù)的小于或等于關(guān)系 構(gòu)成偏序 集 , 集合 A 的冪集 P ( A ) 和包含關(guān)系 R 構(gòu)成偏序集 . 2 哈斯圖 利用偏序關(guān)系的自反、 反對(duì)稱、傳遞性進(jìn)行簡化的關(guān) 系圖 特點(diǎn)： （ 1 ） 每個(gè)結(jié)點(diǎn)沒有環(huán) ； （ 2 ） 兩個(gè)連通的結(jié)點(diǎn) 之間的序關(guān)系通過結(jié)點(diǎn)位置的高低表示，位置低的元素的 順序在前 ； （ 3 ） 具有覆蓋關(guān)系的兩個(gè)結(jié)點(diǎn)之間連邊 . 45 例 偏序集 和 的哈斯圖 . 46 例 已知偏序集 的哈斯圖如下圖所示 , 試求出集 合 A 和關(guān)系 R 的表達(dá)式 . 解 A = a
35、, b , c , d , e , f , g , h , R =, I A 47 三、偏序集中的特殊元素 1. 最小元、最大元、極小元、極大元 定義 7.24 設(shè) 為偏序集 , B A , y B . （ 1 ）若 x ( x B y x ) 成立 , 則稱 y 為 B 的最小元 . （ 2 ）若 x ( x B x y ) 成立 , 則稱 y 為 B 的最大元 . （ 3 ）若 x ( x B x y x = y ) 成立 , 則稱 y 為 B 的極小元 . （ 4 ）若 x ( x B y x x = y ) 成立 , 則稱 y 為 B 的極大元 . 性質(zhì)： (1) 對(duì)于有窮集，極小元和極大元一定存在，還可能存在 多個(gè) . (2) 最小元和最大元不一定存在，如果存在一定惟一 . (3) 最小元一定是極小元；最大元一定是極大元 . (4) 孤立結(jié)點(diǎn)既是極小元，也是極大元 . 48 例 設(shè)偏序集 如下圖所示，求 A 的極小元、最小 元、極大元、最大元 . 設(shè) B b , c , d , 求 B 的下界、上界、 下確界、上確界 . 解 極小元： a , b , c , g ； 極大元： a , f , h ；沒有最小 元與最大元 . B 的下界和最大下界都不存在 , 上界有 d 和 f , 最小上界為 d .
離散數(shù)學(xué)二元關(guān)系.ppt
