首页 离散数学8

离散数学8

离散数学8离散数学8第八章函数§8.1函数的定义与性质§8.2函数的复合与反函数§8.3双射函数与集合的基数§8.4一个电话系统的描述实例定义8.1设F为二元关系，若xdomF都存在唯一的yranF使xFy成立,则称F为函数。对于函数F,如果xFy，则记y=F(x)，并称y为F在x的值。§8.1函数的定义与性质例8.1设F1={,,}，F2={,}.则F1是函数，定义8.2设F、G是函数，则而F2不是函数。F=GFG∧GF.(2)xdomF=domG都有F(x)=G(x).注：如果F=G，那么它们满足：定义8...

离散数学8第八章函数§8.1函数的定义与性质§8.2函数的复合与反函数§8.3双射函数与集合的基数§8.4一个电话系统的描述实例定义8.1设F为二元关系，若xdomF都存在唯一的yranF使xFy成立,则称F为函数。对于函数F,如果xFy，则记y=F(x)，并称y为F在x的值。§8.1函数的定义与性质例8.1设F1={,,}，F2={,}.则F1是函数，定义8.2设F、G是函数，则而F2不是函数。F=GFG∧GF.(2)xdomF=domG都有F(x)=G(x).注：如果F=G，那么它们满足：定义8.3设A,B为集合,如果f是函数,且domf=A，ranfB，则f称为从A到B的函数，记作f:A→B.(1)domF=domG;定义8.4所有从A到B的函数的集合记作BA，即BA={f|f:A→B}.注：1.若|A|=m,|B|=n,则|BA|=nm;2.ΦΦ={Φ},BΦ={Φ},ΦA=Φ.定义8.5设函数f:A→B，A1A，B1B.(1)令f(A1)={f(x)|xA1}.称f(A1)为A1在f下的像。特别地，当A1=A时，称f(A)为函数的像.　　(2)令f–1(B1)={x|xA∧f(x)B1}，称f–1(B1)为B1在f下的完全原像。例8.3见教材P137.§8.1函数的定义例8.2见教材P137.若ranf=B，则称f是满射.若yranf都存在唯一的xA使得f(x)=y，则称f是单射.(3)若f既是满射又是单射，则称f是双射(一一映射).注：如果f是满射，则对yB，都存在xA，使f(x)=y如果f是单射，则对x1,x2A，x1≠x2,必定f(x1)≠f(x2)也就是说，如果f(x1)=f(x2)，则x1=x2。§8.1函数的性质定义8.6设f:A→B.例8.4判断下列函数是否为单射、满射、双射.解：例8.5对如下给定的A,B和f,判断f是否构成A到B的函数，如果是，说明它是否为单射、满射和双射，并按要求进行计算。例8.6对给定的集合A和B构造双射函数f:A→B.设f:A→B，如果存在cB使得对xA都有f(x)=c，则称f是常函数;称A上的恒等关系IA为A上的恒等函数，对xA，都有IA(x)=x.设(A,≼)，(B,≼)为偏序集，f:A→B。若对x1,x2A，x1≺x2时有f(x1)≼f(x2)，则称f是单调递增的；若对x1,x2A，x1≺x2时f(x1)≺f(x2)，则称f是严格单调递增的，类似可定义单调递减和严格单调递减函数.设A为集合,对A'A，A'的特征函数XA':A→{0,1}定义为定义8.7(5)设R是A上的等价关系，令g:A→A/R,g(a)=[a],(aA),称g是从A到商集A/R的自然映射。函数的复合也就是关系的右复合。定理8.1设F,G是函数，则F。G也是函数，且满足(1)dom(F。G)={x|x∈domF∧F(x)∈domG}(2)x∈dom(F。G)有F。G(x)=G(F(x))§8.2函数的复合与反函数证明：(1)∵F，G是关系，∴F。G也是关系。若x∈dom(F。G)有xF。Gy1和xF。Gy2,则∈F。G∧∈F。G=>t1(∈F∧∈G)∧t2(∈F∧∈G)=>t1(∈F∧∈G)∧t2(∈F∧∈G)=>t1t2(t1=t2∧∈G∧∈G)(∵F为函数)=>y1=y2(∵G为函数)∴F。G为函数。（2）对于x,x∈dom(F。G)=>ty(∈F∧∈G)=>t(x∈dom(F)∧t=F(x)∧t∈dom(G))=>x∈{x|x∈dom(F)∧F(x)∈dom(G)}对于x,x∈dom(F)∧F(x)∈dom(G)=>∈F∧∈G=>∈F。G=>x∈dom(F)∧F。G(x)=G(F(x))§8.2函数的复合与反函数推论1设F,G,H为函数，则(F。G)。H和F。(G。H)都是函数，且(F。G)。H=F。(G。H)推论2设f:A→B,g:B→C,则f。g:A→C,且x∈A都有f。g(x)=g(f(x))。§8.2函数的复合与反函数定理8.2设f:A→B,g:B→C(1)若f:A→B,g:B→C都是满射的，则f。g:A→C也是满射的。(2)若f:A→B,g:B→C都是单射的，则f。g:A→C也是单射的。(3)若f:A→B,g:B→C都是双射的，则f。g:A→C也是双射的。证明略，参见P143。定理8.3设f:A→B,则有f=f。IB=IA。f证明:由前定理知f。IB:A→B,IA。f:A→B对于,∈f=>∈f∧y∈B=>∈f∧∈B=>∈f。IB∈f。IB=>t(∈f∧∈IB)=>∈f∧t=y=>∈f∴f=f。IB同理可证明f=f。IA§8.2函数的复合与反函数考虑：任给函数F，那么它的逆F-1是函数吗？答:不一定。如F={<1,2>,<3,2>}为一从{1，3}到{2}的函数，而F-1={<2,1>,<2,3>}不再是函数，仅是一个关系。任给单射函数f:A→B，那么它的逆f-1是函数吗？答:f-1是从ranf到A的函数，而且是双射函数。但不一定是从B到A的函数。对于什么样的函数f:A→B的逆f-1才是从B到A的函数呢？§8.2函数的复合与反函数定理8.4设f:A→B是双射的,则f-1也是双射的。证明:先证明f-1是从B到A的函数f-1：B→A。∵f是函数∴f-1是关系，且domf-1=ranf=B,ranf-1=domf=A对于x∈B=domf-1,若y1,y2∈A使得,∈f-1∧∈f-1成立,则∈f∧∈f=>y1=y2(∵f是单射函数)∴f-1是函数，而且是满射函数。§8.2函数的复合与反函数再证明f-1：B→A的单射性。若x1,x2∈B使得f-1(x1)=f-1(x2)=y,则∈f-1∧∈f–1=>∈f∧∈f=>x1=x2(∵f是函数)∴f-1是单射函数。综上所述f-1是双射的。对于双射函数f:A→B，称f-1：B→A是它的反函数。§8.2函数的复合与反函数§8.2函数的复合与反函数定理8.5设f:A→B是双射,则:f-1f=IB,ff-1=IA.证由定理8.4可知:f-1:B→A也是双射.　　由定理8.1的推论2可知:f-1f:B→B,ff-1:A→A.任取,f-1f　　　　t(f-1∧f)　　　　t(f∧f)　　　　x=y∧x,yB　　　　(因为f是函数)　　　　IB任取,IB　　　　x=y∧x,yB　　　t(f∧f)(f:A→B是双射)　　　　t(f-1∧f)　　　f-1f　　所以有f-1f=IB.同理可证:f-1f=IA.8.2函数的复合与反函数例8.8设f:R→R,g:R→Rg(x)=x+2求fg,gf.如果f和g存在反函数,求出它们的反函数.解　fg:R→Rgf:R→R　　f:R→R不是双射,不存在其反函数.　　g:R→R是双射,其反函数g-1:R→R,g-1(x)=x-2.集合的势是量度集合所含元素多少的量.集合的势越大,所含的元素越多.8.3双射函数与集合的基数定义8.8若存在着从集合A到集合B的双射函数,则称A和B是等势的,记作:A≈B,否则,称A与B不等势,则记作A≈B.下面给出一些集合等势的例子.例8.9(1)Z≈Nf:Z→N,则f是Z到N的双射函数,因此,有:Z≈N.(2)NN≈N如果能够找到“数遍”这些点的方法,这个计数过程就是建立NN到N的双射函数的过程.按照图中箭头所标明的顺序,从<0,0>开始数起,依次得到下面的序列:<0,0>,<0,1>,<1,0>,<0,2>,<1,1>,<2,0>,…↓↓↓↓↓↓012345为建立NN到N的双射函数,只需把NN中所有的元素排成一个有序图形,如右图所示.NN中的元素恰好是坐标平面上第一象限(含坐标轴在内)中所有整数坐标的点.设是图上的一个点,它所对应的自然数是k.考察m,n和k之间的关系.1).计数点所在斜线下方平面上所有的点数1+2+…+(m+n)=(m+n+1)(m+n)/2;2).再计数所在斜线上按照箭头标明的顺序位于点之前的点数是m.因此,点是第(m+n+1)(m+n)/2+m+1个点.于是,可得:k=(m+n+1)(m+n)/2+m根据上面分析 ,可给出NN到N的双射函数f:NN→N,f()=(m+n+1)(m+n)/2+m.(3)N≈Q(有理数的集合)先把所有形式为p/q(p,q为整数且q>0)的数排成一张表.显然,所有有理数都在这张表内(见下图).数上方方括号内标明了这个有理数所对应的计数上图以0/1为第一个数,按照箭头规定的顺序可以“数遍”表中所有的数.但在计数过程并没有建立N到Q的双射,因为同一个有理数可能被多次数到.例如:1/1,2/2,3/3,…都是有理数1.为此规定:在计数过程中,需跳过以后各次所遇到的同一有理数.如:1/1被计数,那么,2/2,3/3,…都要被跳过.这样就可以定义双射函数f:N→Q,其中f(n)是[n]下方的有理数.从而可得:N≈Q.(4)(0,1)≈R(其中:(0,1)={x|xR,且0和<1,b>的单调函数.由解析几何知识不难可得:f:[0,1]→[a,b],f(x)=(b-a)x+a从而可知:[0,1]≈[a,b].类似可证明:(0,1)≈(a,b).(a,bR,ab)例8.10设A为任意集合,则P(A)≈{0,1}A.证：构造函数f:P(A)→{0,1}A,f(A’)=A’,A’P(A).其中A’是集合A’的特征函数(见定义8.7(4)).显然,f是单射的.对于任意的g{0,1}A,那么,有g:A→{0,1}.令,B={x|xA,g(x)=1}则BA,B’=g,即,BP(A),f(B)=g.由此可知:f是满射的.由等势定义可得:P(A)≈{0,1}A.定理8.6设A,B和C是任意集合,(1)A≈A(2)若A≈B,则B≈A(3)若A≈B,B≈C,则A≈C证明从略.由定理9.1可知:等势关系是自反,对称和传递的.根据前面的例子和定理9.1可得:N≈Z≈Q≈NN,R≈[0,1]≈(0,1)后结果可进一步推广成:任何实数区间(包括开区间,闭区间以及半开半闭的区间)都与实数集合R等势.讨论:N与R是否等势？若N≈R,则上面列出的所有集合彼此都是等势的;若N≈R,则与N等势的那些集合也不会与R等势.定理8.7(康托定理)(1)N≈R;(2)对任意集合A,都有:A≈P(A).证：(1)若能证明:N≈[0,1],则可断定:N≈R.为此需证明:任何函数f:N→[0,1]都不是满射的.先规定[0,1]中数的表示法.对x[0,1],规定:x=0.x1x2…,(0xi9)考察两个表示数:0.24999…和0.25000.显然它们是同一个x的表示.为了保证表示法的唯一性,如果遇到上述情况,则将x表示为0.25000….根据这种表示法,任何函数f:N→[0,1]的值都可以用这种表示式给出.GeorgCantoristhefatherofsettheory.设f:N→[0,1]是从N到[0,1]的任何一个函数.如下列出f的所有函数值:f(0)=0.a1(1)a2(1)…f(1)=0.a1(2)a2(2)……f(n-1)=0.a1(n)a2(n)……设y是[0,1]之中的一个小数,y的表示式为0.b1b2…,且满足:biai(i),i=1,2,….显然,y是可以构造出来的,且y与上面列出的任何一个函数值都不相等.这就可知:yranf,即:f不是满射的.(2)用类似(1)的证明方法,证明:任何函数g:A→P(A)都不是满射的.设g:A→P(A)是从A到P(A)的函数.构造集合B:B={x|xA,xg(x)}则BP(A),但对xA,都有:xBxg(x).因此,对xA,都有:Bg(x),即:Brang.根据上面定理可以知道:N≈P(N).再综合前边结果不难断定:N≈{0,1}N.实际上,P(N),{0,1}N和R都是比N“更大”的集合.这里的“大”至今为止还没有给出其严格的定义.定义8.8(1)若存在从集合A到集合B的单射函数,则称B优势于A,记作A≤·B;若B不是优势于A,则记作A≤·B.(2)设A和B是集合,若A≤·B且A≈B,则称B真优势于A,记作A<·B;如果B不是真优势于A,则记作A<·B.例如:N≤·N,N≤·R,A≤·P(A),R≤·N;N<·R,A<·P(A),N<·N.定理8.9设A,B和C是集合,则(1)A≤·A;(2)若A≤·B,B≤·A,则A≈B;(3)若A≤·B,B≤·C,则A≤·C.本定理的证明从略.以上定理不仅为证明集合之间的优势提供了方法,也为证明集合之间的等势提供了有力的工具.在一些情况下,直接构造从集合A到集合B的双射函数是相当困难的.相比之下,构造两个单射函数f:A→B和g:B→A,则可能要容易得多下面证明:{0,1}N≈[0,1].设x是[0,1]内的小数,0.x1x2…是x的二进制表示.为保证表示的唯一性,在表示式中不允许出现连续无数个1的情况,例如:x=0.1010111….应按规定将x记为0.1011000….任取x[0,1),x=0.x1x2…是x的二进制表示.定义f:[0,1]→{0,1}N,使得:f(x)=tx,tx:N→{0,1},tx(n)=xn+1,n=0,1,2,…例如:x=0.10110100…,则对应于x的函数tx是:n01234567…tx(n)10110100…显然,tx{0,1}N,对于x,y[0,1],xy,有:txty,f(x)f(y).这就证明了f:[0,1]→{0,1}N是单射的.若上面定义的f是满射,就可直接证明:{0,1}N≈[0,1].但这是不可能的.因为f不是满射的.考虑t{0,1}N,其中t(0)=0,t(n)=1,n=1,2,….按照f的映射规则,只有x=0.011…才能满足f(x)=t.但根据x的表示法,这个数x应该表为0.100….所以,根本不存在x[0,1],使得:f(x)=t.为解决该问题,定义另一单射函数g:{0,1}N→[0,1].g的映射规则恰好与f相反,即t{0,1}N,t:N→{0,1},g(t)=0.x1x2…,其中xn+1=t(n).但不同的是,将0.x1x2…看作数x的十进制表示.例如t1,t2{0,1}N,g(t1)=0.0111…,g(t2)=0.1000….若将g(t1)和g(t2)都看成二进制表示,则g(t1)=g(t2);若都看成十进制表示,则g(t1)g(t2).这样就避免了因为进位造成的干扰,从而保证了g的单射性.由定理可知:{0,1}N≈[0,1].使用等势的传递性得:{0,1}N≈R.综合前面的讨论, 总结如下:N≈Z≈Q≈NNR≈[a,b]≈(c,d)≈{0,1}N≈P(N){0,1}A≈P(A)N<·RA<·P(A)其中[a,b],(c,d)代表任意的实数闭区间和开区间.前面,我们抽象地讨论了集合的等势与优势.现在讨论研究度量集合势的方法.最简单的集合是有穷集.在介绍前面知识时,已多次用到“有穷集”的概念,但只直观地理解为含有有限多个元素的集合,并没有精确地给出有穷集的定义.为解决该问题,下面先定义自然数和自然数集合.定义8.10设a为集合,称a∪{a}为a的后继,记作a+,即a+=a∪{a}.例考虑空集的一系列后继.+=∪{}={}++={}+={}∪{{}}={,{}}={,+}+++={,{}}+={,{}}∪{{,{}}}={,{},{,{}}}={,+,++}…对任何集合a,都有:aa.在空集的所有后继中,任何两个集合都不相等,且具有下面两个性质:前边的集合都是后边集合的元素前边的集合都是后边集合的子集利用这些性质,可以构造方法用集合来给出自然数的定义,即:0=1=0+=+={}={0}2=1+={}+={,{}}={0,1}…n={0,1,…,n-1}以上定义并没有概括出自然数的共同特征,我们还可采用另一种方法来刻划自然数.下面利用有穷集和无穷集来讨论集合势的度量问题.定义8.11一个集合是有穷的,当且仅当它与某个自然数等势;如果一个集合不是有穷的,则称作无穷集.例如:{a,b,c}是有穷集,因为3={0,1,2},　　{a,b,c}≈{0,1,2}=3而N和R都是无穷集,因为没有自然数与N和R等势.利用自然数的性质可知:任何有穷集只与唯一的自然数等势.定义8.12(1)对于有穷集合A,称与A等势的那个唯一的自然数为A的基数,记作cardA(也可记作|A|),即:cardA=nA≈n(2)自然数集合N的基数记作0(读作阿列夫零),即:cardN=0(3)实数集R的基数记作,即:cardR=定义8.13设A和B为集合,则(1)cardA=cardBA≈B(2)cardAcardBA≤·B(3)Card,AB,有:=i=k∧j=l定义函数f:AB→Nf()=in+j,(i=0,1,…,j=0,1,…,n-1)显然,f是AB到N的双射函数.所以,cardAB=cardN=0.2)直接使用可数集的性质由cardA=0,cardB=n可知:A和B都是可数集.根据性质3可知:AB也是可数集,所以,cardAB0.当B时,cardAcardAB.由此可得:cardAB=0.§8.3一个电话系统的描述实例----软件系统形式化设计，略结束

                    本文档为【离散数学8】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

离散数学8

你可能还喜欢