離散數(shù)學(xué)課件第四章-二元關(guān)系和函數(shù)

《離散數(shù)學(xué)課件第四章-二元關(guān)系和函數(shù)》由會(huì)員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)課件第四章-二元關(guān)系和函數(shù)（156頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、劉 師 少 Tel： 86613747（ h） E-mail： 授 課 : 51學(xué) 時(shí) 教 學(xué) 目 標(biāo) : 知 識(shí) 、 能 力 、 素 質(zhì)Discrete Mathematics 第 四 章 二 元 關(guān) 系 和 函 數(shù) 4.1 集 合 的 笛 卡 爾 積 與 二 元 關(guān) 系 4.2 關(guān) 系 的 運(yùn) 算 4.3 關(guān) 系 的 性 質(zhì) 4.4 關(guān) 系 的 閉 包 4.5 等 價(jià) 關(guān) 系 和 偏 序 關(guān) 系 4.4 函 數(shù) 的 定 義 和 性 質(zhì) 4.4 函 數(shù) 的 復(fù) 合 和 反 函 數(shù) 4.4 例 題 分 析 說 起 關(guān) 系 這 個(gè) 詞 ， 對(duì) 我 們 并 不 陌 生 ， 世 界 上 存在 著 各

2、 種 各 樣 的 關(guān) 系 ， 人 與 人 之 間 的 “ 同 志 ” 關(guān) 系 ；“ 同 學(xué) ” 關(guān) 系 ； “ 朋 友 ” 關(guān) 系 ； “ 師 生 ” 關(guān) 系 ；“ 上 下 級(jí) ” 關(guān) 系 ； “ 父 子 ” 關(guān) 系 ； 兩 個(gè) 數(shù) 之 間 有“ 大 于 ” 關(guān) 系 ； “ 等 于 ” 關(guān) 系 和 “ 小 于 ” 關(guān) 系 ； 兩個(gè) 變 量 之 間 有 一 定 的 “ 函 數(shù) ” 關(guān) 系 ； 計(jì) 算 機(jī) 內(nèi) 兩 電路 間 有 導(dǎo) 線 “ 連 接 ” 關(guān) 系 ； 程 序 間 有 “ 調(diào) 用 ” 關(guān) 系等 等 。 所 以 對(duì) 關(guān) 系 進(jìn) 行 深 刻 的 研 究 ， 對(duì) 數(shù) 學(xué) 與 計(jì) 算機(jī) 科 學(xué)

3、都 有 很 大 的 用 處 。 再 如 : 電 影 票 與 座 位 之 間 有 對(duì) 號(hào) 關(guān) 系 。 設(shè) ： X 表 示 電 影 票 的 集 合 Y 表 示 座 位 的 集 合 ， 則 ， 對(duì) 于 任 意 的 x X和 y Y， 必 有 x 與 y 有 對(duì) 號(hào) “ 對(duì) 號(hào) ” 關(guān) 系 則 上 述 問 題 可 表 達(dá) 為 xRy或 xRy ， 亦 可 記 為 (x ， y)R或 (x ， y)R 因 此 我 們 可 以 看 到 對(duì) 號(hào) 關(guān) 系 R是 序 偶 的 集 合 , 在 這一 章 我 們 要 研 究 集 合 內(nèi) 元 素 間 的 關(guān) 系 以 及 集 合 之 間 元 素之 間 的 關(guān) 系 ， 這

4、 就 是 “ 關(guān) 系 ” 與 “ 函 數(shù) ” 。 它 們 是 很 重要 的 基 本 數(shù) 學(xué) 概 念 ， 在 數(shù) 學(xué) 領(lǐng) 域 中 均 有 很 大 的 作 用 ， 并且 對(duì) 研 究 計(jì) 算 機(jī) 科 學(xué) 中 的 許 多 問 題 如 數(shù) 據(jù) 結(jié) 構(gòu) 、 數(shù) 據(jù) 庫 、情 報(bào) 檢 索 、 算 法 分 析 、 計(jì) 算 理 論 等 都 是 很 好 的 數(shù) 學(xué) 工 具 。 關(guān) 系 的 引 入 例 4.0 設(shè) 一 旅 館 有 n個(gè) 房 間 ， 每 個(gè) 房 間 可 住 兩 個(gè) 旅客 ， 所 以 一 共 可 住 2n個(gè) 旅 客 ， 在 旅 館 內(nèi) ， 旅 客 與 房 間有 一 定 關(guān) 系 ， 用 R 表 示 “ 某

5、 旅 客 住 在 某 房 間 ” 這 種 關(guān)系 。 設(shè) n=3 表 示 旅 館 共 有 3個(gè) 房 間 , 分 別 記 以 1, 2, 3 可住 6個(gè) 旅 客 分 別 記 以 a, b, c, d, e, f , 這 些 旅 客 住 的 房 間 如右 下 圖 所 示 12 3abcdef 滿 足 R 的 所 有 關(guān) 系 可 看 成 是 一 個(gè) 有序 偶 的 集 合 ， 這 個(gè) 集 合 可 叫 RR=, 若 令 A = a, b, c, d, e, f B = 1, 2, 3 則 例 中 關(guān) 系 的 每 一 元 素 均 屬 于 A B亦 即 R 是 A B的 子 集 ， 并 稱 此 關(guān) 系 為 從

6、 A 到 B 的 關(guān) 系 R。 4.1 集 合 的 笛 卡 爾 積 與 二 元 關(guān) 系定 義 4.1由 兩 個(gè) 元 素 x,y（ 允 許 x=y） 按 一 定 順 序 排 列 成的 二 元 組 叫 做 一 個(gè) 有 序 對(duì) 或 序 偶 ， 記 作 ,其 中 x是它 的 第 一 元 素 ， y是 它 的 第 二 元 素 。有 序 對(duì) 具 有 以 下 性 質(zhì) ：(1) 當(dāng) xy時(shí) ， (2) = x=w y=v例 4.1： 已 知 = ， 求 x 和 y。解 ： 由 有 序 對(duì) 相 等 的 充 要 條 件 得 x+3 = y+7 y-2 = 3y-x 解 得 x = 6, y = 2 4.1 集 合

7、 的 笛 卡 爾 積 與 二 元 關(guān) 系定 義 4.2 一 個(gè) 有 序 n元 組 (n 3)是 一 個(gè) 有 序 對(duì) ， 其 中 第 一 個(gè) 元 素 是 一 個(gè) 有 序 n-1元 組 ， 一 個(gè) 有 序 n元 組 記 作 ,即 = , xn 例 如 ： 空 間 直 角 坐 標(biāo) 系 中 點(diǎn) 的 坐 標(biāo) ,等 都 是 有 序 3元 組 。 n維 空 間 中 點(diǎn) 的 坐 標(biāo) 或 n維 向 量 都 是 有 序 n元 組 。形 式 上 也 可 以 把 看 成 有 序 1元 組 。 定 義 4.3 設(shè) A， B為 集 合 ， 用 A中 元 素 為 第 一 元 素 ，B中 元 素 為 第 二 元 素 構(gòu) 成

