離散數(shù)學(xué)二元關(guān)系

《離散數(shù)學(xué)二元關(guān)系》由會員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)二元關(guān)系（107頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 1 第7章 二元關(guān)系7.1 有 序 對 與 笛 卡 兒 積7.2 二 元 關(guān) 系7.3 關(guān) 系 的 運(yùn) 算7.4 關(guān) 系 的 性 質(zhì)7.5 關(guān) 系 的 閉 包7.6 等 價 關(guān) 系 和 劃 分7.7 偏 序 關(guān) 系 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 2 7.1 有序?qū)εc笛卡爾積7.1.1 有 序 對 的 定 義7.1.2 集 合 的 笛 卡 爾 積7.1.3 有 序 n 元 組 和 n 階 笛 卡 爾 積 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 3 7.1.1 有序?qū)Φ亩x定 義 7.1：兩 個 元

2、素 x,y組 成 的 有 序 序 列 x,y ， 稱 為 一 個 有 序?qū)?（ 序 偶 、 二 元 組 ） 。例 ：直 角 坐 標(biāo) 系 中 點(diǎn) 的 坐 標(biāo) x,y日 期 的 表 示 ： y,m 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 4 7.1.1 有序?qū)Φ亩x性 質(zhì) ： 當(dāng) x y時 ， x， y y， x x， y u， v x u y v例 7.1： ， 求 x, y。解 ： x 2 5, 2x y 4 x 3, y 2 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 5 7.1.2 集合的笛卡爾積定 義 7.2： 集 合 A與 B的 笛 卡 兒 乘 積 A B

3、x,y |x A y B例 ： 設(shè) A a , b， B 0， 1， 2， C ，計(jì) 算 A B， B A， A C， A A。解 ： A B a,0 , a,1 , a,2 , b,0 , b,1 , b,2 B A 0,a , 0,b , 1,a , 1,b , 2,a , 2,b A C A A a,a , a,b , b,a , b,b （ A A可 記 作 A2 ）例 7.2： A = 1， 2, 求 P(A)A。 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 6 7.1.2 集合的笛卡爾積集 合 的 笛 卡 兒 積 的 性 質(zhì) ：性 質(zhì) 1： 若 |A| m, |B| n

4、, 則 |AB| mn性 質(zhì) 2： 對 任 意 集 合 A， 有 ： A A 性 質(zhì) 3： 一 般 地 A BB A， 即 笛 卡 兒 乘 積 不 滿足 交 換 律 。問 題 ：什 么 情 況 下 A B B A？（ A B A B ）什 么 情 況 下 A BB A？ （ AB A B ） 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 7 7.1.2 集合的笛卡爾積例 3：設(shè) A a， b， B 1， 2， 3， C p， q，計(jì) 算 (A B) C ， A (B C)。解 ： (A B) C ,p , ,q , ,p , ,q , ,p , ,q , ,p , ,q , ,p ,

5、 ,q , ,p , ,q 。 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 8 7.1.2 集合的笛卡爾積 A (B C) a, , a, , a, , a, , a, , a, , b, , b, , b, , b, , b, , b, 集 合 的 笛 卡 兒 積 的 性 質(zhì) 性 質(zhì) 4： 一 般 地 (A B) CA (B C)， 即 集 合 的 笛 卡 兒 積 不 滿 足 結(jié)合 律 。 性 質(zhì) 5： AC BD A B C D 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 9 7.1.2 集合的笛卡爾積性 質(zhì) 6：笛 卡 兒 積 對 、 運(yùn) 算 滿 足 分 配 律

6、A （ B C） （ A B） （ A C） A （ BC） （ A B） （ A C） （ A B） C （ A C） （ B C） （ AB） C （ A C） （ B C） 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 10 7.1.2 集合的笛卡爾積證 明 ： A （ B C） （ A B） （ A C）證 ： 任 取 x， y x， y A （ B C） x A y B Cx A （ y B y C ）（ x A y B） （ x A y C ）（ x， y A B） （ x ， y A C ） x， y （ A B） （ A C ） 所 以 ， A （ B C） （ A

7、B） （ A C） 成 立 。 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 11 7.1.2 集合的笛卡爾積證 明 ： （ AB） C （ A C） （ B C） 證 ： 任 取 x， y x， y （ AB） Cx （ A B） y Cx A x B y C（ x A y C） （ x B y C ）（ x， y A C） （ x ， y B C ） x， y （ A C） （ B C）所 以 ， （ AB） C （ A C） （ B C） 成 立 。 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 12 7.1.3 有序 n 元組和 n 階笛卡爾積定 義 ：n個 元 素

8、 x1， x2， ， xn組 成 的 有 序 序 列 ,記 做 ： x1,x2,xn稱 為 n重 組 （ n元 序 偶 、 n元 組 ） 。約 定 : x 1， x2， , xn-1, xn = ,xn性 質(zhì) ： x1,x2,xn y1,y2,yn xi yi(i=1,2,n) 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 13 7.1.3 有序 n 元組和 n 階笛卡爾積定 義 4.4：集 合 A1、 A2、 、 An的 笛 卡 兒 乘 積A1 A2 An x1， x2， ， xn | xi Ai i 1,2,n注 意 ： A1 A2 An 1 An （ A1 A2 An 1 ）

