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

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

1、第 7章 二 元 關(guān) 系離 散 數(shù) 學(xué)中國地質(zhì)大學(xué)本科生課程 本 章 說 明q本 章 的 主 要 內(nèi) 容 有 序 對 與 笛 卡 兒 集 二 元 關(guān) 系 的 定 義 和 表 示 法 關(guān) 系 的 運(yùn) 算 關(guān) 系 的 性 質(zhì) 關(guān) 系 的 閉 包 等 價(jià) 關(guān) 系 與 劃 分 偏 序 關(guān) 系q本 章 與 后 續(xù) 各 章 的 關(guān) 系 本 章 是 函 數(shù) 的 基 礎(chǔ) 本 章 是 圖 論 的 基 礎(chǔ) 本 章 內(nèi) 容7.1 有 序 對 與 笛 卡 兒 積7.2 二 元 關(guān) 系7.3 關(guān) 系 的 運(yùn) 算7.4 關(guān) 系 的 性 質(zhì)7.5 關(guān) 系 的 閉 包7.6 等 價(jià) 關(guān) 系 與 劃 分7.7 偏 序 關(guān) 系

2、本 章 小 結(jié) 習(xí) 題 作 業(yè) 7.1 有 序 對 與 笛 卡 兒 積 定 義 7.1 由 兩 個(gè) 元 素 x和 y（ 允 許 x=y） 按 一 定 順 序 排 列 成 的 二 元組 叫 做 一 個(gè) 有 序 對 (ordered pair)或 序 偶 ， 記 作 ， 其 中 x是 它 的 第 一 元 素 ， y是 它 的 第 二 元 素 。有 序 對 具 有 以 下 性 質(zhì) ： （ 1） 當(dāng) x y時(shí) ， 。 （ 2） 的 充 分 必 要 條 件 是 x u且 y v。 說 明 q 有 序 對 中 的 元 素 是 有 序 的q 集 合 中 的 元 素 是 無 序 的 例 7.1例 7.1 已

3、知 ， 求 x和 y。 由 有 序 對 相 等 的 充 要 條 件 有 x + 2 52x+y 4 解 得 x 3,y -2。 解 答 定 義 7.2 設(shè) A， B為 集 合 ,用 A中 元 素 為 第 一 元 素 ， B中 元 素 為 第二 元 素 構(gòu) 成 有 序 對 。 所 有 這 樣 的 有 序 對 組 成 的 集 合 叫 做 A和 B的 笛 卡 兒 積 (Cartesian product)， 記 作 A B。笛 卡 兒 積 的 符 號 化 表 示 為A B |x A y B 笛 卡 兒 積 的 定 義q A表 示 某 大 學(xué) 所 有 學(xué) 生 的 集 合 ， B表 示 大 學(xué) 開 設(shè)

4、的 所 有課 程 的 集 合 ，則 A B可 以 用 來 表 示 該 校 學(xué) 生 選 課 的 所 有 可 能 情 況 。q 令 A是 直 角 坐 標(biāo) 系 中 x軸 上 的 點(diǎn) 集 ， B是 直 角 坐 標(biāo) 系 中 y軸 上 的 點(diǎn) 集 ，于 是 A B就 和 平 面 點(diǎn) 集 一 一 對 應(yīng) 。 舉 例 笛 卡 爾 積 舉 例設(shè) A=a,b, B=0,1,2， 則A B=,B A=, 舉 例 說 明 q 如 果 |A|=m,|B|=n,則 |A B|=mn。 笛 卡 兒 積 的 運(yùn) 算 性 質(zhì) (1)對 任 意 集 合 A， 根 據(jù) 定 義 有A , A (2)一 般 的 說 ， 笛 卡 兒 積

5、 運(yùn) 算 不 滿 足 交 換 律 ， 即A B B A (當(dāng) A B A B 時(shí) )(3)笛 卡 兒 積 運(yùn) 算 不 滿 足 結(jié) 合 律 ， 即(A B) C A (B C) (當(dāng) A B C 時(shí) )(4)笛 卡 兒 積 運(yùn) 算 對 并 和 交 運(yùn) 算 滿 足 分 配 律 ， 即A (B C)=(A B) (A C)(B C) A=(B A) (C A)A (B C)=(A B) (A C) (B C) A=(B A) (C A)(5)AC BD A B C D A (B C)=(A B) (A C)的 證 明任 取 A (B C) x A y B C x A (y B y C) (x A y

6、 B) (x A y C) A B A C (A B) (A C) 所 以 A (B C)=(A B) (A C) 關(guān) 于 AC BD A BC D的 討 論該 性 質(zhì) 的 逆 命 題 不 成 立 ， 可 分 以 下 情 況 討 論 。（ 1） 當(dāng) A=B=時(shí) ， 顯 然 有 AC 和 BD 成 立 。（ 2） 當(dāng) A 且 B 時(shí) ， 也 有 AC和 BD成 立 ， 證 明 如 下 ：任 取 x A， 由 于 B ,必 存 在 y B,因 此 有 x A y B A B C D x C y D x C 從 而 證 明 了 AC。同 理 可 證 BD。 關(guān) 于 AC BD A BC D的 討 論

7、該 性 質(zhì) 的 逆 命 題 不 成 立 ， 可 分 以 下 情 況 討 論 。（ 3） 當(dāng) A 而 B 時(shí) ， 有 AC成 立 ， 但 不 一 定 有 BD成 立 。 反 例 ： 令 A ,B 1,C 3,D 4。（ 4） 當(dāng) A 而 B 時(shí) ， 有 BD成 立 ， 但 不 一 定 有 AC成 立 。 反 例 略 。 例 7.2例 7.2 設(shè) A=1,2,求 P(A) A。 P(A) A ,1,2,1,2 1,2 , , 解 答 例 7.3例 7.3 設(shè) A， B， C， D為 任 意 集 合 ， 判 斷 以 下 命 題 是 否 為 真 ， 并說 明 理 由 。(1) A B A C B C(

8、2) A-(B C) (A-B) (A-C)(3) A B C D A C B D(4) 存 在 集 合 A， 使 得 A A A(1) 不 一 定 為 真 。 當(dāng) A ， B 1,C 2時(shí) ， 有 A B A C， 但 B C。(2) 不 一 定 為 真 。 當(dāng) A=B=1,C 2時(shí) ， 有 A-(B C) 1 1 (A-B) (A-C) 1 (3) 為 真 。 由 等 量 代 入 的 原 理 可 證 。 (4) 為 真 。 當(dāng) A 時(shí) ， 有 AA A 成 立 。 解 答 7.2 二 元 關(guān) 系 (binary relation)定 義 7.3 如 果 一 個(gè) 集 合 滿 足 以 下 條

