东南大学离散数学课件.ppt

1、第八章函数，8.1映射(函数)的定义和性质8.2函数的复合和逆函数8.3全射函数和集合的基数，函数是二项关系中特殊的类。 本节讨论离散函数，这可以把一个穷集合变成另一个穷集合。 例如：在计算机上执行的程序可以看作是函数的转换： (自变量)输入-计算机-输出(函数值)主要讨论：函数定义、特殊函数及其性质、函数的运算。 利用函数的概念，特别是全单射函数，研究无限集合的基数问题。8.1函数的定义和性质、8.1函数的定义和性质、定义：将x和y设为任意两个集合，f是来自XY的关系，如果每个xX都存在唯一的yY，则将f称为函数(映射)，记为f:XY。 在f:XY中，如果x被称为自变量(原始图像)，与x相对

2、应的y被称为通过f获得的点(值，映射) (image )。y=f (x )表示，并且y被称为函数f在x点处的值。 8.1函数的定义和性质，x的各要素有定义，与某f值域对应的函数f的定义域，其值f(x )有时标记为唯一的，Rf，有时也把集合y称为f的共同域，8.1函数的定义和性质，例：判定下面的关系是否是函数假设8.1函数而非函数的定义和性质，例如，X=Y=R (实数)、值是唯一的，不是函数，而是不满足值的唯一性的8.1函数的定义和性质，定义：给定函数f:AB与g:CD，FGFGG F是A=C，b 、8.1函数的定义和性质、64子集只有8个拟合函数的定义，这八个函数是、例如： X=a、b、c、y

3、=0、1，假设8.1函数的定义和性质，|X|=m、|Y|=n， 函数f: XY都有m个偶数的集合(即偶数个=定义域的基数) XYY的所有函数的个数，8.1函数的定义和性质，X Y中其他函数的个数和子集的个数的关系，即两个集合之间能够构成的函数的个数远远大于能够构成的二项关系的数量8.1函数的定义和性质，被赋予的函数f: XY，如果值域即y的各要素一定是x中某个要素的映射，就把f称为从x到y的满射(onto或者surjection )。 满射函数必须给出(1)|X|Y|例，8.1函数的定义和性质，f: XY，有时把f称为从x到y的单射。 单射函数是：8.1函数的定义和性质，(或称为“1-1映射”

4、)全射一定是(1) (值域) (2) (定义域)|X|=|Y|例如：在类全体的集合中，设X=编号，Y=名称，f: XY是单射(编号和名称的关系)，与8.2函数的复合相反定义一函数可见：定义域不是y而是y的子集不满足函数定义：即，值是唯一的二元关系，如果存在不是函数、8.2函数的复合和逆函数、一个函数的逆函数，则该函数一定是双射的，反射、反射的反关系不满足函数的定义作为单反射，称为f的逆函数(inverse function )。 假设、8.2函数的复合和逆函数，f、g都是函数，则fg(x)=g(f(x ) )也是函数，满足dom(fg)=x|xdomff(x)domg xdom(fg )的fg

5、(x)=g(f(x ) )这两个函数的复合是一个函数。 函数的复合也称为函数f和g的积。 例如求出sin(ln x )、ln x，求出sin(ln x )、8.2函数的复合和逆函数。 例如： x=1，2，3，Y=p，q，Z=a，b f: XY=g:YZ=，函数的复合(积)运算不满足交换规则。求f g和各g f，8.2函数的复合和逆函数，定理：函数的合成运算是可耦合的，即如果f、g、h都是函数，函数也是二元关系，二元关系的复合满足结律，函数的复合(积)也满足结律。 设8.2函数的复合和反函数，定理： g: XY，f:YZ为复合函数，则(1)f和g都满射，满射；(2)f和g都是单射，则是单射；(3

6、)f和g都是双射，则是双射。、8.2函数的复合和逆函数，例如、是负的整数集合，定义了两个全射f和g，f(x)=- x=、g(x)=x-1=、是一个全射。 另外，8.2函数的复合和逆函数提供f: XY，并且如果对于所有和的某个常数y，f(x)=y，那么f被称为常数函数。例如，8.2函数的复合和逆函数，对于给定的全部，即，被称为恒等函数。 例如，8.2函数的复合和逆函数，定理：对于任意函数f: YX，在其中，如果是的恒等函数，YY的恒等函数，则是、x、x、y、y、8.2函数的复合和逆函数，定理：如果在函数f: YX中有逆函数f-1，然后证明、8.2函数的复合和反函数，定理： f是单射函数，证明：任

