离散数学第八章.ppt

《离散数学第八章.ppt》由会员分享，可在线阅读，更多相关《离散数学第八章.ppt（60页珍藏版）》请在一课资料网上搜索。

1、1 第八章函数 主要内容函数的定义与性质函数定义函数性质函数运算函数的逆函数的合成双射函数与集合的基数 2 8 1函数的定义与性质 主要内容函数定义与相关概念函数定义函数相等从A到B的函数f A BBA函数的像与完全原像函数的性质单射 满射 双射函数的定义与实例构造双射函数某些重要的函数 3 函数定义 定义8 1设F为二元关系 若 x domF都存在唯一的y ranF使xFy成立 则称F为函数对于函数F 如果有xFy 则记作y F x 并称y为F在x的值 例F1 F2 F1是函数 F2不是函数 定义8 2设F G为函数 则 F G F G G F如果两个函数F和G相等 一定满足下面两个条件 1

2、 domF domG 2 x domF 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 A B 例f N N f x 2x是从N到N的函数 g N N g x 2也是从N到N的函数 定义8 4所有从A到B的函数的集合记作BA 符号化表示为 BA f f A B A m B n 且m n 0 BA nmA 则BA B A 且B 则BA A 5 实例 例1设A 1 2 3 B a b 求BA 解 BA f0 f1 f7 其中

3、 f0 f1 f2 f3 f4 f5 f6 f7 6 函数的像和完全原像 定义8 5设函数f A B A1 A B1 B 1 A1在f下的像f A1 f x x A1 函数的像f A 2 B1在f下的完全原像f 1 B1 x x A f x B1 注意 函数值与像的区别 函数值f x B 像f A1 B一般说来f 1 f A1 A1 但是A1 f 1 f A1 例设f N N 且令A 0 1 B 2 那么有 f A f 0 1 f 0 f 1 0 2 f 1 B f 1 2 1 4 7 函数的性质 定义8 6设f A B 1 若ranf B 则称f A B是满射的 2 若 y ranf都存在唯

4、一的x A使得f x y 则称f A B是单射的 3 若f A B既是满射又是单射的 则称f A B是双射的 例2判断下面函数是否为单射 满射 双射的 为什么 1 f R R f x x2 2x 1 2 f Z R f x lnx Z 为正整数集 3 f R Z f x x 4 f R R f x 2x 1 5 f R R f x x2 1 x 其中R 为正实数集 8 例题解答 解 1 f R R f x x2 2x 1在x 1取得极大值0 既不是单射也不是满射的 2 f Z R f x lnx是单调上升的 是单射的 但不满射 ranf ln1 ln2 3 f R Z f x x 是满射的 但

5、不是单射的 例如f 1 5 f 1 2 1 4 f R R f x 2x 1是满射 单射 双射的 因为它是单调函数并且ranf R 5 f R R f x x2 1 x有极小值f 1 2 该函数既不是单射的也不是满射的 9 实例 例3对于给定的集合A和B构造双射函数f A B 1 A P 1 2 3 B 0 1 1 2 3 2 A 0 1 B 1 4 1 2 3 A Z B N 4 B 1 1 10 解答 1 A 1 2 3 1 2 1 3 2 3 1 2 3 B f0 f1 f7 其中f0 f1 f2 f3 f4 f5 f6 f7 令f A B f f0 f 1 f1 f 2 f2 f 3

6、f3 f 1 2 f4 f 1 3 f5 f 2 3 f6 f 1 2 3 f7 11 2 令f 0 1 1 4 1 2 f x x 1 4 4 令f 2 3 2 1 1 f x sinx 解答 3 将Z中元素以下列顺序排列并与N中元素对应 Z 0 1 1 2 2 3 3 N 0 1 23 4 5 6 这种对应所表示的函数是 12 某些重要函数 定义8 7 1 设f A B 如果存在c B使得对所有的x A都有f x c 则称f A B是常函数 2 称A上的恒等关系IA为A上的恒等函数 对所有的x A都有IA x x 3 设 为偏序集 f A B 如果对任意的x1 x2 A x1 x2 就有f

7、 x1 f x2 则称f为单调递增的 如果对任意的x1 x2 A x1 x2 就有f x1 f x2 则称f为严格单调递增的 类似的也可以定义单调递减和严格单调递减的函数 13 4 设A为集合 对于任意的A A A 的特征函数 A A 0 1 定义为 A a 1 a A A a 0 a A A 5 设R是A上的等价关系 令 g A A R g a a a A称g是从A到商集A R的自然映射 某些重要函数 14 实例 例4 1 偏序集 R 为包含关系 为一般的小于等于关系 令f P a b 0 1 f f a f b 0 f a b 1 f是单调递增的 但不是严格单调递增的 3 不同的等价关系确

