《离散数学 教学课件 ppt 作者 李盘林 第05章》由会员分享，可在线阅读，更多相关《离散数学 教学课件 ppt 作者 李盘林 第05章（42页珍藏版）》请在金锄头文库上搜索。
1、第五章 函 数,5.1 函数基本概念 5.2 函数类型 5.3 函数运算 5.4 基 数,退出,5.1 函数基本概念,函数也常称为映射或变换，其定义如下： 定义5.1.1 设A和B是任意两个集合，且F是从A到B的关系，若对每一个xA，都存在唯一的yB，使F，则称F为从A到B的函数，并记作F:AB。A称为函数F的定义域，即D(F)=A，B称为函数F的陪域，R(F)称为函数F的值域，且R(F)B。有时也用F(A)表示函数F的值域，即,F(A)=R(F)=y|yB(x)(xAy=F(x) 并称F(A)为函数F的像。 对于F:AB来说，若F，则称x为函数的自变元，称y为函数因变元，因为y值依赖于x所取
2、的值，或称y是F在x处的值，或称y为F下x的像。通常把F记作F(x)=y。,从本定义可以看出，从A到B的函数F和一般从A到B的二元关系之不同有以下两点： A的每一元素都必须是F的有序对之第一分量。 若F(x)=y，则函数F在x处的值是唯一的，即 F(x)=yF(x)=zy=z 考虑到习惯用法，以下常常将大写函数符号F改为小写字母f。,定义5.1.2 设f:AB，g:CD，若A=C，B=D，且对每一xA都有f(x)=g(x)，则称函数f和g相等，记为f=g。 本定义表明了，两函数相等，它们必须有相同的定义域、陪域和有序对集合。 有时需要缩小所给函数的定义域，或扩大所给函数的定义域以创建新的函数，
3、为此有下面定义。,定义5.1.3 设f:AB，且CA，若有 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表示这些函数的集合，即 BA=f|f:AB 设|A|=m，|B|=n，则|BA|=nm。这是因为对每个自变元，它的函数值都有n种取法，故总共有nm种从A到B的函数。,上面介绍一元函数，下面给出多元函数的定义
4、。 定义5.1.5 设A1,A2,An和B为集合，若f: AiB为函数，则称f 为n元函数。在上的值用f(x1,x2,xn)表示。 一元函数中概念对n元函数几乎完全适用，在这里不多讨论了。,5.2 函数类型,根据函数具有的不同性质，可以将函数分成不同的类型。本节将定义这些函数，并给出相应的术语。,定义5.2.1 设f:AB是函数，若R(f)=B，或对任意bB，存在aA，使得f(a)=b，或形式表为： (y)(yB(x)(xAf(x)=y) 则称f:AB是满射函数，或称函数f:AB是满射的。 本定义表明了，在函数f的作用下，B中每个元素b，都至少是A中某元素a的像，因此，若A和B是有穷集合，存在
5、满射函数f:AB，则|A|B|。,定义5.2.2 设f:AB是函数，对任意的a，bA，且ab，都有f(a)f(b)，或形式表为 (x)(y)(x,yAxyf(x)f(y) 则称f:AB是单射函数（或一对一函数），或称函数f:AB是单射的，或入射的。 本定义揭示了，A中不同的元素，其在B中像也是不同的。于是，若A的B是有穷集合，存在单射函数f:AB，则|A|B|。,定义5.2.3 设f:AB是函数，若f既是满射又是单射，则称f:AB是双射函数（或一一对应），或称函数f:AB是双射的。 该定义说明了，B中的每个元素b是且仅是A中某个元素a的像。因此，若A和B是有穷集合，存在双射函数f:AB，则|A
6、|=|B|。,定义5.2.4 设f:AB是函数，若存在bB，使对任意aA有f(a)=b，即f(A)=b，则称f:AB为常值函数。,定义5.2.5 设f:AA是函数，若对任意aA，有f(a)=a，亦即 f=|xA 则称f:AA为A上恒等函数，通常记为IA，因为恒等关系即是恒等函数。 由定义可知，A上恒等函数IA是双射函数。,定义5.2.6 设A和B为集合，且AB，若函数A:B0,1为 1 xA xA(x)= 0 否则 则称xA为集合A的特征函数。,特征函数建立了函数与集合的一一对应关系。于是，可通过特征函数的计算来研究集合上的命题。 定理5.2.1 设A和B是全集合U的任意两个子集。对任意xU，
7、则下列关系式成立。 A(x)=0A= A(x)=1A=U, A(x)B(x)AB A(x)=B(x)A=B A(x)=1-A(x) AB(x)=xA(x)*xB(x) AB(x)=A(x)+B(x)-AB(x) A-B(x)=AB(x)=A(x)-AB(x) 其中+，-，*，为通常的算术运算+，-，和。,定义5.2.7 设和为全序集，函数f:AB。对于任意a,bA. 若ab，有f(a)f(b)，则称f为单调递增函数。 若ab，有f(a)f(b)，则称f为单调递减函数。, 若ab，且ab，有f(a)f(b)，则称f为严格单调递减函数。 显然，严格单调递增函数是单调递增函数，严格单调递减函数是单调
8、递减函数。,定义5.2.8 设R是非空集合A上的等价关系，且函数f:AA/R，f(a)=aR，aA，则称f是从A到商集A/R的自然映射。 自然映射在代数结构中有重要的应用。 定义5.2.9 设p:AA为函数，若p是双射，则称p为A上的置换。 置换在群论中作为一节进行讨论，有着重要的应用。,5.3 函数运算,函数是一种特殊关系，对关系可以进行运算，自然对函数也需要讨论运算问题，即如何由已知函数得到新的函数。,1函数复合 利用两个具有一定性质的已知函数通过复合运算可以得到新的函数。 定理5.3.1 设f:AB和g:BC是函数，通过复合运算o，可以得到新的从A到C的函数，记为gof，即对任意aA，有
9、(gof)(x)=g(f(x)。,注意，函数是一种关系，今用斜体“o”表示函数复合运算，记为gof，这是“左复合”，它与关系的“右复合”fog次序正好相反，为区分它们在同一公式中的出现，用粗体符号表示关系复合fog，故有gof=fog。,推论1 若f,g,h都是函数，则(fog)oh=fo(goh)。 本推论表明，函数复合运算是可结合的。 若对于集合A，f:AA，则函数f能同自身复合成任意次。f的n次复合定义为： f 0(x)=x f n+1(x)=f(fn(x)，nN。,定理5.3.2 设f:AB，g:BC 若f:AB，g:BC都是满射，则gof:AC也是满射。 若f:AB，g:BC都是单射
10、，则gof:AC也是单射。 若f:AB，g:BC都是双射，则gof:AC也是双射。,定理5.3.3 若f:AB是函数，则f=foIA=IBof。 本定理揭示了，恒等函数在复合函数运算中的特殊性质，特别地，对于f:AA，有foIA= IAof=f。,2函数逆运算 给定关系R，其逆关系是存在，但对已知一函数，它作为关系其逆是存在，但未必是函数。例如，A=a,b,c，B=1,2,3，f=,是函数，而f-1=,却不是从B到A的函数。但若f:AB是双射，则f-1便是从B到A的函数。 定理5.3.4 若f:AB是双射，则f-1:BA也是双射。,定义5.3.1 设f:AB是双射函数，称 f -1:BA是f的
11、逆函数，习惯上常称f-1为f的反函数。 定理5.3.5 设f:AB是双射函数，则 f -1of=IA，fof-1=IB 定理5.3.6 若f:AB是双射，则(f-1)-1=f。,5.4 基 数,1基数定义 首先选取一个“标准集合”Nn=0,1,2,n-1，称它为N的截段n；再用双射函数为工具，给出集合基数的定义如下：,定义5.4.1 设A是集合，若f:NnA为双射函数，则称集合A是有限的，A的基数是n，记为|A|=n，或card A=n。若集合A不是有限的，则称A是无穷的。 本定义表明了，对于有限集合A，可以用“数”数的方式来确定集合A的基数。 定理5.4.1 自然数集合N是无穷的。 为了确定
12、某些无穷集合的基数，选取第二个“标准集合”N来度量这些集合。,定义5.4.2 设A是集合，若f:NA为双射函数，则称A的基数是0，记为|A|=0。 显然，存在从N到N的双射函数，故|N|=0，0读作“阿列夫零”。符号0是康托引入的。 若f:NnA是双射函数，则示意A的元素是可“数”的，但“数”的过程可能不会终止，这导致了如下定义：,定义5.4.3 设A是集合，若f:NnA是双射函数，则称集合A是可数的；若|A|=0，则称A是可数无穷的；若A是不可数的，则称A是不可数的或不可数无穷的。 可以证明下面一个很有用的定理：,定理5.4.2 若集合A1,A2,A3,都是可数的，则 Ai 是可数的。 本定
13、理表明了，可数集合的可数个并是可数的。其证明略去了。 在上述基数定义中，是使用两个“标准集合”Nn和N以及双射函数（或一一对应），引入了集合基数的概念。这种方式可以把基数简单地看作对集合指派一个符号，指派原则是：与Nn构成双射或一一对应的集合，指派它的基数是n，与N构成双射或一一对应的集合，指派它的基数为0。指派空集的基数为0。,2基数比较 在有了集合基数的基础上，可以建立相等关系和次序关系，进行基数比较和基数运算，这里仅讨论前者。 定义5.4.4 设A和B为任意集合。 若有一个从A到B的双射函数，则称A和B有相同基数（或称A与B是等势），记为|A|=|B|（或AB）。,若有一个从A到B的单射
14、函数，则称A的基数小于等于B的基数，记为|A|B|。 若有一个从A到B的单射函数，但不存在双射函数，则称A的基数小于B的基数，记为|A|B|。,由于在复合运算下，双射函数是封闭的，双射函数的逆函数（即常说反函数）是双射函数，因此等势关系有以下性质： 定理5.4.3 等势是任何集合族上的等价关系。 综上可见，等势关系是个等价关系。,从上面定义及定理可知： 等势是集合族上的等价关系，它把集合族划分成等价类，在同一等价类中的集合具有相同的基数。因此可以说：基数是在等势关系下集合的等价类的特征。或者说：基数是在等势关系下集合的等价类的名称。这实际上就是基数的一种定义。例如，3是等价类a,b,c,p,q
15、,r,1,2,3,的名称（或特征）。0是自然数集合N所属等价类的名称。,要证明一个集合A有基数，只需选取基数为的任意集合B，证明从A到B或从B到A存在一个双射函数。选取集合B的原则是使证明尽可能容易。 上述定义中选用符号和，是因为它们具有这些符号的通常性质。然而，要证明这些性质是冗长和复杂的。下面将不加证明地引入说明这些性质的两个定理。第一个定理称为三歧性定律。第二定理表明：是反对称的。,定理5.4.4 （Zermelo）设A和B是任意两个集合，则下述情况恰有一个成立： |A|B| |B|A| |A|=|B|,定理5.4.5 （Cantor-Schroder-Bernstein）设A和B是任意两个集合，若|A|B|和|B|A|，则|A|=|B|。 本定理对证明两集合具有相同基数提供了有效的方法。若能够构造一单射函数f:AB，则有|A|B|；又能构造另一个单射函数g:BC，以证明|B|A|。于是根据本定理即可得出|A|=|B|。特别要注意，f和g不必是满射。因为通常构造这样两个单射函数比构造一个双射函数要容易许多。,定理5.4.6 设A是有限集合，则|A|0。