8、有 序 對(duì) 。 所 有 這 樣 的 有 序 對(duì)組 成 的 集 合 叫 做 A和 B的 笛 卡 兒 積 ， 記 作 A B。 笛 卡 兒 積 的 符 號(hào) 化 表 示 為 ： A B=|x A y B例 如 ： 若 A=1,2, B=a,b,c,則A B=, , , , , B A=, , , , , 易 知 ： 若 |A|=m,(即 集 合 A的 元 素 的 個(gè) 數(shù) ),|B|=n,則| A B|= |B A|= m n 4.1 集 合 的 笛 卡 爾 積 與 二 元 關(guān) 系 l 主 菜 魚 香 肉 絲 家 常 豆 腐 宮 保 雞 丁 酸 辣 土 豆 絲 蒜 茸 油 麥 菜 l 湯 紫 菜 蛋

9、花 湯 魚 頭 豆 腐 湯 雞 蛋 西 紅 柿 湯 酸 辣 蔬 菜 湯 由 前 面 的 定 義 可 知 ： 有 序 對(duì) 就 是 有 順 序 的 數(shù) 組 ， 如， x,y 的 位 置 是 確 定 的 ， 不 能 隨 意 放 置 。 注 意 ： 有 序 對(duì) ， 以 a,b為 元 素 的 集 合a,b=b,a； 有 序 對(duì) (a,a)有 意 義 ， 而 集 合 a,a不 成立 ， 因 為 它 只 是 單 元 素 集 合 ， 應(yīng) 記 作 a。笛 卡 兒 積 是 一 種 集 合 合 成 的 方 法 ， 把 集 合 A， B合成 集 合 A B， 規(guī) 定A B xA,yB由 于 有 序 對(duì) 中 x,y的

10、位 置 是 確 定 的 ， 因 此 A B的記 法 也 是 確 定 的 ， 不 能 寫 成 B A。笛 卡 兒 積 也 可 以 多 個(gè) 集 合 合 成 A 1 A2 An。笛 卡 兒 積 的 運(yùn) 算 性 質(zhì) 。 笛 卡 兒 積 的 性 質(zhì) ：1、 對(duì) 任 意 集 合 A， 根 據(jù) 定 義 有 A = A= 2、 一 般 來 說 ， 笛 卡 兒 積 不 滿 足 交 換 律 ， 即 A BB A （ 當(dāng) A B B 、 A 時(shí) ）3、 笛 卡 兒 積 不 滿 足 結(jié) 合 律 ， 即 (A B) CA (B C) （ 當(dāng) A B C時(shí) ）4、 笛 卡 兒 積 運(yùn) 算 對(duì) 并 和 交 運(yùn) 算 滿 足

11、分 配 律 ， 即 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.1 集 合 的 笛 卡 爾 積 與 二 元 關(guān) 系 例 4.2 證 明 ： (BC) A = (B A)(C A)對(duì) 于 (BC) A x (B C) y A x B x C y A x B x C y A y A (x B y A) (x C y A) B A C A (B A) (C A) (BC) A = (B A) (C A) 4.1 集 合 的 笛 卡 爾 積 與 二 元 關(guān) 系 例 4.3：

12、設(shè) A， C， B， D為 任 意 集 合 ， 判 斷 以 下命 題 是 否 為 真 ， 并 說 明 理 由 。(1) A B= A C =B= C(2) A-(B C)=( A-B) (A-C)(3) 存 在 集 合 A,使 得 A A A.解 ：(1) 不 一 定 為 真 。 反 例 A= , B、 C為 任 意 不 相 等 的 非 空 集 合 。(2) 不 一 定 為 真 。 反 例 A= 1, B=2, C=3.(3) 為 真 。 當(dāng) A= 時(shí) 成 立 。 定 義 4.4 設(shè) A1,A2,An,是 集 合 (n 2),它 們 的 n階笛 卡 兒 積 記 作 A1 A2 An ， 其 中

13、 A1 A2 An= | x1A1 x2A2 xnAn 當(dāng) A1=A2=An=A時(shí) , 將 起 n階 笛 卡 兒 積 記 作 An例 如 ， A= a ,b ,則 A3=A A A=a,b a,b a,b =, , , 4.1 集 合 的 笛 卡 爾 積 與 二 元 關(guān) 系 例 4.6 設(shè) 集 合 A=a,b,B=1,2,3,C=d, 求 A B C， B A。解 先 計(jì) 算 A B ,A B C , d , B A , 例 4.7 設(shè) 集 合 A 1,2,求 A P(A)。解 P(A)=,1,2,1,2A P(A) 1,2 ,1,2,1,2=, , , 定 義 4.5 如 果 一 個(gè) 集 合

14、 符 合 以 下 條 件 之 一 ：(1) 集 合 非 空 ， 且 它 的 元 素 都 是 有 序 對(duì)(2) 集 合 是 空 集 則 稱 該 集 合 為 一 個(gè) 二 元 關(guān) 系 ， 記 作 R， 簡稱為 關(guān) 系 。 對(duì) 于 二 元 關(guān) 系 R， 若 R,可 記 作 xRy;如 果 R,則 記 作 xRy。例 ： R1=,R2=5,6,7 aR 1b, 1R12, 5R16 4.1 集 合 的 笛 卡 爾 積 與 二 元 關(guān) 系 二 元 關(guān) 系 是 兩 種 客 體 之 間 的 聯(lián) 系 ， 例 如 某 學(xué) 生 學(xué) 習(xí) 語 文、 數(shù) 學(xué) 、 外 語 ， 表 示 為 A 語 文 , 數(shù) 學(xué) , 外 語

15、 功 課 的 成 績 分 四 個(gè) 等 級(jí) ， 記 作 B A， B， C， D于 是 該 生 成 績 的 全 部 可 能 為 A BA B , , ,而 該 生 的 實(shí) 際 成 績 P ,可 以 看 出 P是 A B的 一 個(gè) 子 集 ， 它 表 示 了 功 課 與 其 成 績的 一 種 關(guān) 系 。 由 此 可 見 ： 兩 個(gè) 集 合 之 間 的 二 元 關(guān) 系 ， 實(shí) 際 上 就 是兩 個(gè) 元 素 之 間 的 某 種 相 關(guān) 性 。 再 如 ： 若 A=， ， B=1， 2， 3， 求 A B , B A， A A， B B， （ A B） （ B A）解 ： A B =(， 1)， (，

16、2)， (， 3)， (， 1)， (， 2)， (， 3)B A =(1， )， (1， )， (2， )， (2， )， (3， )， (3， )A A = ( ， )， (， )， (， )， (， )B B = (1， 1)， (1， 2)， (1， 3)， (2， 1)， (2， 2)， (2， 3)， (3， 1)， (3， 2)， (3， 3) （ A B） （ B A） = l 由 上 例 可 看 出 ： A BB A 程 序 實(shí) 現(xiàn) 定 義 4.6 設(shè) A， B為 集 合 ， A B的 任 何 子 集 所 定 義 的二 元 關(guān) 系 叫 做 從 A到 B的 二 元 關(guān) 系 ，

