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

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

1、第 4章 二 元 關(guān) 系 和 函 數(shù) 在 高 等 數(shù) 學(xué) 中 ， 函 數(shù) 是 在 實(shí) 數(shù) 集 合 上 進(jìn) 行 討 論 的 ，其 定 義 域 是 連 續(xù) 的 。 本 章 把 函 數(shù) 概 念 予 以 推 廣 定 義 域 為 一 般 的 集 合 ， 支 持 離 散 應(yīng) 用 。 把 函 數(shù) 看 作 是 一 種 特 殊 的 關(guān) 系 ： 單 值 二 元 關(guān) 系 。4.6函數(shù)的定義與性質(zhì) 函 數(shù) 定 義定 義 設(shè) F 為 二 元 關(guān) 系 , 若 x domF 都 存 在 唯 一 的y ranF 使 xFy 成 立 , 則 稱(chēng) F 為 函 數(shù) . 對(duì) 于 函 數(shù) F, 如 果 有 xFy, 則 記 作 y=F

2、(x), 并 稱(chēng) y 為 F 在 x 的 函 數(shù) 值 . 例 1 F1=, F 2=, F1是 函 數(shù) , F2不 是 函 數(shù) 4.6函數(shù)的定義與性質(zhì) 函 數(shù) 與 關(guān) 系 的 區(qū) 別 從 A到 B的 函 數(shù) f與 一 般 從 A到 B的 二 元 關(guān) 系 R有如 下 區(qū) 別 ：A的 每 一 元 素 都 必 須 是 f的 序 偶 的 第 一坐 標(biāo) ， 即 dom(f)=A； 但 dom(R)R若 f(x)=y， 則 函 數(shù) f在 x處 的 值 是 惟 一的 ， 即 (f(x)=y)(f(x)=z)(y=z)，； 但 (xRy)(xRz)得 不 到 y=z4.6函數(shù)的定義與性質(zhì) 例 1 設(shè) A=1,

3、2,3,4,5， B=6,7,8,9,10， 分 別確 定 下 列 各 式 中 的 f是 否 為 由 A到 B的 函 數(shù) 。(1)f=(1,8),(3,9),(4,10),(2,6),(5,9)(2)f=(1,9),(3,10),(2,6),(4,9)(3)f=(1,7),(2,6),(4,5),(1,9),(5,10),(3,9)解 （ 1） 能 構(gòu) 成 函 數(shù) ， 因 為 符 合 函 數(shù) 的 定 義 條 件。 （ 2） 不 能 構(gòu) 成 函 數(shù) ， 因 為 A中 的 元 素 5沒(méi) 有 像， 不 滿(mǎn) 足 像 的 存 在 性 。 （ 3） 不 能 構(gòu) 成 函 數(shù) ， 因 為 A中 的 元 素 1

4、有 兩 個(gè)像 7和 9， 不 滿(mǎn) 足 像 的 惟 一 性 。 4.6函數(shù)的定義與性質(zhì) 函 數(shù) 相 等定 義 設(shè) F, G為 函 數(shù) , 則 F = G FG GF 一 般 使 用 下 面 兩 個(gè) 條 件 ： (1) domF = domG (2) x domF = domG 都 有 F(x) = G(x) 實(shí) 例 函 數(shù) F(x)=(x 21)/(x+1), G(x)=x1不 相 等 , 因 為 domFdomG. 4.6函數(shù)的定義與性質(zhì) 從 A到 B的 函 數(shù)定 義 設(shè) A, B為 集 合 , 如 果 f 為 函 數(shù) domf = A ranf B, 則 稱(chēng) f 為 從 A到 B的 函 數(shù)

5、, 記 作 f： AB. 實(shí) 例 f： NN, f(x)=2x 是 從 N 到 N 的 函 數(shù) g： NN, g(x)=2也 是 從 N 到 N 的 函 數(shù) 4.6函數(shù)的定義與性質(zhì) B上 A定 義 所 有 從 A 到 B 的 函 數(shù) 的 集 合 記 作 BA, 讀 作 “ B上 A”， 符 號(hào) 化 表 示 為 BA = f | f： AB 計(jì) 數(shù) ： |A|=m, |B|=n, 且 m, n0, |BA|=nm. A=, 則 BA=B=. A且 B=, 則 B A=A= .4.6函數(shù)的定義與性質(zhì) 實(shí) 例例 2 設(shè) A = 1, 2, 3, B = a, b, 求 BA. 解 BA = f0,