9、件 之 一 ：（ 1） 集 合 非 空 ， 且 它 的 元 素 都 是 有 序 對（ 2） 集 合 是 空 集 則 稱 該 集 合 為 一 個(gè) 二 元 關(guān) 系 ， 記 作 R。 二 元 關(guān) 系 也 可 簡 稱 為 關(guān)系 。 對 于 二 元 關(guān) 系 R， 如 果 R， 可 記 作 xRy； 如 果R， 則 記 作 xRy。設(shè) R 1 ,， R2 ,a,b。則 R1是 二 元 關(guān) 系 ， R2不 是 二 元 關(guān) 系 ， 只 是 一 個(gè) 集 合 ，除 非 將 a和 b定 義 為 有 序 對 。根 據(jù) 上 面 的 記 法 可 以 寫 1R12， aR1b， aR1c等 。 舉 例R ,是 否 為 二

10、元 關(guān) 系 ？ 集 合 A上 的 二 元 關(guān) 系 的 數(shù) 目 依 賴 于 A中 的 元 素 數(shù) 。如 果 |A|=n， 那 么 |A A|=n2， A A的 子 集 就 有 個(gè) 。每 一 個(gè) 子 集 代 表 一 個(gè) A上 的 二 元 關(guān) 系 ， 所 以 A上 有 個(gè) 不同 的 二 元 關(guān) 系 。例 如 |A|=3， 則 A上 有 個(gè) 不 同 的 二 元 關(guān) 系 。7.2 二 元 關(guān) 系定 義 7.4 設(shè) A， B為 集 合 ， A B的 任 何 子 集 所 定 義 的 二 元 關(guān) 系 叫 做從 A到 B的 二 元 關(guān) 系 ； 特 別 當(dāng) A=B時(shí) ， 則 叫 做 A上 的 二 元 關(guān) 系 。

11、A=0,1， B=1,2,3， 那 么 R1=， R2=A B， R3= ， R4=等 都 是 從 A到 B的 二 元 關(guān) 系 ， 而 R3和 R4同 時(shí) 也 是 A上 的二 元 關(guān) 系 。 舉 例 22n 22n232說 明 常 用 的 關(guān) 系定 義 7.5 對 任 意 集 合 A， 定 義全 域 關(guān) 系 EA=|x A y A=A A 恒 等 關(guān) 系 IA=|x A空 關(guān) 系 設(shè) A=1,2， 那 么E A=,IA=, 舉 例 其 它 常 用 的 關(guān) 系q小 于 或 等 于 關(guān) 系 ： LA=|x,y A x y， 其 中 AR。q整 除 關(guān) 系 ： DB=|x,y B x整 除 y， 其

12、 中 AZ* Z*是 非 零 整 數(shù) 集q包 含 關(guān) 系 ： R |x,y A xy， 其 中 A是 集 合 族 。 (1)設(shè) A=1,2,3， B a,b則 L A=, DA=, (2)令 A=P(B)=,a,b,a,b， 則 A上 的 包 含 關(guān) 系 是 R , , , 舉 例 例 7.4例 7.4 設(shè) A=1,2,3,4， 下 面 各 式 定 義 的 R都 是 A上 的 關(guān) 系 ， 試用 列 元 素 法 表 示 R。(1) R= | x是 y的 倍 數(shù) (2) R= | (x-y)2 A(3) R= | x/y是 素 數(shù) (4) R= | x y 解 答(1)R=, (2)R=,(3)R