8、定不同的自然映射 恒等关系确定的自然映射是双射 其他自然映射一般来说只是满射 例如A 1 2 3 R IAg A A R g 1 g 2 1 2 g 3 3 2 A的每一个子集A 都对应于一个特征函数 不同的子集对应于不同的特征函数 例如A a b c 则有 a b 15 8 2函数的复合与反函数 主要内容复合函数基本定理函数的复合运算与函数性质反函数的存在条件反函数的性质 16 复合函数基本定理 定理8 1设F G是函数 则F G也是函数 且满足 1 dom F G x x domF F x domG 2 x dom F G 有F G x G F x 证先证明F G是函数 因为F G是关系

9、所以F G也是关系 若对某个x dom F G 有xF Gy1和xF Gy2 则 F G F G t1 F G t2 F G t1 t2 t1 t2 G G F为函数 y1 y2 G为函数 所以F G为函数 17 证明 任取x x dom F G t y F G t x domF t F x t domG x x x domF F x domG 任取x x domF F x domG F G F G x dom F G F G x G F x 所以 1 和 2 得证 18 推论 推论1设F G H为函数 则 F G H和F G H 都是函数 且 F G H F G H 证由上述定理和运算满足结

10、合律得证 推论2设f A B g B C 则f g A C 且 x A都有f g x g f x 证由上述定理知f g是函数 且dom f g x x domf f x domg x x A f x B Aran f g rang C因此f g A C 且 x A有f g x g f x 19 函数复合与函数性质 定理8 2设f A B g B C 1 如果f A B g B C是满射的 则f g A C也是满射的 2 如果f A B g B C是单射的 则f g A C也是单射的 3 如果f A B g B C是双射的 则f g A C也是双射的 证 1 任取c C 由g B C的满射性 b

11、 B使得g b c 对于这个b 由f A B的满射性 a A使得f a b 由合成定理有f g a g f a g b c从而证明了f g A C是满射的 20 证明 2 假设存在x1 x2 A使得 f g x1 f g x2 由合成定理有g f x1 g f x2 因为g B C是单射的 故f x1 f x2 又由于f A B是单射的 所以x1 x2 从而证明f g A C是单射的 3 由 1 和 2 得证 注意 定理逆命题不为真 即如果f g A C是单射 或满射 双射 的 不一定有f A B和g B C都是单射 或满射 双射 的 定理8 3设f A B 则f f IB IA f 证明略

12、21 实例 考虑集合A a1 a2 a3 B b1 b2 b3 b4 C c1 c2 c3 令 f g f g 那么f A B和f g A C是单射的 但g B C不是单射的 考虑集合A a1 a2 a3 B b1 b2 b3 C c1 c2 令 f g f g 那么g B C和f g A C是满射的 但f A B不是满射的 22 反函数 反函数存在的条件 1 任给函数F 它的逆F 1不一定是函数 只是一个二元关系 2 任给单射函数f A B 则f 1是函数 且是从ranf到A的双射函数 但不一定是从B到A的双射函数 3 对于双射函数f A B f 1 B A是从B到A的双射函数 定理8 4设

13、f A B是双射的 则f 1 B A也是双射的 证明思路 先证明f 1 B A 即f 1是函数 且domf 1 B ranf 1 A 再证明f 1 B A的双射性质 23 证明 证因为f是函数 所以f 1是关系 且domf 1 ranf B ranf 1 domf A对于任意的x B domf 1 假设有y1 y2 A使得 f 1 f 1成立 则由逆的定义有 f f根据f的单射性可得y1 y2 从而证明了f 1是函数 且是满射的 若存在x1 x2 B使得f 1 x1 f 1 x2 y 从而有 f 1 f 1 f f x1 x2对于双射函数f A B 称f 1 B A是它的反函数 24 反函数的

14、性质 定理8 5 1 设f A B是双射的 则f 1 f IB f f 1 IA 2 对于双射函数f A A 有f 1 f f f 1 IA证明思路 根据定理可知f 1 B A也是双射的 由合成基本定理可知f 1 f B B f f 1 A A 且它们都是恒等函数 例5设 求f g g f 如果f和g存在反函数 求出它们的反函数 25 解 f R R不是双射的 不存在反函数 g R R是双射的 它的反函数是 g 1 R R g 1 x x 2 求解 26 8 3双射函数与集合的基数 主要内容集合的等势及其性质重要的等势或不等势的结果集合的优势及其性质集合的基数可数集 27 则f是Z到N的双射函

