离散数学PPT电子教案-第08章_函数.ppt

离 散 数 学,2023年2月10日星期五,2023/2/10,第三篇 二元关系,第8章 函数,2023/2/10,8.0 内容提要,2023/2/10,8.1 本章学习要求,2023/2/10,8.2 函数,函数也叫映射、变换或对应。函数是数学的一个基本概念。这里将高等数学中函数的概念推广，将函数看作是一种特殊的二元关系。函数的概念在日常生活和计算机科学中非常重要。如各种高级程序语言中使用了大量的函数。实际上，计算机的任何输出都可看成是某些输入的函数。,2023/2/10,8.2.1函数的定义,定义8.2.1 设f是集合A到B的关系，如果对每个xA，都存在惟一的yB，使得f，则称关系f为A到B的函数(或映射、变换)，记为f:AB。A为函数f的定义域，记为domf=A；f(A)为函数f的值域，记为ranf。函数定义的示意图见图8.2.1。,特殊二元关系,2023/2/10,结论,(1)f y=f(x)；(2)f f y=z；(3)|f|=|A|；(4)f(x)表示一个变值，f代表一个集合，因此ff(x).(5)如果关系f具备下列两种情况之一，那么f就不是函数：存在元素aA，在B中没有象；存在元素aA，有两个及两个以上的象。,2023/2/10,例8.2.1,设A=1,2,3,4,B=a,b,c,d，试判断下列关系哪些是函数。如果是函数，请写出它的值域。（1）f1=,；（2）f2=,；（3）f3=,；（4）f4=,。答案:ranf1=a,c,d；ranf3=a,b,c,d；,2023/2/10,例8.2.3,设A=a,b,B=1,2，请分别写出A到B的不同关系和不同函数。解 因为|A|=2,|B|=2，所以|AB|=|A|B|=4，即AB=,，此时从A到B的不同的关系有24=16个(略)。从A到B的不同的函数仅有2*2=4个。分别如下：f1=,f2=,f3=,f4=,。一般地,从A到B的不同的函数有|B|A|个。,2023/2/10,练习:P236 1,1.下列关系中哪些能构成函数?(1)|(x,yN)(x+y=10);(2)|(x,yR)(y=x2);(3)|(x,yR)(y2=x).答:(2)能构成函数.,2023/2/10,定义8.2.2 设f是从A到B的函数，对任意x1,x2A，如果x1x2，有f(x1)f(x2)，则称f为从A到B的单射（不同的x对应不同的y)；如果ranfB，则称f为从A到B的满射；若f是满射且是单射，则称f为从A到B的双射。若AB，则称f为A上的函数；当A上的函数f是双射时，称f为一个变换。,8.2.2函数的类型,2023/2/10,将定义8.2.2的描述数学化为,（1）f:AB是单射 当且仅当 对x1,x2A，若x1x2，则f(x1)f(x2)；（2）f:AB是满射当且仅当 对yB，一定存在xB，使得f(x)=y；（3）f:AB是双射当且仅当 f既是单射，又是满射；（4）f:AB是变换当且仅当 f是双射且A=B。,2023/2/10,例8.2.4,确定下列函数的类型。（1）设A=1,2,3,4,5,B=a,b,c,d。f:AB定义为：f=,；（2）设A=1,2,3,B=a,b,c,d。f:AB定义为：f=,；（3）设A=1,2,3,B=1,2,3。f:AB定义为:f=,；,2023/2/10,设A，B为有限集合，f是从A到B的函数，则：f是单射的必要条件为|A|B|；f是满射的必要条件为|B|A|；f是双射的必要条件为|A|B|。,结论,A B,2023/2/10,定理8.2.1 设A,B是有限集合,且|A|=|B|.,若f是A到B的函数,则f是单射当且仅当f是满射。证明必要性()：设f是单射,则f是A到f(A)的双射,因此|A|=|f(A)|。由|f(A)|=|B|且f(A)B,得f(A)=B,故f是A到B的满射。充分性()：设f是满射。假设f不是单射,则存在x1,x2A,x1x2,有 f(x1)=f(x2).由于f是A到B的满射,所以f也是A-x1到B的满射,故|A-x1|B|，即|A|-1|B|，这与|A|=|B|矛盾。因此f是A到B的单射。,2023/2/10,例8.2.6,设A=B=R(实数集)。试判断下列函数的类型。（1）f1=|xR；（2）f2=|xR；（3）f3=|xR；解（1）f1仅是一般函数；（2）f2是双射函数；（3）f3是单射函数。,2023/2/10,设R是集合A上的一个等价关系,g：AA/R称为A对商集A/R的典型映射(自然映射),其定义为g(a)aR，aA.显然,自然映射是一个满射。,典型(自然)映射,2023/2/10,设是偏序集，对任意aA,令：f(a)x|(xA)(xa)证明：f:AP(A)是一个单射函数,并且 f 保持与的偏序关系,即：对任意a,bA,若ab,则f(a)f(b)。,例8.2.8,证明：1)f是映射。任取aA，由于f(a)x|(xA)(xa)A，所以f(a)P(A)，即f是从A到P(A)的映射。,2023/2/10,2)f是单射。对任意a,bA,ab,由于“”是反对称的，所以,ba 或 ab.不妨设ab.,则有 af(b)x|(xA)xb,而“”是自反的，所以aa，即af(a)，所以,f(a)f(b)。,例8.2.8(续),3)对任意a,bA，若ab，则：任取yf(a),有 yab,根据“”的传递性,有 yb，从而yf(b).所以f(a)f(b)。,2023/2/10,8.2.3常用函数,定义8.2.3（1）如果A=B，且对xA，都有f(x)=x，则称f为A上的恒等函数,记为IA。（2）如果bB，且对xA，都有f(x)=b，则称f为常值函数。（3）设A是全集U=u1,u2,un的一个子集，则子集A的特征函数定义为从U到0,1的一个函数，且,2023/2/10,定义8.2.3（续）,（4）对有理数x，f(x)为大于等于x的最小的整数，则称f(x)为上取整函数，记为f(x)=；（5）对有理数x，f(x)为小于等于x的最大的整数，则称f(x)为下取整函数，记为f(x)=；（6）如果f(x)是集合A到集合B=0,1上的函数，则称f(x)为布尔函数。,2023/2/10,例8.2.10,设A=B=R(实数集)。试指出下列函数的类型。（1）f1=|xR;（2）f2=|xR,aR;（3）f3=|xR；（4）f4=|xR。解（1）f1是恒等函数;（2）f2是常值函数;（3）f3是上取整函数;（4）f4是下取整函数。,2023/2/10,8.3 函数的运算,8.3.1函数的复合运算定义8.3.1 设 f:AB,g:BC 是两个函数，则 f与g 的复合运算 fg|xAzC(y)(yBxfyygz)是从A到C的函数，记为fg:AC.称 fg 为函数f与g的复合函数。此时 对任意xA,有 fog(x)=g(f(x)。,2023/2/10,例8.3.1,设A=1,2,3,4,5,B=a,b,c,d,C=1,2,3,4,5,函数f:AB，g:BC定义如下：f=,；g=,。求fog。解 fog=,2023/2/10,例8.3.2,设f:RR,g:RR,h:RR，满足 f(x)=2x,g(x)(x+1)2,h(x)x/2。计算：（1）fg，gf；（2）(fg)h，f(gh)；（3）fh，hf。,解(1)fg(x)g(f(x)g(2x)(2x+1)2；gf(x)f(g(x)f(x+1)2)2(x+1)2；(2)(fg)h)(x)(2x+1)2/2(f(gh)(x)(3)fh(x)h(f(x)h(2x)x；hf(x)f(h(x)f(x/2)x；,2023/2/10,设 f:AB 和 g:BC 都是函数，那么：(1)如 f,g 是满射，则 fg 是从A到C满射；(2)如 f,g 是单射，则 fg 是从A到C单射；(3)如 f,g 是双射，则 fg 是从A到C双射。,定理8.3.1,2023/2/10,定理8.3.2(前单,后满),设f和g分别是从A到B和从B到C的函数，则（1）如果 fog 是从A到C的满射，则g是从B到C的满射；（2）如果 fog 是从A到C的单射，则f是从A到B的单射；（3）如果 fog 是从A到C的双射，则f是从A到B的单射，g是从B到C的满射。,2023/2/10,8.3.2 函数的逆运算,定义8.3.2 设f:AB的函数。如果f-1|(xA)(yB)(f)是从B到A的函数，则称f-1：BA的逆函数。由定义可知，逆函数f-1存在当且仅当f是双射。,2023/2/10,例8.3.3 试求出下列函数的逆函数。,(1)设A=1,2,3,B=1,2,3。f1:AB定义为 f1=,；(2)f2=,(3)f3=|xR。答案:(1)f1-1=,；(2)f2-1=,；(3)f3-1=|xR。,2023/2/10,定理8.3.3和定理8.3.4,定理8.3.3 设 f 是A到B的双射函数，则：f-1fIB|bB；ff-1IA|aA；IAffIBf。定理8.3.4 若f是A到B的双射，则f的逆函数 f-1也是B到A的双射。,2023/2/10,8.4置换函数,8.4.1 基本概念定义8.4.1 设A=a1,a2,an是有限集合。从A到A的双射函数称为A上的置换或排列，记为P:AA，n称为置换的阶。,2023/2/10,n元集上置换的表示,n阶置换P:AA常表示为：,第一行是集合A的元素按顺序列出，第二行是A中元素对应的函数值。序列P(a1),P(a2),P(an)恰好是A中元素的重排。,2023/2/10,例8.4.1 设A=1,2,3,请写出A上的所有置换.,解 A上的所有置换P如下：,2023/2/10,例8.4.2,试求出例8.4.1中的置换P2,P4的逆置换，并计算P2,P4的复合运算以及它们的逆的复合运算。解 根据已知有 P2=,P4=,。（1）P2-1=,，P4-1=,；（2）P2oP4=,，P2-1oP4-1=,。,2023/2/10,8.5 本章总结,（1）函数的概念。注意函数与关系的区别和联系；（2）单射、满射和双射函数的概念，数学描述形式；（3）特殊函数的基本概念；（4）函数的复合运算，逆运算及运算性质；（5）置换的表示。,2023/2/10,练习:P237 9,设f,g,h都是自然集N上的函数,对任意xN,f(x)=x+1,g(x)=2x.求 fg,gf,ff.答:fg(x)=2(x+1);gf(x)=2x+1;ff(x)=x+2.,2023/2/10,习题类型,（1）基本概念题：涉及函数、单射、满射、双射的基本概念；（2）判断题：涉及函数及函数类型的判定；（3）计算题：涉及函数做复合运算，求逆运算；（4）证明题：涉及单射函数、满射函数或者双射函数。,2023/2/10,作业,第237页 9,14 复习:第6-8章,