17、特 別 當(dāng) A=B時(shí) 則 叫做 A上 的 二 元 關(guān) 系 。例 4.7： 若 A=a,b， B=2,5,8， 則 A B= , 令 R1= , R2=, , R3=因 為 R1 A B， R2 A B， R3 A B，所 以 R 1， R2和 R5均 是 由 A到 B的 二 元 關(guān) 系因 為 只 討 論 二 元 關(guān) 系 ， 所 以 今 后 無 特 別 聲 明 ， 術(shù) 語 “ 關(guān) 系 ” 皆 指 二 元 關(guān) 系 ？ 又 例 ： 若 A=a,b， B=2,5,8， 則 B A= , 令 R4= , R5=, , 因 為 R4 B A， R5 B A，所 以 R4和 R5均 是 由 B到 A的 關(guān)

18、系又 B B=, , , 令 R6= , , R 7=, , 因 為 R6 B B， R7 B B，所 以 R6和 R7均 是 集 合 B上 的 關(guān) 系 。 若 集 合 |A|=n,則 集 合 A上 的 二 元 關(guān) 系 有 多 少 個(gè) ？答 曰 ： |A|=n， 則 |A A|=n2, A A的 任 一 個(gè) 子 集 就 是A上 的 二 元 關(guān) 系 ， 即 P(A)= 2n 個(gè) 。 例 4.8 A= 1,2 則 A A有 n2 個(gè) 不 同 的 二 元 關(guān) 系 A A=1,2 1,2= , A A的 任 一 個(gè) 子 集 就 是 A A的 冪 集 ， 即 P(A)P(A)= , , , , , ,

19、, , , , , , , , , , , , , , , , , , 集 合 中 的 元 素 不 分 順 序 若 集 合 A= a,b,c 則 A的 冪 集 ， P(A)為P(A) = , a, b, c, a,b, a,c, b,c, a,b,c （ 注 a,a= a b,b= b c,c= c ）三 類 特 殊 的 關(guān) 系 對(duì) 于 任 何 集 合 A， 空 集 是 A A的 子 集 ， 叫 做 A上 的 空 關(guān) 系 定 義 EA=|x A y A= A A為 全 域 關(guān) 系 定 義 IA=|x A 為 恒 等 關(guān) 系例 ： 若 A=1,2， 則 E A= , IA =, 除 上 述 三

20、類 特 殊 的 關(guān) 系 外 ， 還 有 一 些 常 用的 關(guān) 系 ， 如 ： LA= |x,y A x y (A R)為 實(shí)數(shù) 集 上 的 小 于 等 于 關(guān) 系 。 DA= |x,y A x整 除 y (A Z*)為 非正 整 數(shù) 集 上 的 整 除 關(guān) 系 。 R = |x,y A xy (A 是 集 合 族 )為 集 合 上 的 包 含 關(guān) 系 。 類 似 地 還 可 以 定 義 大 于 等 于 關(guān) 系 、 大 于 關(guān)系 、 小 于 關(guān) 系 、 真 包 含 關(guān) 系 等 。 4.1 集 合 的 笛 卡 爾 積 與 二 元 關(guān) 系 例 4.9： 設(shè) A=1,2,3,4， 請(qǐng) 表 示 下 列

21、關(guān) 系 。(1) R= |x是 y的 倍 數(shù) (2) R= |(x-y)2 A(3) R= |x除 y是 素 數(shù) (4) R= |xy 4.1 集 合 的 笛 卡 爾 積 與 二 元 關(guān) 系解 (1) DA = , , , , , (2) R = , , , (3) DA = ,(4) R= , , 例 4.9_1 設(shè) A= 1， 2， 3 ， B= 4， 5， 6 ， 并 定 義 R1， R2為 從 A到 B的 關(guān) 系 ； R3為 從 B到 A的 關(guān) 系 ； （ aA， bB） (1) 當(dāng) 且 僅 當(dāng) ： a能 整 除 b時(shí) ， aR1b；(2) 當(dāng) 且 僅 當(dāng) ： a是 b的 整 數(shù) 倍

22、時(shí) ， aR2b；(3) 當(dāng) 且 僅 當(dāng) ： b是 a的 整 數(shù) 倍 時(shí) ， bR3a；試 寫 出 R1， R2， R3。解 ：R1=(1,4),(1,5),(1,6),(2,4),(2,6),(3,6)R2=；R3=(4,1),(5,1), (6,1),(4,2),(6,2), (6， 3) |A|=n, |B|=m, A , B中 的 元 素 已 按 一 定 的 次 序 排 列 若A=x1,x2,xn ,B= y1,y2,ym 且 RAB,若 1 若 xiRyj r ij= (i=1,2,n j=1,2,m) 0 若 xiRyj則 稱 矩 陣 為 R的 關(guān) 系 矩 陣有 窮 集 合 上 的

23、 二 元 關(guān) 系 的 三 種 表 示 方 法 ：l 集 合 表 示 法 （ 前 已 使 用 ）l 關(guān) 系 矩 陣 法l 關(guān) 系 圖 關(guān) 系 矩 陣 是 表 示 關(guān) 系 的 另 一 種 有 效 的 方 法 ， 其 優(yōu)點(diǎn) 是 可 以 利 用 矩 陣 作 為 研 究 關(guān) 系 的 手 段 ， 而 且 這 樣 做便 于 計(jì) 算 機(jī) 進(jìn) 行 處 理 。 設(shè) R： AB， A和 B都 是 有 限 集 ， 且 設(shè) A， B為 集 合 ， A B的 任 何 子 集 Ri A B則 稱 Ri所 定 義 的 二 元 關(guān) 系 叫 做 從 A到 B的 二 元關(guān) 系 ， 特 別 當(dāng) A=B時(shí) 則 叫 做 A上 的 二 元

24、 關(guān) 系 則 r11 r12 r1n (r ij)= r21 r22 r2n rn1 rn2 rnn是 R的 關(guān) 系 矩 陣 ， 記 作 MR。關(guān) 系 矩 陣 法若 A=x1,x2,xn ,B= y1,y2,yn 則 R的 關(guān) 系 矩 陣 是一 個(gè) n行 n列 矩 陣 M(R)= (rij)nn , 其 中 元 素 rij 為 ： 1 若 xiRyj r ij= (i,j=1,2,n) 0 若 xiRyj 0 1 1 1MR= 0 0 1 1 0 0 0 1 0 0 0 0例 4.10 A=1,2,3,4 R為 A上 的 小 于 關(guān) 系 ， 則 R為 ：R=, , , R的 關(guān) 系 矩 陣 為

25、 ：1 2 3 41 2 3 4 例 4.11 設(shè) 集 合 A 2,3,4, B=8,9,12,14. R是 由 A到 B的二 元 關(guān) 系 ， 定 義 ： R= | a整 除 b寫 出 R的 表 達(dá) 式 和 關(guān) 系 矩 陣 . 解 R=, 8 9 12 14 2 1 0 1 1R的 關(guān) 系 矩 陣 為 .M R= 3 0 1 1 0 4 1 0 1 0 關(guān) 系 圖關(guān) 系 圖 是 表 示 關(guān) 系 的 一 種 直 觀 形 象 的 方 法 ， 設(shè) R： AB，A和 B都 是 有 限 集 ， A=x1,x2,xn , B= y1,y2,ym 關(guān) 系 R的 有 序 偶 可 用 圖 中 從 結(jié) 點(diǎn) xi

