离散数论-函数

《离散数论-函数》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学函数李舟军主要内容1.部分函数2.函数的合成3. 逆函数4.  特征函数5.基数6.基数算术2001.102函数函数（映射）：一个集合和另外一个集合之间的联系。一个集合中的每个元素都对应有另一个集合中唯一的一个元素。函数是一种特殊的关系2001.103函数§3.1部分函数2001.104函数部分函数目的：理解各种部分函数、限制和延拓的概念；掌握根据部分函数概念进行证明的方法；重点：各种部分函数的概念、基于概念的证明方法；难点：各种部分函数概念的理解。2001.105函数部分函数如果从集合X到集合Y的二元关系f是“单值”的，即

2、f满足以下条件：若〈x，y1〉∈f且〈x，y2〉∈f，则y1=y2。就称f为从X到Y的部分函数。当〈x，y〉∈f时，称y为f在x处的值，记为y=f(x)。2001.106函数定义域、值域部分函数f的定义域domf：domf={x｜x∈X且有y∈Y使y=f(x)}f若x∈domf，就称f在x处有定义，记为“f(x)↓”；否则称f在x处无定义，记为“f(x)↑”，显然domfX。部分函数f的值域ranf：ranf={y｜y∈Y且有x∈X使f(x)=y}f显然ranfY。2001.107函数例子exp={

3、ex>

4、xR}arcsin={

5、x，yR且siny=x}不是部分函数2001.108函数特殊的部分函数设f为从集合X到集合Y的部分函数。若domf=X，则称f为从X到Y的全函数，简称f为从X到Y的（全）函数，记为XY或f：X→Y。若domfX，则称f为从X到Y的严格部分函数。若ranf=Y，则称f为从X到Y上的部分函数。若ranfY，则称f为从X到Y内的部分函数。若对任意的x1，x2∈domf，当x1≠x2时皆有f(x1)≠f(x2)，则称f为从X到Y的1-1部分函数。（即，当f(x1)=f(x2)时皆有x1=

6、x2）2001.109函数f={

7、xR}例子R到R内1-1（全）函数2001.1010函数象、原象设f为从集合X到集合Y的部分函数，AX且BY。令f[A]={y｜有x∈A使y=f(x)}f–1[B]={x｜有y∈B使f(x)=y}称f[A]为A在f下的象，f–1[B]为B在f下的原象。即，f[A]={f(x)｜x∈A且f(x)↓}f–1[B]={x｜x∈X使f(x)↓且f(x)B}2001.1011函数限制、延拓设f为从集合X到集合Y的部分函数且AX。定义f在A上的限制fA为从A到Y的部分函数，并且fA=f

8、∩(A×Y)也称f为fA到X上的延拓。2001.1012函数定理3.1.1设f为从集合X到集合Y的部分函数。若A1A2X，则f[A1]f[A2]；若B1B2Y，则f–1[B1]f–1[B2]；若Adomf，则Af–1[f[A]]；若Branf，则B=f[f–1[B]]。2001.1013函数证明：i)和ii)显然，只证iii)和iv)若x∈A，因为Adomf，所以f(x)↓且f(x)∈f[A]，所以x∈f–1[f[A]]。若y∈B，则y∈ranf（因为Branf）。因此，有x∈X使y=f(x)。从而得x∈f–

9、1[B]。这表明y∈f[f–1[B]]。另一方面，若y∈f[f–1[B]]，则有x∈f–1[B]使f(x)=y，所以y∈B。2001.1014函数定理3.1.2设f为从集合X到集合Y的部分函数，Ａ(X)，В(Y)。f[∪Ａ]=∪{f[A]｜A∈Ａ}；若Ａ≠，则f[∩Ａ]∩{f[A]｜A∈Ａ}；f–1[∪В]=∪{f–1[B]｜BВ}；若В≠，则f–1[∩Ｂ]=∩{f–1[B]｜B∈Ｂ}。2001.1015函数证明：只证iv)，其它的证明与此类似。若B∈В，则由∩ВB得：f–1[∩В]f–1[B]从而得：f–1[∩

10、В]∩{f–1[B]｜B∈Ｂ}；另一方面，任取x∈∩{f–1[B]｜B∈Ｂ}，若B∈В，则x∈f–1[B]，即f(x)∈B。因此：f(x)∈∩В，即x∈f–1[∩В]。故有：∩{f–1[B]｜B∈Ｂ}f–1[∩В]。2001.1016函数定理3.1.3若f为从集合X到集合Y的部分函数且AX，则dom(fA)=A∩domf，ran(fA)=f[Ａ]若Adomf，则fA是全函数。2001.1017函数A到B的全函数集设A和B为任意二集合，记BA={f｜f：A→B}。（f为A到B的全函数）2001.1018函数例子设A为任意

11、集合，B为任意非空集合。因为存在唯一的一个从到A的函数，所以A={}；因为不存在从B到的函数，所以B=。？是否存在从B到的部分函数？2001.1019函数定理1.1.4设A和B都是有限集，则n(BA)=(n(B))n