离散数学左孝凌4.ppt

4 1函数的基本概念 Theconceptoffunction 4 2复合函数与逆函数 CompositionsoffunctionsandInversefunctions 4 1函数的基本概念 Theconceptoffunction 4 1 1函数的基本概念4 1 2特殊函数类 Specialfunctions 4 1 1函数的基本概念 函数概念是最基本的数学概念之一 也是最重要的数学工具 初中数学中函数定义为 对自变量每一确定值都有一确定的值与之对应 的因变量 高中数学中函数又被定义为两集合元素之间的映射 现在 我们要把后一个定义作进一步的深化 用一个特殊关系来具体规定这一映射 称这个特殊关系为函数 因为关系是一个集合 从而又将函数作为集合来研究 离散结构之间的函数关系在计算机科学研究中也已显示出极其重要的意义 我们在讨论函数的一般特征时 总把注意力集中在离散结构之间的函数关系上 但这并不意味着这些讨论不适用于其它函数关系 考虑下面几个由图示表示的集合A到集合B的关系 见图4 1 1 在这 个关系中 后 个关系R3 R4 R5 R6与R1 R2不同 它们都有下面两个特点 1 其定义域为A 2 A中任一元素a对应唯一一个B中的元素b 图4 1 1几个关系的示图 图4 1 1几个关系的示图 图4 1 1几个关系的示图 定义4 1 1设X和Y是任何两个集合 而f是X到Y的一个关系 f X Y 如果对于每一个x X 都有唯一的y Y 使 f 则称f是X到Y的函数 functions 记为f X Y 当X X1 Xn时 称f为n元函数 函数也称映射 mapping 或变换 transformation 换言之 函数是特殊的关系 它满足 1 函数的定义域是X 而不能是X的某个真子集 即dom f X 2 若 x y f x y f 则y y 单值性 图4 1 2 由于函数的第二个特性 人们常把 x y f或xfy这两种关系表示形式 在f为函数时改为y f x 这时称x为自变量 y为函数在x处的值 也称y为x在f作用下的像 imageofxunderf x为y的原像 一个自变量只能有唯一的像 但不同的自变量允许有共同的像 注意 函数的上述表示形式不适用于一般关系 因为一般关系不具有单值性 例1 设A a b B 1 2 3 判断下列集合是否是A到B的函数 F1 a 1 b 2 F2 a 1 b 1 F3 a 1 a 2 F4 a 3 例2 下列关系中哪些能构成函数 1 x y x y N x y 10 2 x y x y N x y 10 3 x y x y R x y 4 x y x y R x y 5 x y x y R x y 对于函数f X Y f的前域dom f X就是函数y f x 的定义域 有时也记为Df f的值域ran f Y 有时也记为Rf 即Rf Y称为f的共域 ran f Rf也称为f的像集合 dom f X Df也称为f的原像集 对于 AX 称f A 为A的像 imageofA 定义为f A 显然 f f x f x x A 定义4 1 2设函数f A B g C D 如果A C B D 且对所有x A和x C 都有f x g x 则称函数f等于函数g 记为f g 如果A C B D 且对每一x A f x g x 则称函数f包含于函数g 记为f g 设X和Y都是有限集合 X m Y n 由于从X到Y任意一个函数f的定义域都是X 每一个f都有m个序偶 象存在性 那么 f f X Y 的基数为nm 即共有nm个X到Y的函数 例3 设A a b B 1 2 3 由A B能生成多少个不同的函数 由B A能生成多少个不同的函数 解 设fi A B i 1 2 9 gi B A i 1 2 8 f1 a 1 b 1 g1 1 a 2 a 3 a f2 a 1 b 2 g2 1 a 2 a 3 b f3 a 1 b 3 g3 1 a 2 b 3 a f4 a 2 b 1 g4 1 a 2 b 3 b f5 a 2 b 2 g5 1 b 2 a 3 a f6 a 2 b 3 g6 1 a 2 a 3 b f7 a 3 b 1 g7 1 b 2 a 3 b f8 a 3 b 2 g8 1 b 2 b 3 b f9 a 3 b 3 定理设 X m Y n 那么 f f X Y 的基数为nm 即共有nm个X到Y的函数 证明设X x1 x2 xm Y y1 y2 yn 那么每一个f X Y由一张如下的表来规定 其中xi1 xi2 xim为取自y1 y2 yn的允许元素重复的排列 这种排列总数为nm个 因此 上述形式的表恰有nm张 恰对应全部nm个X到Y的函数 由于上述缘故 当X Y是有穷集合时 我们以YX记所有X到Y的全体函数的集合 YX f f X Y 则 YX Y X 特别地XX表示X上函数的全体 目前在计算机科学中 也用X Y替代YX 定义4 1 3 4 5设f X Y 1 如果对任意y Y 均有x X 使y f x 即ranf Y 则称f为X到Y的满射函数 surjection 满射函数也称到上映射 2 如果对任意x1 x2 X x1 x2蕴涵f x1 f x2 则称f为X到Y的入射函数 injection 入射函数也称一对一的函数或单射函数 3 如果f既是X到Y的满射 又是X到Y的入射 则称f为X到Y的双射函数 bijection 双射函数也称一一对应 4 1 2特殊函数 图4 1 1几个关系的示图 图4 1 1几个关系的示图 下图说明了这三类函数之间的关系 注意 既非单射又非满射的函数是大量存在的 例1 对于给定的f和集合A 请判断f性质 类型 并求A在f下的像f A 1 f R R f x x A 8 2 f N N N f x x x 1 A 2 5 3 f Z N f x x A 1 2 4 f S R S 0 A 0 7 5 f 0 1 a b a b f x b a x a A 0 1 2 解 1 f是双射 f A f 8 8 2 f是单射 f A f 2 5 2 3 5 6 3 f是满射 f A f 1 2 1 2 4 f是单射 f A f 0 7 1 8 1 5 f是双射 f A f 0 1 2 a a b 2 定理4 1 1令X和Y为有限集 若X和Y的元素个数相同 即 X Y 则有f X Y是入射当且仅当它是一个满射 证明思路 a 先证f X Y是入射 它是一个满射若f是入射 则 X f X 一对一映射源的个数 象的个数 因为 f X Y 由定理条件 X Y 象的个数 Y的元素个数 和f X Y 又因为Y是有限集合 故f X Y f X Y是满射 b 再证f X Y是一个满射 它是入射若f是满射 f X Y 则 X Y f X 又因为X是有限集合 源的个数 象的个数 所以f X Y是入射 此定理不适用于无限集合上的映射 作业4 1 P151 1 4 5 6 4 2 1逆函数 Inversefunction 4 2 2复合函数 Compositionsoffunctions 4 2逆函数和复合函数 考虑函数f A B f的逆关系fc是B到A关系 但fc可能不是函数 一方面 如果f不是单射 则fc不是函数 另一方面 如果f不是满射 则fc也不是函数 因此我们有如下定理 定理4 2 1设f X Y是一个双射函数 则fc为Y到X的双射函数 即有fc Y X 此定理可以分三步证明 4 2 1逆函数 证明 a 先证fc是一个函数 需要证存在性和唯一性 设f x X y Y f x y 和fc f 因f是双射 所以f是满射 即所有的y Y都有x与它对应 这正是fc的存在性 又因f是双射 所以f是入射 即所有的y Y都只有唯一的x与它对应 这正是fc的唯一性 b 二证fc是一个满射又因ranfc domf X fc是满射 c 三证fc是一个单射反设若y1 y2 有fc y1 fc y2 因为fc y1 x1 fc y2 x2 得x1 x2 故f x1 f x2 即y1 f x1 f x2 y2 得出矛盾 假设不成立 定理证毕 定义4 2 1设f X Y是一个双射函数 称Y X的双射函数fC为f的逆函数 记为f 1 今后谈到一个函数的逆函数时 都是指双射的逆函数 由定义知 若f a b 则有f 1 b a 因为函数是一种特殊的关系 所以和关系一样也有复合运算 对于函数的复合我们有下面的定义 4 2 2复合函数 定义4 2 2设函数f X Y g W Z 若f X W 则g f x X z Z y y Y y f x z g y 称g在函数f的左边可复合 定理4 2 2两个函数的复合是一个函数 证明 设g W Z f X Y为左复合 即f X W a 先证象存在性对于任意x X 因为f为函数 故必有唯一的序偶使y f x 成立 而f x f X 即f x W 又因为g是函数 故对于任意的y Y必有唯一的序偶使z g y 成立 根据复合定义 g f 即X中的每个x对应Z中的某个z b 再证象唯一性假定g f中包含序偶和且z1 z2 这样在Y中必存在y1和y2 使得在f中有和 在g中有和 因为f为函数 故y1 y2 于是g中有和 但g为函数 故z1 z2 即每个x只能对应一个唯一的z 满足 g f 由a 和b 知g f是一个函数 定理证毕 我们注意到 x z fg是指有y使 x y f y z g 即y f x z g y g f x 因而fg x g f x 这就是说 当f g为函数时 它们的复合作用于自变量的次序刚好与合成的原始记号的顺序相反 故我们约定把两个函数f和g的复合记为gf 复合函数的图示 例1 设A 1 2 3 4 B 1 2 3 4 5 C 1 2 3 f A B f 1 2 2 1 3 3 4 5 g B C g 1 1 2 2 3 3 4 3 5 2 求g f 解 g f 1 2 2 1 3 3 4 2 用关系图图示g f 其中 表示g f 见图 例2 设f g均为实函数 f x 2x 1 g x x2 1 求f g g f f f g g 解f g x f g x 2 x2 1 1 2x2 3g f x g f x 2x 1 2 1 4x2 4x 2f f x f f x 2 2x 1 1 4x 3g g x g g x x2 1 2 1 x4 2x2 2 定理4 2 3设f X Y g Y Z g f是一个复合函数 则 1 如果f和g是满射的 则g f也是满射的 2 如果f和g是单射的 则g f也是单射 3 如果f和g是双射的 则g f也是双射的 证明 a 设f X Y g Y Z为满射的 令z为Z的任意一个元素 因g是满射 故必有某个元素y Y使得g y z 又因为f是满射 故必有某个元素x X使得f x y 故g f x g f x g y z因此 Rg f Z g f是满射的 b 设令x1 x2为X的元素 假定x1 x2 因为f是入射的 故f x1 f x2 又因为g是入射的 故g f x1 g f x2 于是x1 x2 g f x1 g f x2 因此 g f是入射的 c 因为g和f是双射 故根据a 和b g f为满射和入射的 即g f是双射的 定理证毕 定义4 2 3函数f X Y叫做常函数 如果存在某个y0 Y 对于每个x X都有f x y0 即f X y0 定义4 2 4如果Ix x X 则称函数Ix X X为恒等函数 证明 a f 1 f与Ix的定义域都是X b 因为f是一一对应的函数 故f 1也是一一对应的函数 若f x f x 则f 1 f x x 由a 和b 得f 1 f Ix 故x X f 1 f x f 1 f x x 定理证毕 例题3见P 155页 定理4 2 5如果函数f X Y 有逆函数f 1 Y X 则f 1 f Ix且f f 1 Iy 定理4 2 4设f X Y 则f f Ix Iy f 证明 a 因f X Y是一一对应的函数 故f 1 Y X也是一。