离散数学第五章 函数与基数

第五章函数Function函数在数学、应用数学等许多领域，尤其计算机科学领域有着极其重要的作用。

函数的思想、概念和应用无处不在，无时不在。

它主要是研究变量之间的关系和规律。

函数的划分有很多种。

有线性与非线性之分、连续与离散之分。

例如，x12345…y357911…5.1 函数假定A，B是两个非空集合，f : A→B，称f为A到B上的函数，对每个a∈A, 有唯一的f(a)∈B, 记做b = f(a)。

函数也叫映射mappings或变换transformations（错误）a叫做函数f的自变量argument，b被称为因变量，b=f(a)叫做函数的值value，也叫a的像。

例1. A＝{1,2,3,4}, B={a,b,c,d},，则f是一个函数。

也可以简单记为，f={(1,a), (2,a), (3,d), (4,c)}另外,g={(1,a), (1,b), (2,a), (4,c)}因为对于1来说，1∈A, 不是唯一的f(1)∈B与之相对应,f(1)=a,并且f(1)=b, 因此g就不是一个函数。

例2．f：Z→Z，f(a)=f是函数。

例3．恒等函数1A(a)=a是函数。

正如，我们在第四章里表述的，函数f : A→B，b=f(a), 是一个特殊的二元关系，我们知道，由函数f可以确定一个关系，简单地，可以表示为(a,b)∈，或 ab。

关系的特征函数为或者简记为因此，这样一来，我们以前所讨论的有关集合或关系的运算和性质对于函数来说，就可以完全适用。

例如，f：A→B, g：A→B,函数的复合设f：A→B，g：B→C，是函数，则g◦f：A→C，是函数。

g◦f（a）＝g(f(a))例4．函数的复合设f，g都是整数函数，f(a)=a+1, g(b)=2b.则g◦f (a)=2(a +1) 是整数集到偶数集的函数。

f◦g(a)=2a＋1也是整数集到奇数集的函数。

特殊函数Special Type of Functions设f是从A到B的一个函数，如果Dom(f)=A，则称f是处处有定义everywhere defined；如果 Ran(f)=B，则称f是满射；如果对于集合A中两个不同的元素a和b，有f(a)≠f(b), 则称f是单射，即a≠b f(a)≠f(b), 或f(a)=f(b) a=b；例5. A＝{1,2,3,4}, B={a,b,c,d}, f={(1,a), (2,a), (3,d), (4,c)}f是一个函数，但是f既不是单射，也不是满射。

一个十分重要的例子。
2020/3/14
计算机科学与技术学院
12
三、函数的合成运算
定义 考虑g：A→B，f：B→C是两个函数，则合成 关系f•g是从A到C的函数，记为 f•g：A→C，
称为函数g与f的合成函数。
显然，对任意x∈A，有 f•g(x)＝f(g(x))。
2020/3/14
计算机科学与技术学院
2020/3/14
计算机科学与技术学院
16
例
例1 设f：R→R,满足： 1）f＝{<x,x2>|x∈R}； 2）f＝{<x,x+1>|x∈R}。求f-1。
解 1）对任意x∈R，有f(x)＝x2与之对应，所以 f不是单射函数，即f非双射函数，因此f的逆函 数不存在。 2）因f是双射函数，所以f-1存在，且有： f-1＝{<x,x-1>|x∈R}。
计算机科学与技术学院
5
例2
设A＝{a,b}，B＝{1,2}，A×B＝{<a,1>,<a,2>,<b,1>,<b,2>}，
此时从A到B的不同的关系有24＝16个。分别如下：
R0＝Φ R1＝{<a,1>} R2＝{<a,2>} R3＝{<b,1>}；
R4＝{<b,2>}；R5＝{<a,1>,<b,1>} R6＝{<a,1>,<b,2>}
2020/3/14
计算机科学与技术学院
10
例2
设An＝{a1,a2,a3,…,an}是n个元素的有限集， Bn＝{b1b2b3…bn|bi∈{0,1}}，对An的每一个子 集S(即对任意S(An)),令