6、f1, , f7, 其 中 f0=, f1=, f2=,，f3=, f4=,，f 5=, f6=, f7=, 4.6函數(shù)的定義與性質(zhì) 函 數(shù) 的 像定 義 設(shè) 函 數(shù) f： AB, A1A. A1 在 f 下 的 像 ： f(A1) = f(x) | x A1 函 數(shù) 的 像 f(A) = ranf 注 意 ： 函 數(shù) 值 f(x) B, 而 像 f(A1)B. 例 3 設(shè) f： NN, 且 令 A=0,1, B=2, 那 么 有 f(A) = f(0,1) = f(0), f(1) = 0, 2 / 2( ) 1x xf x x x 若 為 偶 數(shù)若 為 奇 數(shù)4.6函數(shù)的定義與性質(zhì) 函 數(shù)

7、 的 性 質(zhì)定 義 設(shè) f： AB,（ 1） 若 ranf = B, 則 稱(chēng) f： AB是 滿(mǎn) 射 的 .（ 2） 若 任 意 x1， x2 A 而 且 不 相 等 ， 都 有 f(x1)與 f(x2)不 相 等 , 則 稱(chēng) f： AB是 單 射 的 .（ 3） 若 f： AB既 是 滿(mǎn) 射 又 是 單 射 的 , 則 稱(chēng) f： AB是 雙 射 的f 滿(mǎn) 射 意 味 著 ： y B, 都 存 在 x使 得 f(x) = y. f 單 射 意 味 著 ： f(x 1) = f(x2) x1= x2 4.6函數(shù)的定義與性質(zhì) 注 意 ： 由 單 射 的 定 義 可 知 ， 設(shè) X和 Y是 有 限集

8、合 ， 若 存 在 單 射 函 數(shù) f:X Y， 則|X| |Y|。 由 滿(mǎn) 射 的 定 義 可 知 ， 設(shè) X和 Y是 有 限集 合 ， 若 存 在 滿(mǎn) 射 函 數(shù) f:X Y， 則|X| |Y|。 由 雙 射 的 定 義 可 知 ， 設(shè) X和 Y是 有 限集 合 ， 若 存 在 雙 射 函 數(shù) f:X Y， 則|X|=|Y|。4.6函數(shù)的定義與性質(zhì) 實(shí) 例例 4 判 斷 下 面 函 數(shù) 是 否 為 單 射 , 滿(mǎn) 射 , 雙 射 的 , 為 什 么 ? (1) f： RR, f(x) = x2+2x1 (2) f： Z+R, f(x) = lnx, Z+為 正 整 數(shù) 集 (3) f： R

9、Z, f(x) = x (4) f： RR, f(x) = 2x+1 (5) f： R +R+, f(x)=(x2+1)/x, 其 中 R+為 正 實(shí) 數(shù) 集 . 4.6函數(shù)的定義與性質(zhì) 解 (1) f： RR, f(x)=x2+2x1 在 x=1取 得 極 大 值 0. 既 不 單 射 也 不 滿(mǎn) 射 . (2) f： Z+R, f(x)=lnx 單 調(diào) 上 升 , 是 單 射 . 但 不 滿(mǎn) 射 , ranf=ln1, ln2, . (3) f： RZ, f(x)= x 滿(mǎn) 射 , 但 不 單 射 , 例 如 f(1.5)=f(1.2)=1. (4) f： RR, f(x)=2x+1 滿(mǎn)