15、数 从而证明了Z N 集合的等势 集合等势的实例例6 1 Z N 定义8 8设A B是集合 如果存在着从A到B的双射函数 就称A和B是等势的 记作A B 如果A不与B等势 则记作A B 28 集合等势的实例 N N N N N N N N中所有的元素排成有序图形 29 2 1 5 1 1 4 3 1 18 2 1 10 3 1 11 0 1 0 1 1 1 2 2 1 2 3 3 2 17 2 2 3 2 12 0 2 1 2 2 2 3 6 1 3 7 3 3 2 3 9 3 3 0 3 1 3 8 2 4 1 4 15 3 4 16 2 4 3 4 13 0 4 1 4 14 PLAY N

16、 Q 双射函数f N Q 其中f n 是 n 下方的有理数 集合等势的实例 N Q 30 对任何a b R a b 0 1 a b 双射函数f 0 1 a b f x b a x a类似地可以证明 对任何a b R a b 有 0 1 a b 4 0 1 R 其中实数区间 0 1 x x R 0 x 1 令 5 0 1 0 1 其中 0 1 和 0 1 分别为实数开区间和闭区间 令f 0 1 0 1 实数集合的等势 31 实例 例7设A为任意集合 则P A 0 1 A 证如下构造从P A 到 0 1 A的函数 f P A 0 1 A f A A A P A 其中 A 是集合A 的特征函数 易证

17、f是单射的 对于任意的g 0 1 A 那么有g A 0 1 令B x x A g x 1 则B A 且 B g 即 B P A f B g 从而证明了f是满射的 由等势定义得P A 0 1 A 32 等势的性质 定理8 6设A B C是任意集合 1 A A 2 若A B 则B A 3 若A B B C 则A C 证明思路 利用等势的等义 1 IA是从A到A的双射 2 若f A B是双射 则f 1 B A是从B到A的双射 3 若f A B g B C是双射 则f g A C是从A到C的双射 33 有关势的重要结果 等势结果N Z Q N N任何实数区间都与实数集合R等势 不等势的结果 定理8 7

18、 康托定理 1 N R 2 对任意集合A都有A P A 证明思路 1 只需证明任何函数f N 0 1 都不是满射的 任取函数f N 0 1 列出f的所有函数值 然后构造一个 0 1 区间的小数b 使得b与所有的函数值都不相等 2 任取函数f A P A 构造B P A 使得B与f的任何函数值都不等 34 Cantor定理的证明 证 1 规定 0 1 中数的表示 对任意的x 0 1 令 x 0 x1x2 0 xi 9规定在x的表示式中不允许在某位后有无数个1的情况 设f N 0 1 是任何函数 列出f的所有函数值 f 0 0 a1 1 a2 1 f 1 0 a1 2 a2 2 f n 1 0 a

19、1 n a2 n 令y的表示式为0 b1b2 并且满足bi ai i i 1 2 那么y 0 1 且y与上面列出的任何函数值都不相等 这就推出y ranf 即f不是满射的 35 2 我们将证明任何函数g A P A 都不是满射的 设g A P A 是从A到P A 的函数 如下构造集合B B x x A x g x 则B P A 但对任意x A都有x B x g x 从而证明了对任意的x A都有B g x 即B rang 注意 根据Cantor定理可以知道N P N N 0 1 N Cantor定理的证明 36 集合的优势 定义8 9 1 设A B是集合 如果存在从A到B的单射函数 就称B优势于

20、A 记作A B 如果B不是优势于A 则记作A B 2 设A B是集合 若A B且A B 则称B真优势于A 记作A B 如果B不是真优势于A 则记作A B 实例N N N R A P A R NN R A P A 但N N 定理8 8设A B C是任意的集合 则 1 A A 2 若A B且B A 则A B 3 若A B且B C 则A C 37 应用 证明等势 证设x 0 1 0 x1x2 是x的二进制表示 规定表示式中不允许出现连续无数个1 对于x 如下定义f 0 1 0 1 N f x tx 且tx N 0 1 tx n xn 1 n 0 1 2 例如x 0 10110100 则对应于x的函数

