第4章二元關(guān)系和函數(shù)課件.ppt

《第4章二元關(guān)系和函數(shù)課件.ppt》由會員分享，可在線閱讀，更多相關(guān)《第4章二元關(guān)系和函數(shù)課件.ppt（124頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第 四 章 二 元 關(guān) 系 和 函 數(shù) 本 章 主 要 內(nèi) 容 :l集 合 的 笛 卡 爾 積 與 二 元 關(guān) 系l關(guān) 系 的 運 算l關(guān) 系 的 性 質(zhì)l關(guān) 系 的 閉 包l等 價 關(guān) 系 和 偏 序 關(guān) 系l函 數(shù) 的 定 義 和 性 質(zhì)l函 數(shù) 的 復(fù) 合 和 反 函 數(shù) 4.1 集 合 的 笛 卡 兒 積 與 二 元 關(guān) 系定 義 4.1 由 兩 個 元 素 x和 y(允 許 x=y)按 一 定 的順 序 排 列 成 的 二 元 組 叫 做 一 個 有 序 對 (也 稱 序偶 ),記 作 ,其 中 x是 它 的 第 一 元 素 ,y是 它 的第 二 元 素 。 平 面 直 角 坐 標(biāo)

2、系 中 點 的 坐 標(biāo) 就 是 有 序 對 ,例如 ,(1,1), ( 1,1) ,都 代 表 坐 標(biāo)系 中 不 同 的 點 。 有 序 對 的 特 點 ：1.當(dāng) xy時 ,。2.兩 個 有 序 對 相 等 ,即 的 充 分 必 要 條 件 是 x u且 y v。 定 義 4.2 一 個 有 序 n元 組 (n3)是 一 個 有 序 對 ,其 中 第 一 個 元 素 是 一 個 有 序 n 1元 組 ,一 個 有序 n元 組 記 作 ,即 , xn 例 如 ,空 間 直 角 坐 標(biāo) 系 中 點 的 坐 標(biāo),等都 是 有 序 3元 組 。n維 空 間 中 點 的 坐 標(biāo) 或 n維 向 量 都 是

3、 有 序 n元 組 。 定 義 4.3 設(shè) A,B為 集 合 ,用 A中 元 素 為 第 一 元素 ,B中 元 素 為 第 二 元 素 ,構(gòu) 成 有 序 對 ,所 有 這樣 的 有 序 對 組 成 的 集 合 叫 做 A和 B的 笛 卡 兒積 ,記 作 A B。 符 號 化 表 示 為 A B |x A y B.例 如 ,A a,b,B 0,1,2,則 A B ,； B A , ,。 如 果 A中 有 m個 元 素 ,B中 有 n個 元 素 ,則 A B和 B A中 都 有 多 少 個 元 素 ?mn個若 A B,則 有x A和 y B。若 A B,則 有xA或 者 y B. 笛 卡 兒 積

4、運 算 的 性 質(zhì) : 1.若 A,B中 有 一 個 空 集 ,則 它 們 的 笛 卡 兒 積 是 空 集 ,即 B B 2.當(dāng) AB且 A,B都 不 是 空 集 時 ,有 A BB A。所 以 ,笛 卡 兒 積 運 算 不 適 合 交 換 律 。 3.當(dāng) A,B,C都 不 是 空 集 時 ,有 (A B) CA (B C).所 以 ,笛 卡 兒 積 運 算 不 適 合 結(jié) 合 律 。 4.笛 卡 兒 積 運 算 對 或 運 算 滿 足 分 配 律 即 A (B C) (A B) (A C)； (B C) A (B A) (C A)； A (BC) (A B)(A C)； (BC) A (B

5、A)(C A)。 證 明 A (B C) (A B) (A C)證 明 對 于 任 意 的 , A (B C) x A y B C x A (yB y C) (x A yB) (x A y C) A B A C (x,y) (A B) (A C). 所 以 A (B C) (A B) (A C)。 例 4.1 設(shè) A=1,2,求 P(A) A 解 P(A) A ,1,2,1,2 1,2 , 例 4.2 設(shè) A,B,C,D為 任 意 集 合 ,判 斷 以 下等 式 是 否 成 立 ,說 明 為 什 么 。 (1) (AB) (CD) (A C)(B D)； (2) (A B) (C D) (A

6、C) (B D)；(3) (AB) (CD) (A C) (B D)； (4) (AB) (CD) (A C) (B D)。 解 .(1)成 立 .因 為 對 于 任 意 的 , (AB) (CD) xAB yCD xA xB yC yD A C B D (A C)(B D) (2)不 成 立 。舉 一 反 例 如 下 ： 若 A D ,B C 1 則 有 ：(A B) (C D) B C ,(A C) (B D) 。 (3)和 (4)都 不 成 立 例 4.3 設(shè) A,B,C,D為 任 意 集 合 ,判 斷 以 下 命 題的 真 假 .(1)若 AC且 BD,則 有 A BC D。(2)若

7、A BC D,則 有 AC且 BD. 解 (1)命 題 為 真 。 請 思 考 ： 為 什 么 ？(2)命 題 為 假 .當(dāng) A B 時 ,或 者 A且B時 ,該 命 題 的 結(jié) 論 是 成 立 的 。 但 是 當(dāng) A和 B之 中 僅 有 一 個 為 時 ,結(jié) 論 不 一 定 成 立 ,例 如 ,令 A C D ,B 1 ,這 時A BC D,但 BD。 定 義 4.4 設(shè) A1,A2, , An是 集 合 (n2),它 們 的 n階 笛 卡 兒 積 ,記 作 A1 A2 An,其 中 Al A2 An|x1 Al x2 A2 xn An。 例 如 : A=a,b,則 A3=, , , , 作

8、 業(yè) P135l4.1 4.4(2) 4.5 二 元 關(guān) 系 Relation 所 謂 二 元 關(guān) 系 就 是 在 集 合 中 兩 個 元 素 之 間 的某 種 相 關(guān) 性 .例 如 ,甲 、 乙 、 丙 三 個 人 進(jìn) 行 乒 乓 球 比 賽 ,如 果任 何 兩 個 人 之 間 都 要 賽 一 場 ,那 么 共 要 賽 三 場 。假 設(shè) 三 場 比 賽 的 結(jié) 果 是 乙 勝 甲 、 甲 勝 丙 、 乙勝 丙 ,這 個 結(jié) 果 可 以 記 作,其 中 表 示 x勝y。 它 表 示 了 集 合 甲 ,乙 ,丙 中 元 素 之 間 的 一種 勝 負(fù) 關(guān) 系 . 例 子 .有 A,B,C三 個 人