9、An一 般 地 ：若 A 1 A2 An A時 ， 上 式 簡 記 為 ： An 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 14 7.2 二元關(guān)系7.2.1 二 元 關(guān) 系 的 基 本 定 義7.2.2 二 元 關(guān) 系 的 表 示 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 15 7.2.1 二元關(guān)系的基本定義關(guān) 系數(shù) 的 , , 關(guān) 系 ; V I R; 計(jì) 算 機(jī) 程 序 的 輸 入 與 輸 出 聯(lián) 系 ；數(shù) 據(jù) 庫 的 數(shù) 據(jù) 特 性 聯(lián) 系 等 。集 合 論 為 刻 劃 這 種 聯(lián) 系 提 供 了 一 種 數(shù) 學(xué) 模 型關(guān) 系 (Relation) 。 計(jì) 算

10、 機(jī) 科 學(xué) 學(xué) 院 劉 芳7.2.1 二元關(guān)系的基本定義定 義 7.3 如 果 一 個 集 合 滿 足 以 下 條 件 之 一 ：（ 1） 集 合 非 空 , 且 它 的 元 素 都 是 有 序 對（ 2） 集 合 是 空 集 則 稱 該 集 合 為 一 個 二 元 關(guān) 系 , 簡 稱 為 關(guān) 系 ， 記 作 R.例 如 ： R , S , 3, 4. 2021-4-29 16 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 17 7.2.1 二元關(guān)系的基本定義例 : (1) R | x,yN, x y 3 , , , , , (2) C | x,yR, x2 y2 1 (3) R

11、| x,y,zR, x 2y z 3 (4) 5元 關(guān) 系 的 實(shí) 例 數(shù) 據(jù) 庫 實(shí) 體 模 型員 工 號 姓 名 年 齡 性 別 工 資301302 303 張 林王 曉 云李 鵬 宇 504347 男女男 160012501500 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 18 7.2.1 二元關(guān)系的基本定義定 義 7.4 設(shè) A,B為 集 合 , R A B， 稱 R為 A到 B的 二 元 關(guān) 系 ；R A A ， 稱 R為 A上 的 關(guān) 系 。例 ： 若 A a,b, B 1, 則 ：（ 1） 寫 出 A到 B的 所 有 二 元 關(guān) 系 。（ 2） 寫 出 A上 的 所

12、 有 二 元 關(guān) 系 。 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 19 7.2.1 二元關(guān)系的基本定義一 般 地 ： 若 |A| m, |B| n |A B| mn, A B 的 子 集 有 2mn個 ,從 A到 B有 2mn個 不 同 的 二元 關(guān) 系 . R ， 稱 R為 空 關(guān) 系 ； R A B ， 稱 R為 全 域 關(guān) 系 若 |A| n |A A| n 2, A A 的 子 集 有 2n2個 , A上 有 2n2不 同 的 二 元 關(guān) 系 . R ， 稱 R為 A上 空 關(guān) 系 R A A ， 稱 R為 A上 的 全 域 關(guān) 系 ， 記 做 EA; R |x A ，

13、 稱 R為 A上 的 相 等 關(guān) 系 ， 記 做 IA; 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 20 7.2.1 二元關(guān)系的基本定義常 見 的 幾 種 特 殊 的 二 元 關(guān) 系 |集 合 之 間 的 關(guān) 系 ： 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 21 7.2.2 二元關(guān)系的表示1.集 合 表 示 法2.關(guān) 系 矩 陣 (matrix of relation) 設(shè) A a1,a2,am ， B b1,b2,bn， R是 A到 B的 一 個 二元 關(guān) 系 ， 令 ： 1 21 11 12 12 21 22 21 2R nnnm m m mnb b ba r

14、 r rM a r r ra r r r 10 i jij ia R br a R其 中 jb稱 ： MR為 R的 關(guān) 系 矩 陣 。 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 22 7.2.2 二元關(guān)系的表示例 1： 設(shè) A a,b,c,B 0,1,2,3,R ,寫出 MR。 0001c 0100b 0010a 3210 MR 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 23 7.2.2 二元關(guān)系的表示例 2： 設(shè) A 1,2,3,4,A上 的 關(guān) 系 R ,4,2,寫 出 MR。1 2 3 41 1 1 0 02 0 0 1 13 0 0 0 0 4 0 1 0

15、0MR 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 24 7.2.2 二元關(guān)系的表示例 3 設(shè) A 1,2,3,4,A上 的 二 元 關(guān) 系 R |x y,寫 出MR。 1 2 3 41 1 0 0 02 1 1 0 03 1 1 1 0 4 1 1 1 1MR 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 25 7.2.2 二元關(guān)系的表示 3.關(guān) 系 圖R為 A到 B的 二 元 關(guān) 系 ；以 A B的 每 個 元 素 為 一 個 結(jié) 點(diǎn) ， 對 每 個 R，均 連 一 條 從 結(jié) 點(diǎn) x到 y的 有 向 邊 ， 得 到 一 個 有 向 圖 ， 稱為 R的 關(guān) 系 圖 ，

16、 記 為 GR。 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 26 7.2.2 二元關(guān)系的表示例 1 設(shè) A a,b,c,B 0,1,2,3,R ,畫 出 GR。 abc 0123 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 27 7.2.2 二元關(guān)系的表示例 2 設(shè) A 1,2,3,4,A上 的 二 元 關(guān) 系 R |xy,畫 出GR。 12 4 3 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 28 7.2.2 二元關(guān)系的表示練 習(xí) ：A a, b, c, d, R ,求 R的 關(guān) 系 矩 陣 MR和 關(guān) 系 圖 GR 。 0010 0000 0001 0