g=f∩(CB)
则称g是f到C的缩小，记为f|c，即g为C到B 的函数：
g:CB
g(x)=f(x)
或
f|c(x)=f(x)
定义5.1.4 设f:CB，g:AB，且CA，
若g|c=f，则称g是f到A的扩大。
下面讨论由集合A和B，构成这样函数 f:AB会有多少呢？或者说，在AB的所有子 集中，是全部还是部分子集可以定义函数？令 BA表示这些函数的集合，即
定理5.3.1 设f:AB和g:BC是函数，通 过复合运算o，可以得到新的从A到C的函数， 记为gof，即对任意aA，有(gof)(x)=g(f(x))。
注意，函数是一种关系，今用斜体“o”表 示函数复合运算，记为gof，这是“左复合”， 它与关系的“右复合”fog次序正好相反，为区 分它们在同一公式中的出现，用粗体符号表示 关系复合fog，故有gof=fog。
BA={f|f:AB}
设 |A|=m ， |B|=n ， 则 |BA|=nm 。 这 是 因 为 对 每个自变元，它的函数值都有n种取法，故总共 有nm种从A到B的函数。
上面介绍一元函数，下面给出多元函数的 定义。
n 定义5.1.5 设A1,A2,···,An和B为集合，若f:
AiB 为 函 数 ， 则 称 f 为 n 元 函 数 。 在
f={<a,a>|xA} 则称f:AA为A上恒等函数，通常记为IA， 因为恒等关系即是恒等函数。 由定义可知，A上恒等函数IA是双射函数。
定义5.2.6 设A和B为集合，且AB，若函 数A:B{0,1}为
{xA(x)=
1 xA
0 否则
则称xA为集合A的特征函数。
特征函数建立了函数与集合的一一对应关 系。于是，可通过特征函数的计算来研究集合 上的命题。

• 二元运算的性质
1.算律: 设 为S上的二元运算, (1)如果对于任意的x,y∈S,有x y=y x, 则称运算在S上满足交换律.
(2)如果对于任意的x,y,z∈S有 (x y) z=x (y z),则称运算在S上满足结 合律. (3)如果对于任意的x∈S有x x=x,则称 运算在S上满足幂等律.
4.群的性质 (1)群的幂运算规则 设G为群,则G中的幂运算满足： 1) a∈G,(a-1)-1=a. 2) a,b∈G,(ab)-1=b-1a-1. 3) a∈G,anam=an+m,n,m∈Z. 4) a∈G,(an)m=anm,n,m∈Z. 5)若G为交换群,则(ab)n=anbn.
设 和 为S上两个不同的二元运算,
(1)如果对于任意的x,y,z∈S有(x y) z= (x z) (y z)和z (x y)=(z x) (z y),则称 运 算对 运算满足分配律.
(2)如果 和 都可交换,并且对于任意的 x,y∈S有x (x y)=x和x (x y)=x,则称 和 运算满足吸收律.
(5) S为任意集合,则∪、∩、－、 为S 的幂集P(S)上的二元运算,这里∪和∩是初级 并和初级交.
(6) S为集合, SS为S上的所有函数的集合, 则函数的集合运算 为SS上的二元运算.
• 一元运算
1. 定义: 设S为集合,函数f：S→S称为S上的一 个一元运算,简称为一元运算. 2. 例: (1) 求一个数的相反数是整数集合Z,有理数集 合Q和实数集合R上的一元运算. (2) 求一个数的倒数是非零有理数集合Q*,非 零实数集合R*上的一元运算.
3.真子代数 任何代数系统V=<S,f1,f2,…,fk>,其子代数一定 存在. 最大的子代数就是V本身. 如果令V中所有代数常数构成的集合是B,且 B对V中所有的运算都是封闭的,则B就构成 了V的最小的子代数. 这种最大和最小的子代数称为V的平凡的子 代数. 若B是S的真子集,则B构成的子代数称为V的 真子代数.