9、 和 四 項 工 作 ,已 知 A可 以 從 事 工 作 ,B可 以 從 事 工 作 ,C可 以 從 事工 作 ,。 那 么 人 和 工 作 之 間 的 對 應(yīng) 關(guān) 系 可 以記 作 R ,。這 是 人 的 集 合 A,B,C到 工 作 的 集 合 ,之 間 的 關(guān) 系 。 定 義 4.5 如 果 一 個 集 合 為 空 集 或 者 它 的元 素 都 是 有 序 對 , 則 稱 這 個 集 合 是 一 個二 元 關(guān) 系 ,一 般 記 作 R。對 于 二 元 關(guān) 系 R,如 果 R,則 記 作 xRy；如 果 R,則 記 作 定 義 4.6 設(shè) A,B為 集 合 ,A B的 任 何 子 集 所

10、定義 的 二 元 關(guān) 系 稱 作 從 A到 B的 二 元 關(guān) 系 ,特 別 當(dāng)A B時 ,則 叫 做 A上 的 二 元 關(guān) 系 。l關(guān) 系 RAB, R is a relation from A to B. lRAA, R is a relation on A. A上 有 多 少 個 不 同 的 二 元 關(guān) 系 ?|A|=n|A A|=n2|P(A A)|=2n2每 一 個 子 集 代 表 一 個 A上 的 關(guān) 系 ,共 2n2個 關(guān) 系 . 對 于 任 何 集 合 A都 有 3種 特 殊 的 關(guān) 系 :1. 空 關(guān) 系 就 是 空 集 。2. 全 域 關(guān) 系 EA3. 恒 等 關(guān) 系 IA。

11、 定 義 4.7 對 任 何 集 合 A, EA x A y A A A。 IA x A。例 如 ： A=0,1,2,則 EA, I A ,2,2)。 常 用 的 三 種 關(guān) 系 :1.小 于 等 于 關(guān) 系 例 如 : 設(shè) A為 實 數(shù) 集 R的 某 個 子 集 ,則 A上 的 小于 等 于 關(guān) 系 定 義 為 LA x,y A xy2. 整 除 關(guān) 系設(shè) B為 正 整 數(shù) 集 Z 的 某 個 子 集 ,則 B上 的 整 除 關(guān)系 定 義 為 D B x,y B xy. 例 如 : A=4,0.5,-1,B=1,2,3,6,則LA, ., ,DB, , , . 3.包 含 關(guān) 系例 4.4

12、設(shè) A a,b,R是 P(A)上 的 包 含 關(guān) 系 , R |x,y P(A) xy,則 有P(A) ,a,b,A。 R,. 1.集 合 的 表 示 例 如 ： 設(shè) A 1,2,3,4, A上 的 關(guān) 系R , 。2.關(guān) 系 圖3.關(guān) 系 矩 陣關(guān) 系 的 三 種 表 示 ： 關(guān) 系 矩 陣 和 關(guān) 系 圖 設(shè) V是 頂 點 的 集 合 ,E是 有 向 邊 的 集 合 ,令 V Ax1,x2,xn,如 果 xiRxj,則 有 向 邊 E.那 么 G 就 是 R的 關(guān) 系 圖 。設(shè) A x1,x2,xn,R是 A上 的 關(guān) 系 ,則 R的 關(guān) 系 矩 陣 可 表 示 為 ： 作 業(yè) P135-

13、136l4.8(2)-(4) 本 章 主 要 內(nèi) 容 :l集 合 的 笛 卡 爾 積 與 二 元 關(guān) 系l關(guān) 系 的 運 算l關(guān) 系 的 性 質(zhì)l關(guān) 系 的 閉 包l等 價 關(guān) 系 和 偏 序 關(guān) 系l函 數(shù) 的 定 義 和 性 質(zhì)l函 數(shù) 的 復(fù) 合 和 反 函 數(shù) 定 理 ： 設(shè) R,S為 集 合 A上 關(guān) 系 ,則 RS、 R S、 R S 、 RS、 R也 是 A上 關(guān) 系 。例 ： 設(shè) R,S為 集 合 A =1,2,3上 關(guān) 系 , R=,，S=,， 則RS =R S =,， R S=R=A A-R=, 4.2 關(guān) 系 的 運 算l關(guān) 系 R的 定 義 域 ,值 域 和 域l關(guān) 系

14、 F的 逆l關(guān) 系 F與 G的 合 成l關(guān) 系 F在 集 合 A上 的 限 制l集 合 A在 關(guān) 系 F下 的 象l關(guān) 系 R的 n次 冪 定 義 4.8 關(guān) 系 R的 定 義 域 domR,值 域 ranR和域 fldR分 別 是 domR xy( R) ranR y| x( R) fldR domR ranR。domR就 是 R的 所 有 有 序 對 的 第 一 個 元 素 構(gòu)成 的 集 合 ,ranR就 是 R的 所 有 有 序 對 的 第 二個 元 素 構(gòu) 成 的 集 合 .例 :實 數(shù) 集 R上 的 關(guān) 系S=|x,y R x2+y2=1,domS=ranS=fldS= 1,1 .

15、例 4.5 下 列 關(guān) 系 都 是 整 數(shù) 集 Z上 的 關(guān) 系 ,分 別求 出 它 們 的 定 義 域 和 值 域 , (1)R1 x,y Z xy；(2)R2 x,y Z x2+y2=1；(3)R3 x,y Z y 2x；(4)R4 x,y Z x y=3。 解 (1) domR1 ranR1 Z. (2) R2 , domR2 ranR2 0,1, 1. (3) domR 3 Z ranR3 2z|z Z,即 偶 數(shù) 集 (4) domR4 ranR4 -3,3. 從 A到 B的 某 些 關(guān) 系 R的 圖 解 方 法 (不 是 R的 關(guān) 系 圖 )1.用 封 閉 的 曲 線 表 示 R的