17、111 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 29 7.2.2 二元關(guān)系的表示關(guān) 系 的 表 示 方 法關(guān) 系 R的 集 合 表 達(dá) 式關(guān) 系 矩 陣 MR關(guān) 系 圖 GR三 者 均 可 以 唯 一 相 互 確 定 。 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 30 7.3 關(guān)系的運(yùn)算7.3.1 關(guān) 系 的 定 義 域 、 值 域 和 域7.3.2 關(guān) 系 的 逆7.3.3 關(guān) 系 的 右 復(fù) 合7.3.4 關(guān) 系 運(yùn) 算 的 性 質(zhì)7.3.5 關(guān) 系 的 冪 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 31 7.3.1 關(guān)系的定義域、值域 和 域定

18、 義 7.6：dom（ R） = x| y（ xRy） ran（ R） = y| x（ xRy） fld（ R） = dom（ R） ran（ R） 例 ：設(shè) R a,1 , b,2 , a,3 計(jì) 算 dom（ R） ,ran（ R） ,域 fld（ R） 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 32 7.3.2 關(guān)系的逆運(yùn)算定 義 7.7關(guān) 系 R的 逆 關(guān) 系 R-1=|xRy例 ：R ,則 ：R-1 ,問 題 ：已 知 M R， 如 何 計(jì) 算 MR-1?已 知 GR， 如 何 計(jì) 算 GR-1? 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 33 7.3.3

19、 關(guān)系的右復(fù)合定 義 7.8關(guān) 系 F,G的 右 復(fù) 合 , | ( )F G x y t xFt tGy 關(guān) 系 復(fù) 合 的 求 解 方 法集 合 表 達(dá) 式圖 示 法關(guān) 系 矩 陣 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 34 7.3.3 關(guān)系的右復(fù)合例 ： R=, , , S=, , , , 法 1： R S = S R =, , , , , 法 2： 利 用 圖 示 方 法 求 合 成 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 35 7.3.3 關(guān)系的右復(fù)合法 3： 關(guān) 系 矩 陣 相 乘 的 方 法一 般 地 ：設(shè) : A= a1 , a2 , , am

20、 B= b1 , b2 , , bp C= c1 , c2 , , cn R是 A到 B的 一 個 二 元 關(guān) 系 ， S是 B到 C的 一 個 二 元 關(guān) 系 ， RS是 A到 C的 一 個 二 元 關(guān) 系 ， 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 36 7.3.3 關(guān)系的右復(fù)合則 ： MR ( rij )m p MS ( sij )p n MR S ( tij )m n 1 ( )(1 ,1 )ik kjpij kt r si m j n ：其 中 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 37 MR MsMRS a b c1 1 1 02 0 0 1 p

21、qa 1 0b 1 0c 0 1p q1 1 02 0 17.3.3 關(guān)系的右復(fù)合例 1： 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 38 7.3.4 關(guān)系運(yùn)算的性質(zhì)定 理 7.1 設(shè) F是 任 意 的 關(guān) 系 , 則 (1) (F1)1 F (2) domF1 ranF, ranF1 domF證 明 ： (1) 任 取 , 由 逆 的 定 義 有 (F 1)1 F1 F 所 以 有 (F1)1 F (2) 任 取 x domF1 y( F1) y( F) x ranF 所 以 有 domF1 ranF. 同 理 可 證 ranF1 domF. 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳

22、 2021-4-29 39 7.3.4 關(guān)系運(yùn)算的性質(zhì)定 理 7.2 設(shè) F, G, H是 任 意 的 關(guān) 系 , 則 (1) (F 。 G) 。 H=F 。 (G 。 H) 證 明 ： 任 取 , (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) 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 40 7.3.4 關(guān)系運(yùn)算的性質(zhì)定 理 7.2 設(shè) F, G, H是 任 意 的 關(guān) 系 , 則(2) (F 。 G)1= G1 。 F1

23、 證 明 ： 任 取 , (F G)1 F Gt ( F (t, x) G)t ( G 1 (t, y) F1) G1 F1所 以 (F G)1 = G1 F1 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 41 7.3.4 關(guān)系運(yùn)算的性質(zhì)定 理 7.3 設(shè) R 為 A上 的 關(guān) 系 , 則 R IA= IA R = R例 ：設(shè) A 1,2,3,4， A上 的 二 元 關(guān) 系 R=, , , ， 求 ： R IA I A R 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 42 7.3.5 關(guān)系的冪定 義 7.10： 若 R是 A上 二 元 關(guān) 系 ,Rn(n N) 定 義

24、如 下 ： R0 IA Rn+1 RnR問 題 ： 給 定 集 合 A和 A上 的 關(guān) 系 R， 如 何 計(jì) 算 Rn （ n N） ? 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 43 7.3.5 關(guān)系的冪例 ： 設(shè) A a,b,c,d,R ,求 Rn。方 法 1： 按 照 定 義 求 解 解 ：R0 ,R1 ,R2 ,R3 ,R 4 ,R2 R4 R6 R3 R5 R7 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 44 7.3.5 關(guān)系的冪方 法 2： 利 用 關(guān) 系 矩 陣 相 乘 的 方 法0 1 0 0 00 1 0 00 0 1 00 0 0 1M 2 0

25、1 0 0 0 1 0 0 1 0 1 01 0 1 0 1 0 1 0 0 1 0 10 0 0 1 0 0 0 1 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0M 1 0 1 0 01 0 1 00 0 0 10 0 0 0M 3 0 1 0 11 0 1 00 0 0 00 0 0 0M 由 于 ： M4 = M2, 即 R4 = R2. 于 是 ： 可 以 得 到 R2 = R4 = R6 = , R3 = R5 = R7 = 4 1 0 1 00 1 0 10 0 0 00 0 0 0M 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 45 7.3.5 關(guān)系的