13、=, (4)R=EA-IA=, , 關(guān) 系 的 表 示 方 法q關(guān) 系 的 三 種 表 示 方 法 ： 集 合 表 達(dá) 式 關(guān) 系 矩 陣 關(guān) 系 圖q關(guān) 系 矩 陣 和 關(guān) 系 圖 可 以 表 示 有 窮 集 上 的 關(guān) 系 。 關(guān) 系 矩 陣 和 關(guān) 系 圖 的 定 義設(shè) A=x1,x2,xn,R是 A上 的 關(guān) 系 。 令 n),1,2,j(i,Rx若 x0 Rx若 x1r ji jiij nnn2n1 2n2221 1n1211ij rrr rrr rrr)(r 則 是 R的 關(guān) 系 矩 陣 ， 記 作 MR。 設(shè) A=x1,x2,xn,R是 A上 的 關(guān) 系 。 令 圖 G=， 其

14、中 頂 點(diǎn)集 合 V=A， 邊 集 為 E。 對 于 xi,xj V， 滿 足 E xiRxj稱 圖 G為 R的 關(guān) 系 圖 ， 記 作 GR。 關(guān) 系 矩 陣 和 關(guān) 系 圖 的 實(shí) 例設(shè) A=1,2,3,4， R=,，則 R的 關(guān) 系 矩 陣 和 關(guān) 系 圖 分 別 是 0010 0000 1100 0011MR n元 關(guān) 系 及 其 應(yīng) 用q兩 個(gè) 以 上 集 合 的 元 素 之 間 的 關(guān) 系 稱 為 n元 關(guān) 系q例 1:R是 三 元 組 構(gòu) 成 的 關(guān) 系 ， 其 中 a,b,c是 滿 足abc的 整 數(shù) 。q例 2： R是 五 元 組 構(gòu) 成 的 表 示 飛 機(jī) 航 班 的 關(guān)

15、系 。其 中 ， A是 航 空 公 司 ， N是 航 班 好 ， S是 出 發(fā) 地 ， D是 目 的 地， T是 起 飛 時(shí) 間 。 數(shù) 據(jù) 庫 和 關(guān) 系q例 1： n元 組 的 某 個(gè) 域 的 值 能 夠 確 定 這 個(gè) n元 組時(shí) ， n元 關(guān) 系 的 這 個(gè) 域 就 叫 做 主 鍵 碼 。學(xué) 生 姓 名 學(xué) 號 專 業(yè) 平 均 成 績Ackermann 231455 計(jì) 算 機(jī) 科 學(xué) 88Adams 888323 物 理 學(xué) 75Chou 102147 軟 件 工 程 79Goodfriend 453876 數(shù) 學(xué) 75 Rao 678543 數(shù) 學(xué) 90Stevens 786576

16、 哲 學(xué) 92 數(shù) 據(jù) 庫 和 關(guān) 系q 例 2： 連 接 運(yùn) 算教 授 系 課 號Cruz 動(dòng) 物 學(xué) 335Cruz 動(dòng) 物 學(xué) 412Farber 心 理 學(xué) 501Farber 心 理 學(xué) 617Grammar 物 理 學(xué) 544 Grammar 物 理 學(xué) 551Rosen 計(jì) 算 機(jī) 518Rosen 數(shù) 學(xué) 575 系 課 號 教 室 時(shí) 間計(jì) 算 機(jī) 518 N521 2:00 p.m數(shù) 學(xué) 575 N502 3:00 p.m數(shù) 學(xué) 611 N521 4:00 p.m物 理 學(xué) 544 B505 4:00 p.m心 理 學(xué) 501 A100 3:00 p.m心 理 學(xué) 617

17、A110 11:00 a.m動(dòng) 物 學(xué) 335 A100 9:00 a.m動(dòng) 物 學(xué) 412 A100 8:00 a.m 數(shù) 據(jù) 庫 和 關(guān) 系教 授 系 課 號 教 室 時(shí) 間Cruz 動(dòng) 物 學(xué) 335 A100 9:00 a.mCruz 動(dòng) 物 學(xué) 412 A100 8:00 a.mFarber 心 理 學(xué) 501 A100 3:00 p.mFarber 心 理 學(xué) 617 A110 11:00 a.mGrammar 物 理 學(xué) 544 B505 4:00 p.m Rosen 計(jì) 算 機(jī) 518 N521 2:00 p.mRosen 數(shù) 學(xué) 575 N502 3:00 p.m 7.3 關(guān)

18、 系 的 運(yùn) 算定 義 7.6 設(shè) R是 二 元 關(guān) 系 。(1)R中 所 有 有 序 對 的 第 一 元 素 構(gòu) 成 的 集 合 稱 為 R的 定 義 域(domain)， 記 為 dom R。 形 式 化 表 示 為 ：dom R x | y( R )(2)R中 所 有 有 序 對 的 第 二 元 素 構(gòu) 成 的 集 合 稱 為 R的 值 域 (range) ， 記 作 ran R。 形 式 化 表 示 為ran R y | x( R)(3)R的 定 義 域 和 值 域 的 并 集 稱 為 R的 域 (field)， 記 作 fld R。形 式 化 表 示 為fld R dom R ran

19、 R 例 7.5 求 R=,的 定 義 域 、 值 域 和 域 。 解 答 dom R 1,2,4 ran R 2,3,4 fld R 1,2,3,4 關(guān) 系 的 逆 和 右 復(fù) 合 運(yùn) 算定 義 7.7 設(shè) R為 二 元 關(guān) 系 ， R的 逆 關(guān) 系 ， 簡 稱 R的 逆 (inverse)，記 作 R-1,其 中R-1 | R定 義 7.8 設(shè) F,G為 二 元 關(guān) 系 ， G對 F的 右 復(fù) 合 (composite)記 作FG， 其 中FG | t( F G)例 7.6 設(shè) F ,G=， 則F -1 ,FG GF 說 明 q 可 以 把 二 元 關(guān) 系 看 作 一 種 作 用 ， R可

20、 以 解 釋 為x通 過 R的 作 用 變 到 y。q FG表 示 兩 個(gè) 作 用 的 連 續(xù) 發(fā) 生 。 關(guān) 系 的 限 制 和 像定 義 7.9 設(shè) R為 二 元 關(guān) 系 ， A是 集 合(1) R在 A上 的 限 制 (restriction)記 作 R A， 其 中R A=|xRy x A (2) A在 R下 的 像 (image)記 作 RA， 其 中RA=ran(R A) 說 明 q R在 A上 的 限 制 R A是 R的 子 關(guān) 系 。q A在 R下 的 像 RA是 ran R的 子 集 。 例 7.7設(shè) R ， ， ， ， R 1 ， R R 2,3 ， ， R1 2,3R R

21、3 2 關(guān) 系 與 集 合 的 說 明q關(guān) 系 是 集 合 ， 集 合 運(yùn) 算 對 于 關(guān) 系 也 是 適 用 的 。 q規(guī) 定 ： 關(guān) 系 運(yùn) 算 中 逆 運(yùn) 算 優(yōu) 先 于 其 它 運(yùn) 算 所 有 的 關(guān) 系 運(yùn) 算 都 優(yōu) 先 于 集 合 運(yùn) 算 ， 優(yōu) 先 權(quán) 的 運(yùn) 算 以 括 號 決 定 運(yùn) 算 順 序 。 q例 如 ： ran F -1 FG FH ran (F A) 例 題q設(shè) A表 示 是 學(xué) 校 的 所 有 學(xué) 生 的 集 合 ， B表 示 學(xué) 校 的 所 有 課 程 的 集合 ， 并 設(shè) R1由 所 有 有 序 對 組 成 ， 其 中 a是 選 修 課 程 b的 學(xué) 生。

22、 R2由 所 有 的 有 序 對 構(gòu) 成 ， 其 中 課 程 b是 a的 必 修 課 。 則 關(guān)系 R1 R2、 R1 R2、 R1 R2、 R1 R2、 R2 R1的 含 義 為qR1 R2： a是 一 個(gè) 學(xué) 生 ， 他 或 者 選 修 了 課 程 b， 或 者 課 程 b是 他 的必 修 課 。qR1 R2： a是 一 個(gè) 學(xué) 生 ， 他 選 修 了 課 程 b并 且 課 程 b也 是 a的 必 修課 。 qR 1 R2： 學(xué) 生 a已 經(jīng) 選 修 了 課 程 b， 但 課 程 b不 是 a的 選 修 課 ， 或者 課 程 b是 a的 必 修 課 ， 但 是 a沒 有 選 修 它 。qR

23、1 R2： 學(xué) 生 a已 經(jīng) 選 修 了 課 程 b， 但 課 程 b不 是 a的 選 修 課 。 qR2 R1： 課 程 b是 學(xué) 生 a的 必 修 課 ， 但 是 a沒 有 選 修 它 。 定 理 7.1定 理 7.1 設(shè) F是 任 意 的 關(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 (2)任 取 x x dom F-1 y( F-1) y( F) x ran F 所 以 有 dom F-1 ran F證 明 定 理 7.2定 理 7.2 設(shè) F， G， H

24、是 任 意 的 關(guān) 系 ， 則(1)(FG)H F(GH)(2)(FG)-1 G-1 F-1證 明 (1)任 取 ， (FG)H t( FG (t,y) H) t(s( F G) H) ts( F G H) s( F t( G H) s( F GH) F(GH) 定 理 7.2定 理 7.2 設(shè) F， G， H是 任 意 的 關(guān) 系 ， 則(1)(FG)H F(GH)(2)(FG)-1 G-1F-1證 明 (2)任 取 ， (FG)-1 FG t( F G) t( F -1 G-1) G-1 F-1 定 理 7.3定 理 7.3 設(shè) R為 A上 的 關(guān) 系 ， 則R IA IA R R證 明

25、(1)任 取 ， R IA t( R (t,y) IA) t( R t y) R R R y A R I A) R IA綜 上 所 述 ， 有 RIA R同 理 可 證 IAR R 定 理 7.4定 理 7.4 設(shè) F， G， H是 任 意 的 關(guān) 系 ， 則(1) F(G H) FG FH(2) (G H)F GF HF(3) F(G H)FG FH(4) (G H)FGF HF證 明 (3) F(G H) t( F (t,y) G H) t( F (t,y) G (t,y) H) t( F (t,y) G) ( F (t,y) H) t( F (t,y) G) t( F (t,y) H)

26、FG FH FG FH 定 理 7.4的 推 論q由 數(shù) 學(xué) 歸 納 法 不 難 證 明 定 理 7.4的 結(jié) 論 對 于 有 限 多 個(gè) 關(guān) 系的 并 和 交 也 是 成 立 的 ， 即 有R(R1 R2 Rn) RR1 RR2 RRnR1 R2 Rn)R R1R R2R RnRR(R1 R2 Rn)RR1 RR2 RRnR 1 R2 Rn)RR1R R2R RnR 定 理 7.5定 理 7.5 設(shè) F為 關(guān) 系 ， A,B為 集 合 ， 則(1) F (A B) F A F B (2) FA B FA FB (3) F (A B) F A F B (4) FA BFA FB 定 理 7.5