26、到 yj 的 有 向邊 表 示 ， 這 樣 即 可 將 關(guān) 系 用 圖 表 示 之 。例 4.12 設(shè) R: AB， A=x1,x2, x3, x4 , B= y1,y2,y3 R=, R的 關(guān) 系 如 下 圖 所 示x 1x2x3x4 y1y2y3 關(guān) 系 圖關(guān) 系 圖 是 表 示 關(guān) 系 的 一 種 直 觀 形 象 的 方 法 ， 設(shè) R： AB，A和 B都 是 有 限 集 ， A=x1,x2,xn , B= y1,y2,ym 關(guān) 系 R的 有 序 偶 可 用 圖 中 從 結(jié) 點(diǎn) xi 到 yj 的 有 向邊 表 示 ， 這 樣 即 可 將 關(guān) 系 用 圖 表 示 之 。例 4.13 設(shè)

27、R: AA， A= a,b, c, d R=, , , R的 關(guān) 系 如 下 圖 所 示ab c d 其 中 c 到 c的 邊 稱 為 環(huán) 定 義 4.8設(shè) R是 二 元 關(guān) 系(1) R中 所 有 的 有 序 對(duì) 的 第 一 元 素 構(gòu) 成 的 集 合 稱 為 R的 定 義 域 ， 記 作 domR,形 式 化 表 示 為 ： domR= x| y( R)(2) R中 所 有 的 有 序 對(duì) 的 第 二 元 素 構(gòu) 成 的 集 合 稱 為 R的值 域 ， 記 作 ranR,形 式 化 表 示 為 ： ranR= y| x( R)(3) R的 定 義 域 和 值 域 的 并 集 稱 為 R的

28、域 ， 記 作 fldR,形式 化 表 示 為 ： fldR= domR ranR 4.2 關(guān) 系 的 運(yùn) 算 例 4.14 下 列 關(guān) 系 都 是 整 數(shù) 集 Z上 的 關(guān) 系 ， 分 別 求 出 它 們的 定 義 域 和 值 域(1) R1= |x,yZ x y(2) R2= |x,yZ x2+y2=1(3) R3= |x,yZ y=2x(4) R4= |x,yZ |x|=|y|=3解 (1) dom R1= ram R1= Z (2) R2=, dom R2= 0, 1, -1 ram R2= 0, 1, -1 (3) dom R 3=Z ram R3= 2z|zZ 即 偶 數(shù) 集(4)

29、 dom R4= -3, 3 ram R4= -3, 3 10-1 -101dom R2 ram R2R2210-1-2 43210-1-2-3-4dom R3=Z ram R3R3 例 4.15 設(shè) R1=, R2= , 求 其 定 義 域 和 值 域解 題 目 沒 有 告 訴 我 們 R1 和 R2 是 由 什 么 集 合 到 什 么 的 關(guān) 系 ,這 對(duì) 于 我 們 解 此 題 是 無 關(guān) 緊 要 的 ,事 實(shí) 上 ,不 論 R1 和 R2 是 定 義 在 何 種 集 合 上 的 關(guān) 系 ,據(jù) 定 義 域 和 值 域 的 定 義domR=x| y( R) ranR=y| x( R) 有

30、dom R1= 1,2,3 dom R2= 1,2,4 ram R1= 2,4,3 ram R 2= 3,4,2 規(guī) 律 :集 合 R1 和 R2 中 序 偶 中的 第 一 個(gè) 元 素 的 集 合 即 為 其定 義 域 , 序 偶 中 的 第 二 個(gè) 元素 的 集 合 即 為 其 值 域 .如 果 此 題 再 加 上 求 R1 R2及 R1R2定 義 域 和 值 域 , 則 因 為R1 R2= , ,R1R2= 所 以 domR1 domR2= 1,2,3,4 ramR1 ramR2= 2,3,4 定 義 4.9 設(shè) F,G為 任 意 的 關(guān) 系 ,A 為 集 合 ， 則 (1) F的 逆 記

