資源描述：
《離散數(shù)學(xué)(第13講)函數(shù)1》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、第6章函數(shù)(1)欒新成四川大學(xué)軟件學(xué)院luanxch@sina.com8599782213808024081主要內(nèi)容1、函數(shù)的基本概念2、單射、滿射、雙射和逆函數(shù)3、函數(shù)的遞歸定義2021年7月10日2概述函數(shù)是一種特殊的二元關(guān)系,我們可以把函數(shù)看作輸入輸出關(guān)系;它把一個集合(輸入集合)的元素變成另一個集合(輸出集合)的元素。在高等數(shù)學(xué)中，函數(shù)的概念是從變量的角度提出來，而且是在實數(shù)集合上討論，這種函數(shù)一般是連續(xù)或間斷連續(xù)的函數(shù)。這里，將連續(xù)函數(shù)的概念推廣到對離散量的討論。前面所討論的有關(guān)集合或關(guān)系的運(yùn)算和性質(zhì)，對于函數(shù)完全適用。任何程序在計算機(jī)中的實現(xiàn),都包含種種這樣或
2、那樣的變換。如編譯程序把一個源程序變換成機(jī)器語言的指令集合—目標(biāo)程序?；蛘哒f,計算機(jī)中的程序可以把一定范圍內(nèi)的任一組數(shù)據(jù)變換成另一組數(shù)據(jù)。函數(shù)是許多數(shù)學(xué)工具的基礎(chǔ),計算機(jī)科學(xué)中大量用到函數(shù),如數(shù)據(jù)結(jié)構(gòu),程序語言的設(shè)計與實現(xiàn),開關(guān)理論,自動機(jī)理論,代數(shù)結(jié)構(gòu),可計算性理論,計算復(fù)雜性,程序正確性證明等。2021年7月10日3一般集合的函數(shù)概念定義6-1.1設(shè)f是集合A到B的關(guān)系，如果對每個x∈A，都存在惟一的y∈B，使得∈f，則稱關(guān)系f為A到B的函數(shù)（或映射、變換），記為f：A→B。當(dāng)∈f時，通常記為y=f(x)，這時稱x為函數(shù)的自變量，稱y為x在f下的函
3、數(shù)值（或映象）。由函數(shù)的定義顯然有：(1)domf=A，稱為函數(shù)f的定義域；(2)ranf=B，稱為函數(shù)f的值域，ranf也可記為f(A)，并稱f(A)為A在f下的象；(3)∈f∧∈f?y=z；(4)
4、f
5、=
6、A
7、。注意，f(x)僅表示一個變值，但f則代表一個集合，因此f≠f(x)。2021年7月10日4一般集合的函數(shù)概念例6.1判斷下圖所示的幾個關(guān)系是否是函數(shù)：解f3、f4、f5、f6都是函數(shù)，但f1、f2則不是函數(shù)。因f1中A的元素5沒出現(xiàn)在序偶的第一元素中，f2中A的元素4出現(xiàn)在兩個不同序偶的第一元素中。2021年7月10日5函數(shù)與關(guān)系的差別20
8、21年7月10日6如果記由此可以知道，函數(shù)確是一種特殊的關(guān)系，它與一般關(guān)系比較具備如下差別：(1)A×B的任何一個子集，都是A到B的二元關(guān)系，因此，從A到B的不同的關(guān)系有2
9、A
10、?
11、B
12、個；但從A到B的不同的函數(shù)卻僅有
13、B
14、
15、A
16、個。(2)每一個函數(shù)的基數(shù)都為
17、A
18、個，但關(guān)系的基數(shù)卻可以從零一直到
19、A
20、×
21、B
22、。(3)每一個函數(shù)中序偶的第一個元素一定是互不相同的。函數(shù)與關(guān)系的差別例6.2設(shè)A＝{a,b}，B＝{1,2}，A×B＝{,,,}，此時從A到B的不同的關(guān)系有24＝16個。分別如下：R0＝Φ；R1＝{}；R2＝{
23、}；R3＝{}；R4＝{}；R5＝{,}；R6＝{,}；R7＝{,}；R8＝{,}；R9＝{,}；R10＝{,}；R11＝{,,}；R12＝{,,}；R13＝{,,}；2021年7月10日7函數(shù)與關(guān)系的差別R14＝{,,}；R15＝{,,,}。從A到B的不同的函數(shù)
24、僅有22＝4個。分別如下：f1＝{,}；f2＝{,}；f3＝{,}；f4＝{,}。常將從A到B的一切函數(shù)構(gòu)成的集合記為BA：BA＝｛f
25、f：A→B}2021年7月10日8函數(shù)的復(fù)合運(yùn)算定義6-1.2設(shè)f和g：X→Y是兩個函數(shù)，如果對?x?X,都有f(x)=g(x),則稱f與g相等，記為f=g。定義6-1.3設(shè)f：X→Y，g：Y→Z是兩個函數(shù)，稱g?f={︱（?y?Y）[y=f(x)∧z=g(y)]}稱為函數(shù)f與g的復(fù)合函數(shù)，記為g?f：X→Z。(g?f)（x）=g（f（x））函
26、數(shù)復(fù)合的性質(zhì)1)函數(shù)復(fù)合是可結(jié)合的(∵關(guān)系的復(fù)合是可結(jié)合的)2)函數(shù)復(fù)合一般是不可交換的,2021年7月10日9由于歷史的原因，函數(shù)f和g的復(fù)合記成了g?f的形式，與關(guān)系的復(fù)合記法相反單射、滿射和雙射定義6-2.1設(shè)f是從X到Y(jié)的函數(shù)，若f滿足：對任意x1,x2∈X，若x1≠x2，則f(x1)≠f(x2)，則稱f為從X到Y(jié)的單射或1-1映射；若ranf＝Y(jié)，則稱f為從X到Y(jié)的滿射或從X到Y(jié)上的映射；若f既是從X到Y(jié)的滿射，又是從X到Y(jié)的單射，則稱f為從X到Y(jié)的雙射或一一對應(yīng)的映射。若X＝Y(jié)，則稱f為X上的函數(shù)；當(dāng)X上的函數(shù)f是