27、 (1)的 證 明(1) F (A B) F A F B 證 明 任 取 ， 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。 定 理 7.5 (4)的 證 明(4) FA BFA FB 證 明 任 取 y， y FA B x( F x A B) x( F x A x B) x( F x A) ( F x B) x( F x A) x( F x B) y FA y FB y FA FB 所 以 有 FA BFA FB 關(guān) 系 的 冪 運(yùn) 算定 義 7.10 設(shè) R為 A上

28、 的 關(guān) 系 ， n為 自 然 數(shù) ， 則 R的 n次 冪定 義 為 ：（ 1） R0 |x A IA（ 2） Rn+1 Rn R說 明 q 對 于 A上 的 任 何 關(guān) 系 R 1和 R2都 有R10 R20 IA 即 ： A上 任 何 關(guān) 系 的 0次 冪 都 相 等 ， 都 等 于 A上 的 恒 等關(guān) 系 IA。q 對 于 A上 的 任 何 關(guān) 系 R都 有 R1 R， 因 為R1 R0 R IA R R Rn的 計(jì) 算q給 定 A上 的 關(guān) 系 R和 自 然 數(shù) n， 怎 樣 計(jì) 算 Rn呢 ？q若 n是 0或 1， 結(jié) 果 是 很 簡 單 的 。 下 面 考 慮 n 2的 情 況 。

29、 如 果 R是 用 集 合 表 達(dá) 式 給 出 的 ， 可 以 通 過 n-1次 右 復(fù) 合 計(jì) 算得 到 Rn。 如 果 R是 用 關(guān) 系 矩 陣 M給 出 的 ， 則 Rn的 關(guān) 系 矩 陣 是 Mn， 即 n個(gè) 矩 陣 M之 積 。 與 普 通 矩 陣 乘 法 不 同 的 是 ， 其 中 的 相 加 是邏 輯 加 ， 即 1+1 1， 1+0 0+1 1， 0+0 0 如 果 R是 用 關(guān) 系 圖 G給 出 的 ， 可 以 直 接 由 圖 G得 到 R n的 關(guān) 系圖 G。 G的 頂 點(diǎn) 集 與 G相 同 。 考 察 G的 每 個(gè) 頂 點(diǎn) xi， 如 果 在G中 從 xi出 發(fā) 經(jīng) 過

30、n步 長 的 路 徑 到 達(dá) 頂 點(diǎn) xj， 則 在 G中 加 一條 從 xi到 xj的 邊 。 當(dāng) 把 所 有 這 樣 的 便 都 找 到 以 后 ， 就 得 到圖 G。 例 7.8例 7.8 設(shè) A a,b,c,d， R ,， 求R的 各 次 冪 ， 分 別 用 矩 陣 和 關(guān) 系 圖 表 示 。 解 答 0000 1000 0101 0010M 0000 1000 0101 00100000 1000 0101 0010M 2 0000 1000 0101 00100000 0000 1010 0101MMM 23 1000 0100 0010 0001M0 0000 0000 1010

31、 0101 0000 0000 0101 1010 例 7.8因 此 M4 M2， 即 R4 R2。 因 此 可 以 得 到R2 R4 R6 R3 R5 R7 用 關(guān) 系 圖 的 方 法 得 到 R 0, R1, R2, R3,的 關(guān) 系 圖 如 下 圖 所 示 。 0000 1000 0101 00100000 0000 0101 1010MMM 34 0000 0000 1010 0101 冪 運(yùn) 算 的 性 質(zhì)定 理 7.6 設(shè) A為 n元 集 ， R是 A上 的 關(guān) 系 ， 則 存 在 自 然 數(shù) s和 t,使得 Rs=Rt。R為 A上 的 關(guān) 系 ， 對 任 何 自 然 數(shù) k， R

32、k都 是 A A的 子 集 。證 明 又 知 |A A|=n2， |P(A A)|= ， 2n2即 A A的 不 同 子 集 僅 個(gè) 。2n2當(dāng) 列 出 R的 各 次 冪 R0， R1， R2， ， ， 時(shí) ，2n2R必 存 在 自 然 數(shù) s和 t使 得 Rs=Rt。說 明 q 該 定 理 說 明 有 窮 集 上 只 有 有 窮 多 個(gè) 不 同 的 二 元 關(guān) 系 。當(dāng) t足 夠 大 時(shí) ， Rt必 與 某 個(gè) Rs(st)相 等 。q 如 例 7.8中 的 R 4=R2。 定 理 7.7定 理 7.7 設(shè) R是 A上 的 關(guān) 系 ， m,n N， 則(1)Rm Rn Rm+n(2)(Rm)

33、n Rmn證 明 (1)對 于 任 意 給 定 的 m N,施 歸 納 于 n。若 n=0， 則 有所 以 對 一 切 m,n N有 R m Rn Rm+n。Rm R0 Rm IA Rm Rm+0假 設(shè) Rm Rn=Rm+n， 則 有Rm Rn+1 Rm (Rn R) (Rm Rn)R Rm+n+1， 定 理 7.7定 理 7.7 設(shè) R是 A上 的 關(guān) 系 ， m,n N， 則(1)Rm Rn Rm+n(2)(Rm)n Rmn證 明 (2)對 于 任 意 給 定 的 m N,施 歸 納 于 n。若 n=0， 則 有 所 以 對 一 切 m,n N 有 (Rm)n=Rmn。(Rm)0 IA R

34、0 Rm 0假 設(shè) (Rm)n Rmn， 則 有(Rm)n+1 (Rm)n Rm Rmn+m Rm(n+1) 定 理 7.8定 理 7.8 設(shè) R是 A上 的 關(guān) 系 ， 若 存 在 自 然 數(shù) s,t(st)使 得 Rs=Rt， 則(1) 對 任 何 k N有 Rs+k=Rt+k(2) 對 任 何 k,i N有 Rs+kp+i=Rs+i， 其 中 p=t-s(3) 令 S=R0， R1， ， Rt-1， 則 對 于 任 意 的 q N有 Rq S證 明 (1) Rs+k Rs Rk Rt Rk Rt+k(2)對 k歸 納 。若 k=0， 則 有 R s+0 p+i Rs+i假 設(shè) Rs+kp