31、 作 F-1, F-1 =|yFx (2) F與 G的 合 成 記 作 F G， 其 中 F G=| z(xGz zFy 或 F G=| z(xFz zGy p87 (3) F在 A上 限 制 記 作 F A F A =| xFy x A) (4) A在 F下 的 象 記 作 FA FA =ran(F A ) 4.2 關(guān) 系 的 運(yùn) 算 逆 關(guān) 系 ： 設(shè) R是 一 個(gè) X到 Y的 關(guān) 系 ， 則 Y到 X的 關(guān) 系 R-1： R-1 =| R 稱 為 R的 逆 關(guān) 系 。例 4.16 設(shè) X=1, 2, 3 Y=a, b, c 且 設(shè) R是 從 X到 Y的 關(guān) 系 R =, 則 R-1 =,

32、 例 4.17 設(shè) X=x1, x2, x3 Y=y1, y2, y3 且 設(shè) R是 從 X到 Y的 關(guān) 系 R =, 的 逆 關(guān) 系 R-1 =, 如 下 圖 所 示 ：x 1x2x3 y1y2y3 y1y2y3 x1x2x3 R R-1 合 成 關(guān) 系 （ 或 復(fù) 合 關(guān) 系 ） 設(shè) R是 一 個(gè) X到 Y的 關(guān) 系 ， S是 一 個(gè) Y到 Z的 關(guān)系 , 則 R與 S的 合 成 關(guān) 系 ( 或 復(fù) 合 關(guān) 系 ) : R S 為 ： R S =| z(xSz zRy 例 4.18 設(shè) X =x1, x2, x3, Y=y1, y2, y3, Z=z1, z2, z3 從 X 到 Z的 關(guān)

33、 系 S =, 從 Z 到 Y的 關(guān) 系 R = , 則 X到 Y的 關(guān) 系 R S = , X Z Y X YRS R S x 1x2x3 z1z2z3 y1 y2y3 x1x2x3 y1y3y2 例 4.19 設(shè) 有 集 合 A=4,5,8,15, B=3,4,5,9,11C=1,6,8,13, F 是 由 A 到 B 的 關(guān) 系 , G 是 由 B 到 C 的關(guān) 系 ,分 別 定 義 為 F=| |b-a|=1 G=| |b-c|=2或 |b-c|=4求 合 成 關(guān) 系 G F和 F G 解 先 求 G F, 由 題 意 知 F=, , G=, , G F= , 例 4.19(續(xù) ) 設(shè)

34、 有 集 合 A=4,5,8,15, B=3,4,5,9,11C=1,6,8,13, F 是 由 A 到 B 的 關(guān) 系 , G 是 由 B 到 C 的關(guān) 系 ,分 別 定 義 為 F=| |b-a|=1 G=| |b-c|=2或 |b-c|=4求 合 成 關(guān) 系 G F和 F G 解 再 求 F G, 由 題 意 知 G=, , F=, , F G= 例 4.20: 設(shè) A=2,3 , G=, , R=, , 則 R-1 , R G， G R， R A, R , RA, R分 別 是 R-1 = , , R G=, G R= , , R A=| x R y xA= R = RA =ran (

35、 R A ) =2 R= 注 意 ： 逆 運(yùn) 算 的 優(yōu) 先 級(jí) 高 于 其 他 運(yùn) 算 ， 而 所 有 的 關(guān) 系運(yùn) 算 都 優(yōu) 于 集 合 運(yùn) 算 。 例 4.21： 設(shè) F=, 求 F F， F a， F a解 因 為 F=, F=, 所 以 F F= 由 公 式 F A =| xFy x A)有 F a= 由 公 式 FA =ran(F A )有 F a=ran(F a)=ran= a 定 義 域 值 域 綜 上 所 述 ,兩 個(gè) 關(guān) 系 的 合 成 , 如 F與 G的 合 成 記 作 F G， 其 中 F G=| z(xGz zFy 稱 為 關(guān) 系 的 合 成 運(yùn) 算 。 它 是 對(duì)

36、 關(guān) 系 的 一 種 二 元 運(yùn) 算 ， 通 過 這 種 運(yùn) 算 ， 可 由兩 個(gè) 已 知 關(guān) 系 產(chǎn) 生 一 個(gè) 新 的 關(guān) 系 。 例 4.22 設(shè) A=1,2,3,4， B=2,3,4， C=1,2,3， 且R1=| aA bB (a+b)=5，R2=| bB cC (bc)=2， 求 R1R2。解 ： 由 題 意 知 ：R1=， ， R2=， R1R2 = , 例 4.23 設(shè) R1=， ， R2=， ， 求 R1R2； R2R1； R1R1 ； (R1R2)R1 ； R1(R2R1)。解 ： R2R1 = ， ， R1R2 = (不 滿 足 交 換 律 ) R1R1=， ， (R 1

37、oR2)R1= R1(R2oR1)= (滿 足 結(jié) 合 律 ) 定 理 4.1 設(shè) F、 G、 H是 任 意 關(guān) 系 , 則 (1) (F-1)-1=F (2) dom(F-1)=ranF , ranF-1=domF (3) (F G) H= F (G H) (4) (F G)-1= G-1 F-1證 明 : (1) 任 取 ,由 逆 的 定 義 有 (F-1)-1 F-1 F (F-1) -1 = F(2) 任 取 x,x ran F -1 y( F-1 ) y( F) x dom F ran F-1 = dom F同 理 可 證 dom (F-1) = ran F 定 理 4.2 設(shè) F、

38、 G、 H是 任 意 關(guān) 系 ,則 (1) F (G H)= F G F H (2) (G H) F= G F H F (3) F (GH) F G F H (4) (GH) F G F H F本 定 理 對(duì) 有 限 個(gè) 關(guān) 系 的 并 和 交 都 成 立 。R (R1 R2 Rn)= R R1 R R2 R Rn(R1 R2 Rn) R= R1 R R2 R Rn RR (R 1R2 Rn) R R1R R2 R Rn(R1R2 Rn) R R1 RR2 RRn R 定 義 4.10 設(shè) R是 A上 的 關(guān) 系 , n為 自 然 數(shù) ， 則 R的 n次 冪 規(guī) 定 如 下 (1) R0= |

39、 x A (2) Rn= Rn-1 R n1 由 定 義 可 以 知 道 R0就 是 A上 的 恒 等 關(guān) 系 IA， 不 難 證明 下 面 的 等 式 R R0 =R=R0 R 由 這 個(gè) 等 式 立 即 可 以 得 到 R1 =R0 R =R例 4.24 設(shè) A= a,b,c,d ,R= , 求 R0 ， R1， R2， R3 ， R4和 R5解 R 0 = , R1 = R0 R = , , = , R2 = R R = , , = , R3 = R2 R = , , =, R4 = R3 R = , , =, R5 = R4 R = , , =, 例 4.25 設(shè) A= 1， 2， 3

40、， 4 ，A上 的 關(guān) 系 R=|aA bA (ab)=1，求 ： R2 ， R3， R4解 ： 因 為 R = ， ， ，所 以 R2 = ， R3 = ，R 4= 。 定 理 4.3 設(shè) R是 A上 的 關(guān) 系 , m, n 為 自 然 數(shù) ， 則 下 面的 等 式 成 立 (1) Rm Rn= Rm+n (2) (Rm)n= Rmn證 明 ：(1) 任 給 m， 對(duì) n作 歸 納 法 。n=0時(shí) ， Rm R0=Rm = Rm+0。假 設(shè) Rm Rn=Rm+n， 那 么 RmRn+1=Rm(RnR1)= (RmRn )R1= Rm+nR1= Rm+n+1= Rm+(n+1) 。(2) 任

41、 給 m， 對(duì) n作 歸 納 法 。n=0時(shí) ， (R m)0= R0 = Rm0。假 設(shè) (Rm)n=Rmn。那 么 (Rm)n+1= (Rm)n Rm = Rmn Rm= Rmn+m= Rm(n+1) 0 1 1 0 0 1 1 0 1 1 1 0M 2 =MM= 1 0 0 0 1 0 0 0 = 0 1 1 0 0 1 1 0 0 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 1 1 0 1 1 1 0M 3 = M2M = 0 1 1 0 1 0 0 0 = 1 1 1 0 1 1 1 0 0 1 1 0 1 1 1 0 0 0 0

42、0 0 0 0 0 0 0 0 0例 4.25： 設(shè) A = 1,2,3,4, R 是 A 上 二 元 關(guān) 系 ， 關(guān) 系矩 陣 為 0 1 1 0M = 1 0 0 0 0 1 1 0 0 0 0 0解 ： R， R2 , R3 的 關(guān) 系 矩 陣 分 別 為 ：求 R 3。 (M為 R的 關(guān) 系 矩 陣 ) 設(shè) R 是 A 上 的 關(guān) 系 ， R 的 性 質(zhì) 主 要 有 以 下 5 種(1) 若 x(x A R),則 稱 R 在 A 上 是 自 反 的 。也 就 是 說 ， 對(duì) RAA， 若 A中 每 個(gè) x， 都 有 xRx， 則 稱 R是 自 反 的 ， 即 A上 關(guān) 系 R是 自 反

43、 的 x(xAxRx)該 定 義 表 明 了 ， 在 自 反 的 關(guān) 系 R中 ， 除 其 他 有 序 對(duì) 外 ，必 須 包 括 有 全 部 由 每 個(gè) xA所 組 成 的 元 素 相 同 的 有 序 對(duì)例 如 ： 設(shè) A=1, 2, 3, R 是 A 上 的 關(guān) 系 ， R=, , 則 R 是 自 反 的 4.3 關(guān) 系 的 性 質(zhì) 設(shè) R 是 A 上 的 關(guān) 系 ， R 的 性 質(zhì) 主 要 有 以 下 5 種(2) 若 x(x A R),則 稱 R 在 A 上 是 反 自 反 的也 就 是 說 ， 對(duì) RAA， 若 A中 每 個(gè) x， 有 xRx， 則 稱 R是反 自 反 的 ， 即 A上

44、 關(guān) 系 R是 反 自 反 的 x(xAxRx)該 定 義 表 明 了 ， 一 個(gè) 反 自 反 的 關(guān) 系 R中 ， 不 應(yīng) 包 括 有 任何 相 同 元 素 的 有 序 對(duì) 。例 如 ： 設(shè) A=1,2,3， R 是 A 上 的 關(guān) 系 ， R=, R是 反 自 反 的 4.3 關(guān) 系 的 性 質(zhì) 對(duì) 關(guān) 系 圖 ： 若 R 是 自 反 的 ,則 每 個(gè) 結(jié) 點(diǎn) 都 有 自 回 路出 現(xiàn) .若 R是 反 自 反 ,則 每 個(gè) 結(jié) 點(diǎn) 沒 有 自 回 路 出 現(xiàn) 。 對(duì) 關(guān) 系 矩 陣 ： 若 R是 自 反 的 ,當(dāng) 且 僅 當(dāng) 在 關(guān) 系 矩 陣 中 ，對(duì) 角 線 上 的 所 有 元 素 都

45、 是 1， 若 R是 反 自 反 的 ,當(dāng) 且僅 當(dāng) 在 關(guān) 系 矩 陣 中 ， 對(duì) 角 線 上 的 所 有 元 素 都 是 0。 1 1 1* * * *RM cab 應(yīng) 該 指 出 ， 任 何 一 個(gè) 不 是 自 反 的 關(guān) 系 ， 未 必 是 反 自 反的 ； 反 之 ， 任 何 一 個(gè) 不 是 反 自 反 的 關(guān) 系 ， 未 必 是 自 反的 。 這 就 是 說 ， 存 在 既 不 是 自 反 的 也 不 是 反 自 反 的 二元 關(guān) 系 。例 如 ： 設(shè) A=1,2,3, R 是 A 上 的 關(guān) 系 ， R=, 缺 少 則 R是 既 不 是 自 反 的 ， 也 不 是 反 自 反 的

46、 4.3 關(guān) 系 的 性 質(zhì) (3) 若 x y(x,y A R R),則 稱 R 在 A上 是 對(duì) 稱 的 。也 就 是 說 , 對(duì) RAA, 對(duì) A中 每 個(gè) x和 y, 若 xRy, 則 yRx, 稱R是 對(duì) 稱 的 , 即 A上 關(guān) 系 R是 對(duì) 稱 的 ( x ) ( y ) ( x , y A x R y y R x )該 定 義 表 明 了 ， 在 表 示 對(duì) 稱 的 關(guān) 系 R的 有 序 對(duì) 集 合 中 ，若 有 有 序 對(duì) ， 則 必 定 還 會(huì) 有 有 序 對(duì) 。例 如 ： 設(shè) A=1,2,3,R是 A上 的 關(guān) 系 ， R 4=, , 則 R 是 對(duì) 稱 的 (4) 若

47、x y(x,y A R xy R), 則 稱 R在 A上 是 反 對(duì) 稱 的 。 ( 隱 含 x = y R )也 就 是 說 , 對(duì) RAA， 對(duì) A中 每 個(gè) x和 y， 若 xRy且 yRx，則 x=y， 稱 R是 反 對(duì) 稱 的 ， 即A上 關(guān) 系 R是 反 對(duì) 稱 的 ( x ) ( y ) ( x , y A x R y y R x x = y )該 定 義 表 明 了 ， 在 表 示 反 對(duì) 稱 關(guān) 系 R的 有 序 對(duì) 集 合 中 ，若 存 在 有 序 對(duì) 和 ， 則 必 定 是 x=y。 或 者 說 ，在 R中 若 有 有 序 對(duì) ， 則 除 非 x=y， 否 則 必 定 不

48、 會(huì) 出現(xiàn) 。例 如 ： 設(shè) A=1,2,3, R=, 是 A上 的 關(guān) 系 ， 則 R是 反 對(duì) 稱 的 判 斷 一 個(gè) 關(guān) 系 是 否 反 對(duì)稱 , 通 俗 地 講 就 是 對(duì) 于所 有 的 a,b A, 若 ab,則 序 偶 ,至多 只 有 一 個(gè) 出 現(xiàn) 在 關(guān) 系R中 。 如R=, 有 些 關(guān) 系 既 是 對(duì) 稱 的 又 是 反 對(duì) 稱 的還 有 的 關(guān) 系 既 不 是 對(duì) 稱 的 又 不 是 反 對(duì) 稱 的 ，例 如 ： 設(shè) A=1,2,3, R6 , R7是 A上 的 關(guān) 系 ， R6= R7=, , 則 R6是 對(duì) 稱 的 ， 也 是 反 對(duì) 稱 的 R7既 不 是 對(duì) 稱 的

49、 又 不 是 反 對(duì) 稱 的再 如 ， A=a, c, b,中 R=, 既 不 是 對(duì) 稱 的 又 不 是 反 對(duì) 稱 的 。 例 4.26 設(shè) A=1， 2， 3 則 R1=, , ,在 A上 是 自 反 的 ， 對(duì) 稱 的 ， 反 對(duì) 稱 的 。 R2=, , ,在 A上 既 不 是 對(duì) 稱 的 ， 也 不 是 對(duì) 反 稱 的 。 R3=, , ,在 A上 是 對(duì) 稱 的 ， 但 不 是 反 對(duì) 稱 的 。 R 4=, ),在 A上 不 是 對(duì) 稱 的 ， 但 是 反 對(duì) 稱 的 。 例 4.27 設(shè) A =1,2,3,4,5, A 上 的 關(guān) 系 R為 R=| a-b是 偶 數(shù) 用 列

50、舉 法 表 示 R R是 否 自 反 、 對(duì) 稱 、 反 對(duì) 稱 ？解 : R=, , , , , , , , 對(duì) 任 意 a A , a-a=0是 偶 數(shù) R 是 自 反 關(guān) 系 又 對(duì) 任 意 a, b A , 若 a-b是 偶 數(shù) , 則 b-a也 是 偶 數(shù) R 是 對(duì) 稱 關(guān) 系 。 當(dāng) ab時(shí) ， 有 和 同 時(shí) 出 現(xiàn) 在 R中 , 例 如 , , , , , R 不 是 反 對(duì) 稱 關(guān) 系 。 若 關(guān) 系 R是 對(duì) 稱 的 ， 當(dāng) 且 僅 當(dāng) 關(guān) 系 矩 陣 關(guān)于 主 對(duì) 角 線 是 對(duì) 稱 的 ， 且 在 關(guān) 系 圖 上 ，任 何 兩 個(gè) 結(jié) 點(diǎn) 間 若 有 定 向 弧 線

51、， 必 是 成對(duì) 反 向 出 現(xiàn) 。 若 關(guān) 系 R是 反 對(duì) 稱 的 ， 當(dāng) 且 僅 當(dāng) 關(guān) 系 矩 陣中 以 主 對(duì) 角 線 對(duì) 稱 的 元 素 不 能 同 時(shí) 為 1，在 關(guān) 系 圖 上 兩 個(gè) 不 同 結(jié) 點(diǎn) 間 的 定 向 弧 不能 成 對(duì) 出 現(xiàn) 。 R1=,; R2=,R3=,; R4=, 1 1 0 00 1 00 0 1RM 12 3 2 0 1 10 0 01 0 0RM 12 3 3 1 11 0RM 12 24 0 1 00 0 10 0 0RM 132 (5) xyz(x,y,z A R R R) 則 稱 R在 A上 是 傳 遞 的 關(guān) 系 。也 就 是 說 , 對(duì)

52、RAA， 對(duì) 于 A中 每 個(gè) x, y, z， 若 xRy且 yRz，則 xRz， 稱 R是 傳 遞 的 ， 即A上 關(guān) 系 R是 傳 遞 的(x)(y)(z)(x,y,zAxRyyRzxRz)該 定 義 表 明 了 ， 在 表 示 可 傳 遞 關(guān) 系 R的 有 序 對(duì) 集 合 中 ， 若有 有 序 對(duì) 和 ， 則 必 有 有 序 對(duì) 。 換 句 話 說 ,設(shè) R為 定 義 在 集 合 A上 的 二 元 關(guān) 系 ， 如 果對(duì) 于 任 意 a， b ， cA， 每 當(dāng) 有 aRb 且 有 bRc時(shí) ， 就 有aRc， 則 稱 關(guān) 系 R在 A上 是 可 傳 遞 的 。 即 ： R在 A上 傳

53、遞 abc(aA) (bA) (cA) (aRb) (bRc)aRc)例 4.28 設(shè) A=a， b， c， dR1=， ， ， R 2=， , ， ， R3=， ， ， ， R1， R2 , R3是 可 傳 遞 的 。 傳 遞 性 在 關(guān) 系 圖 上 表 現(xiàn) 為 ： 從 一 個(gè) 結(jié) 點(diǎn) 到另 一 個(gè) 結(jié) 點(diǎn) ， 如 果 是 可 達(dá) 的 ， 則 必 有 長 度為 1的 路 。 cab d例 4.29 設(shè) A=a， b， c， d， 試 討 論 下 列 關(guān) 系 的 性 質(zhì)R1=， ， ， ， ， ， ， R 2=， ， R1 是 自 反 的 ， 對(duì) 稱 的 ， 可 傳 遞 的 。R2 不 是 自

