《离散数学 function》由会员分享，可在线阅读，更多相关《离散数学 function（47页珍藏版）》请在金锄头文库上搜索。
1、 2007 苏州大学计算机科学与技术学院离散数学 2007 苏州大学计算机科学院与技术学院2第四章 函数4-1函数的概念 4-2逆函数和复合函数 4-4基数的概念 4-5可数集与不可数集 4-6基数的比较 2007 苏州大学计算机科学院与技术学院3第四章 函数4-1函数的概念 4-2逆函数和复合函数 4-4基数的概念 4-5可数集与不可数集 4-6基数的比较 2007 苏州大学计算机科学院与技术学院4函数的概念定义4-1.1设X 和Y是任何两个集合。而 f 是X 到Y的一个关 系，如果对于每一个xX ，有唯一的 yY，使得 x,y f ，称关系 f 为函数，记作：f:XY 或概念：自变量、映像
2、、定义域和值域注意： 1 函数与关系 2 函数亦称映射或变换。习惯用小写英文 f,g, 表示函数符 。 3 在 x,y f 中，f 的前域就是函数的定义域,记作dom f (或 Df ) 显然由定义可知：Df=x xX (y)(yY y = f (x) =X 2007 苏州大学计算机科学院与技术学院54 f 的值域记为 ran f (或Rf)， 即： Rf=yyY (x)(xX y = f (x) 。问题：ran f=Y?5 映像集：f(X)=ran f 2007 苏州大学计算机科学院与技术学院6实例例1 设 X=1,5,p,张明，Y=2,q,7,9,G,f = 1,2 , 5,q , p,7
3、 , 张明, G 。求：Dom f和ran f例2 判别下列关系中哪个能构成函数 1 f = x1,x2 x1,x2 N ,且x1+x2|xXzZ(y)(yYy=f (x)z=g(y) 称g在 函数f 的左边可复合。注意： 1、关系的复合与函数复合在记法上的区别。 2、若ran f dom g 这个条件不成立，则定义g f 为空。 3、定理4-2.3两个函数的复合是一个函数。 4、定义4-2.2中，当W=Y是，则函数g f 称为复合函数，或称 g f 为g对 f 的左复合。 5、g f(x) = g(f(x) 。 6、由于函数的复合仍为函数，故可推广到有限个函数的复合 。 2007 苏州大学计
4、算机科学院与技术学院16例 f :RR, g:RR, h :RR, f(x)=x+2,g(x)=x-2,h(x)=3x 问题：函数的复合满足可结合性吗？定理4-2.3令g f 是一个复合函数。 a)若g 和 f 是满射，则g f是满射的。 b)若g 和 f 是入射，则g f 是入射的。 c)若g 和 f 是双射，则g f 是双射的。证明思路：利用满射、入射和双射的定义直接证明 2007 苏州大学计算机科学院与技术学院17常函数和恒等函数定义4-2.3 函数 f :XY 叫做常函数，如果存在某个 y0Y ， 对于每个xX都有 f (x) = y0，即f (X) = y0 。定义4-2.4 如果I
5、X = x,x |xX，则称函数 IX:XX 为恒等函数。定理4-2.4 设函数 f :XY ，则 f = f IX = IY f 。证明思路：证明定义域相同，对应关系相同。定理4-2.5 如果函数f :XY 有逆函数f -1:YX ， f-1 f = IX , f f1 = IY。 2007 苏州大学计算机科学院与技术学院18逆函数的逆函数与复合函数的逆函数定理4-2.6若f : XY 是双射函数，则( f 1)1 = f 。定理4-2.7若f :XY, g :YZ 均为双射，则(g f )-1 = f -1 g -1 。 证明： 因为f, g为双射，由定理4-2.3知g f 是双射。 由逆
6、函数定义可知：f 1 =f c, g 1 =g c , (g f )-1= (g f )c。再由 复合关系逆的性质知：( g f) c =f c gc。 所以 (g f )-1= (g f )c = f c g c= f -1 g -1 。 2007 苏州大学计算机科学院与技术学院19第四章 函数4-1函数的概念 4-2逆函数和复合函数 4-4基数的概念 4-5可数集与不可数集 4-6基数的比较 2007 苏州大学计算机科学院与技术学院20集合的大小有限集合的大小 无限集合的大小问题：如何比较两个集合的大小？ 2007 苏州大学计算机科学院与技术学院21G.Peano公理定义4-4.1设A是任
7、意集合，A的后继集定义为集合：A+ = AA。(G.Peano公理)自然数N是如下集合： (1)0 N (其中0 = )。 (2)如果n N ，那么 n+ N ，(其中n = n+ n ) 。 (3)如果一个子集S N具有性质：a. 0 S ;b. 如果n S ，有n+ S ，则S = N 。 2007 苏州大学计算机科学院与技术学院22说明： 1 上述自然数定义称为归纳定义。其中(1)为基础，(2)为归纳，(3)为极小性(指明了自然数系统 是满足公理(1)和(2)的最小集合)。 2 从N的定义可见，任意一个自然数可看作是 一个集合的名。问题：自然数系统是什么呢？ 2007 苏州大学计算机科学
8、院与技术学院23等势集合定义4-4.2给定两个集合P与Q，若对P中每个不同 元素，与Q中每个元素可以分别两两成对，则说P的 元素与Q的元素间存在着一一对应。定义4-4.3iff 集合A的元素与集合B的元素之间存在 着一一对应，集合A与集合B称为是等势的(或称同浓 的)，记作AB 。 2007 苏州大学计算机科学院与技术学院24实例例1：N1=x|x=2*i, i N，证明N1N例2：设R为实数集合，S =x|xR0, , S2 = , , S3 = , , 则NN= 由定理4-5.5可知 NN是可数集。说明：注意此种证明方法与教材上方法的差异 2007 苏州大学计算机科学院与技术学院38定理4
9、-5.7有理数集 Q 为可数集。（用排队法证明）证明：一切有理数均呈n/m(n,mN,m0) 。现将所有 n/m 按下列次序排列： （1）正分数按其分子、分母之和的大小顺序排列：从小到 大。 （2）正分数的分子、分母之和相同者按分子大小顺序排列 ：从大到小。 （3）将0放在首位，与正分数具有相同形式的负分数排于 正分数之后。按照上述规则可得： 0,1/1,-1/1,2/1,-2/1,1/2,-1/2,3/1,-3/12/2,-2/2,1/3,-1/3, 故所有呈n/m 状的数所组成的集合为可数集，而 Q 为其 无限子集，由定理4-5.4知 Q为可数集。 2007 苏州大学计算机科学院与技术学院
10、39不可数的无限集概念：连续统并非所有的无限集均为可数集。选取（0,1）作为新的 “标准集合”，记（0,1）的基数为 ，如果 A(0,1) ，那么KA = 。 也称作连续统的势。 2007 苏州大学计算机科学院与技术学院40定理4-5.8实数集R是不可数的。（用反证法证明 ）证明： 2007 苏州大学计算机科学院与技术学院41关于定理4-5.8的证明几点说明：1、仅由 0,1 构成的无限序列集合是不可数的。即 T=a0a1a2an|nN,an=0or1为不可数集。2、将(1)推广由 0,1,2, ,9 构成的无限序列集合也是不可 数集。3、S =(x,y)|x.yR0 KB c) KA = K
11、B 定理4-6.2 （Cantor-Schroder-Bernstein定理）设A和B是集合，如果KA KB ， KB KA ,则 KA = KB 。说明：定理4-6.2等价于：若存在从A到B和B到A的入射函 数，则存在从A到B的双射函数。它为证明两个集合具有 相同的基提供了有效方法。这是因为构造两个入射函数 比构造一个双射函数要容易得多。 2007 苏州大学计算机科学院与技术学院45实例例 证明0,1与（0，1）有相同的基数。证明：作入射函数：f:(0,1) 0,1, f (x) = x （恒等函数）g:0,1 (0,1), g(x) =x/2+1/4 说明：此两个函数的选取方法不唯一。如f
12、 (x) =x/2 , g(x) =x/3+1/3.故：0,1与(0,1)具有相同的基数。例 设A =N,B = (0,1),KA = ,KB = 。求证：KAB=证明：作入射函数 f :ABR, f (n,x) = n+x 故： KAB KR = 。 作入射函数 g:(0,1) AB, g(x) = 故 KAB ，因此KAB= 。 2007 苏州大学计算机科学院与技术学院46定理4-6.3设 A 是有限集合，则定理4-6.4如果 A 是无限集，那么说明：1、定理4-6.4说明 是无限集中最小的基数。 2、如果 A 为无限集，那么 ，德国数 学家康托尔认为 与 之间没有其他基数存在，但是 到目前为止还没有人能够证明它，这就是著名的连续统 假设。 3、康托尔证明了：没有最大的基数和没有最大的集合。 2007 苏州大学计算机科学院与技术学院47定理4-6.5(Cantor定理)设M是一个集合，T =(M) 则 KM KT