35、+i Rs+i， 其 中 p t-s， 則Rs+(k+1)p+i Rs+kp+i+p Rs+i Rp=Rs+p+i Rs+t-s+i Rt+i Rs+i由 歸 納 法 命 題 得 證 。 Rs+kp+i Rp 定 理 7.8定 理 7.8 設(shè) R是 A上 的 關(guān) 系 ， 若 存 在 自 然 數(shù) s,t(st)使 得 Rs=Rt， 則(1) 對 任 何 k N有 Rs+k=Rt+k(2) 對 任 何 k,i N有 Rs+kp+i=Rs+i， 其 中 p=t-s(3) 令 S=R0， R1， ， Rt-1， 則 對 于 任 意 的 q N有 Rq S證 明 (3)任 取 q N， 若 qt， 顯

36、然 有 Rq S，若 q t， 則 存 在 自 然 數(shù) k和 i使 得 q s+kp+i其 中 0 i p-1,p t-s。 于 是 R q Rs+kp+i Rs+i而 s+i s+p-1 s+t-s-1 t-1這 就 證 明 了 Rq S。 定 理 7.8的 說 明q有 窮 集 A上 的 關(guān) 系 R的 冪 序 列 R0， R1， 是 一 個(gè) 周 期 性 變 化 的 序 列。 就 象 正 弦 函 數(shù) 一 樣 ， 利 用 它 的 周 期 性 可 以 將 R的 高 次 冪 化 簡 為R的 低 次 冪 。例 7.9 設(shè) A=a,b,d,e,f， R=,。 求 出 最 小 的 自 然 數(shù) m和 n，

37、使 得 mn且 Rm=Rn。 解 答 由 R的 定 義 可 以 看 出 A中 的 元 素 可 分 成 兩 組 ， 即 a,b和d,e,f。 它 們 在 R的 右 復(fù) 合 運(yùn) 算 下 有 下 述 變 化 規(guī) 律 ： a b a b d e f d e f對 于 a或 b,每 個(gè) 元 素 的 變 化 周 期 是 2。 對 于 d， e， f， 每 個(gè) 元素 的 變 化 周 期 是 3。 因 此 必 有 R m=Rm+6， 其 中 6是 2和 3的 最 小公 倍 數(shù) 。 取 m=0,n=6即 滿 足 題 目 要 求 。 7.4 關(guān) 系 的 性 質(zhì)q自 反 性q反 自 反 性q對 稱 性q反 對 稱

38、性q傳 遞 性 自 反 性 和 反 自 反 性定 義 7.11 設(shè) R為 A上 的 關(guān) 系 ，(1)若 x(x A R)， 則 稱 R在 A上 是 自 反 (reflexivity)的 。(2)若 x(x A R)， 則 稱 R在 A上 是 反 自 反(irreflexivity)的 。例 如 全 域 關(guān) 系 EA， 恒 等 關(guān) 系 IA， 小 于 等 于 關(guān) 系 LA， 整 除 關(guān) 系D A都 是 為 A上 的 自 反 關(guān) 系 。包 含 關(guān) 系 R是 給 定 集 合 族 A上 的 自 反 關(guān) 系 。小 于 關(guān) 系 和 真 包 含 關(guān) 系 都 是 給 定 集 合 或 集 合 族 上 的 反 自

39、 反關(guān) 系 。 例 7.10例 7.10 設(shè) A=1,2,3， R1， R2， R3是 A上 的 關(guān) 系 ， 其 中 R1 , R2 , R3 說 明 R1， R2和 R3是 否 為 A上 的 自 反 關(guān) 系 和 反 自 反 關(guān) 系 。解 答 R 1既 不 是 自 反 的 也 不 是 反 自 反 的 ，R2是 自 反 的 ，R3是 反 自 反 的 。 對 稱 性 和 反 對 稱 性定 義 7.12 設(shè) R為 A上 的 關(guān) 系 ，（ 1） 若 xy(x,y A R R)， 則 稱 R為 A上對 稱 (symmetry)的 關(guān) 系 。（ 2） 若 xy(x,y A R R x=y)， 則 稱 R為

40、 A上 的 反 對 稱 (antisymmetry)關(guān) 系 。 例 如 A上 的 全 域 關(guān) 系 E A， 恒 等 關(guān) 系 IA和 空 關(guān) 系 都 是 A上 的 對 稱 關(guān)系 。恒 等 關(guān) 系 IA和 空 關(guān) 系 也 是 A上 的 反 對 稱 關(guān) 系 。但 全 域 關(guān) 系 EA一 般 不 是 A上 的 反 對 稱 關(guān) 系 ， 除 非 A為 單 元 集或 空 集 。 例 7.11例 7.11 設(shè) A 1,2,3， R1， R2， R3和 R4都 是 A上 的 關(guān) 系 ， 其 中 R1 , R2 , R3 , R4 ,說 明 R 1， R2， R3和 R4是 否 為 A上 對 稱 和 反 對 稱

41、的 關(guān) 系 。解 答 R1既 是 對 稱 也 是 反 對 稱 的 。R2是 對 稱 的 但 不 是 反 對 稱 的 。R3是 反 對 稱 的 但 不 是 對 稱 的 。R4既 不 是 對 稱 的 也 不 是 反 對 稱 的 。 傳 遞 性定 義 7.13 設(shè) R為 A上 的 關(guān) 系 ， 若 xyz(x,y,z A R R R)則 稱 R是 A上 的 傳 遞 (transitivity)關(guān) 系 。例 如 A上 的 全 域 關(guān) 系 EA,恒 等 關(guān) 系 IA和 空 關(guān) 系 都 是 A上 的 傳 遞 關(guān) 系 。小 于 等 于 關(guān) 系 ， 整 除 關(guān) 系 和 包 含 關(guān) 系 也 是 相 應(yīng) 集 合 上

42、 的 傳 遞關(guān) 系 。小 于 關(guān) 系 和 真 包 含 關(guān) 系 仍 舊 是 相 應(yīng) 集 合 上 的 傳 遞 關(guān) 系 。 例 7.12例 7.12 設(shè) A 1,2,3， R1， R2， R3是 A上 的 關(guān) 系 ， 其 中 R1 , R2 , R3 說 明 R1， R2和 R3是 否 為 A上 的 傳 遞 關(guān) 系 。解 答 R 1和 R3是 A上 的 傳 遞 關(guān) 系 ，R2不 是 A上 的 傳 遞 關(guān) 系 。 關(guān) 系 性 質(zhì) 的 等 價(jià) 描 述 定 理 7.9 設(shè) R為 A上 的 關(guān) 系 ， 則 （ 1） R在 A上 自 反 當(dāng) 且 僅 當(dāng) IA R （ 2） R在 A上 反 自 反 當(dāng) 且 僅