21、tx是 n 01234567 tx n 10110100 tx 0 1 N 且对于x y 0 1 x y 必有tx ty 即f x f y 这就证明了f 0 1 0 1 N是单射的 例8证明 0 1 N 0 1 38 考虑t 0 1 N 其中t 0 0 t n 1 n 1 2 按照f的定义 只有x 0 011 才能满足f x t 但根据规定 这个数x记为0 100 所以根本不存在x 0 1 满足f x t 定义函数g 0 1 N 0 1 g的映射法则恰好与f相反 即 t 0 1 N t N 0 1 g t 0 x1x2 其中xn 1 t n 将0 x1x2 看作数x的十进制表示 这样就避免了形

22、如0 0111 和0 1000 在二进制表示中对应了同一个数的情况 从而保证了g的单射性 根据定理有 0 1 N 0 1 再使用等势的传递性得 0 1 N R 构造另一个单射 39 自然数的集合定义 定义8 10设a为集合 称a a 为a的后继 记作a 即a a a 如下定义自然数 0 1 0 0 2 1 0 1 3 2 0 1 2 n 0 1 n 1 自然数的相等与大小 即对任何自然数n和m 有m n m n m n m n 40 有穷集和无穷集 定义8 11 1 一个集合是有穷的当且仅当它与某个自然数等势 2 如果一个集合不是有穷的 就称作无穷集 实例 1 a b c 是有穷集 因为3 0

23、 1 2 且 a b c 0 1 2 3 2 N和R都是无穷集 因为没有自然数与N和R等势利用自然数的性质可以证明 任何有穷集只与惟一的自然数等势 41 集合基数的定义 定义8 12 1 对于有穷集合A 称与A等势的那个惟一的自然数为A的基数 记作cardA 也可以记作 A cardA n A n 2 自然数集合N的基数记作 0 即 cardN 0 3 实数集R的基数记作 即 cardR 42 基数的相等和大小 定义8 13设A B为集合 则 1 cardA cardB A B 2 cardA cardB A B 3 cardA cardB cardA cardB cardA cardB 根据

24、上一节关于势的讨论不难得到 cardZ cardQ cardN N 0cardP N card2N card a b card c d 0 cardA cardP A 其中2N 0 1 N 43 基数的大小 不存在最大的基数 将已知的基数按从小到大的顺序排列就得到 0 1 2 n 0 其中 0 1 2 n 是全体自然数 是有穷基数 0 是无穷基数 0是最小的无穷基数 后面还有更大的基数 如cardP R 等 44 可数集 定义8 14设A为集合 若cardA 0 则称A为可数集或可列集 实例 a b c 5 整数集Z 有理数集Q N N等都是可数集 实数集R不是可数集 与R等势的集合也不是可数

25、集 对于任何的可数集 它的元素都可以排列成一个有序图形 换句话说 都可以找到一个 数遍 集合中全体元素的顺序 可数集的性质 可数集的任何子集都是可数集 两个可数集的并是可数集 两个可数集的笛卡儿积是可数集 可数个可数集的笛卡儿积仍是可数集 无穷集A的幂集P A 不是可数集 45 实例 解 1 由T B A S E L 知cardT 5 2 由B 可知cardB 0 3 由 A 4可知cardC cardP A P A 24 16 例9求下列集合的基数 1 T x x是单词 BASEBALL 中的字母 2 B x x R x2 9 2x 8 3 C P A A 1 3 7 11 46 例10设A

26、 B为集合 且cardA 0 cardB n n是自然数 n 0 求cardA B 实例 解方法一构造双射函数由cardA 0 cardB n 可知A B都是可数集 令A a0 a1 a2 B b0 b1 b2 bn 1 对任意的 A B有 i k j l定义函数 f A B N f in j i 0 1 j 0 1 n 1易见f是A B到N的双射函数 所以 cardA B cardN 0 47 方法二直接使用可数集的性质求解 因为cardA 0 cardB n 所以A B都是可数集 根据性质 3 可知A B也是可数集 所以cardA B 0显然当B 时 cardA cardA B 这就推出

27、0 cardA B综合上述得到cardA B 0 实例 48 第八章习题课 主要内容函数 从A到B的函数f A B BA 函数的像与完全原像函数的性质 单射 满射 双射函数重要函数 恒等函数 常函数 单调函数 集合的特征函数 自然映射集合等势的定义与性质集合优势的定义与性质重要的集合等势以及优势的结果可数集与不可数集集合基数的定义 49 基本要求 给定f A B 判别f是否为从A到B的函数判别函数f A B的性质 单射 满射 双射 熟练计算函数的值 像 复合以及反函数证明函数f A B的性质 单射 满射 双射 给定集合A B 构造双射函数f A B能够证明两个集合等势能够证明一个集合优势于另一