54、 反 ， 是 反 自 反 。 反 對(duì) 稱 ， 可 傳 遞 的 (5) xyz(x,y,z A R R R) 則 稱 R在 A上 是 傳 遞 的 關(guān) 系 。例 4.30 設(shè) A =1,2,3,4,5, A 上 的 關(guān) 系 R為 R=| a-b是 偶 數(shù) 用 列 舉 法 表 示 R R是 否 是 可 傳 遞 的 ？解 : R=, , , , , , , , 對(duì) 于 任 意 的 a, b, c A 若 a-b = 2m, b-c = 2n, 則 a-c = (a-b)+(b-c) = 2(m+n) 也 是 偶 數(shù) 。 因 此 A是 可 傳 遞 的 。 R R R 例 4.31 設(shè) A = 1,2,3

55、,4,5,6,7,8,9,10 R是 A上 的 關(guān) 系 ， R=|x,y A x+y=10 說 明 R具 有 哪 些 性 質(zhì) 。 4.3 關(guān) 系 的 性 質(zhì)解 ： R=, , , , , , , 易 知 R既 不 是 自 反 也 不 是 反 自 反 的 R是 對(duì) 稱 的 R不 是 反 對(duì) 稱 的 R不 是 傳 遞 的 。 P1 P3P4P2 這 個(gè) 關(guān) 系 如 右 圖 所 示 。 我 們 知 道 ， 調(diào) 用關(guān) 系 是 傳 遞 的 ， 如 P1能 調(diào) 用 P2， P2能 調(diào) 用 P4，則 P1亦 能 調(diào) 用 P4。 我 們 希 望 在 R的 基 礎(chǔ) 上 建立 一 個(gè) 滿 足 傳 遞 性 的 新