43、當(dāng) R IA （ 3） R在 A上 對 稱 當(dāng) 且 僅 當(dāng) R R-1 （ 4） R在 A上 反 對 稱 當(dāng) 且 僅 當(dāng) R R-1 IA （ 5） R在 A上 傳 遞 當(dāng) 且 僅 當(dāng) RRR 說 明 q 利 用 該 定 理 可 以 從 關(guān) 系 的 集 合 表 達(dá) 式 來 判 斷 或 證 明 關(guān)系 的 性 質(zhì) 。分 析 關(guān) 系 性 質(zhì) 的 證 明 方 法 定 理 7.9 (1)的 證 明（ 1） R在 A上 自 反 當(dāng) 且 僅 當(dāng) IA R必 要 性 。 任 取 ， 有 IA x,y A x y R 所 以 I A R 充 分 性 。 任 取 x， 有 x A IA R 所 以 R在 A上 是

44、 自 反 的 。 定 理 7.9 (2)的 證 明（ 2） R在 A上 反 自 反 當(dāng) 且 僅 當(dāng) R IA 充 分 性 。 任 取 x， 有 x A IA R (R IA= ) 所 以 R在 A上 是 反 自 反 的 。必 要 性 。 用 反 證 法 。 假 設(shè) R IA ， 必 存 在 R IA。 由 于 IA是 A上 恒 等 關(guān) 系 ， 可 知 x A且 R。 這 與 R在 A上 是 反 自 反 的 相 矛 盾 。 定 理 7.9 (3)的 證 明（ 3） R在 A上 對 稱 當(dāng) 且 僅 當(dāng) R R-1必 要 性 。任 取 ， 有 R R (因 為 R在 A上 對 稱 ) R -1 所

45、以 R R-1 充 分 性 。 任 取 ， 由 R R-1 得 R R-1 R 所 以 R在 A上 是 對 稱 的 。 定 理 7.9 (4)的 證 明（ 4） R在 A上 反 對 稱 當(dāng) 且 僅 當(dāng) R R-1 IA必 要 性 。 任 取 ， 有 R R-1 R R-1 R R x y (R是 反 對 稱 的 ) I A所 以 R R-1 IA 充 分 性 。任 取 , 則 有 R R R R-1 R R-1 IA (R R-1 IA) x y所 以 R在 A上 是 反 對 稱 的 。 定 理 7.9 (5)的 證 明（ 5） R在 A上 傳 遞 當(dāng) 且 僅 當(dāng) RRR必 要 性 。 任 取

46、 ， 有 RR t( R R) R (因 為 R在 A上 是 傳 遞 的 )所 以 RRR。充 分 性 。 任 取 , R， 則 R R RR R (因 為 RRR) 所 以 R在 A上 是 傳 遞 的 。 例 7.13例 7.13 設(shè) A是 集 合 ， R1和 R2是 A上 的 關(guān) 系 ， 證 明 ：(1)若 R1， R2是 自 反 的 和 對 稱 的 ， 則 R1 R2也 是 自 反 的 和 對 稱 的 。(2)若 R1和 R2是 傳 遞 的 ， 則 R1 R2也 是 傳 遞 的 。 例 7.13 (1)的 證 明(1)若 R1， R2是 自 反 的 和 對 稱 的 ， 則 R1 R2也

47、是 自 反 的 和 對 稱 的 。證 明 由 于 R1和 R2是 A上 的 自 反 關(guān) 系 ， 故 有IA R1 和 IA R2從 而 得 到 IA R1 R2。根 據(jù) 定 理 7.9可 知 R1 R2在 A上 是 自 反 的 。再 由 R 1和 R2的 對 稱 性 有 R1 R1-1 和 R2 R2-1根 據(jù) 練 習(xí) 七 第 18題 的 結(jié) 果 有 (R1 R2)-1 R1-1 R2-1 R1 R2從 而 證 明 了 R1 R2也 是 A上 對 稱 的 關(guān) 系 。 例 7.13 (2)的 證 明(2)若 R1和 R2是 傳 遞 的 ， 則 R1 R2也 是 傳 遞 的 。證 明 由 R1和

48、R2的 傳 遞 性 有R1 R1 R1 和 R2 R2 R2再 使 用 定 理 7.4得 (R1 R2)(R1 R2) R 1 R1 R1 R2 R2 R1 R2 R2 (R1 R2) R1 R2 R2 R1 (將 前 面 的 包 含 式 代 入 ) R1 R2從 而 證 明 了 R1 R2也 是 A上 的 傳 遞 關(guān) 系 。 關(guān) 系 性 質(zhì) 的 特 點(diǎn)自 反 性 反 自 反 性 對 稱 性 反 對 稱 性 傳 遞 性集 合 表 達(dá) 式 IA R R IA R R-1 R R-1 IA RRR關(guān) 系 矩 陣 主 對 角 線元 素 全 是 1 主 對 角 線元 素 全 是 0 矩 陣 是 對稱

49、矩 陣 若 rij 1，且 i j， 則r ji 0 對 M2中 1所在 位 置 ， M中 相 應(yīng) 的 位置 都 是 1 關(guān) 系 圖 每 個(gè) 頂 點(diǎn)都 有 環(huán) 每 個(gè) 頂 點(diǎn)都 沒 有 環(huán) 如 果 兩 個(gè)頂 點(diǎn) 之 間有 邊 ， 一定 是 一 對方 向 相 反的 邊 (無 單邊 ) 如 果 兩 點(diǎn) 之間 有 邊 ， 一定 是 一 條 有向 邊 (無 雙向 邊 ) 如 果 頂 點(diǎn) xi到 xj有 邊 ，xj到 xk有 邊， 則 從 xi到xk也 有 邊 例 7.14例 7.14 判 斷 下 圖 中 關(guān) 系 的 性 質(zhì) ， 并 說 明 理 由 。 （ 1） 對 稱 的 ， 不 是 自 反 的 ，

50、不 是 反 自 反 的 ， 不 是 反 對 稱 的 ，不 是 傳 遞 的 。（ 2） 是 反 自 反 的 ， 不 是 自 反 的 ， 是 反 對 稱 的 ， 不 是 對 稱 的 ，是 傳 遞 的 。（ 3） 是 自 反 的 ， 不 是 反 自 反 的 ， 是 反 對 稱 的 ， 不 是 對 稱 的 ， 不 是 傳 遞 的 。 關(guān) 系 的 性 質(zhì) 和 運(yùn) 算 之 間 的 關(guān) 系自 反 性 反 自 反 性 對 稱 性 反 對 稱 性 傳 遞 性R1-1 R1 R2 R1 R2 R 1 R2 R1 R2 問 題q如 果 存 在 一 條 從 數(shù) 據(jù) 中 心 a到 b的 電 話 線 ， 就 屬 于 關(guān)