28、个集合知道什么是可数集与不可数集会求一个简单集合的基数 50 练习1 1 给定A B和f 判断是否构成函数f A B 如果是 说明该函数是否为单射 满射 双射的 并根据要求进行计算 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 R R f 令L x y R y x 1 计算f L 7 A N N B N f x2 y2 计算f N 0 f 1 0 51 解 解答 1 能构成f A B f A B既不是单射也不是满射 因为f 3 f 5 9 且7 ranf 2

29、不构成f A B 因为f不是函数 f且 f 与函数定义矛盾 3 不构成f A B 因为domf 1 2 3 4 A 4 能构成f A B 且f A B是双射的 5 能构成f A B f A B既不是单射的也不是满射的 因为该函数在x 1取极大值f 1 1 2 函数不是单调的 且ranf R 6 能构成f A B 且f A B是双射的 f L x R R 1 7 能构成f A B f A B既不是单射的也不是满射的 因为f f 0 2 ranf f N 0 n2 02 n N n2 n N f 1 0 n N 52 练习2 2 设f1 f2 f3 f4 RR 且 令Ei是由fi导出的等价关系 i

30、 1 2 3 4 即xEiy fi x fi y 1 画出偏序集的哈斯图 其中T是加细关系 T x x R Ei y y R Ej x y 2 gi R R Ei是自然映射 求gi 0 i 1 2 3 4 3 对每个i 说明gi的性质 单射 满射 双射 53 1 哈斯图如下 2 g1 0 x x R x 0 g2 0 0 g3 0 Z g4 0 R 3 g1 g3 g4是满射的 g2是双射的 解 图1 解答 54 练习3 3 对于以下集合A和B 构造从A到B的双射函数f A B 1 A 1 2 3 B a b c 2 A 0 1 B 0 2 3 A x x Z x 0 B N 4 A R B

31、R 解 1 f 2 f A B f x 2x 3 f A B f x x 1 4 f A B f x ex 55 4 设证明f既是满射的 也是单射的 证任取 R R 存在 使得 练习4 因此f是满射的对于任意的 R R 有 因此f是单射的 56 证明方法 1 证明f A B是满射的方法 任取y B 找到x 即给出x的表示 或者证明存在x A 使得f x y 2 证明f A B是单射的方法方法一 x1 x2 A f x1 f x2 x1 x2推理前提推理过程推理结论方法二 x1 x2 A x1 x2 f x1 f x2 推理前提推理过程推理结论3 证明f A B不是满射的方法 找到y B y r

32、anf4 证明f A B不是单射的方法 找到x1 x2 A x1 x2 且f x1 f x2 57 5 设A B为二集合 证明 如果A B 则P A P B 练习5 证因为A B 存在双射函数f A B 反函数f 1 B A构造函数g P A P B g T f T T A f T 是T在函数f的像 证明g的满射性 对于任何S B 存在f 1 S A 且g f 1 S f f 1 S S证明g的单射性 g T1 g T2 f T1 f T2 f 1 f T1 f 1 f T2 IA T1 IA T2 T1 T2综合上述得到P A P B 58 证明集合A与B等势的方法 方法一 直接构造从A到B

33、的双射 即定义一个从A到B的函数f A B 证明f的满射性 证明f的单射性方法二 利用定理8 8 构造两个单射f A B和g B A 即定义函数f和g 证明f和g的单射性方法三 利用等势的传递性方法四 直接计算A与B的基数 得到cardA cardB 注意 以上方法中最重要的是方法一 证明集合A与自然数集合N等势的通常方法是 找到一个 数遍 A中元素的顺序 59 练习6 6 已知A n7 n N B n109 n N 求下列各题 1 CardA 2 CardB 3 card A B 4 card A B 解 1 构造双射函数f N A f n n7 因此cardA 0 2 构造双射函数g N

34、A g n n109 因此cardB 0 3 可数集的并仍旧是可数集 因此card A B 0 但是card A B cardA 0 从而得到card A B 0 4 因为7与109互素 card A B n7 109 n N 与 1 类似得到card A B 0 60 7 已知cardA 0 且cardB cardA 求card A B 练习7 解由A B A得到card A B cardA 即card A B 0由cardB cardA可知B为有穷集 即存在自然数n使得cardB n 假设card A B 0 那么存在自然数m 使得card A B m从而得到cardA card A B B n m 与cardA 0矛盾 因此 card A B 0