计算机数学基础PPT课件.ppt

清华大学现代远程教育 专升本课程 计算机数学基础 集合代数关系与函数 清华大学现代远程教育 专升本课程 函数 函数 单值的二元关系设F为二元关系 如果 x domF y ranF 使得xFy成立 则称F为函数 如果 F 则记F x y 并称y是F的函数值 存在唯一的 清华大学现代远程教育 专升本课程 函数 设A B是集合 如果函数f满足以下条件 a domf Ab ranf B则称f是从A到B的偏函数 记为f A B 其中A是f的前域 B是陪域 清华大学现代远程教育 专升本课程 函数 设A B是集合 如果函数f满足以下条件 a domf Ab ranf B则称是从A到B的全函数 简称从A到B的函数 记为f A B 清华大学现代远程教育 专升本课程 函数 显然一个从A到B的函数 是满足下列性质的二元关系 1 每个元素x A 都必须有一个y A与之成为二元关系中一个元素即函数的定义域就是A本身 而不是A的一个真子集 清华大学现代远程教育 专升本课程 函数 2 任何一个x A 都只能有唯一一个y A与之成为二元关系中一个元素 即 f f y z 3 如果任何一个y A 都只有唯一一个x A与之成为二元关系中一个元素 则函数称为单根的 清华大学现代远程教育 专升本课程 函数 对一个从A到B的函数来说 其值域可能是B的真子集 如下术语都是函数的同义词 在不同的场合可交替使用 变换 映射 对应 运算 清华大学现代远程教育 专升本课程 函数 将所有从A到B的函数构成的集合记为BABA f f A B 如果A B分别为n m元集合 则BA的元素个数为mn 如果A B至少有一个是 而从A到B的函数存在 则 B 不存在从A 到 的函数 清华大学现代远程教育 专升本课程 函数性质 设函数f A B 1 若ranf B 则称f是满射的 2 若对任意的y ranf 只存在唯一的x使得f x y 则称f是单射的 或一对一的 3 若f既是满射的 又是单射的 则称f是双射的 或一一对应的 清华大学现代远程教育 专升本课程 函数性质 为使得从A到B的函数具有某种性质 A B的元素个数需要满足一定的条件 对于有限集合 我们有1 A B 从A到B才能存在单射函数2 A B 从A到B才能存在满射函数3 A B 从A到B才能存在双射函数 清华大学现代远程教育 专升本课程 函数性质 其中1 也称为鸽巢原理 抽屉原则 其通俗说法是如果m只鸽子 物体 放入n个鸽巢 盒子 里 且m n则某个鸽巢 盒子 里一定有两个或更多的鸽子 物体 清华大学现代远程教育 专升本课程 函数性质 例某校某个班有49人 其中年龄最大的是20岁 最小的17岁 则其中必有两个学生是同年同月生 清华大学现代远程教育 专升本课程 常见的函数 常数函数 f A B 如果存在y B 使得所有的x A都有f x y 则f称为常数 常值 函数恒等函数 A上的恒等关系IA称为恒等函数 它是双射的 清华大学现代远程教育 专升本课程 常见的函数 单调增加函数 f R R称为单调增加 如果对于任意的x1 x2 如果x1 x2 则f x1 f x2 严格单调增加如果对于任意的x1 x2 如果x1 x2 则f x1 f x2 清华大学现代远程教育 专升本课程 常见的函数 单调递减函数 f R R称为单调递减 如果对于任意的x1 x2 如果x1f x2 清华大学现代远程教育 专升本课程 函数的合成 函数是关系的特例 因此函数也有合成的概念 设f X Y和g Y Z是两个函数 则合成关系f g是f和g的合成函数 清华大学现代远程教育 专升本课程 函数的合成 1 dom f g x x domf f x domg 因为i dom f g domf Ii ranf domg 否则f g是空函数 清华大学现代远程教育 专升本课程 函数的合成 2 x dom f g 有f g x g f x 设f X Y和g Y Z则有f g X Z 且 x X 有f g x g f x 清华大学现代远程教育 专升本课程 函数的合成 函数的合成满足结合律 f g h f g h 函数的幂定义 i 1 f0 x I x 2 fn 1 x f fn x Ii 如果f2 f 则称f是等幂函数 清华大学现代远程教育 专升本课程 函数合成的性质 设f X Y和g Y Z 1 如果f g是满射 单射 双射 函数 则f g是满射 单射 双射 函数 2a 如果f g是满射函数 则g是满射函数 2b 如果f g是单射函数 则f是单射函数 清华大学现代远程教育 专升本课程 函数合成的性质 设f X Y和g Y Z 2c 如果f g是双射函数 则f是单射函数 g是满射函数与恒等函数的合成设f X Y 则f IX f f IY 清华大学现代远程教育 专升本课程 逆关系与函数 不能直接用逆关系来定义反函数 因为关系是函数 逆关系不一定是函数 1 逆关系F 1是函数 关系F是单根的 关系f是函数 逆关系f 1是单根的 因此 逆关系F 1是函数 并没有限定F是函数 而只是说明关系F是单根的 所以如果F是函数 则F一定是单射函数 清华大学现代远程教育 专升本课程 逆关系与函数 2 如果f X Y是单射函数 则逆关系f 1是函数 且 x domF X 有f 1 f x x y ranf 有f f 1 y y注意f 1不一定是从Y到X的函数 清华大学现代远程教育 专升本课程 反函数 如果函数f是双射函数 则f的逆关系是f的反函数 记为f 1 如果函数f存在反函数f 1 则称f是可逆的 1 仅当函数f是双射的 才定义反函数 2 f X Y 则f 1 Y X 也是双射的 3 函数f X Y是双射的 则反函数f 1 Y X 也是双射的 清华大学现代远程教育 专升本课程 反函数 4 如果函数f X Y的逆关系f 1是从Y到X的函数 则f是双射的 5 如果函数f X Y 是可逆的 则f f 1 IX f 1 f IY 6 设函数f X Y g Y X g f 1当且仅当f g IX g f IY 清华大学现代远程教育 专升本课程 反函数 左逆和右逆对于函数f X Y 如果存在g Y Z1 使得g f IY 则称g是f的左逆2 使得f g IX 则称g是f的右逆左逆和右逆可能没有 也可能有多个 清华大学现代远程教育 专升本课程 反函数 设函数f X Y X 则f有一个右逆 f是单射的 f有一个左逆 f是满射的 f有一个左逆且有一个右逆 f是双射的 左逆与右逆相等 清华大学现代远程教育 专升本课程 特殊函数 特征函数 设全集为U 对于任意的A UA的特征函数 A A 0 1 定义为 清华大学现代远程教育 专升本课程 函数表示 为了描述特征函数的性质 首先规定如下的函数表示方法设X是任意集合 Y R f和g都是从X到Y的函数 则 1 f g表示对于每个x X 都有f x g x 2 f g表示对于每个x X 都有 f g x f x g x 清华大学现代远程教育 专升本课程 函数表示 3 f g表示对于每个x X 都有 f g x f x g x 4 f g表示对于每个x X 都有 f g x f x g x 0表示从U到 0 1 的函数 x A 1表示从U到 0 1 的函数 x A 清华大学现代远程教育 专升本课程 特征函数 特征函数的特性1 A 1 A2 A B A B3 A B A B A B4 A B A A B 清华大学现代远程教育 专升本课程 特征函数 特征函数的特性5 A A U 0 A 1 6 A 0 A 7 A 1 A U8 A B A B 清华大学现代远程教育 专升本课程 特征函数 特征函数的特性9 A B A B10 A B A A B11 A A A 清华大学现代远程教育 专升本课程 变换和置换函数 非空集合A上的函数 即一个从A到A的函数称为A的一个变换 如果是双射函数则称为A的一个一一变换 相应A上的恒等关系称为恒等变换 清华大学现代远程教育 专升本课程 变换和置换函数 按照函数合成的概念 A上两个变换是可以合成的 合成函数仍然是从A到A的函数 即仍然是一个变换任何一个变换和恒等变换的合成仍为原变换 即 f IA f f IA 清华大学现代远程教育 专升本课程 变换和置换函数 由于只有双射函数才有反函数 所以只有一一变换才有反变换对于A上的一一变换f 有f f 1 f 1 f IA如果A是有限集 则A上的一个一一变换称为A的一个置换 清华大学现代远程教育 专升本课程 变换和置换函数 如果A a1 a2 an 则置换 习惯记作 这是有n个元素的置换 称为n元置换 共有n 个 清华大学现代远程教育 专升本课程 变换和置换函数 以Sn表示这n 个n元置换的集合例A 1 2 3 则S3 1 2 6 其中 清华大学现代远程教育 专升本课程 变换和置换函数 1是恒等置换 清华大学现代远程教育 专升本课程 变换和置换函数 可以计算任何两个置换的合成 如 一般合成运算不满足交换律 通常 清华大学现代远程教育 专升本课程 变换和置换函数 对于n个元素的集合A中的m个不同元素 b1 b2 bm 如果n元置换 定义为 这时称 为m次轮换 m 2时称为对换 简单表示成 b1 b2 bm 清华大学现代远程教育 专升本课程 变换和置换函数 如上述的 等等 其中 2 3 4是对换 清华大学现代远程教育 专升本课程 变换和置换函数 轮换也能进行合成运算 显然一个对换与其自己的合成为恒等置换即 bi bj bi bj IA 清华大学现代远程教育 专升本课程 变换和置换函数 例A 1 2 3 4 5 6 1 4 1 3 5 2 5 6 3 清华大学现代远程教育 专升本课程 变换和置换函数 例A 1 2 3 4 5 6 1 4 1 3 5 2 5 6 3 清华大学现代远程教育 专升本课程 变换和置换函数 一般情况下 轮换的合成不满足交换律 而且也不再是轮换 在什么情况下 轮换的合成还是轮换呢 如果A中元素没有同时出现在其上的两个轮换 这两个轮换称为是不交的 如S6中的轮换 1 2 4 和 3 5 是不交的 清华大学现代远程教育 专升本课程 变换和置换函数 两个不交的轮换的合成运算满足交换律任何一个置换 都可以表示成一系列不交轮换的合成 且表达式是唯一的 任何一个轮换 都可以表示成一系列对换的合成 但表达式不是是唯一的 清华大学现代远程教育 专升本课程 变换和置换函数 例如 显然两个表达式是不同的 清华大学现代远程教育 专升本课程 集合的基数 对于有限集合的基数 有包含排斥定理 现在不局限于有限集 基数定义 集合A的元素数 记为 A实际度量和比较集合大小的根本方法是建立一一对应关系这个方法可推广到任意集合上 清华大学现代远程教育 专升本课程 集合的基数 集合等势的概念A和B为集合如果存在双射函数f A B则称A和B等势或等位记为A B 清华大学现代远程教育 专升本课程 集合的基数 集合N N与N等势 存在双射函数f N N Nf m n m n 2 3m n 2所以集合N N N 清华大学现代远程教育 专升本课程 集合的基数 双射函数f N N N如下图 清华大学现代远程教育 专升本课程 集合的基数 自然数集合N与有理数集合Q等势 函数f N Q f n 就是 n 旁边的有理数 见下图 由于f的双射性 N Q 清华大学现代远程教育 专升本课程 集合的基数 基数比较定义 1 A B 则称A和B的基数相等 即 A B 2 如果存在单射函数f A B则称 A B 3 如果 A B 且 A B则称 A B 清华大学现代远程教育 专升本课程 集合的基数 基数比较