51、系 R。q如 何 確 定 從 一 個(gè) 中 心 是 否 有 一 條 電 話 線 (可 能 不 直 接 )鏈 接 到 另一 個(gè) 中 心 ？q通 過 構(gòu) 造 包 含 R的 最 小 的 傳 遞 關(guān) 系 來 找 出 每 一 對 有 著 聯(lián) 系 的 數(shù) 據(jù) 中 心 ， 這 個(gè) 關(guān) 系 叫 做 R的 傳 遞 閉 包 。波 士 頓 芝 加 哥 丹 佛底 特 律圣 地 亞 哥 紐 約 7.5 關(guān) 系 的 閉 包q閉 包 （ closure） 的 定 義q閉 包 的 構(gòu) 造 方 法q閉 包 的 性 質(zhì)q閉 包 的 相 互 關(guān) 系 閉 包 的 定 義定 義 7.14 設(shè) R是 非 空 集 合 A上 的 關(guān) 系 ，

52、R的 自 反 （ 對 稱 或 傳 遞 ）閉 包 是 A上 的 關(guān) 系 R ， 使 得 R 滿 足 以 下 條 件 ：（ 1） R 是 自 反 的 （ 對 稱 的 或 傳 遞 的 ）（ 2） RR（ 3） 對 A上 任 何 包 含 R的 自 反 （ 對 稱 或 傳 遞 ） 關(guān) 系 R 有R R 。一 般 將 R的 自 反 閉 包 記 作 r(R)， 對 稱 閉 包 記 作 s(R)， 傳 遞 閉包 記 作 t(R)。 閉 包 的 構(gòu) 造 方 法定 理 7.10 設(shè) R為 A上 的 關(guān) 系 ， 則 有（ 1） r(R) R R0（ 2） s(R) R R-1（ 3） t(R) R R2 R3 證

53、明 思 路(1)和 (2)： 證 明 右 邊 的 集 合 滿 足 閉 包 定 義 的 三 個(gè) 條 件 。(3) 采 用 集 合 相 等 的 證 明 方 法 。證 明 左 邊 包 含 右 邊 ， 即 t(R)包 含 每 個(gè) R n。證 明 右 邊 包 含 左 邊 ， 即 R R2 具 有 傳 遞 的 性 質(zhì) 。 定 理 7.10 (1)的 證 明（ 1） r(R) R R0證 明 由 IA R0 R R0， 可 知 R R0是 自 反 的 ， RR R0。 設(shè) R是 A上 包 含 R的 自 反 關(guān) 系 ， 則 有 RR和 IAR。 任 取 ， 必 有 R R 0 R IA R R R 所 以 R

54、 R0 R。綜 上 所 述 ， r(R) R R0。 定 理 7.10 (2)的 證 明（ 2） s(R) R R-1證 明 RR R-1。 證 明 R R-1是 對 稱 的 ， 任 取 ， 有 R R-1 R R-1 R -1 R R R-1 所 以 R R-1 是 對 稱 的 。綜 上 所 述 ， s(R) R R-1。 設(shè) R 是 包 含 R的 對 稱 關(guān) 系 ， 任 取 ， 有 R R-1 R R-1 R R R R R R R 所 以 R R-1 R 。 定 理 7.10 (3)的 證 明（ 3） t(R) R R2 R3 證 明 先 證 R R2 t(R)成 立 ， 為 此 只 需

55、 證 明 對 任 意 的 正 整數(shù) n有 Rn t(R)即 可 。 用 歸 納 法 。n 1時(shí) ， 有 R1 R t(R)。假 設(shè) Rnt(R)成 立 ， 那 么 對 任 意 的 有 Rn+1 Rn R t( R n R) t( t(R) t(R) t(R) （ 因 為 t(R)是 傳 遞 的 ）這 就 證 明 了 Rn+1 t(R)。由 歸 納 法 命 題 得 證 。 定 理 7.10 (3)的 證 明（ 3） t(R) R R2 R3 證 明 再 證 t(R)R R2 成 立 ， 為 此 只 須 證 明 R R2 是 傳遞 的 。任 取 ,， 則 R R2 R R2 t( Rt) s( R

56、s) ts( R t Rs) ts( Rt Rs) ts( Rt+s) R R2 從 而 證 明 了 R R2 是 傳 遞 的 。 推 論推 論 設(shè) R為 有 窮 集 A上 的 關(guān) 系 ， 則 存 在 正 整 數(shù) r使 得t(R)=R R2 Rr證 明 由 定 理 7.6和 7.10(3)得 證 。 例 題 求 整 數(shù) 集 合 Z上 的 關(guān) 系 R | ab的 自 反 閉 包 和對 稱 閉 包 。解 答 r(R) R R0 |ab |a b |a b s(R) R R -1 |ab |ba |a b 通 過 關(guān) 系 矩 陣 求 閉 包 的 方 法設(shè) 關(guān) 系 R， r(R)， s(R)， t(R

57、)的 關(guān) 系 矩 陣 分 別 為 M， Mr， Ms和Mt， 則Mr M E 對 角 線 上 的 值 都 改 為 1Ms M M 若 aij 1， 則 令 aji 1Mt M M2 M3 沃 舍 爾 算 法其 中 E是 和 M同 階 的 單 位 矩 陣 ， M 是 M的 轉(zhuǎn) 置 矩 陣 。注 意 在 上 述 等 式 中 矩 陣 的 元 素 相 加 時(shí) 使 用 邏 輯 加 。 通 過 關(guān) 系 圖 求 閉 包 的 方 法設(shè) 關(guān) 系 R， r(R)， s(R)， t(R)的 關(guān) 系 圖 分 別 記 為 G， Gr， Gs，Gt， 則 Gr， Gs， Gt的 頂 點(diǎn) 集 與 G的 頂 點(diǎn) 集 相 等

58、。除 了 G的 邊 以 外 ， 以 下 述 方 法 添 加 新 的 邊 。1)考 察 G的 每 個(gè) 頂 點(diǎn) ， 如 果 沒 有 環(huán) 就 加 上 一 個(gè) 環(huán) 。 最 終 得 到 的是 Gr。2)考 察 G的 每 一 條 邊 ， 如 果 有 一 條 xi到 xj的 單 向 邊 ， i j， 則 在G中 加 一 條 邊 x j到 xi的 反 方 向 邊 。 最 終 得 到 Gs。3)考 察 G的 每 個(gè) 頂 點(diǎn) xi， 找 出 從 xi出 發(fā) 的 所 有 2步 ， 3步 ， ， n步 長 的 路 徑 （ n為 G中 的 頂 點(diǎn) 數(shù) ） 。設(shè) 路 徑 的 終 點(diǎn) 為 。如 果 沒 有 從 xi到 (l

59、=1,2,k)的 邊 ， 就 加 上 這 條 邊 。 當(dāng)檢 查 完 所 有 的 頂 點(diǎn) 后 就 得 到 圖 Gt。k21 jjj x,x,x Ijx 例 7.15例 7.15 設(shè) A=a,b,c,d， R=,， 則 R和 r(R)， s(R)， t(R)的 關(guān) 系 圖 如 下 圖 所 示 。 其 中 r(R)，s(R)， t(R)的 關(guān) 系 圖 就 是 使 用 上 述 方 法 直 接 從 R的 關(guān) 系 圖 得 到的 。 Warshall 算 法輸 入 ： M（ R的 關(guān) 系 矩 陣 ）輸 出 ： MT（ t(R)的 關(guān) 系 矩 陣 ）1.MT M2.for k 1 to n do3. for

