离散数学离散第八章

1、广东工业大学计算机学院1第八章第八章 函数函数主要内容主要内容8.1 函数的定义与性质函数的定义与性质l 函数定义函数定义l 函数性质函数性质8.2 函数运算函数运算l 函数的逆函数的逆l 函数的合成函数的合成8.3 双射函数与集合的基数双射函数与集合的基数(课外阅读课外阅读)广东工业大学计算机学院28.1 函数的定义与性质函数的定义与性质主要内容主要内容1. 函数定义与相关概念函数定义与相关概念l 函数定义函数定义l 函数相等函数相等l 从从A到到B的函数的函数f:ABl BAl 函数的像与完全原像函数的像与完全原像2. 函数的性质函数的性质l 单射、满射、双射函数的定义与实例单射、满射、双

2、射函数的定义与实例l 构造双射函数构造双射函数3. 某些重要的函数某些重要的函数广东工业大学计算机学院3函数定义函数定义定义定义8.1 设设 F 为二元关系为二元关系, 若若 xdomF 都存在唯一的都存在唯一的yranF 使使 xFy 成立成立, 则称则称 F 为为函数函数 对于函数对于函数F, 如果有如果有 xFy, 则记作则记作 y=F(x), 并称并称 y 为为F 在在 x 的的值值. 例例 F1 = , , F2 = , F1是函数是函数, F2不是函数不是函数定义定义8.2 设设F, G 为函数为函数, 则则 F=G F GG F 如果两个函数如果两个函数F 和和 G 相等相等,

3、一定满足下面两个条件：一定满足下面两个条件： (1) domF = domG (2) xdomF = domG 都有都有F(x) = G(x) 例：例：函数函数F(x) = (x2 1)/(x+1)与与G(x) = x 1不相等不相等, 因为因为 domF domG广东工业大学计算机学院4从从A到到B的函数的函数定义定义8.3 设设A, B为集合为集合, 如果如果 f 为函数为函数, domf=A, ranf B, 则称则称 f 为为从从A到到B的函数的函数, 记作记作 f：AB.例例 f：NN, f(x) = 2x 是从是从N到到N的函数的函数, g：NN, g(x) = 2 也是从也是从N

4、到到N的函数的函数. 定义定义8.4 所有从所有从A到到B的的函数的集合函数的集合记作记作BA, 符号化表示为符号化表示为 BA = f | f：AB |A| = m, |B| = n, 且且m, n0, |BA|=nmA = , 则则BA = B = A且且B = , 则则BA = A = 广东工业大学计算机学院5实例实例例例1 设设A = 1, 2, 3, B = a, b, 求求BA.解解BA = f0, f1, , f7, 其中其中 f0 = , , f1 = , , f2 = , , f3 = , , f4 = , , f5 = , , f6 = , , f7 = , , 注意注意:

