电子科技大学离散数学第8章 函数.pptVIP

* 例8.4.2 试求出例8.4.1中的置换P2,P4的逆置换，并计算P2,P4的复合运算以及它们的逆的复合运算。 解 根据已知有P2={1,1,2,3,3,2}， P4={1,2,2,3,3,1}。 （1）P2-1={1,1,2,3,3,2}， P4-1={1,3,2,1,3,2}； （2）P2oP4={1,2,2,1,3,3}， P2-1oP4-1={1,3,2,2,3,1}。 * 8.4.3置换函数的应用 例8.4.3 等边三角形如图8.4.1所示。求经过旋转和翻转能使之重合的所有置换函数。 A 1 3 2 图8.4.1 解 能使三角形重合的置换有6个： （1）三角形绕中心A反时针旋转120°、240°和360°对应的置换分别为: （2）绕中线1A,2A,3A翻转对应的置换分别为： * 8.5 本章总结 函数的概念。注意函数与关系的区别和联系； 单射、满射和双射函数的概念，数学描述形式； 特殊函数的基本概念； 函数的复合运算，逆运算及运算性质。 * 习题类型 基本概念题：涉及函数、单射、满射、双射的基本概念； 判断题：涉及函数及函数类型的判定； 计算题：涉及函数做复合运算，求逆运算； 证明题：涉及单射函数、满射函数或者双射函数。 * 习题 第250-251页 6. 8. 10. 13. * * 8.2.3常用函数 定义8.2.3 （1）如果A=B，且对任意x∈A，都有f(x)=x，则称f为A上的恒等函数，记为IA。 （2）如果?b∈B，且对任意x∈A，都有f(x)=b，则称f为常值函数。 （3）设A是全集U={u1,u2,…,un}的一个子集，则子集A的特征函数定义为从U到{0,1}的一个函数，且 * 定义8.2.3（续） （4）对有理数x，f(x)为大于等于x的最小的整数，则称f(x)为上取整函数(强取整函数)，记为f(x)= ； （5）对有理数x，f(x)为小于等于x的最大的整数，则称f(x)为下取整函数(弱取整函数)，记为f(x)= ； * 例8.2.10 设A=B=R(实数集)。试指出下列函数的类型。 （1）f1={x,x|x∈R}； （2）f2={x,a|x∈R,a∈R}； （3）f3={x, |x∈R}； （4）f4={x, |x∈R}。 解（1）f1是恒等函数， （2）f2是常值函数， （3）f3是上取整函数， （4）f4是下取整函数。 * 8.2.5函数的应用 解 P(An)到Bn可以按照如下的方式建立关系：对任意S∈P(An)，令 f(S)＝b1b2b3…bn， 其中： 例8.2.11 设An＝{a1,a2,a3,…,an}是n个元素的有限集，Bn＝{b1 b2b3…bn|bi∈{0,1}}，试建立P(An)到Bn的一个双射。 * （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.11(续) 3) 证f是满射。任取二进制数b1b2b3…bn∈Bn，对每一个二进制数b1b2b3…bn，建立对应的集合S?An，S＝{ai|若bi＝1}(即若bi＝1，令ai∈S，否则ai?S)，则S∈P(An)，从而f(S)＝b1b2b3…bn，故f是满射。 由1)、2)和3)知，f是双射。 例如A3={a1,a2,a3}，则有： Ф├→000, {a1}├→110, {a2}├→010, {a3}├→001, {a1,a2}├→110, {a1,a3}├→101, {a2,a3}├→011, {a1,a2,a3}├→111。 * 例8.2.12 Hash函数 假设在计算机内存中有编号从0到10的存储单元，见图8.2.2。图8.2.2表示了在初始时刻全为空的单元中，按次序15、558、32、132、102和5存入后的情形。现希望能在这些存储单元中存储任意的非负整数并能进行检索，试用Hash函数方法完成257的存储和558的检索。 132 0 1 2 3 4 5 6 7 8 9 10 0