10、射 、 單 射 、 雙 射 , 因 為 它 是 單 調(diào) 的 并 且 ranf=R. (5) f： R+R+, f(x)=(x2+1)/x 有 極 小 值 f(1)=2. 該 函 數(shù) 既 不 單 射 也 不 滿(mǎn) 射 . 實(shí) 例 （ 續(xù) ）4.6函數(shù)的定義與性質(zhì) 構(gòu) 造 從 A到 B的 雙 射 函 數(shù)有 窮 集 之 間 的 構(gòu) 造例 5 A=P(1,2,3), B=0,11,2,3解 A=,1,2,3,1,2,1,3,2,3,1,2,3. B= f0, f1, , f7 , 其 中 f0=, f1=, f2=, f3=, f4=, f5=, f 6=, f7=,.令 f： AB, f()=f0,

11、f(1)=f1, f(2)=f2, f(3)=f3, f(1,2)=f4, f(1,3)=f5, f(2,3)=f6, f(1,2,3)=f74.6函數(shù)的定義與性質(zhì) 實(shí) 數(shù) 區(qū) 間 之 間 構(gòu) 造 雙 射構(gòu) 造 方 法 ： 直 線 方 程例 6 A=0,1 B=1/4,1/2構(gòu) 造 雙 射 f :AB構(gòu) 造 從 A到 B的 雙 射 函 數(shù) （ 續(xù) ）解 令 f： 0,11/4,1/2 f(x)=(x+1)/4 4.6函數(shù)的定義與性質(zhì) 構(gòu) 造 從 A到 B的 雙 射 函 數(shù) （ 續(xù) ）A 與 自 然 數(shù) 集 合 之 間 構(gòu) 造 雙 射方 法 ： 將 A中 元 素 排 成 有 序 圖 形 ， 然

12、后 從 第 一 個(gè) 元 素 開(kāi) 始 按 照 次 序 與 自 然 數(shù) 對(duì) 應(yīng)例 7 A=Z, B=N， 構(gòu) 造 雙 射 f： AB將 Z中 元 素 以 下 列 順 序 排 列 并 與 N中 元 素 對(duì) 應(yīng) ： Z： 0 1 1 2 2 3 3 N： 0 1 2 3 4 5 6 則 這 種 對(duì) 應(yīng) 所 表 示 的 函 數(shù) 是 ： 2 0Z , ( ) 2 1 0 xf N f x x x ：4.6函數(shù)的定義與性質(zhì) 常 函 數(shù) 、 恒 等 函 數(shù) 、 單 調(diào) 函 數(shù) 1. 設(shè) f： AB, 若 存 在 c B 使 得 x A 都 有 f(x)=c, 則 稱(chēng) f： AB是 常 函 數(shù) . 2. 稱(chēng) A

13、 上 的 恒 等 關(guān) 系 IA為 A 上 的 恒 等 函 數(shù) , 對(duì) 所 有 的 x A 都 有 IA(x)=x. 3. 設(shè) f： RR， 如 果 對(duì) 任 意 的 x1, x2 R， x1x2, 就 有 f(x1) f(x2), 則 稱(chēng) f 為 單 調(diào) 遞 增 的 ； 如 果 對(duì) 任 意 的 x 1, x2 A, x1 x2, 就 有 f(x1) f(x2), 則 稱(chēng) f 為 嚴(yán) 格 單 調(diào) 遞 增 的 . 類(lèi) 似 可 以 定 義 單 調(diào) 遞 減 和 嚴(yán) 格 單 調(diào) 遞 減 的 函 數(shù) .4.6函數(shù)的定義與性質(zhì) 集 合 的 特 征 函 數(shù) 設(shè) A 為 集 合 , A A, A 的 特 征 函