26、冪方 法 3：用 關(guān) 系 圖 的 方 法 得 到 R0, R1, R2, R3,的 關(guān) 系 圖 如 下 圖 所示從 關(guān) 系 圖 看 冪 Rn運(yùn) 算 (n 1)：1.從 R的 每 個 結(jié) 點(diǎn) x出 發(fā) ， 凡 通 過 數(shù) n條 邊 能 到 達(dá) 的 結(jié) 點(diǎn) y，則 有 Rn。2. Rn， 意 味 著 關(guān) 系 圖 中 從 x到 y存 在 長 為 n的 一條 路 徑 ； 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 46 7.3.5 關(guān)系的冪冪 運(yùn) 算 的 性 質(zhì)引 ： 鴿 籠 原 理 （ 抽 屜 原 理 ）若 有 n個 鴿 籠 ， n 1只 鴿 子 ， 則 至 少 有 一 個 鴿 籠 里

27、至 少有 兩 只 鴿 子 。（ 將 n 1個 物 體 放 入 n個 盒 子 里 ， 則 至 少 有 一 個 盒 子 里有 2個 或 2個 以 上 的 物 體 。 ） 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 47 7.3.5 關(guān)系的冪定 理 7.6： 設(shè) |A| n, R是 A上 二 元 關(guān) 系 ， 則 存 在 s、 t,使 Rs Rt(0s t2n2)。證 明 ： R是 A上 的 關(guān) 系 ， 則 對 任 意 k N， Rk A A。又 | A A| n2 |( A A)| 2 n2 ， 即 A上 共 有 2n2個 不 同 的 二 元 關(guān) 系 。但 ： 序 列 R0， R1， ，

28、 R 2n2共 有 2n2 1項(xiàng) ，因 此 ,存 在 s,t N,使 Rs=Rt (0s t2n2)。 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 48 7.3.5 關(guān)系的冪定 理 7.7： 若 R是 A上 二 元 關(guān) 系 ， m,n N,則 ：1. Rm Rn Rm n2. (Rm) n Rmn定 理 7.8： 若 R是 A上 二 元 關(guān) 系 ， 若 存 在 自 然 數(shù) s,t(s t)，使 得 Rs Rt ,則 ：1. 對 任 意 k N, Rs+k Rt k2. 對 任 意 k,i N, Rs+kp+i Rs i,其 中 p=t s。 3. 令 S=R 0,R1,Rt-1，

29、則 對 任 意 q N, Rq S. 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 49 7.4 關(guān)系的性質(zhì)7.4.1 自 反 性 和 反 自 反 性7.4.2 對 稱 性 和 反 對 稱 性7.4.3 傳 遞 性7.4.4 關(guān) 系 性 質(zhì) 的 判 定 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 50 7.4.1 自反性和反自反性定 義 7.11： 設(shè) R為 A上 的 關(guān) 系 , (1) 若 x(x AR), 則 稱 R在 A上 是 自 反 的 . (2) 若 x(x AR), 則 稱 R在 A上 是 反 自 反 的 .例 7.10： A = 1, 2, 3, R1, R

30、2, R3 是 A上 的 關(guān) 系 , 其 中 R1 = , R2 = , R 3 = 關(guān) 系 是 自 反 （ 反 自 反 ） 的 關(guān) 系 圖 中 每 個 結(jié) 點(diǎn) 均 有 （ 無 ） 環(huán) 。關(guān) 系 是 自 反 （ 反 自 反 ） 的 關(guān) 系 矩 陣 主 對 角 線 的 元 素 全 為 1（ 0）自 反 性 與 反 自 反 性 是 互 斥 的 ， 但 不 互 補(bǔ) 。 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 51 7.4.2 對稱性和反對稱性定 義 7.12： 設(shè) R為 A上 的 關(guān) 系 , (1) 若 xy(x,y A R R), 則 稱 R為 A上 對 稱 的 關(guān) 系 .(2)

31、若 xy(x,y A R Rx=y), xy(x,y A R xy R), 則 稱 為 A上 的 反 對 稱 關(guān) 系 . 例 7.11 設(shè) A 1,2,3, R 1, R2, R3和 R4都 是 A上 的 關(guān) 系 , 其 中 R1 ,， R2 , R3 ,， R4 , 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 52 7.4.2 對稱和反對稱性注 意 ：從 關(guān) 系 圖 判 斷關(guān) 系 是 對 稱 的 關(guān) 系 圖 兩 結(jié) 點(diǎn) 若 有 邊 ， 則 一 定 是雙 向 的 ， 即 方 向 相 反 的 一 對 有 向 邊 。關(guān) 系 是 反 對 稱 的 關(guān) 系 圖 中 兩 結(jié) 點(diǎn) 之 間 若 有

32、 邊 ，則 一 定 為 單 向 的 。從 關(guān) 系 矩 陣 判 斷關(guān) 系 是 對 稱 的 關(guān) 系 矩 陣 關(guān) 于 主 對 角 線 對 稱 。關(guān) 系 是 反 對 稱 的 對 任 意 的 i,j,(ij),r ij 1rji 0。 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 53 7.4.3 傳遞性例 7.12 設(shè) A 1, 2, 3, R1, R2, R3是 A上 的 關(guān) 系 , 其 中 R1 , R 2 , R3 定 義 7.13： 設(shè) R為 A上 的 關(guān) 系 , 若 xyz(x,y,z A R R R),則 稱 R是 A上 的 傳 遞 關(guān) 系 .關(guān) 系 是 傳 遞 的 關(guān) 系 圖