16、 定 義 域 (或 集 合 A)和 值 域 (或集 合 B).2.從 x到 y畫 一 個 箭 頭 ,如 果 R 逆 、 復(fù) 合 定 義 4.9 設(shè) F,G為 任 意 的 關(guān) 系 ,A為 集合 ,則(1)F的 逆 記 作 F-1 F-1 |yFx.(2)F與 G的 復(fù) 合 記 作 F G, F G z(xFz zGy) 例 4.6 設(shè) F,G是 N上 的 關(guān) 系 ,其 定 義 為 F x,y N y x2 G x,y N y x 1。求 : G F =? F G=? G-1 =?解 ： 1)對 任 何 的 x N有 F G(x)=G(F(x)=x2 +1 F G= x,y N 3) 對 任 何

17、的 x N有 G F (x)=F (G(x)=(x +1)2 G F = x,y N l由 這 個 例 子 不 難 看 出 ,合 成 運 算 不 是 可l交 換 的 ,即 對 任 何 關(guān) 系 F,G,一 般 說 來F GG F. 定 理 4.1 設(shè) F,G,H是 任 意 的 關(guān) 系 ,則 有l(wèi)(3)(F G) H F (G H)l(4)l怎 樣 證 明 ?關(guān) 系 的 基 本 運 算 的 主 要 性 質(zhì) 定 理 4.2 設(shè) F,G,H為 任 意 的 關(guān) 系 ,則 有(1)F (GH)=F GF H(2) (GH) F=G F H F (3) F (GH) F GF H(4) (GH) F G F

18、 H F怎 樣 證 明 ? 定 義 4.10 設(shè) R為 A上 的 關(guān) 系 ,n為 自 然 數(shù) ,則R的 n次 冪 規(guī) 定 如 下 ：R0=IAR1=R0 R=R R0 在 有 窮 集 A上 給 定 了 關(guān) 系 R和 自 然 數(shù) n,求 Rn的 方 法 :l1.集 合 運 算 :依 據(jù) 定 義l2.關(guān) 系 矩 陣 :用 關(guān) 系 矩 陣 M表 示 關(guān) 系 R,計 算 MM,在兩 個 矩 陣 相 乘 時 ,第 i行 第 j列 的 元 素 rij滿 足 下 式(i,j=1,2,3,4)rij = ri1 r1j + ri2 r2j + ri3 r3j + ri4 r4j這 里 的 加 法 +是 邏 輯

19、 加 ,即0+0=0,0+1=1,1+0=1,1+1=13.關(guān) 系 圖 :對 R的 關(guān) 系 圖 G中 的 任 何 一 個 結(jié) 點 x,考 慮 從 x出 發(fā) 的 長 為 n的 路 徑 ,如 果 路 徑 的 終 點 是 y,則在 R n的 關(guān) 系 圖 中 有 一 條 從 x到 y的 有 向 邊 . 定 理 4.3 設(shè) R為 A上 的 關(guān) 系 ,m,n是 自 然 數(shù) ,則 下 面 的 等 式 成 立 . 本 章 主 要 內(nèi) 容 :l集 合 的 笛 卡 爾 積 與 二 元 關(guān) 系l關(guān) 系 的 運 算l關(guān) 系 的 性 質(zhì)l關(guān) 系 的 閉 包l等 價 關(guān) 系 和 偏 序 關(guān) 系l函 數(shù) 的 定 義 和 性

20、 質(zhì)l函 數(shù) 的 復(fù) 合 和 反 函 數(shù) 作 業(yè) P136l4.10l4.11l4.13 4.3 關(guān) 系 的 性 質(zhì)l設(shè) R是 A上 的 關(guān) 系 ,R的 性 質(zhì) 主 要 有以 下 5種 ：l自 反 性l反 自 反 性l對 稱 性l反 對 稱 性l傳 遞 性 49 定 義 1 設(shè) R是 非 空 集 合 X上 的 二 元 關(guān) 系 。 若 對 X中 的 每 個 元 素 x，都 有 R， 則 稱 R是 X上 的 自 反 關(guān) 系 。例 1 設(shè) X=a,b,c,d， R=, 由 自 反 關(guān) 系 的 定 義 知 R是 X上 的 自 反 關(guān) 系 。 若 R=,， 則 R是 X上 的 恒 等 關(guān) 系 。 由 此

21、 可 知 恒 等 關(guān) 系 一 定 是 自 反 關(guān) 系 ， 但 自 反 關(guān) 系 不 一 定 是 恒等 關(guān) 系 。 50 定 義 2 設(shè) R是 非 空 集 合 X上 的 二 元 關(guān) 系 。 若對 X中 的 每 個 元 素 x， 都 有 R， 則稱 R是 X上 的 反 自 反 關(guān) 系 。例 2 設(shè) X=a,b,c,d，R=,(a,d, 由 反 自 反 關(guān) 系 的 定 義 知 R是 X上 的 反 自反 關(guān) 系 。 51 定 義 3 設(shè) R是 非 空 集 合 X上 的 二 元 關(guān) 系 。 若 對 于 任 意 的x,yX， 當(dāng) R 時 ， 有 R， 則 稱 R是 X上 的對 稱 關(guān) 系 。例 1 設(shè) X=

22、a,b,c， R1=, ， R2=, ，R3=X2 由 對 稱 關(guān) 系 的 定 義 知 R1， R2， R3都 是 X上 的 對 稱 關(guān) 系 。例 2 設(shè) R是 實 數(shù) 集 合 ， S= | xR yR x=y 由 實 數(shù) 的 性 質(zhì) 知 ， 當(dāng) x=y時 ， 有 y=x， 由 對 稱 關(guān) 系 的 定 義 知S是 R上 的 對 稱 關(guān) 系 。 推 而 廣 之 ， 凡 是 相 等 關(guān) 系 都 是 對 稱 關(guān) 系 。 52 定 義 4 設(shè) R是 非 空 集 合 X上 的 二 元 關(guān) 系 。 若 對 于 任 意 的x,yX， 當(dāng) R 且 x y時 ， 有 R ， 則 稱R是 X上 的 反 對 稱 關(guān)

23、 系 。例 1 設(shè) R是 實 數(shù) 集 合 ， S= | xR yR xy 由 實 數(shù) 的 性 質(zhì) 知 ， 當(dāng) xy且 yx時 ， 有 x=y， 由 反 對稱 關(guān) 系 的 定 義 知 S是 R上 的 反 對 稱 關(guān) 系 。 53 定 義 5 設(shè) R是 非 空 集 合 X上 的 二 元 關(guān) 系 。 若 對 于 任 意 的x,y,zX， 當(dāng) R 且 R 時 ， 有 R ， 則稱 R是 X上 的 傳 遞 關(guān) 系 。例 1 設(shè) X=a,b,c,d， R=, 由 傳 遞 關(guān) 系 的 定 義 知 R是 X上 的 傳 遞 關(guān) 系 。例 2 設(shè) X是 平 面 上 直 線 的 集 合 ， R= | xX yX x

24、 y 由 平 面 幾 何 的 知 識 知 ， 若 x y 且 y z， 則 x z。 由 傳 遞 關(guān) 系 的 定 義 知 R是 X上 的 傳 遞 關(guān) 系 。例 3 相 等 關(guān) 系 是 傳 遞 關(guān) 系 。l全 關(guān) 系 X 2是 自 反 的 、 對 稱 的 、 傳 遞 的 。l幺 關(guān) 系 I 是 自 反 的 、 對 稱 的 、 反 對 稱 的 、 傳 遞 的 。l空 關(guān) 系 是 反 自 反 的 、 對 稱 的 、 反 對 稱 的 、 傳 遞 的 。 判 斷 下 列 關(guān) 系 的 性 質(zhì)l集 合 A上 的 全 域 關(guān) 系 :自 反 的 、 對 稱 的 和 傳 遞 的l恒 等 關(guān) 系 自 反 的 、 對

25、 稱 的 和 傳 遞 的 .l整 除 關(guān) 系 自 反 的 、 反 對 稱 的 和 傳 遞 的l小 于 等 于 關(guān) 系自 反 的 、 反 對 稱 的 和 傳 遞 的l冪 集 上 的 包 含 關(guān) 系自 反 的 、 反 對 稱 的 和 傳 遞 的 l設(shè) A為 非 空 集 合 :l1.A上 的 關(guān) 系 可 以 是 自 反 的 , 反 自 反 的 ,或 者 既 不 是 自 反 的 也 不 是 反 自 反 的 . l例 如 :Q=1,2,3,令lR=, IQ RlR=, IQR=lR=, IQR且 IQR l2. A上 的 關(guān) 系 可 以 是 對 稱 的 , 反 對 稱 的 ,或者 既 是 對 稱 的 又

26、 是 反 對 稱 的 , 既 不 是 對 稱的 也 不 是 反 對 稱 的 . l例 如 :Q=1,2,3,令lR=, R-1=RlR=, R R-1 IQ lR= R IQ lR= ,lR R R是 什 么 關(guān) 系 ? 例 4.9 試 判 斷 圖 4.5中 關(guān) 系 的 性 質(zhì) 。 設(shè) R1,R2是 A上 的 關(guān) 系 ,如 果 經(jīng) 過 某 種 運 算后 仍 保 持 原 來 的 性 質(zhì) ,則 在 相 對 應(yīng) 的 格 內(nèi)劃 ,否 則 劃 。 例 ： 設(shè) R1,R2為 A上 的 對 稱 關(guān) 系 ,證 明 R1R2也是 A上 的 對 稱 關(guān) 系 。證 明 ： 對 于 任 意 的 R1R2 R1 R2

27、R1 R2 R1 R2所 以 , R1R2在 A上 是 對 稱 的 。例 : R1 , R2 是 A上 的 反 對 稱 關(guān) 系 , A=x1, x2, R 1 =, R2 =,R1 R2 =, 不 是 A上 的 反 對 稱 關(guān) 系 . 作 業(yè)l4.7l 4.14l 4.17l 4.18l4.20l4.22l4.23l4.25 本 章 主 要 內(nèi) 容 :l集 合 的 笛 卡 爾 積 與 二 元 關(guān) 系l關(guān) 系 的 運 算l關(guān) 系 的 性 質(zhì)l關(guān) 系 的 閉 包l等 價 關(guān) 系 和 偏 序 關(guān) 系l函 數(shù) 的 定 義 和 性 質(zhì)l函 數(shù) 的 復(fù) 合 和 反 函 數(shù) 63 4.4 關(guān) 系 的 閉 包

28、定 義 4.11 設(shè) R是 非 空 集 合 A上 的 關(guān) 系 ,R的 自 反閉 包 對 稱 閉 包 或 傳 遞 閉 包 )是 A上 的 關(guān) 系 R,且R滿 足 以 下 條 件 :(1)R是 自 反 的 (對 稱 的 或 傳 遞 的 )；(2)RR；(3)對 A上 的 任 何 包 含 R的 自 反 關(guān) 系 (對 稱 或 傳遞 關(guān) 系 )R”都 有 R R”.一 般 將 R的 自 反 reflexive閉 包 記 作 r(R),對 稱symmetric閉 包 記 作 s(R),傳 遞 transitive閉 包 記作 t(R)。 64 例 4.10 設(shè) A a,b,c,d,R,則 R和 r(R),

29、s(R),t(R)的關(guān) 系 圖 如 圖 4.6所 示 , 65 A上 關(guān) 系 R的 閉 包l定 理 4.4 設(shè) R為 非 空 集 合 A上 的 關(guān) 系 ,則 有 (1)r(R) R R0；(2)s(R) R R-1；(3)t(R)=R R2 R3 (4)A是 含 有 n個 元 素 的 集 合t(R)=R R2 R3 Rk , kn 66 例 4.10 設(shè) A a,b,c,d,R,則 r(R),s(R),t(R)有解 :(1)r(R) R R0 =, , =,.,(2)s(R) R R-1 =, , =,(3)t(R)=R R 2 R3 =, , , =, 67 閉 包 的 矩 陣 表 示 (定

30、 理 4.4的 公 式 轉(zhuǎn) 換 成 矩陣 表 示 ）Mr M EMs=M+MMt=M+M2+M3+其 中 E表 示 同 階 的 單 位 矩 陣 (主 對 角 線 元 素為 1,其 他 元 素 都 是 0)M表 示 M的 轉(zhuǎn) 置 ,而 +均 表 示 矩 陣 中 對 應(yīng) 元素 的 邏 輯 加 。 68 在 例 4.10中 3個 結(jié) 果 矩 陣 是 : 作 業(yè)設(shè) A a,b,c,d,R ,請 畫 出 R和 r(R),s(R),t(R)的 關(guān) 系 圖 本 章 主 要 內(nèi) 容 :l集 合 的 笛 卡 爾 積 與 二 元 關(guān) 系l關(guān) 系 的 運 算l關(guān) 系 的 性 質(zhì)l關(guān) 系 的 閉 包l等 價 關(guān) 系

31、和 偏 序 關(guān) 系l函 數(shù) 的 定 義 和 性 質(zhì)l函 數(shù) 的 復(fù) 合 和 反 函 數(shù) 71 4.5 等 價 關(guān) 系 和 偏 序 關(guān) 系定 義 4.12 設(shè) R為 非 空 集 合 A上 的 關(guān) 系 ,如 果 R是 自 反 的 、 對 稱 的 和 傳 遞 的 ,則 稱 R為 A上 的等 價 關(guān) 系 .對 任 何 x,y A,如 果 x,y) 等 價 關(guān)系 R,則 記 作 xy. 72 下 面 是 一 些 等 價 關(guān) 系 的 例 子 .(1)在 一 群 人 的 集 合 上 年 齡 相 等 的 關(guān) 系 是 等 價 關(guān)系 ,而 朋 友 關(guān) 系 不 一 定 是 等 價 關(guān) 系 ,因 為 它 可 能 不是

32、 傳 遞 的 .一 般 稱 這 種 自 反 的 對 稱 的 關(guān) 系 為 相 容關(guān) 系 .顯 然 等 價 關(guān) 系 都 是 相 容 關(guān) 系 ,但 相 容 關(guān) 系 不一 定 是 等 價 關(guān) 系 .(2)動 物 是 按 種 屬 分 類 的 ； “ 具 有 相 同 種 屬 ” 的關(guān) 系 是 動 物 集 合 上 的 等 價 關(guān) 系 . (3)集 合 上 的 恒 等 關(guān) 系 和 全 域 關(guān) 系 都 是 等 價 關(guān) 系 . (4)在 同 一 平 面 上 三 角 形 之 間 的 相 似 關(guān) 系 是 等 價關(guān) 系 ,但 直 線 間 的 平 行 關(guān) 系 不 是 等 價 關(guān) 系 ,因 為 它不 是 自 反 的 . 7

33、3 例 4.11 A 1,2,8,R |x,y A xy(mod 3),其 中 x-y(mod 3)的 含 義 就 是 x-y可 以 被 3整 除 . R為 A上 的 等 價 關(guān) 系 ,它 的 關(guān) 系 圖 如 下 所 示 ,其 中147,258,36. 74 把 模 3的 等 價 關(guān) 系 推 廣 ,對 任 何 正 整 數(shù)n可 以 定 義 整 數(shù) 集 合 Z上 模 n的 等 價 關(guān)系 . R |x,y Z xy(mod n)例 如 ,當(dāng) n 5時 ,整 數(shù) 之 間 的 等 價 性 滿 足 : 10 50510, 9 41611 8 32712 7 23813, 6 14914. 75 設(shè) R是

34、非 空 集 合 A上 的 等 價 關(guān) 系 ,則 A上 互 相 等 價 的 元素 構(gòu) 成 了 A的 若 干 個 子 集 ,叫 做 等 價 類 .定 義 4.13 設(shè) R是 非 空 集 合 A上 的 等 價 關(guān) 系 ,對 任 意的 x A,令稱 為 x關(guān) 于 R的 等 價 類 ,簡 稱 為 x等 價 類 ,簡 記 為x.在 例 4.11中 有 1 4 7 1,4,7, 2 5 8 2,5,8, 3 6= 3,6. 76 等 價 類 的 性 質(zhì) .定 理 4.5 設(shè) R是 非 空 集 合 A上 的 等 價 關(guān) 系 ,對 任 意的 x,y A,下 面 的 結(jié) 論 成 立 . (1) x,且 xA； (

35、2) 若 xRy,則 x=y； (3) 若 xRy,則 xy ； (4) =A. 77 商 集定 義 4.14 設(shè) R為 非 空 集 合 A上 的 等 價 關(guān) 系 ,以 R的 不 交的 等 價 類 為 元 素 的 集 合 叫 做 A在 R下 的 商 集 ,記 作 A R, A R x A.在 例 4.11中 ,A在 R下 的 商 集 是A/R=1,4,7,2,5,8,3,6 例 4.13(1)非 空 集 合 A上 的 恒 等 關(guān) 系 是 A上 的 等 價 關(guān) 系 ,對任 意 x A有 x x,商 集 A/ =x|x A. 78 (2)在 整 數(shù) 集 合 z上 模 n的 等 價 關(guān) 系 ,其 等

36、 價 類 是0 , 2n, n,0,n,2n,=nz|nz Z nZ,1 , 2n 1, n十 1,1,n 1,2n 1, =nz 1 z Z nZ 12 , 2n 2, n 2,2,n 2,2n十 2, =nz 2 z Z nZ 2, n 1 , 2n n 1, n n 1,n 1,n n1, =nz+n 1 zZ =nZ+n 1.商 集 為 0,1,n 1 79 劃 分定 義 4.15 設(shè) A是 非 空 集 合 ,如 果 存 在 一 個 A的 子集 族 (P(A)滿 足 以 下 條 件(1)；(2)中 任 意 兩 個 元 素 不 交 ；(3)中 所 有 元 素 的 并 集 等 于 A,則

37、稱 為 A的 一 個 劃 分 ,且 稱 中 的 元 素 為 劃 分塊 . 80 例 . 考 慮 集 合 A a,b,c,d的 下 列 子 集 族(1) a,b,c,d,(2) a,b,c,d,(3) a,b,c,a,d,(4) ,a,b,c,d,(5) a,b,c, 81 例 4.15 設(shè) A 1,2,3,求 出 A上 所 有 的 等 價 關(guān)系 .解 : 先 求 A的 各 種 劃 分 :只 有 1個 劃 分 塊 的 劃 分 1,具 有兩 個 劃 分 塊 的 劃 分 2,3和 4,具 有 3個 劃 分 塊 的 劃 分 5,請 看 下 圖 | 82 設(shè) 對 應(yīng) 于 劃 分 i的 等 價 關(guān) 系 為

38、 Ri,i 1,2,5.則 有R5 , IA ；R1, IA EA；R2 , IA ； .R3 , IA ；R4 , IA. 作 業(yè) P137l4.31l4.32l4.33l4.34l4.35l4.37 84 偏 序 關(guān) 系定 義 4.1 設(shè) R為 非 空 集 合 A上 的 關(guān) 系 ,如 果 R是 自 反的 、 反 對 稱 的 和 傳 遞 的 ,則 稱 R為 A上 的 偏 序 關(guān) 系 .簡 稱 偏 序 ,記 作 .任 何 集 合 A上 的 恒 等 關(guān) 系 ,集 合 的 冪 集 P(A)上 的 包 含 關(guān) 系 ,實 數(shù) 集 上 的 小 于 等 于 關(guān) 系 ,正 整 數(shù) 集 上 的 整 除 關(guān) 系

39、 都 是 偏 序 關(guān) 系 . 85 l定 義 4.17 一 個 集 合 A與 A上 的 偏 序 關(guān) 系 R一 起 叫 做 偏 序 集 ,記 作 .l定 義 4.18 設(shè) 為 偏 序 集 ,對 于 任 意 的x,y A,如 果 xy或 者 yx成 立 ,則 稱 x與 y是可 比 的 ,如 果 x y(即 xy xy),且 不 存 在zA使 得 xzy,則 稱 y蓋 住 x. 86 例 如 ,是 偏 序 集 ,其 中 A 1,2,3,4,5, 是 整 除 關(guān) 系 .那 么 ,對 任 意 x A都 有 1x,所 以 ,1和 1,2,3,4,5都是 可 比 的 ,但 是 2不 能 整 除 3,3也 不

40、 能 整 除 2,所 以2和 3是 不 可 比 的 .對 于 1和 2來 說 ,1 2,并 且 不 存在 z A使 得 1整 除 z并 且 z整 除 2,所 以 ,2蓋 住 1.同 樣 ,4蓋 住 2,但 4不 蓋 住 1,因 為 有 1 2 4成 立 .顯 然 ,如 果 x與 y不 可 比 ,則 一 定 不 會 有 x蓋 住 y或y蓋 住 x. 87 全 序 關(guān) 系l 定 義 4.19 設(shè) 為 偏 序 集 ,若 對 任 意 的 :x,y A,x和 y都 可 比 ,則 稱 為 A上 的 全 序 關(guān) 系 ,且 稱 為 全 序 集 .例 如 ,1,2,3,4,5上 的小 于 等 于 關(guān) 系 是 全

41、 序 關(guān) 系 ,而 整 除 關(guān) 系 不 是 全 序 關(guān) 系 . 88 例 4.16 畫 出 和的 哈 斯 圖 .解 :哈 斯 圖 如 圖 4,9所 示 89 例 4.17 設(shè) 偏 序 集 的 哈 斯 圖 如 圖 所 示 ,求 出 集 合 A的 偏 序 .解 A a,b,c,d,e, f, g, h. , , IA. 90 最 大 元 ,最 小 元 ,極 大 元 ,極 小 元定 義 4.20 設(shè) 為 偏 序 集 ,B A.y是 B的 最 小 元 :若 y B,使 得 x(x Byx)y是 B的 最 大 元 :若 y B,使 得 x(x Bxy) y是 B的 極 小 元 :若 y B,使 得 x(

42、x B x y)y是 B的 極 大 元 :若 y B,使 得 x(x B y x) 91 上 界 ,下 界 ,上 確 界 ,下 確 界定 義 4.21 設(shè) 為 偏 序 集 ,BA.y是 B的 上 界 :若 y A,使 得 x(x Bxy)y是 B的 下 界 :若 y A,使 得 x(x Byx)B的 最 小 上 界 或 上 確 界 :令 C y|y為 B的 上界 ,則 稱 C的 最 小 元 為 上 確 界B的 最 大 下 界 或 下 確 界 :令 D y|y為 B的 下界 ,則 稱 D的 最 大 元 為 下 確 界 92 在 圖 4.9中 ,如 果 B 2,3,6, B的 上 界 ?最 小 上

43、界 ? B的 下 界 ?最 大 下 界 ?B的 上 界 是 6和 12,最 小 上 界 是 6,B的 下 界 是 1,最大 下 界 也 是 1.而 在 圖 4.10中 ,令 B c,d,e, 問 題 同 上 。則 B的 上 界 和 最 小 上 界 都 是 e,B的 下 界 為 a,b,但B沒 有 最 大 下 界 .如 果 最 小 上 界 或 最 大 下 界 存 在 ,一 定 是 唯 一 的 . 93 一 些 結(jié) 論 ：（ 1） 最 大 （ 小 ） 元 未 必 存 在 ， 若 存 在 則 必 唯 一 ；（ 2） 極 大 （ 小 ） 元 必 存 在 ， 但 不 唯 一 ；（ 3） 最 大 （ 小

44、） 元 也 必 須 是 極 大 （ 小 ） 元 ；（ 4） 上 （ 下 ） 界 未 必 存 在 ， 若 存 在 也 未 必 唯 一 ；（ 5） 上 （ 下 ） 確 界 未 必 存 在 ， 若 存 在 則 必 唯 一 ；（ 6） 若 a是 子 集 B的 最 大 （ 小 ） 元 ， 則 a必 是 子 集 B的 上 （ 下 ） 確 界 ； 反 之 ， 若 a是 子 集 B 的 上 （ 下 ） 確 界 且 a B， 則 a必 是 B的 最 大 （ 小 ） 元 。 作 業(yè) P138-139l4.40l4.41l4.42l4.43l4.45l4.46(3)(4) 本 章 主 要 內(nèi) 容 :l集 合 的 笛

45、 卡 爾 積 與 二 元 關(guān) 系l關(guān) 系 的 運 算l關(guān) 系 的 性 質(zhì)l關(guān) 系 的 閉 包l等 價 關(guān) 系 和 偏 序 關(guān) 系l函 數(shù) 的 定 義 和 性 質(zhì)l函 數(shù) 的 復(fù) 合 和 反 函 數(shù) 96 4.6 函 數(shù) 的 定 義 和 性 質(zhì)l定 義 4.22 設(shè) X,Y為 集 合 ， F為 X到 Y二 元 關(guān)系 ,若 對 任 意 的 x domF都 存 在 唯 一 的y ranF使 得 xFy成 立 ,則 稱 F為 函 數(shù) . 例 如 ,如 下 關(guān) 系 X=x1,x2,x3 Y =y1 ,y2F1 ,是 函 數(shù)F2 , , ,不 是 函 數(shù) ,因 為 對 于 x 1domF有 x1Fy1,x

46、1Fy2同 時 成 立 . 97 如 果 函 數(shù) F,則 記 作 F(x) y,稱 y是 F在 x的 函 數(shù) 值 .l 定 義 4.23 設(shè) A,B是 集 合 ,如 果 函 數(shù) f滿 足 以 下條 件 (1) domf A, (2) ranfB, 則 稱 f是 從 A到 B的 函 數(shù) ,記 作 f:AB.l定 義 4.24 設(shè) A,B為 集 合 ,所 有 從 A到 B的 函 數(shù)構(gòu) 成 集 合 BA,讀 作 “ B上 A”.即 B A =f | f:AB , 98 l 例 2： 設(shè) P是 一 個 程 序 ， 輸 入 輸 出 都 是 整數(shù) ， (m, n) fP意 為 輸 入 m時 程 序 運 行

47、 輸 出n。 則 fP是 一 個 函 數(shù) 。l 例 3： 標(biāo) 識 圖 是 一 個 圖 ， 每 個 頂 點 或 每 條邊 或 兩 者 都 帶 有 標(biāo) 記 。 例 如 一 個 圖 的 頂點 代 表 一 個 城 市 ， 邊 代 表 兩 個 城 市 之 間的 距 離 。 設(shè) V是 頂 點 集 ， L是 標(biāo) 記 集 ， 則 f：VL是 一 個 函 數(shù) 。 用 E作 邊 集 ， g： EL，也 是 一 個 函 數(shù) 。 99 例 如 A 0,1,2,B a,b,則 BA=f1,f2,f8 f1 , f2 , , f3 , f4 , f5 , f6 , f7 , f 8=, ,.|A|=m,|B|=n,m,n

48、不 是 0,|BA|=? 100 l 定 義 4.25 設(shè) f:AB,AA,則 A在 f下 的 象 是 f(A) f(x)|x A fA,當(dāng) A A時 ,稱 f(A)=f(A) ranf是 函 數(shù) 的 象 . 101 函 數(shù) 的 性 質(zhì)l 定 義 4.26 設(shè) 函 數(shù) f:AB.(1)若 ranf B,則 稱 f是 滿 射 的 (或 到 上 的 )(2)若 對 于 任 何 的 x1, x2 A, x1x2 ,都 有f (x1)f(x2 ),則 稱 f是 單 射 的 (或 一 一 的 ),(3)若 f既 是 滿 射 的 ,又 是 單 射 的 ,則 稱 f是 雙 射的 (或 一 一 到 上 的 )

49、 102 例 如 ,函 數(shù) f:1,20,f(1) f(2) 0,那 么 f是 滿 射 的 ,但 不 是 單 射 的 .函 數(shù) f:NN,f(x) 2x是 單 射 的 ,但 不 是 滿 射 的 ,因 為 ranf不 含 有奇 數(shù) ,即 ranfN.而 函 數(shù) f:ZZ,f(x)=x 1是 雙 射 的 . 103 l定 理 . 設(shè) A， B都 是 有 限 集 ， |A|=|B|,lf： AB是 一 個 函 數(shù) ,處 處 有 定 義 。lf一 一 f滿 。lf滿 f一 一 。 104 例 4.18 分 別 確 定 以 下 各 題 中 的 f是 否為 從 A到 B的 函 數(shù) ,并 對 其 中 的f:

50、AB指 出 它 是 否 為 單 射 、 滿 射 或 雙射 的 .如 果 不 是 ,請 說 明 理 由 . (1)A 1,2,3,4,5 ,B 6,7,8,9,10, f=,. 105 (2) A 1,2,3,4,5 ,B 6,7,8,9,10, f , .(3) A 1,2,3,4,5 ,B 6,7,8,9,10, f ,. 106 (3)A,B為 實 數(shù) 集 f(x)=x3 . 雙 射(4)A,B為 實 數(shù) 集 f(x)= 不 是 函 數(shù) (5)A,B為 正 整 數(shù) 集 , f(x) x 1. 是 單 射 ， 不 是 滿 射 107 (6)A,B為 正 整 數(shù) 集是 單 射 不 是 滿 射

51、。 因 為 f(1)=f(2)=1 108 例 :判 斷 以 下 函 數(shù) 的 單 射 、 滿 射 和 雙 射(1)f:R R- R R,R為 實 數(shù) 集 ， f()=(x+y,x-y)(2)f: N N - N, N為 自 然 數(shù) 集 0 N,f()=|x2-y2| 例 :判 斷 以 下 函 數(shù) 的 單 射 、 滿 射 和 雙 射； 求 A在 f下 的 像 f(A)l (1)f: R-R , f(x)=x , A=6l 2） f: N- N N ， f(x)=, A=2,5l 3) f: Z- N ， f(x)=|x| ,A=-1,2 l 定 義 ： 函 數(shù) 相 等 、 包 含l 設(shè) f:A

52、B,g:C D,如 果 A=C， B=D,且 對 每 個 x A,有 f(x)=g(x),稱 函 數(shù) f等 于 g,記 為 f=g.l 如 果 A C， B=D,且 對 每 個 x A,有 f(x)=g(x),稱 函數(shù) f包 含 于 g,記 為 f g. 空 函 數(shù)l 設(shè) X,Y為 集 合 ，l （ 1） 當(dāng) X=時 ， X到 Y的 空 關(guān) 系 為 一 函 數(shù) ，稱 為 空 函 數(shù) 。l （ 2） 當(dāng) X 且 Y=時 , X到 Y的 空 關(guān) 系 不是 一 函 數(shù) 112 (1)設(shè) :AB,如 果 存 在 y B使 得 對 所 有 的 x A都 有f(x) y,則 稱 f:AB是 常 函 數(shù) .

53、(2)A上 的 恒 等 關(guān) 系 IA就 是 A上 的 恒 等 函 數(shù) ,對 于 所 有的 x A有 IA(x)=x.(3)設(shè) f:RR,對 于 任 意 的 x1 , x2 R,如 果 x1 x2則 有f(x1)f(x2),稱 y為 單 調(diào) 遞 增 的 .如 果 x1 x2則 有 f(x1)f(x2),就 稱 f為 嚴(yán) 格 單 調(diào) 遞 增 的 .類 似 地 也 可 以 定 義 單調(diào) 遞 減 和 嚴(yán) 格 單 調(diào) 遞 減 的 函 數(shù) ,它 們 統(tǒng) 稱 為 單 調(diào) 函 數(shù) .(4)設(shè) A為 集 合 ,對 于 任 意 的 AA,A的 特 征 函 數(shù) :A 0,1定 義 為 113 (5)設(shè) R是 A上

54、的 等 價 關(guān) 系 ,定 義 一 個 從 A到 A/R的 函 數(shù) g:A A/R且 g(a) a,它 把 A中 的 元素 a映 到 a的 等 價 類 a.我 們 稱 g是 從 A到 商 集A/R的 自 然 映 射 .例 如 ,A 1,2,3,R , IA,則 有 g(1) g(2) 1,2, g(3) 3. 作 業(yè) P139l4.49(3)-(4)l4.54l4.55 本 章 主 要 內(nèi) 容 :l集 合 的 笛 卡 爾 積 與 二 元 關(guān) 系l關(guān) 系 的 運 算l關(guān) 系 的 性 質(zhì)l關(guān) 系 的 閉 包l等 價 關(guān) 系 和 偏 序 關(guān) 系l函 數(shù) 的 定 義 和 性 質(zhì)l函 數(shù) 的 復(fù) 合 和

55、反 函 數(shù) 116 4.9 函 數(shù) 的 復(fù) 合 和 反 函 數(shù)定 理 9.1 設(shè) f:X Y,g:Y Z, 那 么 合 成 關(guān) 系 f g為 X-Z的 函 數(shù) 。證 明 ：（ 1） 先 證 明 Dom(f g)=X. 因 為 對 任 意 x X， 有 y=f(x); 又 對 任 意 y Y,有z=g(y);所 以 z=g(f(x) )= f g(x) (2)證 明 單 值 性假 設(shè) 任 意 x X,有 兩 個 z1,z2,使 得 z1= f g(x） z2= f g(x）)， 由 定 義 ， 存 在 y1,y2,使 得 y1=f(x),z1=g(y1); y2=f(x),z2=g(y2);因

56、f是 函 數(shù) ， 得 y1=y2,又 因 g是 函 數(shù) ，得 z1=z2 117 例 4.21 設(shè) f,g,h RR ,且 有 f(x) x 3,g(x) 2x 1,h(x) x/2.求 g g, h f, g h, f h, f h g(x)g g(x)=g(g(x) 2(2x 1) 1=4x 3；g g=(x,4x+3h f= ；g h = f h ；f h g(x) g (h(f (x)= g (h(x+3)=g(x+3)/2)=2 (x 3) /2)+1=x+4 118 定 理 4.9.3 設(shè) f:AB,g:B C, (1)如 果 f,g是 滿 射 的 ,則 f g:AC也 是 滿 射

57、 的 . (2)如 果 f,g是 單 射 的 ,則 f g:AC也 是 單 射 的 .(3)如 果 f,g是 雙 射 的 ,則 f g:AC也 是 雙 射 的 . 119 函 數(shù) 的 反 函 數(shù)定 理 4.9.5 設(shè) f:AB是 雙 射 的 ,則 f -1是 函 數(shù) ,并 且 是 從 B到 A的 雙 射 函 數(shù) . 對 雙 射 函 數(shù) f:AB,稱 f -1 :BA是 f的 反 函數(shù) .對 任 何 雙 射 函 數(shù) f:AB及 其反 函 數(shù) f -1 :BA,它 們 的 復(fù) 合 函 數(shù) 都 是 恒等 函 數(shù) ,且 滿 足 （ 1） f -1 f IB, f f -1 =IA （ 2） （ f -

58、1 ） -1 = f 定 理 4.9.7 設(shè) f:X Y,g:Y Z都 是 可 以 可 逆 的 ，那 么 復(fù) 合 關(guān) 系 f g也 是 可 逆 的 ， 且 (f g) -1 = g -1 f -1 122 例 4.21 設(shè) f,g,h RR ,且 有 f(x) x2-2, g(x) x 4.求 (1) f g, g f (2) 判 斷 f g, g f是 否 為 單 射 、 滿 射 和 雙射 （ 3） 求 f,g, f g, g f中 可 逆 的 反 函 數(shù) 123 本 章 重 點l集 合 的 笛 卡 爾 積 與 二 元 關(guān) 系l關(guān) 系 的 運 算 ： 關(guān) 系 的 逆 運 算 、 復(fù) 合 運 算 、閉 包 運 算 。 計 算 、 證 明l關(guān) 系 的 性 質(zhì) ： 判 斷 、 證 明l等 價 關(guān) 系 、 等 價 類 、 商 集 、 劃 分 間 的 關(guān) 系l偏 序 關(guān) 系 : 哈 斯 圖 、 8個 值 的 計 算l函 數(shù) 的 定 義 和 性 質(zhì) （ 單 射 ,滿 射 ,雙 射 ）l函 數(shù) 的 復(fù) 合 和 反 函 數(shù) 124 作 業(yè) P1404.56 , 4.61