5、 1. 有序对的第一元各不相同有序对的第一元各不相同2. 定义域中每一个元素都必定义域中每一个元素都必须出现须出现广东工业大学计算机学院6函数的像和完全原像函数的像和完全原像定义定义8.5 设函数设函数 f：AB, A1 A, B1 B(1) A1在在 f 下的像下的像 f(A1) = f(x) | xA1, 函数的像函数的像 f(A) (2) B1在在 f 下的完全原像下的完全原像 f 1(B1) = x|xAf(x)B1注意注意：(1) 函数值与像的区别：函数值函数值与像的区别：函数值 f(x)B, 像像f(A1) Bl (2) 一般说来一般说来 f 1(f(A1)A1, 但是但是A1 f

6、 1(f(A1)l 例如函数例如函数f: 1, 2, 3 0, 1，满足，满足f(1) = f(2) = 0, f(3) = 1令令A1 = 1，则有，则有f 1(f(A1) = f 1(f(1) = f 1(0) = 1, 2例例 设设 f：NN, 且且令令A = 0,1, B = 2, 那么有那么有 f(A) = f(0, 1) = f(0), f(1) = 0, 2 f 1(B) = f 1(2) = 1, 4 为奇数为奇数若若为偶数为偶数若若xxxxxf12/)(广东工业大学计算机学院7函数的性质函数的性质定义定义8.6 设设 f：AB,(1) 若若 ranf = B, 则称则称 f:

7、AB是是满射满射的的(2) 若若 yranf 都存在唯一的都存在唯一的 xA 使得使得 f(x)=y, 则称则称 f: AB 是是单射单射的的(3) 若若 f: AB 既是满射又是单射的既是满射又是单射的, 则称则称 f: AB是是双射双射的的例例2 判断下面函数是否为单射判断下面函数是否为单射, 满射满射, 双射的双射的, 为什么为什么?(1) f: RR, f(x) = x2+2x 1 在在x=1取得极大值取得极大值0. 既不是单射也不是满射的既不是单射也不是满射的(2) f: Z+R, f(x) = lnx, Z+为正整数集为正整数集 是单调上升的是单调上升的, 是单射的是单射的. 但不

8、满射但不满射, ranf = ln1, ln2, .广东工业大学计算机学院8例题解答例题解答解：解：(3) f: RZ, f(x) = x 是满射的是满射的, 但不是单射的但不是单射的, 例如例如f(1.5) = f(1.2) = 1(4) f: RR, f(x)=2x+1 是满射、单射、双射的是满射、单射、双射的, 因为它是单调函数并且因为它是单调函数并且ranf=R(5) f: R+R+, f(x)=(x2+1)/x 有极小值有极小值 f(1)=2. 该函数既不是单射的也不是满射的该函数既不是单射的也不是满射的广东工业大学计算机学院9特殊函数的图形表示特殊函数的图形表示广东工业大学计算机学

9、院10从定义可知从定义可知: 当当A、B为有限集时为有限集时, f: AB1. f 为单射的必要条件是为单射的必要条件是 |A|B|；2. f 为满射的必要条件是为满射的必要条件是 |A|B|；3. f 为双射的必要条件是为双射的必要条件是 |A| = |B|。讨论：讨论：设设 |A| = n, |B| = m,(1) 当当n m, AB中共含的中共含的单单射射函数函数： 满满射函数：射函数：关于特殊函数的讨论关于特殊函数的讨论ABnmCnmP0n!0!rnm12211001111nnnnrnrnrrn广东工业大学计算机学院11举例举例1已知已知 A1=a ,b, B1 = 1, 2, 3,

10、求求A1B1求求A1B1中的单射、满射、双射函数中的单射、满射、双射函数.解解: |A| = 2, |B| = 3，无满射，无双射。，无满射，无双射。 A1B1中单射有中单射有 = 6个：个： f1 = , , f2 = , , f3 = , , f4 = , , f5 = , , f6 = , . 23P广东工业大学计算机学院12举例举例2例例2：A2 = a, b, c, B2 = 1, 2, 求求A2B2的单射、满射、双的单射、满射、双射函数射函数.解解: (2) |A| =3, |B| = 2，无单射，无双射，无单射，无双射. A2B2中中满射满射 = 6个个: f1 = , , ,

11、f2 = , , , f3 = , , , f4 = , , , f5 = , , , f6 = , , . 1!mnnCm广东工业大学计算机学院13某些重要函数某些重要函数定义定义8.7 (1)设设 f:AB, 如果存在如果存在cB使得对所有的使得对所有的 xA都有都有 f(x) = c, 则称则称 f: AB是是常函数常函数.(2) 称称 A上的恒等关系上的恒等关系IA为为A上的上的恒等函数恒等函数, 对所有的对所有的xA都有都有IA(x) = x.(3) 设设, 为偏序集，为偏序集，f: AB，如果对任意的，如果对任意的 x1, x2A, x1 x2, 就有就有 f(x1) f(x2),

12、 则称则称 f 为为单调递增单调递增的；如的；如果对任意的果对任意的x1, x2A, x1 x2, 就有就有f(x1) f(x2), 则称则称 f 为为严严格单调递增格单调递增的的. 类似的也可以定义单调递减和严格单调递减的函数类似的也可以定义单调递减和严格单调递减的函数例：例：(1) 偏序集偏序集, , R 为包含关系为包含关系, 为为一般的小于等于关系一般的小于等于关系, 令令 f: P(a, b)0, 1, f() = f(a) = f(b) = 0, f(a, b) = 1 f 是单调递增的是单调递增的, 但不是严格单调递增的但不是严格单调递增的广东工业大学计算机学院14(4) 设设A

13、为集合为集合, 对于任意的对于任意的A A, A的的特征函数特征函数 A: A0, 1定义为定义为 A(a) = 1, a A A(a) = 0, a A A举例：举例：A的每一个子集的每一个子集 A都对应于一个特征函数都对应于一个特征函数, 不同的子不同的子集对应于不同的特征函数集对应于不同的特征函数. 例如例如A = a, b, c, 则有则有 =, , ， a, b=, , 某些重要函数某些重要函数(续续1)广东工业大学计算机学院15(5) 设设R是是A上的等价关系上的等价关系, 令令 g: AA/R g(a) = a, aA称称 g 是从是从 A 到商集到商集 A/R 的的自然映射自然

14、映射举例：举例：不同的等价关系确定不同的自然映射。不同的等价关系确定不同的自然映射。 恒等关系确定的自然映射是双射恒等关系确定的自然映射是双射, 其他自然映射一般来说其他自然映射一般来说只是满射只是满射. 例如例如 A = 1, 2, 3, R = , IA g: AA/R, g(1) = g(2) = 1, 2, g(3) = 3某些重要函数某些重要函数(续续2)广东工业大学计算机学院168.2 函数的复合与反函数函数的复合与反函数 主要内容主要内容l 1. 复合函数基本定理复合函数基本定理l 2. 函数的复合运算与函数性质函数的复合运算与函数性质l 3. 反函数的存在条件反函数的存在条件l

15、 4. 反函数的性质反函数的性质广东工业大学计算机学院171. 复合函数基本定理复合函数基本定理定理定理8.1 设设F, G是函数是函数, 则则F G也是函数也是函数, 且满足且满足(1) dom(F G) = x|xdomF F(x)domG(2) xdom(F G)有有F G(x) = G(F(x)【也写作也写作(F G)(x) 】证明：证明：先证明先证明F G是函数是函数. 因为因为F, G是关系是关系, 所以所以F G也是关系也是关系. 若对某个若对某个xdom(F G)有有xF Gy1和和 xF Gy2, 则则 F GF G t1(FG) t2(FG) t1 t2(t1 = t2GG

16、) （F为函数）为函数） y1 = y2 （G为函数）为函数）所以所以 F G 为函数为函数广东工业大学计算机学院18函数的复合定理证明函数的复合定理证明定理定理8.1 设设F, G是函数是函数, 则则F G也是函数也是函数, 且满足且满足(1) dom(F G) = x|xdomF F(x)domG(2) xdom(F G)有有F G(x) = G(F(x)证明：证明：(1) 任取任取x, xdom(F G) t y(FG) t (xdomFt=F(x)tdomG) x x | xdomFF(x)domG (2) 任取任取x, xdomFF(x)domG FG F G xdom(F G)F

17、G(x)G(F(x)广东工业大学计算机学院19函数的复合定理推论函数的复合定理推论推论推论1 设设F, G, H为函数为函数, 则则(F G) H和和F (G H)都是函数都是函数, 且且 (F G) H=F (G H)证证 由上述定理和运算满足结合律得证由上述定理和运算满足结合律得证.推论推论2 设设 f: AB, g: BC, 则则 f g: AC, 且且 xA都有都有 f g(x) = g(f(x)证证 由上述定理知由上述定理知 f g是函数是函数, 且且 dom(f g)=x|xdomff(x)domg =x|xAf(x)B=A ran(f g) rang C因此因此 f g: AC,

18、 且且 xA有有 f g(x) = g(f(x)广东工业大学计算机学院20函数复合与函数性质函数复合与函数性质定理定理8.2 设设f: AB, g: BC (1) 如果如果 f: AB, g: BC是是满射满射的的, 则则 f g: AC也是也是满射满射的的(2) 如果如果 f: AB, g: BC是是单射单射的的, 则则 f g: AC也是也是单射单射的的 (3) 如果如果 f: AB, g: BC是是双射双射的的, 则则 f g: AC也是也是双射双射的的 证明：证明：(1) 任取任取cC, 由由g: BC的满射性，的满射性， bB使得使得 g(b) = c.对于对于b, 由由 f: AB

19、的满射性，的满射性， aA使得使得 f(a) = b.由合成定理有由合成定理有 f g(a) = g(f(a) = g(b) = c从而证明了从而证明了f g: AC是满射的是满射的广东工业大学计算机学院21函数复合与函数性质函数复合与函数性质证明证明定理定理8.2 设设f: AB, g: BC (2) 如果如果 f: AB, g: BC是是单射单射的的, 则则 f g: AC也是也是单射单射的的 证明：证明：假设存在假设存在x1, x2A使得：使得：f g(x1)=f g(x2)由合成定理有由合成定理有 g(f(x1) = g(f(x2)因为因为g: BC是单射的是单射的, 故故 f(x1)

20、=f(x2). 又由于又由于f: AB是单射的是单射的, 所以所以x1=x2. 从而证明从而证明f g: AC是单射的是单射的.注意：注意：定理逆命题不为真定理逆命题不为真, 即如果即如果f g: AC是单射是单射(或满射、或满射、双射双射)的的, 不一定有不一定有 f: AB 和和g: BC都是单射都是单射(或满射、双或满射、双射射)的的.定理定理8.3 设设 f: AB, 则则 f = f IB = IA f （证明略）（证明略）广东工业大学计算机学院22实例实例考虑集合考虑集合A=a1, a2, a3, B=b1, b2, b3, b4, C=c1, c2, c3. 令令 f=, g=,

21、 f g=,那么那么 f: AB和和f g: AC是单射的是单射的, 但但g: BC不是单射的不是单射的. 考虑集合考虑集合A=a1, a2, a3, B=b1, b2, b3, C=c1, c2. 令令f=,g=,f g=,那么那么g: BC 和和 f g: AC是满射的是满射的, 但但 f: AB不是满射的不是满射的.广东工业大学计算机学院232. 反函数反函数反函数存在的条件：反函数存在的条件：(1) 任给函数任给函数F, 它的逆它的逆F 1不一定是函数不一定是函数, 只是一个二元关系只是一个二元关系.(2) 任给单射函数任给单射函数 f: AB, 则则f 1是函数是函数, 且是从且是从

22、ranf 到到A的双的双 射函数射函数, 但不一定是从但不一定是从B到到A的双射函数的双射函数(3) 对于双射函数对于双射函数 f: AB, f 1: BA是从是从B到到A的双射函数的双射函数. 注意注意: 仅当仅当f是双射函数，才可定义是双射函数，才可定义f逆函数，逆函数，且且f 1就是就是f的逆的逆关系。关系。广东工业大学计算机学院24证明证明定理定理8.4 设设 f: AB是双射的是双射的, 则则f 1: BA也是双射的也是双射的.证明思路：证明思路：(1) 先证明先证明 f 1: BA，即，即f 1是函数，且是函数，且domf 1=B, ranf 1=A. (2) 再证明再证明f 1:

23、 BA具有双射性质具有双射性质.证明：证明：因为因为 f 是函数是函数, 所以所以 f 1是关系是关系, 且且 dom f 1 = ranf = B , ran f 1 = domf = A对于任意的对于任意的 xB = dom f 1, 假设有假设有y1, y2A使得使得 f 1f 1成立成立, 则由逆的定义有则由逆的定义有 ff根据根据 f 的单射性可得的单射性可得y1=y2, 从而证明了从而证明了f 1是函数。是函数。由由x的任意性可知，的任意性可知， f 1是满射的是满射的.广东工业大学计算机学院25证明证明(续续)定理定理8.4 设设 f: AB是双射的是双射的, 则则f 1: BA

24、也是双射的也是双射的.证明思路：证明思路：先证明先证明 f 1: BA，即，即f 1是函数，且是函数，且domf 1=B, ranf 1=A. 再证明再证明f 1: BA的双射性质的双射性质.证明证明(续续)：再证明再证明f 1的单射性。的单射性。若存在若存在x1, x2B使得使得f 1 (x1)= f 1 (x2)=y, 从而有从而有 f 1f 1 ff x1=x2 对于双射函数对于双射函数f:AB, 称称 f 1:BA是它的是它的反函数反函数. 所以所以f 1是双射的是双射的广东工业大学计算机学院26反函数的性质反函数的性质定理定理8.5 (1) 设设 f: AB是双射的是双射的, 则则

25、f 1 f = IB, f f 1 = IA(2) 对于双射函数对于双射函数 f: AA, 有有 f 1 f = f f 1 = IA 证明思路：证明思路：根据定理可知根据定理可知 f 1: BA也是双射的也是双射的, 由合成基本定理可知由合成基本定理可知 f 1 f: BB, f f 1: AA，且它们都是恒等函数，且它们都是恒等函数. 广东工业大学计算机学院27解解 121)2()(RR:3032)(RR:22xxxxfgfgxxxxgfgff: RR不是双射的不是双射的, 不存在反函不存在反函数数. g: RR是双射的是双射的, 它的反函数是它的反函数是g 1: RR, g 1(x)=x

26、 2求解求解例例5 设设 求求 f g, g f. 如果如果f 和和 g 存在反函数存在反函数, 求出它们的反函数求出它们的反函数.2)(323)(RR:,RR:2 xxgxxxxfgf广东工业大学计算机学院283. 鸽巢原理鸽巢原理(pigeonhole principle)鸽巢原理鸽巢原理(pigeonhole principle): 又名又名鸽洞原理鸽洞原理。若把。若把n+1只只鸽子装进鸽子装进n只鸽巢只鸽巢, 则至少有一只鸽巢装则至少有一只鸽巢装2只以上的鸽子只以上的鸽子.又名又名抽屉原则抽屉原则(Dirichlet drawer principle), (Peter Gustav L

27、ejeune Dirichlet,18051859)例：例：一个轮盘赌转盘的圆周分为一个轮盘赌转盘的圆周分为36段，将段，将1，2，36，任意标在每一段上，证明一定存在连续的三段，它们的数字任意标在每一段上，证明一定存在连续的三段，它们的数字之和至少是之和至少是56。解：解：1+2+36 = 666 36段可以分作段可以分作12个组连续的个组连续的3段，每组平均数字之和：段，每组平均数字之和： 666/12 = 55.5， 55.5 = 56 必存在连续的三段，它们的数字之和至少是必存在连续的三段，它们的数字之和至少是56广东工业大学计算机学院298.3 双射函数与集合的基数双射函数与集合的基

28、数主要内容主要内容l 集合的等势及其性质集合的等势及其性质l 重要的等势或不等势的结果重要的等势或不等势的结果l 集合的优势及其性质集合的优势及其性质l 集合的基数集合的基数l 可数集可数集广东工业大学计算机学院30 01202)(,NZ:xxxxxff则则 f 是是Z到到N的双射函数的双射函数. 从而证明了从而证明了ZN.集合的等势集合的等势集合等势的实例集合等势的实例例例6 (1) ZN. 定义定义8.8 设设A, B是集合是集合, 如果存在着从如果存在着从A到到B的双射函数的双射函数, 就称就称A和和B是是等势等势的的, 记作记作AB. 如果如果A不与不与B 等势等势, 则记作则记作A

29、B.广东工业大学计算机学院31mnmnmnmff 2)(1(),(,NNN:集合等势的实例集合等势的实例: NNNNNN. NN中所有的元素排成有序图形中所有的元素排成有序图形广东工业大学计算机学院32-2/1-2/155-1/1-1/144-3/1-3/118182/12/110103/13/111110/10/1001/11/111-2/2-2/2-1/2-1/233-3/2-3/217172/22/23/23/212120/20/21/21/222-2/3-2/366-1/3-1/377-3/3-3/32/32/3993/33/30/30/31/31/388-2/4-2/4-1/4-1/

30、41515-3/4-3/416162/42/43/43/413130/40/41/41/41414PLAYNQ. 双射函数双射函数 f:NQ, 其中其中f(n)是是n下方的有理数下方的有理数. 集合等势的实例集合等势的实例: NQ广东工业大学计算机学院33212tan)(,R)1 , 0(: xxff xxnxxxxfnn其它其它,.2 , 1,2/12/112/102/1)(12(6) 对任何对任何a, bR, ab, 0,1a,b，双射函数双射函数 f:0,1a,b, f(x)=(b a)x+a类似地可以证明类似地可以证明, 对任何对任何a, bR, ab, 有有(0,1)(a,b).(4

31、) (0,1)R. 其中实数区间其中实数区间 (0,1)=x| xR0 x1. 令令(5) 0,1(0,1). 其中其中(0,1)和和0,1分别为实数开区间和闭区间分别为实数开区间和闭区间. 令令 f : 0,1(0,1)实数集合的等势实数集合的等势广东工业大学计算机学院34实例实例例例7 设设A为任意集合为任意集合, 则则P(A)0,1A.证证 如下构造从如下构造从P(A) 到到 0,1A 的函数的函数 f:P(A)0,1A, f(A)= A, AP(A).其中其中 A是集合是集合A的特征函数的特征函数. 易证易证 f 是单射的是单射的. 对于任意的对于任意的 g0,1A, 那么有那么有 g

32、:A0,1. 令令 B= x| xAg(x)=1则则B A, 且且 B=g, 即即 BP(A), f(B)=g. 从而证明了从而证明了f 是满射是满射的的. 由等势定义得由等势定义得 P(A)0,1A.广东工业大学计算机学院35等势的性质等势的性质定理定理8.6 设设A, B,C是任意集合，是任意集合，(1) AA(2) 若若AB，则，则BA(3) 若若AB，BC，则，则AC.证明思路：利用等势的等义证明思路：利用等势的等义. (1) IA是从是从A到到A的双射的双射(2) 若若 f:AB是双射，则是双射，则f 1:BA是从是从B到到A的双射的双射.(3) 若若 f:AB，g:BC是双射，则是

33、双射，则f g:AC是从是从A到到C的双射的双射 广东工业大学计算机学院36有关势的重要结果有关势的重要结果等势结果等势结果l N Z Q NNl 任何实数区间都与实数集合任何实数区间都与实数集合R等势等势不等势的结果不等势的结果: 定理定理8.7 (康托定理康托定理)(1) N R； (2) 对任意集合对任意集合A都有都有A P(A)证明思路：证明思路：(1) 只需证明任何函数只需证明任何函数 f:N0,1都不是满射的都不是满射的. 任取函数任取函数 f:N0,1, 列出列出 f 的所有函数值，然后构造一个的所有函数值，然后构造一个0,1区间的小数区间的小数b，使得，使得b与所有的函数值都不

34、相等与所有的函数值都不相等. (2) 任取函数任取函数 f:AP(A)，构造，构造B P(A)，使得，使得B与与 f 的任何函的任何函 数值都不等数值都不等. 广东工业大学计算机学院37Cantor定理的证明定理的证明证证 (1) 规定规定0,1中数的表示中数的表示. 对任意的对任意的x0,1, 令令 x = 0. x1 x2 , 0 xi 9规定在规定在 x 的表示式中不允许在某位后有无数个的表示式中不允许在某位后有无数个1的情况的情况. 设设 f: N0,1是任何函数，列出是任何函数，列出 f 的所有函数值：的所有函数值： f(0) = 0.a1(1)a2(1) f(1) = 0.a1(2

35、)a2(2) f(n 1) = 0.a1(n)a2(n) 令令 y 的表示式为的表示式为0.b1b2, 并且满足并且满足bi ai(i), i=1,2, 那么那么y 0,1, 且且y与上面列出的任何函数值都不相等与上面列出的任何函数值都不相等. 这就推出这就推出y ranf, 即即 f 不是满射的不是满射的.广东工业大学计算机学院38(2) 我们将证明任何函数我们将证明任何函数 g:AP(A)都不是满射的都不是满射的. 设设 g:AP(A)是从是从A到到P(A)的函数的函数, 如下构造集合如下构造集合B： B=x| xAx g(x)则则BP(A), 但对任意但对任意xA都有都有 xB x g(

36、x)从而证明了对任意的从而证明了对任意的 xA都有都有 Bg(x). 即即B rang. 注意：根据注意：根据Cantor定理可以知道定理可以知道N P(N)，N 0,1N.Cantor定理的证明定理的证明广东工业大学计算机学院39集合的优势集合的优势定义定义8.9 (1) 设设A, B是集合是集合, 如果存在从如果存在从A到到B的单射函数的单射函数, 就就称称B优势于优势于A, 记作记作A B. 如果如果B不是优势于不是优势于A, 则记作则记作A B.(2) 设设A, B是集合是集合, 若若A B 且且 A B, 则称则称 B 真优势于真优势于A, 记作记作 A B. 如果如果 B 不是真优

37、势于不是真优势于A, 则记作则记作A B. 实例实例 N N, N R, A P(A), R N N R, A P(A), 但但N N定理定理8.8 设设 A, B, C是任意的集合是任意的集合, 则则(1) A A(2) 若若A B且且B A, 则则AB(3) 若若A B且且B C, 则则A C 广东工业大学计算机学院40应用：证明等势应用：证明等势证证 设设x 0,1), 0. x1x2 是是 x 的二进制表示的二进制表示. 规定表示式中不规定表示式中不允许出现连续无数个允许出现连续无数个1. 对于对于x，如下定义，如下定义 f:0,1)0,1N, f(x) = tx, 且且 tx:N0,

38、1, tx(n) = xn+1, n = 0,1,2,例如例如 x = 0.1 0 1 1 0 1 0 0, 则对应于则对应于x 的函数的函数 tx是：是： n 0 1 2 3 4 5 6 7 tx(n) 1 0 1 1 0 1 0 0 tx0,1N, 且对于且对于x,y0,1), xy, 必有必有txty, 即即 f(x)f(y). 这就证明了这就证明了f:0,1)0,1N是单射的是单射的.例例8 证明证明 0,1N0,1).广东工业大学计算机学院41考虑考虑 t0,1N, 其中其中 t(0)=0, t(n)=1, n=1, 2, . 按照按照 f 的定义的定义, 只有只有 x = 0.01

39、1 才能满足才能满足 f(x)=t. 但根据规定但根据规定, 这个数这个数 x 记为记为0.100, 所以根本不存在所以根本不存在 x0,1), 满足满足 f(x)=t.定义函数定义函数 g:0,1N0,1). g的映射法则恰好与的映射法则恰好与 f 相反相反. 即即 t0,1N, t：N0,1, g(t)=0. x1x2, 其中其中xn+1=t(n). 将将0. x1x2 看作数看作数 x 的十进制表示的十进制表示. 这样就避免了形如这样就避免了形如 0.0111和和0.1000.在二进制表示中对应了同一个数的情在二进制表示中对应了同一个数的情况，从而保证了况，从而保证了g的单射性的单射性.

40、根据定理有根据定理有0,1N0,1). 再使用等势的传递性得再使用等势的传递性得0,1NR.构造另一个单射构造另一个单射广东工业大学计算机学院42自然数的集合定义自然数的集合定义 定义定义8.10 设设a为集合为集合, 称称aa为为a的的后继后继, 记作记作a+, 即即 a+=aa.如下定义自然数：如下定义自然数： 0= 1=0+=+ = =0 2=1+= + = =,=0,1 3=2+=,+= ,= 0,1,2 n=0, 1, , n 1 自然数的相等与大小，即对任何自然数自然数的相等与大小，即对任何自然数 n和和m，有有 m=n m n ， mn m n广东工业大学计算机学院43有穷集和无

41、穷集有穷集和无穷集定义定义8.11 (1) 一个集合是一个集合是有穷有穷的当且仅当它与某个自然数等势；的当且仅当它与某个自然数等势；(2) 如果一个集合不是有穷的如果一个集合不是有穷的, 就称作就称作无穷集无穷集.实例：实例：(1) a,b,c是有穷集是有穷集, 因为因为3=0,1,2, 且且 a,b,c0,1,2=3(2) N和和R都是无穷集都是无穷集, 因为没有自然数与因为没有自然数与N和和R等势等势利用自然数的性质可以证明：任何有穷集只与惟一的自然数利用自然数的性质可以证明：任何有穷集只与惟一的自然数等势等势. 广东工业大学计算机学院44集合基数的定义集合基数的定义定义定义8.12(1)

42、 对于有穷集合对于有穷集合A, 称与称与A等势的那个惟一的自然数为等势的那个惟一的自然数为A的的基基数数, 记作记作cardA (也可以记作也可以记作|A|) cardA = n A n (2) 自然数集合自然数集合N的基数记作的基数记作0, 即即 cardN =0(3) 实数集实数集R的基数记作的基数记作, 即即 cardR =广东工业大学计算机学院45基数的相等和大小基数的相等和大小定义定义8.13 设设A, B为集合为集合, 则则(1) cardA=cardB AB(2) cardAcardB A B(3) cardAcardB cardAcardBcardAcardB根据上一节关于势的

43、讨论不难得到：根据上一节关于势的讨论不难得到： card Z = card Q = card NN =0 card P(N) = card 2N = card a,b = card (c,d) = 0 card Acard P(A)其中其中2N = 0,1N广东工业大学计算机学院46基数的大小基数的大小不存在最大的基数不存在最大的基数. 将已知的基数按从小到大的顺序排列就将已知的基数按从小到大的顺序排列就得到：得到： 0, 1, 2, , n, , 0, , 其中：其中： 0, 1, 2, n, 是全体自然数是全体自然数, 是有穷基数是有穷基数. 0, , 是无穷基数是无穷基数, 0是最小的无

44、穷基数是最小的无穷基数, 后面还后面还有更大的基数有更大的基数, 如如cardP(R)等等. 广东工业大学计算机学院47可数集可数集定义定义8.14 设设A为集合为集合, 若若cardA0, 则称则称A为为可数集可数集或或可列集可列集.实例：实例：a,b,c, 5, 整数集整数集Z, 有理数集有理数集Q, NN等都是可数集等都是可数集, 实数集实数集 R不是可数集不是可数集, 与与R等势的集合也不是可数集等势的集合也不是可数集. 对于任何的可数集对于任何的可数集, 它的元素都可以排列成一个有序图形它的元素都可以排列成一个有序图形. 换换句话说句话说, 都可以找到一个都可以找到一个“数遍数遍”集

45、合中全体元素的顺序集合中全体元素的顺序. 可数集的性质：可数集的性质：l 可数集的任何子集都是可数集可数集的任何子集都是可数集.l 两个可数集的并是可数集两个可数集的并是可数集.l 两个可数集的笛卡儿积是可数集两个可数集的笛卡儿积是可数集.l 可数个可数集的笛卡儿积仍是可数集可数个可数集的笛卡儿积仍是可数集.l 无穷集无穷集A的幂集的幂集P(A)不是可数集不是可数集广东工业大学计算机学院48实例实例解解 (1) 由由T=B, A, S, E, L知知 cardT=5(2) 由由B=, 可知可知 cardB=0.(3) 由由|A|=4 可知可知 cardC=cardP(A)=|P(A)|=24=

46、16.例例9 求下列集合的基数求下列集合的基数(1) T=x | x是单词是单词“BASEBALL”中的字母中的字母(2) B=x | xRx2=92x=8(3) C=P(A), A=1, 3, 7, 11广东工业大学计算机学院49例例10 设设A, B为集合为集合, 且且 cardA=0, cardB=n, n是自然数是自然数, n0. 求求card AB.实例实例解解 方法一方法一 构造双射函数构造双射函数由由cardA=0, cardB=n, 可知可知 A, B都是可数集都是可数集. 令令 A=a0,a1,a2, B=b0,b1,b2,bn 1 对任意的对任意的, AB有有 = i=kj

47、=l 定义函数定义函数 f :ABN f()=in+j, i=0,1, j=0,1,n 1易见易见f是是AB到到N的双射函数的双射函数, 所以所以 card AB=card N = 0广东工业大学计算机学院50方法二方法二 直接使用可数集的性质求解直接使用可数集的性质求解. 因为因为 card A=0, card B=n, 所以所以A, B都是可数集都是可数集.根据性质根据性质(3) 可知可知 AB也是可数集也是可数集, 所以所以 card AB0 显然当显然当 B时时, card A card AB, 这就推出这就推出 0 card AB综合上述得到综合上述得到 card AB=0. 实例实

48、例广东工业大学计算机学院51第八章第八章 习题课习题课主要内容主要内容l 函数，函数，从从A到到B的函数的函数 f:AB，BA，函数的像与完全原像，函数的像与完全原像l 函数的性质：单射、满射、双射函数函数的性质：单射、满射、双射函数l 重要函数：恒等函数、常函数、单调函数、集合的特征函重要函数：恒等函数、常函数、单调函数、集合的特征函 数、自然映射数、自然映射l 集合等势的定义与性质集合等势的定义与性质l 集合优势的定义与性质集合优势的定义与性质l 重要的集合等势以及优势的结果重要的集合等势以及优势的结果l 可数集与不可数集可数集与不可数集l 集合基数的定义集合基数的定义广东工业大学计算机学

49、院52基本要求基本要求l 给定给定 f, A, B, 判别判别 f 是否为从是否为从A到到B的函数的函数l 判别函数判别函数 f:AB的性质（单射、满射、双射）的性质（单射、满射、双射）l 熟练计算函数的值、像、复合以及反函数熟练计算函数的值、像、复合以及反函数l 证明函数证明函数 f:AB的性质（单射、满射、双射）的性质（单射、满射、双射）l 给定集合给定集合A, B，构造双射函数，构造双射函数 f:AB l 能够证明两个集合等势能够证明两个集合等势l 能够证明一个集合优势于另一个集合能够证明一个集合优势于另一个集合l 知道什么是可数集与不可数集知道什么是可数集与不可数集l 会求一个简单集合

50、的基数会求一个简单集合的基数广东工业大学计算机学院53练习练习11给定给定A, B 和和 f, 判断是否构成函数判断是否构成函数 f:AB. 如果是如果是, 说明该说明该 函数是否为单射、满射、双射的函数是否为单射、满射、双射的. 并根据要求进行计算并根据要求进行计算.(1) A=1,2,3,4,5, B=6,7,8,9,10, f=,.(2) A,B同同(1), f=,.(3) A,B同同(1), f=,.(4) A=B=R, f(x)=x3(5) A=B=R+, f(x)=x/(x2+1).(6) A=B=RR, f()=, 令令 L=|x,yRy=x+1, 计算计算 f(L).(7) A

51、=NN, B=N, f()=|x2 y2|. 计算计算f(N0), f 1(0)广东工业大学计算机学院54解解答解答(1) 能构成能构成 f:AB, f:AB既不是单射也不是满射既不是单射也不是满射, 因为因为 f(3)=f(5)=9, 且且7 ranf.(2) 不构成不构成 f:AB, 因为因为 f 不是函数不是函数. f 且且f, 与函与函 数定义矛盾数定义矛盾(3) 不构成不构成 f:AB, 因为因为dom f = 1,2,3,4 A(4) 能构成能构成 f:AB, 且且 f:AB是双射的是双射的(5) 能构成能构成 f:AB, f:AB既不是单射的也不是满射的既不是单射的也不是满射的.

52、 因为该因为该 函数在函数在 x=1取极大值取极大值 f(1)=1/2. 函数不是单调的函数不是单调的,且且ranfR+.(6) 能构成能构成 f:AB, 且且 f:AB是双射的是双射的. f(L) = |xR=R 1(7) 能构成能构成 f:AB, f:AB既不是单射的也不是满射的既不是单射的也不是满射的. 因为因为 f()=f()=0, 2 ranf. f(N0) = n2 02|nN = n2|nN f 1(0) = |nN广东工业大学计算机学院551)(, 1, 1)(,)(,0, 10, 1)(4321 xfZxZxxfxxfxxxf练习练习22. 设设 f1, f2, f3, f4

53、 RR，且，且令令Ei 是由是由 fi 导出的等价关系，导出的等价关系，i=1,2,3,4，即，即 xEiy fi(x)=fi(y) (1) 画出偏序集画出偏序集的哈斯图，其中的哈斯图，其中T 是加细关系：是加细关系： T x(x R/Eiy(y R/Ej x y) (2) gi:RR/Ei 是自然映射，求是自然映射，求gi(0), i=1,2,3,4.(3) 对每个对每个i, 说明说明 gi 的性质（单射、满射、双射）的性质（单射、满射、双射）.广东工业大学计算机学院56(1) 哈斯图如下哈斯图如下(2) g1(0) = x | x R x 0, g2(0)=0, g3(0)=Z, g4(0

54、)=R(3) g1, g3, g4是满射的；是满射的；g2是双射的是双射的. 解图1解答解答广东工业大学计算机学院57练习练习33对于以下集合对于以下集合A和和B，构造从，构造从A到到B的双射函数的双射函数 f:AB(1) A=1,2,3，B=a, b, c(2) A=(0,1)，B=(0,2)(3) A=x| x Zx0，B=N (4) A=R，B=R+ 解解 (1) f=, , (2) f:AB, f(x)=2x(3) f:AB, f(x)= x 1(4) f:AB, f(x)=ex 广东工业大学计算机学院584.4.设设 证明证明 f 既是满射的，也是单射的既是满射的，也是单射的. yxyxyxff,),(,RRRR: 2,2vuvuvuvuvuf,)2,2( vuyxvyuxvuyxvuyxvuvuyxyxvufyxf,),(),(证证 任取任取 R R，存在，存在使得使得 练习练习4因此因此 f 是是满射的满射的对于任意的对于任意的 , R R, 有有因此因此