33、中 若 兩 結(jié) 點(diǎn) 之 間 至 少 有 兩 條 邊 相 連 ， 則 一 定 存 在 捷 徑 。 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 54 7.4.4 關(guān)系性質(zhì)的判定自反性反自反性對稱性反對稱性傳遞性表達(dá)式IAR RIA= R=R1 RR1 IA RRR關(guān)系矩陣主對角線元素全是1主對角線元素全是0矩陣是對稱矩陣若rij1, 且ij, 則rji0對M2中1所在位置,M中相應(yīng)位置都是1關(guān)系圖每個頂點(diǎn)都有環(huán)每個頂點(diǎn)都沒有環(huán)如果兩個頂點(diǎn)之間有邊, 一定是一對 方向相反的邊(無單邊)如果兩點(diǎn)之間有邊, 一定是一條單向邊(無雙向邊)如果頂點(diǎn)xi到xj有邊, xj到xk有邊,則從xi到xk

34、也有邊 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 55 7.4.4 關(guān)系性質(zhì)的判定例 7.14: 判 斷 下 圖 中 關(guān) 系 的 性 質(zhì) , 并 說 明 理 由(3) 自 反 ， 不 是 反 自 反 ； 反 對 稱 ， 不 是 對 稱 ； 不 傳 遞 . (1) (2) (3)(1) 不 自 反 也 不 反 自 反 ； 對 稱 , 不 反 對 稱 ； 不 傳 遞 .(2) 不 是 自 反 ； 反 自 反 ； 反 對 稱 , 不 是 對 稱 ； 傳 遞 . 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 56 7.4.4 關(guān)系性質(zhì)的判定思 考 ：設(shè) A a,b,c， 試 給

35、 出 A上 的 一 個 二 元 關(guān) 系 R， 使 其 同時 不 滿 足 自 反 性 、 反 自 反 性 、 對 稱 性 、 反 對 稱 性 和傳 遞 性 (要 求 畫 出 R的 關(guān) 系 圖 ) 。 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 57 7.5 關(guān)系的閉包7.5.1 閉 包 的 定 義7.5.2 閉 包 的 構(gòu) 造 方 法 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 58 7.5.1 閉包的定義定 義 7.14（ 閉 包 ) 設(shè) R為 A上 的 二 元 關(guān) 系 ， 如 果 A上 的 二 元 關(guān) 系 R， 使 ：1. R R ；2. R是 自 反 的 （ 對 稱

36、 的 或 傳 遞 的 ） ；3. 對 A上 的 任 何 關(guān) 系 R”， 如 果 R R”, 且 R”自 反 （ 對 稱 或 傳 遞 ） ,必 有 R R” ； 則 稱 R為 R的 自 反 （ 對 稱 或 傳 遞 ） 閉 包 。 記 做 ： r(R)（ s(R)或 t(R) ） 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 59 7.5.1 閉包的定義例 ：A a,b,c,d,R , , , 求 r(R),s(R), t(R) 。 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 60 7.5.2 閉包的構(gòu)造方法1.集 合 表 達(dá) 式定 理 7.10 設(shè) R為 A上 的 二 元

37、關(guān) 系 ， 則 ：(1) r（ R） R R0（ R0 IA）(2) s（ R） R R-1(3) t（ R） R R 2 R3 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 61 7.5.2 閉包的構(gòu)造方法（ 1） r（ R） R IA證 明 ： 令 R R IA1. 顯 然 R R ；2. 對 任 意 x A， 有 IA, 當(dāng) 然 R IA R， 故 R自 反 ；3. 設(shè) 另 有 關(guān) 系 R”也 是 自 反 的 ， 且 R R”， R”自 反 I A R”， 又 R R”故 ： R IA R” ， 即 R R” 。所 以 說 ： r（ R） R IA。 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院

38、 劉 芳 2021-4-29 62 (2) s（ R） R R-1證 明 ： 令 R R R-1i . 顯 然 R R ；i i . 對 任 意 R R R R 1 R 1 R R R 1 R 故 R 對 稱 ； 7.5.2 閉包的構(gòu)造方法 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 63 i i i .設(shè) 另 有 關(guān) 系 R 也 是 對 稱 的 ， 且 R R ，則 對 任 意 R R R 1 若 R,由 于 R R 知 R 若 R1,則 R,由 于 R R ,故 有 R ,而 R 對 稱 ,于 是 R 。 R R 所 以 說 ： s（ R） R R-1。7.5.2 閉包的構(gòu)造方

39、法 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 64 (3) t（ R） R R2 R3 證 明 ： 令 R R R2 R3 i . 顯 然 R R ；i i . 對 任 意 ， R , 必 k,j（ k,j1,使 Rk, Rj ,于 是 Rk Rj Rk+j R ,即 R故 R 傳 遞 ；7.5.2 閉包的構(gòu)造方法 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 65 i i i .設(shè) 另 有 關(guān) 系 R 也 是 傳 遞 的 ， 且 R R ，則 對 任 意 R ,必 k(k1),使 Rk,顯 然 存 在 序 列 ： x c0,c1,c2,ck y,使 ：, R R 由