56、關(guān) 系 ， 譬 如 說 ， 下 面的 關(guān) 系 R即 是 這 樣 一 個(gè) 關(guān) 系 4.4 關(guān) 系 的 閉 包 什 么 叫 一 個(gè) 關(guān) 系 上 的 閉 包 呢 ？ 設(shè) 有 四 個(gè) 程 序 所 組 成 的 集 合 P = P1 , P2 , P3 , P4 上的 “ 調(diào) 用 ” 關(guān) 系 R：R= , , , R=,當(dāng) 然 滿 足 這 個(gè) 條 件 的 關(guān) 系 不 僅 僅 R一 個(gè) ， 如 下 面 的 關(guān) 系R亦 是R=, 我 們 選 用 滿 足 這 個(gè) 條 件 的 最 小 者 ， 在 這 個(gè) 例 子 中 即為 R。 這 個(gè) R我 們 就 叫 做 R上 的 傳 遞 閉 包 。 R是 一 個(gè)新 關(guān) 系 ，

57、 它 是 在 集 合 P上 的 一 個(gè) 新 的 調(diào) 用 關(guān) 系 顯 然 有 R R R R 選 用 滿 足 這 個(gè) 條 件 的 最 小 者 R, 這 個(gè) 新 關(guān) 系 叫 做 R上 的 傳 遞 閉 包 ， 它 是 在 集 合 P上 的 一 個(gè) 新 的 調(diào) 用 關(guān) 系 。 對(duì) 于 關(guān) 系 的 自 反 性 、 對(duì) 稱 性 、 傳 遞 性 均 可 建 立 閉 包 定 義 4.11 設(shè) R是 非 空 集 合 A上 的 關(guān) 系 ， R的 自 反 (對(duì) 稱或 傳 遞 )閉 包 是 A上 的 關(guān) 系 R,使 得 R滿 足 以 下 條 件 :(1) R是 自 反 (對(duì) 稱 或 傳 遞 )的(2) R R (3)

58、 對(duì) A上 的 任 何 包 含 R的 自 反 (對(duì) 稱 或 傳 遞 )關(guān) 系 R 有 R R 一 般 將 R的 自 反 閉 包 記 作 r(R),對(duì) 稱 閉 包 記 作 s(R)， 傳 遞 閉 包 記 作 t(R)。 4.4 關(guān) 系 的 閉 包 例 4.33 設(shè) A=a， b， c， d， 試 討 論 下 列 關(guān) 系 的 性 質(zhì) R=， ， ， R=， ， ， , R =， ， ， , , cab d R=， ， ， , R=， ， ， , , 閉 包 ： 包 含 一 些 給 定 對(duì) 象 ， 具 有 指 定 性 質(zhì) 的 最 小 集 合 。 “ 最 小 ” ： 任 何 包 含 同 樣 對(duì) 象 ，