7、何一个，定理： g: XY和f:YZ，f和g是双射，*归纳法和自然数(1)，集合的归纳定义的第一部分：基础。 表示一部分基本要素属于集合的情况。 第二部分：总结。 展示从基本要素创建新元素的方法。 第三部分：极小性。 指出这个集合的边界。 例如：集合s的谓语记述定义为Sxx0y(x=3y )，论域定义为整数I。 s如果是(1) (基础)3S (2) (归纳) xS和yS，则可以将x y S (3) (极小性) s定义为满足基础和归纳的最小集合。 将归纳法和自然数(2)、给定的集合a、A=AA、a称为a的后继集合。 利用后续集合的概念定义自然数集合0，1，2，设A=的话，a的后续集合在如上述那样

8、求出0的后续集合中，n=0，1，2， 能够写成归纳法和自然数(3)的自然数集n，如(1) (基础) N (2) (归纳) n，如nN (3) (极小性) SN，s满足(1)(2)时，SN，8.3集合的基数，对有限集合：集合中的不同元素的个数来定义。 关于无限集？ 无限集的基数都一样吗？ 为了比较两个集合的“大小”，确定有限集合和无限集合的概念，并导入自然数集合。 8.3集合的基数：定义：把a，b作为集合，如果在a和b之间存在1-1映射，则a和b的基数相同，a和b也称为对等(等势，等浓)|A|=|B|。 例如，在集合中，奇整数和偶数的集合是等位的f :AB、f(x)=(x 1)、f(1)=2、f

9、(1)=2、8.3集合的基数，例如，n和偶数的集合e是等位。 证明：此外，对于任何函数，如果f(n)=2n，则有一对一映射，NE。 例如，对于有限集合，该定义也适用： a=1、2、3、4、5、B=a、b、c、d、e，定义一函数f=f是单反射函数，AB(|A|=|B|，8.3集合的基数，定义： a、b是任意两个集合。 (1)a的基数为b的基数以下，标记为AB，a到b为单射，或b到a为满射。 (2)a的基数比b的基数小，标记为AB，如果是AB的话。 说明： a和b的某子集有1-1的对应关系的话为AB； a和b的某个子集有1-1的对应关系，a和b没有1-1的对应关系的话AB。 显然，上述定义在有限集

10、合的要素数中有大小的扩展，8.3集合的基数，如果是从集合0、1、2、n-1到集合a的全反射函数，则a是无限集合，如果集合a不是无限集合，则是无限集合。这个定义也可以说基数的自然数的任意集合是穷的集合，相反是无限集合。8.3集合的基数、定理：自然数集合n是无限集合。 证明：当两个集合可以建立全单射函数时，两个集合元素一对一对应，这两个集合具有相同的基数。8.3集合的基数，定义：自然数集合和等势的任意集合称为可数集合(或可数无限集合)，它们的基数等于、 |A|=|B|=|C|=|D|=、8.3集合的基数、元素数非有限的可数集合称为可数无限集合，对于可数无限集合，其元素编号： a1、a2、an， 关于可数集有以下命题：定理：可数集的子集还是可数的两个可数集是可数集，两个可数集的笛卡尔积是可数集，可数的还是可数的，8.3集的基数，定理： A1，A1 证明：在不失去普遍性的情况下，如果设为A1，A2，An，则全部是数不清的集合，A1=a11，a12，a1n，A2=a21，a22，a2n，A3=a31，a32，a3n，An=an1，an2，ann， 作为8.3集合的基数，规定对任意的ai j，按各元素ij之和的大小进行排序的同一者按I的大小进行排序，如果当前排序