40、已 知 ： R 傳 遞 ， 故 R R R 因 此 t（ R） R R 2 R3 成 立 。 即 R R R RK個 7.5.2 閉包的構(gòu)造方法 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 66 7.5.2 閉包的構(gòu)造方法 2.關(guān) 系 矩 陣 表 示設(shè) 關(guān) 系 R, r(R), s(R), t(R)的 關(guān) 系 矩 陣 分 別 為 M, Mr, Ms和 Mt , 則Mr =M+E Ms =M+MT Mt =M+M2+M3+3.關(guān) 系 圖 表 示 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 67 7.5.2 閉包的構(gòu)造方法例 7.15 設(shè) A=a,b,c,d, R=,R和

41、r(R), s(R), t(R)的 關(guān) 系 圖 如 下 圖 所 示 . 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 68 7.6 等價關(guān)系和劃分7.6.1 等 價 關(guān) 系 的 定 義7.6.2 等 價 類 和 商 集7.6.3 集 合 的 劃 分7.6.4 等 價 關(guān) 系 與 劃 分 的 關(guān) 系 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 69 7.6.1 等價關(guān)系的定義定 義 7.15 非 空 集 合 A上 的 二 元 關(guān) 系 R， 如 果 R是 (1) 自 反 的 (2) 對 稱 的 (3) 傳 遞 的稱 R為 等 價 關(guān) 系 Equivalence Relatio

42、ns 。若 R為 一 個 等 價 關(guān) 系 ， xRy， 稱 為 x等 價 于 y, 記 作 ： xy。 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 70 7.6.1 等價關(guān)系的定義例 7.16A 1,2,3,4,5,6,7,8上 的 關(guān) 系 RR |x,y A xy(mod 3) 為 A上 的 一 個 等 價 關(guān) 系 。 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 71 7.6.1 等價關(guān)系的定義模 m相 等 （ 同 余 ） 關(guān) 系設(shè) x， y A（ A Z） ， m Z+，如 果 x y m k ( k Z )，那 么 x與 y是 模 m相 等 ， 記 為 ： x y

43、 ( mod m )（ 或 稱 x和 y模 m同 余 ） 。一 般 地非 空 集 合 A 上 的 模 m 同 余 關(guān) 系 R |x,y A xy(mod m)是 一 個 等 價 關(guān) 系 。 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 72 7.6.2 等價類和商集定 義 7.16： 等 價 類設(shè) R為 非 空 集 合 A上 的 等 價 關(guān) 系 , x A， 令 xR y | y A xRy 稱 xR 為 x關(guān) 于 R 的 等 價 類 , 簡 稱 為 x 的 等 價 類 , 簡 記為 x. 定 義 7.17 : 商 集 A R x R|x A 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 20

44、21-4-29 73 7.6.2 等價類和商集例 ：寫 出 A 1,2,3,4,5,6,7,8上 的 模 3等 價 關(guān) 系 的 等 價類 和 商 集 。 則 : 1 4 7 1,4,7 2 5 8 2,5,8 3 6 3,6 A R 1,4,7 , 2,5,8 , 3,6 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 74 例 2A a,b,c,d,e,f， A上 的 等 價 關(guān) 系 R的 關(guān) 系 圖 如 下 ：b ca de f 則 ：a b c a,b,cd e d,ef fA R a , d , f7.6.2 等價類和商集 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29

45、 75 7.6.2 等價類和商集例 3R是 Z上 的 模 4等 價 關(guān) 系 ， 則 ： 0 , 8, 4, 0, 4, 8, 1 , 7, 3, 1, 5, 9, 2 , 6, 2, 2, 6, 10, 3 , 5, 1, 3， 7, 11, Z R 0 , 1 , 2 , 3 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 76 7.6.2 等價類和商集等 價 類 的 性 質(zhì)定 理 7.14：設(shè) R為 非 空 集 合 A上 的 等 價 關(guān) 系 ， 則 , , , ,x A x x Ax y A xRy x yx y A x R ， x A y x yx A 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院