60、i 1 to n do4. for j 1 to n do5. M Ti,j MTi,j+MTi,k*MTk,j注 意 ： 算 法 中 矩 陣 加 法 和 乘 法 中 的 元 素 相 加 都 使 用 邏 輯 加 。 Warshall 算 法 舉 例例 設(shè) A=a,b,c,d， R=,， 求 t(R)。 0010 1000 0101 0010M0 0010 1000 0111 0010M1分 析 k 1 時(shí) ， MTi,j MTi,j+MTi,1*MT1,j M T1,j MT1,j+MT1,1*MT1,j MT2,j MT2,j+MT2,1*MT1,j 將 第 1行 加 到 第 2行 上 MT

61、3,j MT3,j+MT3,1*MT1,j MT4,j MT4,j+MT4,1*MT1,j 得 到 M1。 Warshall 算 法 舉 例 0010 1000 0101 0010M0 0010 1000 0111 0010M 1 0111 1000 0111 0111M2k 1時(shí) ， 第 1列 中 只 有 M2,1 1， 將 第 1行 加 到 第 2行 上 。k 2時(shí) ， 第 2列 中 M1,2 M2,2 M4,2 1， 將 第 2行 分 別 加 到 第 1,2,4行 上 。 Warshall 算 法 舉 例 0111 1000 0111 0111M2 1111 1000 1111 1111

62、M 3 1111 1111 1111 1111M4k 3時(shí) ， 第 3列 中 M1,3 M2,3 M4,3 1， 將 第 3行 分 別 加 到第 1,2,4行 上 。k 4時(shí) ， 第 4列 中 M1,4 M2,4 M3,4 M4,4 1，將 第 4行 分 別 加 到 第 1,2,3,4行 上 。 閉 包 的 主 要 性 質(zhì)定 理 7.11 設(shè) R是 非 空 集 合 A上 的 關(guān) 系 ， 則（ 1） R是 自 反 的 當(dāng) 且 僅 當(dāng) r(R) R。（ 2） R是 對 稱 的 當(dāng) 且 僅 當(dāng) s(R) R。（ 3） R是 傳 遞 的 當(dāng) 且 僅 當(dāng) t(R) R。證 明 （ 1） 充 分 性 。

63、因 為 R r(R)， 所 以 R是 自 反 的 。必 要 性 。顯 然 有 R r(R)。由 于 R是 包 含 R的 自 反 關(guān) 系 ， 根 據(jù) 自 反 閉 包 定 義 有 r(R)R。 從 而 得 到 r(R)=R。 閉 包 的 主 要 性 質(zhì)定 理 7.12 設(shè) R1和 R2是 非 空 集 合 A上 的 關(guān) 系 ， 且 R1 R2， 則（ 1） r(R1) r(R2)（ 2） s(R1) s(R2)（ 3） t(R1) t(R2)證 明 ： (1)任 取 ， 有 r(R1) R 1 IA R1 IA R2 IA R2 IA r(R2) 命 題命 題 若 R是 對 稱 的 ， 則 Rn也

64、是 對 稱 的 ， 其 中 n是 任 何 正 整 數(shù) 。證 明 用 歸 納 法 。n=1， R1 R顯 然 是 對 稱 的 。假 設(shè) Rn是 對 稱 的 ， 則 對 任 意 的 ， 有 Rn+1 Rn R t( R n R) t( Rn R) RRn R1+n Rn+1所 以 Rn+1是 對 稱 的 。 由 歸 納 法 命 題 得 證 。 關(guān) 系 性 質(zhì) 與 閉 包 運(yùn) 算 之 間 的 聯(lián) 系定 理 7.13 設(shè) R是 非 空 集 合 A上 的 關(guān) 系 ，（ 1） 若 R是 自 反 的 ， 則 s(R)與 t(R)也 是 自 反 的 。（ 2） 若 R是 對 稱 的 ， 則 r(R)與 t(R

65、)也 是 對 稱 的 。（ 3） 若 R是 傳 遞 的 ， 則 r(R)是 傳 遞 的 。證 明 ： 只 證 （ 2） 。 定 理 7.13 (2)的 證 明（ 2） 若 R是 對 稱 的 ， 則 r(R)與 t(R)也 是 對 稱 的 。證 明 r(R)是 對 稱 的 。由 于 R是 A上 的 對 稱 關(guān) 系 ， 所 以 R R-1， 同 時(shí) IA IA-1。r(R)-1 (R R0)-1 (R IA)-1 R -1 IA-1 R IA r(R)所 以 ， r(R)是 對 稱 的 。 定 理 7.13 (2)的 證 明（ 2） 若 R是 對 稱 的 ， 則 r(R)與 t(R)也 是 對 稱

66、 的 。下 面 證 明 t(R)的 對 稱 性 。任 取 t(R) n( Rn) n( R n) （ 因 為 Rn是 對 稱 的 ） t(R)所 以 ， t(R)是 對 稱 的 。 定 理 7.13的 討 論q從 這 里 可 以 看 出 ， 如 果 計(jì) 算 關(guān) 系 R的 自 反 、 對 稱 、 傳 遞 的 閉包 ， 為 了 不 失 去 傳 遞 性 ， 傳 遞 閉 包 運(yùn) 算 應(yīng) 該 放 在 對 稱 閉 包運(yùn) 算 的 后 邊 ， 若 令 tsr(R)表 示 R的 自 反 、 對 稱 、 傳 遞 閉 包 ，則 tsr(R)=t(s(r(R) 自 反 性 對 稱 性 傳 遞 性r(R) s(R) (反 例 )t(R) 反 例 A=1， 2， 3，R= 是 傳 遞 的s(R)=,顯 然 s(R)不 是 傳 遞 的 。 7.6 等 價(jià) 關(guān) 系 與 劃 分定 義 7.15 設(shè) R為 非 空 集 合 上 的 關(guān) 系 。 如 果 R是 自 反 的 、 對 稱 的和 傳 遞 的 ， 則 稱 R為 A上 的 等 價(jià) 關(guān) 系 (equivalent relation)。設(shè) R是 一 個(gè) 等 價(jià) 關(guān) 系 ，