離散數(shù)學函數(shù)

離散數(shù)學函數(shù)第一頁，共十五頁，編輯于2023年，星期一§5.1函數(shù)的定義和性質高等數(shù)學課程中詳細研究了函數(shù)的概念和性質，但這些函數(shù)概念一般不好直接應用地計算機科學。如數(shù)據結構，開關理論，自動機等。計算機科學要求推廣以往的函數(shù)概念。第二頁，共十五頁，編輯于2023年，星期一函數(shù)：設F為二元關系，如F1={<x1,y1>,<x2,y1>,<x3,y2>}是函數(shù)F2={<x1,y1>,<x1,y2>,<x2,y1>,<x3,y2>}不是函數(shù)若對任意的xdomF都存在唯一的yranF，使得xFy成立，則F為函數(shù)，y是F在x的函數(shù)值。第三頁，共十五頁，編輯于2023年，星期一從A到B的函數(shù)：設A、B是集合，如果函數(shù)f滿足以下條件(1)domf=A(2)ranf

B則稱f是從A到B的函數(shù)，記作：f：AB集A'

在

f

下的象：設f：AB，A'A，則f[A']是A'在f下的象。則f(A')={f(x)|xA'}=

f[A']，第四頁，共十五頁，編輯于2023年，星期一設函數(shù)f：AB(1)若ranf=B，則說f具有滿射性；(2)若對于任何x1,x2A，x1x2都有f(x1)f(x2)，則說f具有單射性；(3)若f既具有滿射性，又具有單射性，則說f具有雙射性。函數(shù)的性質第五頁，共十五頁，編輯于2023年，星期一例5.1判斷以下函數(shù)的單射、滿射和雙射性。(1)f：RRRR，R為實數(shù)集f(<x,y>)=<x+y,xy解：(1)先說f是單射的。這要證明對任取<x,y>，<u,v>RR。反證，如果<x+y,xy>=<u+v,uv>，則，x+y

=u+v且xy=uv。<x,y><u,v>時,<x+y,xy><u+v,uv>；第六頁，共十五頁，編輯于2023年，星期一解關于x,y的方程組知：x=u且y=v，故<x,y>=<u,v>與已知矛盾。再說f是滿射的。這只要讓對任意的(u,v)RR，可以找到<x,y>RR,使得f(<x,y>)=<u,v>就可以了。由f的定義有x+y=u和xy=v綜上所述，f是雙射的。第七頁，共十五頁，編輯于2023年，星期一(2)f：NNN，N為自然數(shù)集(0N)f(<x,y>)=|x2y2|解：

f不是單射，因為f(<2,2>)=f(<1,1>)=0；f不是滿射，因為找不到自然數(shù)x和y滿足|x2y2|=2，所以2ranf

第八頁，共十五頁，編輯于2023年，星期一特征函數(shù)：設A為集合，XA'(a)=1aA'0aAA'如A={a,b,c}，A'={a}，則XA'(a)=1，XA'(b)=XA'(c)=0對于任意的A'A，A'的特征函數(shù)XA'：A{0，1}定義為：第九頁，共十五頁，編輯于2023年，星期一自然映射：設R是A上的等價關系，如：A={1,2,3}，R={<1,2>,<2,1>}∪IA則有g(1)=g(2)={1,2}，g(3)={3}稱g為從A到A/R的自然映射。定義一個從A到A/R的函數(shù)g：AA/R且g(a)=[a]，它把A中的元素a映到a的等價類[a]。第十頁，共十五頁，編輯于2023年，星期一§5.2函數(shù)的運算由定義可知：只有當f：AB是雙射函數(shù)時，它才有逆函數(shù).函數(shù)的逆：關系f是從A到B的一個函數(shù)，如果f的逆關系f1也是一個函數(shù)(B到A的)，這個函數(shù)稱之為f的逆函數(shù)，記作f1：BA。第十一頁，共十五頁，編輯于2023年，星期一函數(shù)的合成：設f：

AB和g：BC都是函數(shù)，則合成關系g

f={<a,c>|aAcCb(bB<a,b>f<b,c>g)}稱為f與g的合成函數(shù)：g

f：AC第十二頁，共十五頁，編輯于2023年，星期一例5.2設函數(shù)f：RR,f(x)=3x+2,求f2,f3,f4解：∵

f2=f

f

∴f2(x)=f(f(x))=f(3x+2)∵f3=f

f2

∴f3(x)=f(f2(x))∵f4=f

f3

∴f4(x)=f(f3(x))=3(3x+2)+2=9x+8

=3f2(x)+2=3(9x+8)+2=27x+26

=3f3(x)+2=3(27x+26)+2=81x+80

第十三頁，共十五頁，編輯于2023年，星期一合成運算的性質(1)若f:AB,g:BC都是滿射，則g

f也是滿射；(2)若f:AB,g:

BC都是單射，則g

f也是單射；(3)若f:AB,g:BC