46、 劉 芳 2021-4-29 77 7.6.3 集合的劃分定 義 7.18：設(shè) A為 非 空 集 合 , 若 A的 子 集 族 ( P(A) 滿 足 下 面 條件 ： (1) (2) xy (x,y xyxy ) (3) A 稱 是 A的 一 個 劃 分 , 稱 中 的 元 素 為 A的 劃 分 塊 . 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 78 7.6.3 集合的劃分問 題 1： 設(shè) A a, b, c, d, 給 定 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 ,

47、a, b, c, d 6 a,a, b, c, d 其 中 1和 2是 A的 劃 分 , 其 他 都 不 是 A的 劃 分 . 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 79 7.6.3 集合的劃分問 題 2A 1,2,3， 則 集 合 A的 劃 分 有 幾 個 ？ 分 別 是 什 么 ？ 1 1,2,3 2 2,1,3 3 3,1,2 4 1,2,3 5 1,2,3 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 80 7.6.4 等價關(guān)系與劃分的關(guān)系等 價 關(guān) 系 與 劃 分 是 一 一 對 應(yīng) 的 關(guān) 系 一 方 面 ：集 合 A上 的 一 個 等 價 關(guān) 系 R確

48、 定 A的 一 個 劃 分 ,即 A R。 另 一 方 面 ：集 合 A的 一 個 劃 分 ， 確 定 A上 的 一 個 等 價 關(guān) 系 R。任 給 A 的 一 個 劃 分 , 如 下 定 義 A 上 的 關(guān) 系 R： R | x,y A x 與 y 在 的 同 一 劃 分 塊 中 R 為 A上 的 等 價 關(guān) 系 ， 且 該 等 價 關(guān) 系 確 定 的 商 集 就是 . 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 81 7.6.4 等價關(guān)系與劃分的關(guān)系例 ：若 A a,b,c,d,e,f,A上 的 一 個 劃 分 a， b， c， d， e， f ，則 ： 確 定 A上 的 一

49、個 等 價 關(guān) 系 。 R , , b c a de f 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 82 7.6.4 等價關(guān)系與劃分的關(guān)系一 般 地 ：若 A上 的 劃 分 A1,A2,Am。則 確 定 A上 的 一 個 等 價 關(guān) 系 R 1 ( )m i iiR A A 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 83 7.6.4 等價關(guān)系與劃分的關(guān)系問 題 3： 設(shè) A 1， 2， 3（ 1） A上 共 有 多 少 個 不 同 的 二 元 關(guān) 系 ；（ 2） 給 出 A上 所 有 的 等 價 關(guān) 系 。分 析 ： 1 5分 別 對 應(yīng) 于 等 價 關(guān) 系 R1R

50、5. 其 中 :R1=, IAR2=, IAR 3=, IAR4=EAR5=IA 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 84 7.6.4 等價關(guān)系與劃分的關(guān)系思 考 練 習(xí)A 1， 2共 有 多 少 個 二 元 關(guān) 系 ， 其 中 有 幾 個 是 等 價關(guān) 系 ， 請 寫 出 來 。A 1， 2， 3， 4共 有 多 少 個 二 元 關(guān) 系 ， 其 中 有 幾 個是 等 價 關(guān) 系 ， 請 寫 出 來 。A 1， 2， 3， 4， 5共 有 多 少 個 二 元 關(guān) 系 ， 其 中 有 幾個 是 等 價 關(guān) 系 ， 請 寫 出 來 。 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 202

51、1-4-29 85 7.7 偏序關(guān)系7.7.1 偏 序 關(guān) 系 及 相 關(guān) 定 義7.7.2 哈 斯 圖7.7.3 偏 序 集 中 的 特 殊 元 素7.7.4 調(diào) 度 問 題 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 86 7.7.1偏序關(guān)系及相關(guān)定義定 義 7.19：R是 非 空 集 合 A上 的 二 元 關(guān) 系 ， 如 果 R是 ： (1) 自 反 的 (2) 反 對 稱 的 (3) 傳 遞 的則 稱 R是 A上 偏 序 關(guān) 系 (半 序 關(guān) 系 部 分 序 關(guān) 系 ),記 作 。設(shè) 為 偏 序 關(guān) 系 , 如 果 , 則 記 作 x y, 讀 作 x“小 于 或 等 于

52、” y. 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 87 7.7.1偏序關(guān)系及相關(guān)定義實(shí) 例 :集 合 A上 的 恒 等 關(guān) 系 IA 是 A上 的 偏 序 關(guān) 系 . 小 于 或 等 于 關(guān) 系 , 整 除 關(guān) 系 和 包 含 關(guān) 系 也 是 相 應(yīng) 集 合上 的 偏 序 關(guān) 系 .定 義 7.22：集 合 A連 同 A上 的 偏 序 關(guān) 系 R一 起 稱 為 一 個 偏 序 集 ， 記 為 （ 或 ： ） 。 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 88 7.7.1偏序關(guān)系及相關(guān)定義定 義 7.20：設(shè) R為 非 空 集 合 A上 的 偏 序 關(guān) 系 ,定 義

53、 ：x, yA， x y x y xy x, yA, x與 y 可 比 x y y x.定 義 7.21 ： 全 序 R為 非 空 集 合 A上 的 偏 序 , x, yA, x與 y 都 可 比 ， 則 稱 R為 全 序 （ 線 序 ） 關(guān) 系 。如 ： 4 2 68 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 89 7.7.1偏序關(guān)系及相關(guān)定義定 義 7.23： 覆 蓋設(shè) R為 非 空 集 合 A上 的 偏 序 關(guān) 系 , x,y A, 如 果x y且 不 存 在 zA使 得 x z y, 則 稱 y覆 蓋 x。如 ： 4 2 68 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021

54、-4-29 90 7.7.2 哈斯圖偏 序 關(guān) 系 的 表 示 方 法1.關(guān) 系 矩 陣不 能 明 顯 看 出 二 元 關(guān) 系 的 特 征 。2.關(guān) 系 圖 比 較 煩 瑣3.簡 化 的 關(guān) 系 圖哈 斯 圖 （ Hasse圖 ） 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 91 7.7.2 哈斯圖例 1： A 2， 4， 6， 8， A上 的 二 元 關(guān) 系 ： R a， b a|b， a,b A 4 2 68 4 2 68簡 化 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 92 7.7.2 哈斯圖關(guān) 系 圖 哈 斯 圖 ： 自 反 性 ：每 個 頂 點(diǎn) 都 有 自

55、回 路 ， 省 去 。 反 對 稱 性 ：兩 個 頂 點(diǎn) 間 只 可 能 有 一 個 箭 頭 ,從 下 上 的 方 向 從小 到 大 安 置 頂 點(diǎn) ， 可 省 略 箭 頭 。 傳 遞 性 ：若 y覆 蓋 x， 則 在 x和 y之 間 連 一 條 線 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 93 7.7.2 哈斯圖例 2： 畫 出 1,2,9， R 的 哈 斯 圖 。 全 序 關(guān) 系 線 序 關(guān) 系 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 94 7.7.2 哈斯圖例 3 ： 畫 出 1, 2, 3, 4, 5, 6, 7, 8, 9 , R整 除 ， P(a,

56、b, c), R 的 哈 斯 圖 。 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳練 習(xí) 1： 已 知 偏 序 集 的 哈 斯 圖 如 下 圖 所 示 , 試 求 出 集 合 A和 關(guān) 系 R的 表 達(dá) 式 . 2021-4-29 95 7.7.2 哈斯圖A=a, b, c, d, e, f, g, h R=, I A 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 96 課堂練習(xí)練 習(xí) 2：已 知 偏 序 集 ,的 關(guān) 系 圖 如 下 ， 試 將 關(guān) 系 圖 改 畫成 哈 斯 圖 。 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 97 課堂練習(xí)練 習(xí) 3圖 示 為 偏 序 集 的 哈

57、 斯 圖 ， 試 畫 出 其 關(guān) 系 圖 。 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 98 課堂練習(xí)問 題設(shè) A=1,2， 求 A上 的 所 有 的 偏 序 關(guān) 系 。設(shè) A=1,2,3， 求 A上 的 所 有 的 偏 序 關(guān) 系 。 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 99 7.7.3 偏序集中的特殊元素定 義 7.24 ： 設(shè) A, 是 偏 序 集 ,BA, b B：若 x(x B x b)成 立 ， 則 稱 b為 B的 最 大 元 。若 x(x B b x)成 立 ， 則 稱 b為 B的 最 小 元 。例 1：對 偏 序 集 合 2,4,6,8， R整

58、 除 分 別 寫 出 如 下 集 合 的最 大 元 和 最 小 元 ：2， 4， 6， 82， 4， 82， 4， 64， 6， 8 4 2 68 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 100 例 2：對 偏 序 集 合 1, 2, 3, 4, 5, 6, 7, 8, 9 , R整 除 分 別 寫出 如 下 集 合 的 最 大 元 和 最 小 元 ：1,3,5,91,2,3,6 1,3,5,7 2,3,4,6,87.7.3 偏序集中的特殊元素 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 101 7.7.3 偏序集中的特殊元素定 義 7.24 ： 設(shè) A, 是 偏

59、序 集 ,BA, b B： x（ x B b x） ， 則 稱 b為 B的 極 大 元 。 x（ x B x b ） ， 則 稱 b為 B的 極 小 元 。例 1：對 偏 序 集 合 2,4,6,8， R整 除 分 別 寫 出 如 下 集 合的 極 大 元 和 極 小 元 ：2， 4， 6， 82， 4， 82， 4， 64， 6， 8 4 2 68 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 102 例 2：對 偏 序 集 合 1, 2, 3, 4, 5, 6, 7, 8, 9 , R整 除 分 別 寫出 如 下 集 合 的 極 大 元 和 極 小 元 ：1,3,5,91,2,3

60、,6 1,3,5,7 2,3,4,6,87.7.3 偏序集中的特殊元素 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 103 7.7.3 偏序集中的特殊元素性 質(zhì)對 于 有 窮 集 ， 極 小 元 和 極 大 元 必 存 在 ， 可 能 存 在 多個 . 最 小 元 和 最 大 元 不 一 定 存 在 ， 如 果 存 在 一 定 惟 一 .最 小 元 一 定 是 極 小 元 ； 最 大 元 一 定 是 極 大 元 . 孤 立 結(jié) 點(diǎn) 既 是 極 小 元 ， 也 是 極 大 元 . 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 104 7.7.3 偏序集中的特殊元素定 義 7

61、.25: 設(shè) 為 偏 序 集 , BA, aA.（ 1） 若 x (x Bx a) 成 立 , 則 稱 a為 B 的 上 界 . （ 2） 若 x (x B a x) 成 立 , 則 稱 a 為 B 的 下 界 . （ 3） 令 C y | y為 B的 上 界 , 則 稱 C的 最 小 元 為 B 的 最 小 上 界 或 上 確 界 . （ 4） 令 D y | y為 B的 下 界 , 則 稱 D的 最 大 元 為 B 的 最 大 下 界 或 下 確 界 . 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳例 ：對 偏 序 集 合 2,3,6,12,24,36, R整 除 ,求 如 下 集 合 的 上界 、

62、 最 小 上 界 、 下 界 、 最 大 下 界 。 2， 3， 6 12， 24， 36 2， 3 24， 36 6， 12 2021-4-29 105 242 6 363127.7.3 偏序集中的特殊元素 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 106 7.7.3 偏序集中的特殊元素例 7.21： 設(shè) 偏 序 集 如 下 圖 所 示求 A 的 極 小 元 、 最 小 元 、 極 大 元 、 最 大 元 . 設(shè) B b, c, d , 求 B 的 下 界 、 上 界 、 下 確 界 、 上 確 界 . 解 ：極 小 元 ： a, b, c, g；極 大 元 ： a, f, h；最 小 元 ： 無最 大 元 ： 無B的 下 界 和 最 大 下 界 都 不 存 在 ,B的 上 界 有 d 和 f, 最 小 上 界 為 d. 計(jì) 算 機(jī) 科 學(xué) 學(xué) 院 劉 芳 2021-4-29 107 7.7.3 偏序集中的特殊元素性 質(zhì) ：下 界 、 上 界 、 下 確 界 、 上 確 界 不 一 定 存 在下 界 、 上 界 存 在 不 一 定 惟 一下 確 界 、 上 確 界 如 果 存 在 ， 則 惟 一集 合 的 最 小 元 就 是 它 的 下 確 界 ， 最 大 元 就 是 它 的 上確 界 ； 反 之 不 對 .