《離散數(shù)學》二元關系和函數(shù)》由會員分享，可在線閱讀，更多相關《離散數(shù)學》二元關系和函數(shù)（35頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、第 4章 二 元 關 系 和 函 數(shù) Relation 在 高 等 數(shù) 學 中 ， 函 數(shù) 是 在 實 數(shù) 集 合 上 進 行 討 論 的 ，其 定 義 域 是 連 續(xù) 的 。 本 章 把 函 數(shù) 概 念 予 以 推 廣 定 義 域 為 一 般 的 集 合 ， 支 持 離 散 應 用 。 把 函 數(shù) 看 作 是 一 種 特 殊 的 關 系 ： 單 值 二 元 關 系 。4.6函數(shù)的定義與性質(zhì) 函 數(shù) 定 義定 義 設 F 為 二 元 關 系 , 若 x domF 都 存 在 唯 一 的y ranF 使 xFy 成 立 , 則 稱 F 為 函 數(shù) . 對 于 函 數(shù) F, 如 果 有 xFy,
2、則 記 作 y=F(x), 并 稱 y 為 F 在 x 的 函 數(shù) 值 . 例 1 F1=, F 2=, F1是 函 數(shù) , F2不 是 函 數(shù) 4.6函數(shù)的定義與性質(zhì) 函 數(shù) 與 關 系 的 區(qū) 別 從 A到 B的 函 數(shù) f與 一 般 從 A到 B的 二 元 關 系 R有如 下 區(qū) 別 ：A的 每 一 元 素 都 必 須 是 f的 序 偶 的 第 一坐 標 ， 即 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ì) 例
3、 1 設 A=1,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沒 有 像， 不 滿 足 像 的 存 在 性 。 （ 3） 不 能 構(gòu) 成 函 數(shù) ， 因 為 A
4、中 的 元 素 1有 兩 個像 7和 9， 不 滿 足 像 的 惟 一 性 。 4.6函數(shù)的定義與性質(zhì) 函 數(shù) 相 等定 義 設 F, G為 函 數(shù) , 則 F = G FG GF 一 般 使 用 下 面 兩 個 條 件 ： (1) domF = domG (2) x domF = domG 都 有 F(x) = G(x) 實 例 函 數(shù) F(x)=(x 21)/(x+1), G(x)=x1不 相 等 , 因 為 domFdomG. 4.6函數(shù)的定義與性質(zhì) 從 A到 B的 函 數(shù)定 義 設 A, B為 集 合 , 如 果 f 為 函 數(shù) domf = A ranf B, 則 稱 f 為 從 A
5、到 B的 函 數(shù) , 記 作 f： AB. 實 例 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”， 符 號 化 表 示 為 BA = f | f： AB 計 數(shù) ： |A|=m, |B|=n, 且 m, n0, |BA|=nm. A=, 則 BA=B=. A且 B=, 則 B A=A= .4.6函數(shù)的定義與性質(zhì) 實 例例 2 設 A = 1, 2, 3, B = a, b, 求 BA. 解
6、BA = f0, f1, , f7, 其 中 f0=, f1=, f2=,，f3=, f4=,，f 5=, f6=, f7=, 4.6函數(shù)的定義與性質(zhì) 函 數(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 設 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ù)的
7、定義與性質(zhì) 函 數(shù) 的 性 質(zhì)定 義 設 f： AB,（ 1） 若 ranf = B, 則 稱 f： AB是 滿 射 的 .（ 2） 若 任 意 x1， x2 A 而 且 不 相 等 ， 都 有 f(x1)與 f(x2)不 相 等 , 則 稱 f： AB是 單 射 的 .（ 3） 若 f： AB既 是 滿 射 又 是 單 射 的 , 則 稱 f： AB是 雙 射 的f 滿 射 意 味 著 ： y B, 都 存 在 x使 得 f(x) = y. f 單 射 意 味 著 ： f(x 1) = f(x2) x1= x2 4.6函數(shù)的定義與性質(zhì) 注 意 ： 由 單 射 的 定 義 可 知 ， 設 X和
8、 Y是 有 限集 合 ， 若 存 在 單 射 函 數(shù) f:X Y， 則|X| |Y|。 由 滿 射 的 定 義 可 知 ， 設 X和 Y是 有 限集 合 ， 若 存 在 滿 射 函 數(shù) f:X Y， 則|X| |Y|。 由 雙 射 的 定 義 可 知 ， 設 X和 Y是 有 限集 合 ， 若 存 在 雙 射 函 數(shù) f:X Y， 則|X|=|Y|。4.6函數(shù)的定義與性質(zhì) 實 例例 4 判 斷 下 面 函 數(shù) 是 否 為 單 射 , 滿 射 , 雙 射 的 , 為 什 么 ? (1) f： RR, f(x) = x2+2x1 (2) f： Z+R, f(x) = lnx, Z+為 正 整 數(shù) 集
9、 (3) f： RZ, f(x) = x (4) f： RR, f(x) = 2x+1 (5) f： R +R+, f(x)=(x2+1)/x, 其 中 R+為 正 實 數(shù) 集 . 4.6函數(shù)的定義與性質(zhì) 解 (1) f： RR, f(x)=x2+2x1 在 x=1取 得 極 大 值 0. 既 不 單 射 也 不 滿 射 . (2) f： Z+R, f(x)=lnx 單 調(diào) 上 升 , 是 單 射 . 但 不 滿 射 , ranf=ln1, ln2, . (3) f： RZ, f(x)= x 滿 射 , 但 不 單 射 , 例 如 f(1.5)=f(1.2)=1. (4) f： RR, f(x
10、)=2x+1 滿 射 、 單 射 、 雙 射 , 因 為 它 是 單 調(diào) 的 并 且 ranf=R. (5) f： R+R+, f(x)=(x2+1)/x 有 極 小 值 f(1)=2. 該 函 數(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,
11、 f()=f0, 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ù) 區(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、 圖 形 ， 然 后 從 第 一 個 元 素 開 始 按 照 次 序 與 自 然 數(shù) 對 應例 7 A=Z, B=N， 構(gòu) 造 雙 射 f： AB將 Z中 元 素 以 下 列 順 序 排 列 并 與 N中 元 素 對 應 ： Z： 0 1 1 2 2 3 3 N： 0 1 2 3 4 5 6 則 這 種 對 應 所 表 示 的 函 數(shù) 是 ： 2 0Z , ( ) 2 1 0 xf N f x x x ：4.6函數(shù)的定義與性質(zhì) 常 函 數(shù) 、 恒 等 函 數(shù) 、 單 調(diào) 函 數(shù) 1. 設 f： AB, 若 存 在 c B 使 得 x A 都 有 f(x)=c, 則 稱 f： AB是 常 函 數(shù)
13、 . 2. 稱 A 上 的 恒 等 關 系 IA為 A 上 的 恒 等 函 數(shù) , 對 所 有 的 x A 都 有 IA(x)=x. 3. 設 f： RR， 如 果 對 任 意 的 x1, x2 R， x1x2, 就 有 f(x1) f(x2), 則 稱 f 為 單 調(diào) 遞 增 的 ； 如 果 對 任 意 的 x 1, x2 A, x1 x2, 就 有 f(x1) f(x2), 則 稱 f 為 嚴 格 單 調(diào) 遞 增 的 . 類 似 可 以 定 義 單 調(diào) 遞 減 和 嚴 格 單 調(diào) 遞 減 的 函 數(shù) .4.6函數(shù)的定義與性質(zhì) 集 合 的 特 征 函 數(shù)4.設 A 為 集 合 , A A,
14、A 的 特 征 函 數(shù) A： A0,1 定 義 為 ,0 ,1)( AAa AaaA實 例 集 合 ： 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. 設 R 是 A 上 的 等 價 關 系 , 令 g： AA/R g(a) = a, a A稱 g 是 從 A 到 商 集 A/R 的 自 然 映 射 . 自 然 映 射 4.6函數(shù)的定義與性質(zhì) 實 例例 8 (1) A的 每 一 個 子 集 A都 對
15、 應 于 一 個 特 征 函數(shù) , 不 同 的 子 集 對 應 于 不 同 的 特 征 函 數(shù) . 例 如 A=a, b, c, 則 有 = , , ， a,b = , , (2) 給 定 集 合 A， A 上 不 同 的 等 價 關 系 確 定 不 同的 自 然 映 射 , 其 中 恒 等 關 系 確 定 的 自 然 映 射 是雙 射 , 其 他 的 自 然 映 射 一 般 來 說 是 滿 射 . 例 如 A=1, 2, 3, R=, I A g(1) = g(2) = 1,2, g(3) = 34.6函數(shù)的定義與性質(zhì) 函 數(shù) 復 合 的 定 理定 理 設 F, G是 函 數(shù) , 則 F G
16、也 是 函 數(shù) , 且 滿 足 (1) dom( FG)= x | x domG G(x) domF (2) x dom(F G) 有 FG(x) = F (G(x)推 論 1 設 F, G, H為 函 數(shù) , 則 (F G) H 和 F (G H) 都 是 函 數(shù) , 且 (F G) H = F (G H)推 論 2 設 f： BC, g： AB, 則 f g： AC, 且 x A 都 有 f g(x) = f (g(x). 4.7函數(shù)復合和反函數(shù) 函 數(shù) 復 合 運 算 的 性 質(zhì)定 理 設 g ： AB, f ： BC. (1) 如 果 f,g都 是 滿 射 , 則 fg： AC也 是
17、滿 射 . (2) 如 果 g, f 都 是 單 射 , 則 f g:AC也 是 單 射 . (3) 如 果 g, f 都 是 雙 射 , 則 f g： AC也 是 雙 射 . 證 (1) c C, 由 f： BC 的 滿 射 性 , b B 使 得 f(b)=c. 對 這 個 b, 由 g： AB 的 滿 射 性 ， a A 使 得 f(a)=b. 由 合 成 定 理 f g(a)= f ( g(a)=f(b)=c 從 而 證 明 了 f g： AC是 滿 射 的 . 函 數(shù) 復 合 運 算 的 性 質(zhì) (2) 假 設 存 在 x1, x2 A使 得 fg(x1) = f g(x2) 由 合
18、 成 定 理 有 f (g(x1)= f (g(x2). 因 為 f： BC是 單 射 的 , 故 g(x1)=g(x2). 又 由 于 g： AB也 是 單 射 的 , 所 以 x1=x2. 從 而 證 明 f g： AC是 單 射 的 . (3) 由 (1) 和 (2) 得 證 .定 理 設 f: AB， 則 f = f I B = IA f 定 理 設 f:X Y， g:Y Z， 那 么（ 1） 若 gf是 單 射 ， 則 f是 單 射 。（ 2） 若 gf是 滿 射 ， 則 g是 滿 射 。（ 3） 若 gf是 雙 射 ， 則 f是 單 射 ， g是 滿 射 。函 數(shù) 復 合 運 算
19、的 性 質(zhì) 反 函 數(shù) 存 在 的 條 件任 給 函 數(shù) F, 它 的 逆 F 1不 一 定 是 函 數(shù) , 是 二 元 關 系 .實 例 ： F=,， F 1=, 任 給 單 射 函 數(shù) f： AB, 則 f 1是 函 數(shù) , 且 是 從 ranf 到 A的 雙 射 函 數(shù) , 但 不 一 定 是 從 B 到 A 的 雙 射 函數(shù) .實 例 ： f : N N, f(x) = 2x, f 1 : ranf N, f 1 (x) = x/2 反 函 數(shù)定 理 設 f： AB是 雙 射 的 , 則 f 1： BA也 是 雙 射 函 數(shù) .證 因 為 f 是 函 數(shù) , 所 以 f 1 是 關 系
20、 , 且 dom f 1 = ranf = B , ran f 1 = domf = A, 對 于 任 意 的 y B = dom f 1, 假 設 有 x1, x2 A使 得 f 1 f 1成 立 , 則 由 逆 的 定 義 有 f f根 據(jù) f 的 單 射 性 可 得 x1 = x2, 從 而 證 明 了 f 1是 函 數(shù) ， 且 是滿 射 的 . 下 面 證 明 f 1 的 單 射 性 . 若 存 在 y1, y2 B 使 得 f 1 (y1) = f 1 (y2) = x, 從 而 有 f 1 f 1 f f y1 = y2 反 函 數(shù) 的 定 義 及 性 質(zhì)對 于 雙 射 函 數(shù) f
21、： AB, 稱 f 1： BA是 它 的 反函 數(shù) . 反 函 數(shù) 的 性 質(zhì)定 理 設 f： AB是 雙 射 的 , 則 f 1f = IA, ff 1 = IB 對 于 雙 射 函 數(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 設 X,Y,Z是 集 合 ， 如 果 f:X Y，g:Y Z都 是 可 逆 的 ， 那 么 gf也 是 可 逆 的， 且 (gf)-1=f-1g-1 。 函 數(shù) 復 合 與 反 函 數(shù) 的 計 算例 設 f： RR, g
22、： RR 求 f g, 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 一 、 兩 個 有 限 集 如 何 比 較 多 少 。 設 兩 個 班 級 A 和 B， 要 比 較 這 兩 個 班 級 的 學 生哪
23、班 多 ， 哪 班 少 ， 可 采 取 兩 種 方 法 。方 法 1： 報 數(shù) 。 報 數(shù) 后 看 誰 的 數(shù) 目 大 ， 數(shù) 目 大 的就 表 示 這 個 班 上 學 生 人 數(shù) 多 。 但 這 個 方 法 對 無 限集 卻 行 不 通 。方 法 2： 配 對 。 將 A 中 的 一 個 學 生 a1 和 B 中 的 一個 學 生 b1 配 成 一 對 ， 配 好 以 后 ， 不 許 他 們 再 和別 人 配 對 了 。 然 后 再 把 A 中 的 另 一 個 學 生 a2 和 B 中 的 一 個 學 生 b2 配 成 一 對 ， 同 樣 ， 配 好 以 后 也不 準 他 們 再 和 其 他
24、 人 配 對 了 。 這 樣 一 對 一 配 下 去， 如 果 A中 的 人 都 配 完 了 ， 而 B還 剩 下 一 些 人 ， 則說 B中 的 學 生 比 A多 ； 如 果 B 中 的 人 都 配 完 了 ， 而A 剩 下 一 些 人 ， 則 說 A中 的 學 生 比 B多 ； 如 果 A和 B中 的 學 生 正 好 都 能 一 對 一 地 搭 配 起 來 ， 則 說 A和 B的 學 生 人 數(shù) 一 樣 多 。 這 種 “ 配 對 ” 的 辦 法 可 以 應用 到 無 限 集 中 去 。 定 義 一 設 A與 B為 集 合 ， 若 存 在 從 A到 B的 雙 射， 則 稱 A和 B為 等
25、勢 ， 記 為 A B。例 6.13 (-1,1) (- ,+ )。證 明 因 存 在 著 雙 射 ， x (-1,1)， 所 以 (-1,1) (- ,+ )。 等 勢 關 系 具 有 如 下 性 質(zhì) A A。 若 A B， 則 B A。 若 A B， B C， 則 A C。 所 以 等 勢 關 系 是 等 價 關 系 。 定 義 二 設 Nn=0,1,2, ,n-1， A 為 任 一 集 合 。 若A= 或 A 與 某 個 Nn等 勢 ， 則 稱 A為 有 限 集 ； 否 則 稱 A 為 無 限 集 。定 理 一 自 然 數(shù) 集 N為 無 限 集 。 證 明 任 取 n N， f 是 從
26、Nn 到 N 的 任 意 一 個 函 數(shù) 。令 k=1+maxf(0),f(1), ,f(n-1)， 則 k N。 但 對每 個 x Nn， 都 有 f(x) k， 因 此 f不 是 滿 射 ， 從 而 f 不 是 雙 射 。 由 n和 f的 任 意 性 得 知 N 是 無 限 的 。 定 義 三 （ 1） 對 于 有 限 集 合 A， 有 唯 一 的 Nn與 其 等 勢， 對 應 的 n稱 為 A的 基 數(shù) ， 記 為 |A|（ 2） 自 然 數(shù) 集 N 的 基 數(shù) 記 為 0（ 讀 作 阿 列 夫 零 ） 。（ 3） 實 數(shù) 集 R 的 基 數(shù) 記 為 （ 讀 作 阿 列 夫 ） 。 由
27、定 義 可 知 ， 有 限 集 合 的 基 數(shù) 就 是 其 所 含 元 素 的個 數(shù) 。 兩 個 有 限 集 合 等 勢 當 且 僅 當 A和 B 的 元 素 個 數(shù)相 同 。 定 義 四 與 自 然 數(shù) 集 N 等 勢 的 集 合 叫 做 可 數(shù) 集 或可 列 集 ， 其 基 數(shù) 記 為 0。 與 自 然 數(shù) 集 N不 等 勢的 無 限 集 叫 做 不 可 數(shù) 集 或 不 可 列 集 。下 面 介 紹 可 數(shù) 集 的 一 些 性 質(zhì) 。定 理 五 集 合 A 為 可 數(shù) 集 的 充 要 條 件 是 A 的 元 素可 以 排 列 成 無 限 序 列 的 形 式 （ 即A=a0,a1, ,an, ） 。定 理 二 任 一 無 限 集 必 含 有 可 數(shù) 子 集 。定 理 三 任 一 無 限 集 必 與 其 某 一 真 子 集 等 勢 。定 理 四 可 數(shù) 集 的 任 何 無 限 子 集 是 可 數(shù) 的 。定 理 五 兩 個 可 數(shù) 集 的 并 集 仍 是 可 數(shù) 集 。
離散數(shù)學》二元關系和函數(shù)