59、 具 有 同 樣 性 質(zhì) 的集 合 ， 都 包 含 這 個(gè) 閉 包 集 合 。cab d 定 理 4.4 設(shè) R是 非 空 集 合 A上 的 關(guān) 系 ， 則 有(1) r(R) =R R0(2) s(R) =R R-1(3) t(R)= R R2 R3 此 定 理 提 供 了 一 種 集 合 表 示 形 式 下 關(guān)系 閉 包 的 求 解 方 法 4.4 關(guān) 系 的 閉 包 例 4.34 設(shè) A = a,b,c,d, R=, , , , , 則r(R) =R R0= , , , , , , , ,s(R) =R R-1 = , , , , , , , , = , , , , , , , t(R)

60、= R R 2 R3 (甚 不 方 便 ) 當(dāng) 關(guān) 系 用 關(guān) 系 矩 陣 表 示 時(shí) ， 相應(yīng) 閉 包 求 法 為 ： (1) Mr =M+E(2) Ms =M+M(3) Mt=M+M2+M3+其 中 M為 R的 關(guān) 系 矩 陣 ， E是單 位 矩 陣 ， M 是 M的 轉(zhuǎn) 置 矩陣 . 4.4 關(guān) 系 的 閉 包 0 1 0 0 1 0 0 0 1 1 0 0Mr =M+E= 1 0 1 0 + 0 1 0 0 = 1 1 1 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 1 0 0Ms=M+M= 1

61、 0 1 0 + 1 0 0 1 = 1 0 1 1 0 0 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0 0 1 0 0 1 1 0 1 1 1 1M t= M+M2+M3+ = 1 1 1 1 1 1 1 1 1 1 1 1 例 4.35 設(shè) A = a,b,c,d,R=, , , , , 則 4.4 關(guān) 系 的 閉 包E表 示 同 階 單 位 陣 ；M表 示 M的 轉(zhuǎn) 置矩 陣 a b c dabcd 當(dāng) 關(guān) 系 用 關(guān) 系 圖 表 示 時(shí) ， 相 應(yīng) 閉 包 求 法 為 : 設(shè) R, r(R), s(R), t(R) 的 關(guān) 系 圖 分 別 為 G,Gr,Gs,Gt,則

62、Gr,Gs,Gt與 G的頂 點(diǎn) 集 相 等 ,除 了 G的 邊 以 外 依 據(jù) 下 列 方 法 添 加 新 的 邊 :(1)考 察 G的 每 個(gè) 頂 點(diǎn) ,如 果 沒 有 環(huán) 就 加 上 一 個(gè) 環(huán) ,最 終 得到 的 是 Gr 。(2)考 察 G的 每 一 條 邊 ， 如 果 有 一 條 xi到 xj的 單 向 邊 ， ij， 則 在 G中 加 一 條 xj到 xi的 反 方 向 邊 ， 最 終 得 到 Gs 。(3)考 察 G的 每 個(gè) 頂 點(diǎn) xi,找 出 從 xi出 發(fā) 的 所 有 2步 ,3步 ,n步 長 的 路 徑 (n為 G中 的 頂 點(diǎn) 數(shù) ).設(shè) 路 徑 的 終 點(diǎn) 為 xj

63、1,xj2, ,x jk， 如 果 沒 有 從 xi到 xjl (i=1,2, ,k)的 邊 ， 就 加 上 這條 邊 ， 最 終 得 到 Gt 。例 題 參 見 P93例 4.10 4.5 等 價(jià) 關(guān) 系 和 偏 序 關(guān) 系定 義 4.12 設(shè) R是 非 空 集 合 A上 的 關(guān) 系 。 若 R是 自 反 的 、對(duì) 稱 的 和 傳 遞 的 , 則 稱 R是 A上 的 等 價(jià) 關(guān) 系 如 果 R是 一 個(gè) 等 價(jià) 關(guān) 系 ， 若 R,稱 x等價(jià) 于 y,記 作 xy。 等 價(jià) 關(guān) 系 = 自 反 性 + 對(duì) 稱 性 + 傳 遞 性也 就 是 說 ,若 R, 或 aRb, 稱 a等 價(jià) b, 記

64、 ab 由 于 R是 對(duì) 稱 的 ， a等 價(jià) b即 b等 價(jià) a， 反 之 亦 然 ，a與 b彼 此 等 價(jià) 。. 例 4.36 設(shè) 有 一 個(gè) 整 數(shù) 集 Z 上 的 關(guān) 系 R： R=|x-y 可 被 3整 除 求 證 這 個(gè) 關(guān) 系 是 等 價(jià) 關(guān) 系 。證 ： 對(duì) 每 個(gè) xZ, x-x可 被 3整 除 ， 所 以 是 自 反 的 。 對(duì) 于 x, yZ, 如 果 x-y能 被 3整 除 ， 則 y-x也 能 被 3 整 除 所 以 是 對(duì) 稱 的 。 對(duì) 于 x, yZ, 如 果 有 x-y， y- c均 能 被 3整 除 ， 則 x-c =(x-y)+(y-c)亦 能 被 3整

65、除 ， 所 以 是 傳 遞 的 。將 這 個(gè) 例 子 推 廣 到 一 般 ， 比 如 ：例 4.30 設(shè) A=1,2,3,4,5,6,7,8,R為 A上 的 關(guān) 系 R=|x,y A x=y(mod 3)其 中 ， x=y(mod 3)的 含 義 就 是 x-y可 以 被 3整 除 。這 個(gè) 關(guān) 系 亦 是 等 價(jià) 關(guān) 系 )(, yxAPyxyxR 例 4.37 設(shè) 集 合 A a,b,R是 P(A)上 的 包 含 關(guān) 系 ,寫 出 R的 表 達(dá) 式 和 關(guān) 系 矩 陣 . 解 用 描 述 法 表 示 ；用 列 舉 法 表 示 ： 因 為 所 以 , , AAAbbbAa aaAbaR ,)

66、( AbaAP 1000 1100 1010 1111RM a b A 圖 4 1關(guān) 系 矩 陣 關(guān) 系 圖 a bA 例 4.38 設(shè) A 1,2,3,用 列 舉 法 給 出 A上 的 恒 等 關(guān) 系 IA,全 域 關(guān) 系 EA, A上 的 小 于 關(guān) 系及 其 逆 關(guān) 系 和 關(guān) 系 矩 陣 關(guān) 系 矩 陣 a A , yxAyxyxLA 3,3,2,2,1,1 AI AA IE ,2,3,1,3,3,2,1,2,3,1,2,1 3,2,3,1,2,1 AL 2,3,1,3,1,21 ALLA的 逆 關(guān) 系 000 100 110 ALM 011 001 0001ALM TLL AA MM 1有 例 4.39 設(shè) 集 合 A 2,3,4, B=4,6,7, C=8,9,12,14. R1是由 A到 B的 二 元 關(guān) 系 ,R2是 由 B到 C的 二 元 關(guān) 系 ,定 義 如 下 :a A解 : ,1 baabaR 整 除是 素 數(shù) 且 ,2 cbcbR 整 除求 復(fù) 合 關(guān) 系 R2 R1 和 R1 R2 并 用 關(guān) 系 矩 陣 表 示 6,3,6,2,4,21 R 14,7,12