14、數(shù) A： A0,1 定 義 為 ,0 ,1)( AAa AaaA實(shí) 例 集 合 ： X = A, B, C, D, E, F, G, H , 子 集 ： T = A, C, F, G, H T 的 特 征 函 數(shù) T ： x A B C D E F G H T(x) 1 0 1 0 0 1 1 1 4.6函數(shù)的定義與性質(zhì) 5. 設(shè) R 是 A 上 的 等 價(jià) 關(guān) 系 , 令 g： AA/R g(a) = a, a A稱(chēng) g 是 從 A 到 商 集 A/R 的 自 然 映 射 . 自 然 映 射 4.6函數(shù)的定義與性質(zhì) 實(shí) 例例 8 (1) A的 每 一 個(gè) 子 集 A都 對(duì) 應(yīng) 于 一 個(gè) 特

15、 征 函數(shù) , 不 同 的 子 集 對(duì) 應(yīng) 于 不 同 的 特 征 函 數(shù) . 例 如 A=a, b, c, 則 有 = , , ， a,b = , , (2) 給 定 集 合 A， A 上 不 同 的 等 價(jià) 關(guān) 系 確 定 不 同的 自 然 映 射 , 其 中 恒 等 關(guān) 系 確 定 的 自 然 映 射 是雙 射 , 其 他 的 自 然 映 射 一 般 來(lái) 說(shuō) 是 滿(mǎn) 射 . 例 如 A=1, 2, 3, R=, I A g(1) = g(2) = 1,2, g(3) = 34.6函數(shù)的定義與性質(zhì) 函 數(shù) 復(fù) 合 的 定 理定 理 設(shè) F, G是 函 數(shù) , 則 F G也 是 函 數(shù) ,

16、且 滿(mǎn) 足 (1) dom( FG)= x | x domG G(x) domF (2) x dom(F G) 有 FG(x) = F (G(x)推 論 1 設(shè) F, G, H為 函 數(shù) , 則 (F G) H 和 F (G H) 都 是 函 數(shù) , 且 (F G) H = F (G H)推 論 2 設(shè) f： BC, g： AB, 則 f g： AC, 且 x A 都 有 f g(x) = f (g(x). 4.7函數(shù)復(fù)合和反函數(shù) 函 數(shù) 復(fù) 合 運(yùn) 算 的 性 質(zhì)定 理 設(shè) g ： AB, f ： BC. (1) 如 果 f,g都 是 滿(mǎn) 射 , 則 fg： AC也 是 滿(mǎn) 射 . (2)

17、如 果 g, f 都 是 單 射 , 則 f g:AC也 是 單 射 . (3) 如 果 g, f 都 是 雙 射 , 則 f g： AC也 是 雙 射 . 證 (1) c C, 由 f： BC 的 滿(mǎn) 射 性 , b B 使 得 f(b)=c. 對(duì) 這 個(gè) b, 由 g： AB 的 滿(mǎn) 射 性 ， a A 使 得 f(a)=b. 由 合 成 定 理 f g(a)= f ( g(a)=f(b)=c 從 而 證 明 了 f g： AC是 滿(mǎn) 射 的 . 函 數(shù) 復(fù) 合 運(yùn) 算 的 性 質(zhì) (2) 假 設(shè) 存 在 x1, x2 A使 得 fg(x1) = f g(x2) 由 合 成 定 理 有 f

18、 (g(x1)= f (g(x2). 因 為 f： BC是 單 射 的 , 故 g(x1)=g(x2). 又 由 于 g： AB也 是 單 射 的 , 所 以 x1=x2. 從 而 證 明 f g： AC是 單 射 的 . (3) 由 (1) 和 (2) 得 證 .定 理 設(shè) f: AB， 則 f = f I B = IA f 定 理 設(shè) f:X Y， g:Y Z， 那 么（ 1） 若 gf是 單 射 ， 則 f是 單 射 。（ 2） 若 gf是 滿(mǎn) 射 ， 則 g是 滿(mǎn) 射 。（ 3） 若 gf是 雙 射 ， 則 f是 單 射 ， g是 滿(mǎn) 射 。函 數(shù) 復(fù) 合 運(yùn) 算 的 性 質(zhì) 反 函

19、數(shù) 存 在 的 條 件任 給 函 數(shù) F, 它 的 逆 F 1不 一 定 是 函 數(shù) , 是 二 元 關(guān) 系 .實(shí) 例 ： F=,， F 1=, 任 給 單 射 函 數(shù) f： AB, 則 f 1是 函 數(shù) , 且 是 從 ranf 到 A的 雙 射 函 數(shù) , 但 不 一 定 是 從 B 到 A 的 雙 射 函數(shù) .實(shí) 例 ： f : N N, f(x) = 2x, f 1 : ranf N, f 1 (x) = x/2 反 函 數(shù)定 理 設(shè) f： AB是 雙 射 的 , 則 f 1： BA也 是 雙 射 函 數(shù) .證 因 為 f 是 函 數(shù) , 所 以 f 1 是 關(guān) 系 , 且 dom f

20、 1 = ranf = B , ran f 1 = domf = A, 對(duì) 于 任 意 的 y B = dom f 1, 假 設(shè) 有 x1, x2 A使 得 f 1 f 1成 立 , 則 由 逆 的 定 義 有 f f根 據(jù) f 的 單 射 性 可 得 x1 = x2, 從 而 證 明 了 f 1是 函 數(shù) ， 且 是滿(mǎn) 射 的 . 下 面 證 明 f 1 的 單 射 性 . 若 存 在 y1, y2 B 使 得 f 1 (y1) = f 1 (y2) = x, 從 而 有 f 1 f 1 f f y1 = y2 反 函 數(shù) 的 定 義 及 性 質(zhì)對(duì) 于 雙 射 函 數(shù) f： AB, 稱(chēng) f

21、1： BA是 它 的 反函 數(shù) . 反 函 數(shù) 的 性 質(zhì)定 理 設(shè) f： AB是 雙 射 的 , 則 f 1f = IA, ff 1 = IB 對(duì) 于 雙 射 函 數(shù) f： AA, 有 f 1f = ff 1 = IA 定 理 若 f:X Y是 可 逆 的 ， 那 么 （ l） (f-1)-1=f （ 2） f-1f=IX， ff-1=IY定 理 3.9 設(shè) X,Y,Z是 集 合 ， 如 果 f:X Y，g:Y Z都 是 可 逆 的 ， 那 么 gf也 是 可 逆 的， 且 (gf)-1=f-1g-1 。 函 數(shù) 復(fù) 合 與 反 函 數(shù) 的 計(jì) 算例 設(shè) f： RR, g： RR 求 f g

22、, g f. 如 果 f 和 g 存 在 反 函 數(shù) , 求 出 它 們 的 反 函 數(shù) . 2 3( ) ( ) 22 3x xf x g x xx 解 f： RR不 是 雙 射 的 , 不 存 在 反 函 數(shù) . g： RR是 雙 射 的 , 它的 反 函 數(shù) 是 g 1： RR, g1(x) = x2 2 2: :2 3 ( 2) 1( ) ( )0 3 2 1f g R R g f R Rx x x xf g x g f xx x 一 、 兩 個(gè) 有 限 集 如 何 比 較 多 少 。 設(shè) 兩 個(gè) 班 級(jí) A 和 B， 要 比 較 這 兩 個(gè) 班 級(jí) 的 學(xué) 生哪 班 多 ， 哪 班

23、少 ， 可 采 取 兩 種 方 法 。方 法 1： 報(bào) 數(shù) 。 報(bào) 數(shù) 后 看 誰(shuí) 的 數(shù) 目 大 ， 數(shù) 目 大 的就 表 示 這 個(gè) 班 上 學(xué) 生 人 數(shù) 多 。 但 這 個(gè) 方 法 對(duì) 無(wú) 限集 卻 行 不 通 。方 法 2： 配 對(duì) 。 將 A 中 的 一 個(gè) 學(xué) 生 a1 和 B 中 的 一個(gè) 學(xué) 生 b1 配 成 一 對(duì) ， 配 好 以 后 ， 不 許 他 們 再 和別 人 配 對(duì) 了 。 然 后 再 把 A 中 的 另 一 個(gè) 學(xué) 生 a2 和 B 中 的 一 個(gè) 學(xué) 生 b2 配 成 一 對(duì) ， 同 樣 ， 配 好 以 后 也不 準(zhǔn) 他 們 再 和 其 他 人 配 對(duì) 了 。

24、 這 樣 一 對(duì) 一 配 下 去， 如 果 A中 的 人 都 配 完 了 ， 而 B還 剩 下 一 些 人 ， 則說(shuō) B中 的 學(xué) 生 比 A多 ； 如 果 B 中 的 人 都 配 完 了 ， 而A 剩 下 一 些 人 ， 則 說(shuō) A中 的 學(xué) 生 比 B多 ； 如 果 A和 B中 的 學(xué) 生 正 好 都 能 一 對(duì) 一 地 搭 配 起 來(lái) ， 則 說(shuō) A和 B的 學(xué) 生 人 數(shù) 一 樣 多 。 這 種 “ 配 對(duì) ” 的 辦 法 可 以 應(yīng)用 到 無(wú) 限 集 中 去 。 定 義 一 設(shè) A與 B為 集 合 ， 若 存 在 從 A到 B的 雙 射， 則 稱(chēng) A和 B為 等 勢(shì) ， 記 為 A

25、B。例 6.13 (-1,1) (- ,+ )。證 明 因 存 在 著 雙 射 ， x (-1,1)， 所 以 (-1,1) (- ,+ )。 等 勢(shì) 關(guān) 系 具 有 如 下 性 質(zhì) A A。 若 A B， 則 B A。 若 A B， B C， 則 A C。 所 以 等 勢(shì) 關(guān) 系 是 等 價(jià) 關(guān) 系 。 定 義 二 設(shè) Nn=0,1,2, ,n-1， A 為 任 一 集 合 。 若A= 或 A 與 某 個(gè) Nn等 勢(shì) ， 則 稱(chēng) A為 有 限 集 ； 否 則 稱(chēng) A 為 無(wú) 限 集 。定 理 一 自 然 數(shù) 集 N為 無(wú) 限 集 。 證 明 任 取 n N， f 是 從 Nn 到 N 的 任

26、 意 一 個(gè) 函 數(shù) 。令 k=1+maxf(0),f(1), ,f(n-1)， 則 k N。 但 對(duì)每 個(gè) x Nn， 都 有 f(x) k， 因 此 f不 是 滿(mǎn) 射 ， 從 而 f 不 是 雙 射 。 由 n和 f的 任 意 性 得 知 N 是 無(wú) 限 的 。 定 義 三 （ 1） 對(duì) 于 有 限 集 合 A， 有 唯 一 的 Nn與 其 等 勢(shì)， 對(duì) 應(yīng) 的 n稱(chēng) 為 A的 基 數(shù) ， 記 為 |A|（ 2） 自 然 數(shù) 集 N 的 基 數(shù) 記 為 0（ 讀 作 阿 列 夫 零 ） 。（ 3） 實(shí) 數(shù) 集 R 的 基 數(shù) 記 為 （ 讀 作 阿 列 夫 ） 。 由 定 義 可 知 ，

27、有 限 集 合 的 基 數(shù) 就 是 其 所 含 元 素 的個(gè) 數(shù) 。 兩 個(gè) 有 限 集 合 等 勢(shì) 當(dāng) 且 僅 當(dāng) A和 B 的 元 素 個(gè) 數(shù)相 同 。 定 義 四 與 自 然 數(shù) 集 N 等 勢(shì) 的 集 合 叫 做 可 數(shù) 集 或可 列 集 ， 其 基 數(shù) 記 為 0。 與 自 然 數(shù) 集 N不 等 勢(shì)的 無(wú) 限 集 叫 做 不 可 數(shù) 集 或 不 可 列 集 。下 面 介 紹 可 數(shù) 集 的 一 些 性 質(zhì) 。定 理 五 集 合 A 為 可 數(shù) 集 的 充 要 條 件 是 A 的 元 素可 以 排 列 成 無(wú) 限 序 列 的 形 式 （ 即A=a0,a1, ,an, ） 。定 理 二 任 一 無(wú) 限 集 必 含 有 可 數(shù) 子 集 。定 理 三 任 一 無(wú) 限 集 必 與 其 某 一 真 子 集 等 勢(shì) 。定 理 四 可 數(shù) 集 的 任 何 無(wú) 限 子 集 是 可 數(shù) 的 。定 理 五 兩 個(gè) 可 數(shù) 集 的 并 集 仍 是 可 數(shù) 集 。