第8章 节 函数 电子科大离散数学内部.ppt

离 散 数 学;第三篇 二元关系;8.0 内容提要;8.1 本章学习要求;8.2函数;例8.2.1;例8.2.1 解;例;例8.2.2;例8.2.2 解;例8.2.3;例8.2.3 解（续）; 函数是一种特殊的关系，它与一般关系比较具备如下差别：;定义8.2.2 设f是从A到B的函数， 对任意x1,x2∈A，如果x1≠x2，有f(x1)≠f(x2)， 则称f为从A到B的单射（不同的x对应不同的y)； 如果ranf＝B，则称f为从A到B的满射； 若f是满射且是单射，则称f为从A到B的双射。 若A＝B，则称f为A上的函数；当A上的函数f是双射时，称f为一个变换。;将定义8.2.2的描述数学化为;例8.2.4;例8.2.4 解;设A，B为有限集合，f是从A到B的函数，则： f是单射的必要条件为|A|≤|B|； f是满射的必要条件为|B|≤|A|； f是双射的必要条件为|A|＝|B|。;定理8.2.1;定理8.2.1（续）;例8.2.5;例8.2.5 解;例8.2.5 解;例8.2.6;典型(自然)映射。设R是集合A上的一个等价关系，g：A→A/R称为A对商集A/R的典型(自然)映射，其定义为g(a)＝[a]R，a∈A. 证明：典型映射是一个满射。;设A,≤是偏序集，对任意a∈A,令： f(a)＝{x|(x∈A)∧(x≤a)} 证明：f是一个从A到P(A)的一个单射函数，并且f保持A,≤与P(A),?的偏序关系，即：对任意a,b∈A，若a≤b，则f(a)?f(b)。;2)f是单射。对任意a,b∈A，a≠b 若a,b存在偏序关系，不妨设a≤b(或b≤a)，由于“≤”是反对称的，所以b≤a(或a≤b)，从而 b?f(a)＝{x|(x∈A)∧x≤a}（或a?f(b))， 而“≤”是自反的，所以b≤b(或a≤a),即b∈f(b)(或a∈f(a)),所以f(a)≠f(b)。 ;例8.2.8(续);设A＝{1,2,3,…,n}，f是A到A的满射，并且具有性质：f(xi)＝yi，i＝1,2,3,…,k，k≤n，xi,yi∈A。求f的个数。;8.2.3常用函数;定义8.2.3（续）;例8.2.10;8.2.5函数的应用;（2）证明f是双射。 1)证f是映射。显然，f是P(An)到Bn的映射。 2)证f是单射。任取S1,S2∈P(An)，S1≠S2， 则存在元素aj(1≤j≤n),使得aj∈S1,aj?S2或aj∈S2,aj?S1。 从而f(S1)＝b1b2b3…bn中必有bj＝1，f(S2)＝c1c2c3…cn必有cj＝0或f(S1)＝b1b2b3…bn中必有bj＝0，f(S2)＝c1c2c3…cn必有cj＝1。所以f(S1)≠f(S2)，即f是单射。;例8.2.11(续);例8.2.12 Hash函数 ;解;例8.2.13;例8.2.14;8.3函数的运算;注意;例8.3.1;例8.3.2;（2）((f?g)?h)(x)＝h((f?g)(x))＝h(g(f(x))) ＝h(g(2x))＝h((2x+1)2)＝(2x+1)2/2； (f?(g???h))(x)=(g?h)(f(x))＝h(g(f(x))) ＝h(g(2x))＝h((2x+1)2)＝(2x+1)2/2 ； （3）f?h(x)＝h(f(x))＝h(2x)＝x； h?f(x)＝f(h(x))＝f(x/2)＝x；;设f和g分别是A到B和从B到C的函数，则： 如f,g是满射，则f?g也是从A到C满射； 如f,g是单射，则f?g也是从A到C单射； 如f,g是双射，则f?g也是从A到C双射。;2) 对任意a1,a2∈A，a1≠a2，由于f是单射，所以f(a1)≠f(a2)。 令b1＝f(a1)，b2＝f(a2)，由于g是单射,所以g(b1)≠g(b2)，即g(f(a1))≠g(f(a2))。 从而有f?g(a1)≠f?g(a2)， 所以f?g是单射。 3)是1)、2)的直接结果。■;定理8.3.2;8.3.2函数的逆运算;例8.3.3;解;定理8.3.3 ;定理8.3.4;8.3.4函数运算的应用;8.3.4函数运算的应用;例8.3.5;例8.3.5 解;8.4置换函数;;例8.4.1;例8.4.2;8.4.3置换函数的应用;8.5 本章总结 ;习题类型;习题;Thank You !