第五章函數(shù)離散數(shù)學(xué)陳志奎主編人民郵電出版社前言函數(shù)是滿足某些條件的二元關(guān)系。這里所要討論的是離散函數(shù)，它能把一個(gè)有限集合變換成另一個(gè)有限集合。計(jì)算機(jī)執(zhí)行任何程序都屬于這樣一種變換。通常，總是認(rèn)為函數(shù)是輸入和輸出之間的一種關(guān)系，即對(duì)于每一個(gè)輸入或自變量，函數(shù)都能產(chǎn)生一個(gè)輸出或函數(shù)值。因此，可以把計(jì)算機(jī)的輸出看成是輸入的函數(shù)。編譯程序則能把一個(gè)源程序變換成一個(gè)機(jī)器語言的指令集合目標(biāo)程序。在本章中，首先將定義一般的函數(shù)，然后討論特種函數(shù)，由一種特殊函數(shù)——雙射函數(shù)引出不可數(shù)集合基數(shù)的比較方法。在以后的各章中，這些概念將起著重要作用。在開關(guān)理論、自動(dòng)機(jī)理論、可計(jì)算性理論等領(lǐng)域中，函數(shù)都有著極其廣泛的應(yīng)用。PART01函數(shù)的基本概念和性質(zhì)主要內(nèi)容PART02函數(shù)的合成和合成函數(shù)的性質(zhì)PART03特殊函數(shù)PART04反函數(shù)PART05特征函數(shù)PART06基數(shù)PART07不可解問題5.1函數(shù)的基本概念和性質(zhì)定義5.1設(shè)A和B是兩個(gè)任意的集合，并且f是從A到B的一種關(guān)系。如果對(duì)于每一個(gè)，都存在唯一的，使得，則稱關(guān)系f為函數(shù)或映射，并記作對(duì)于函數(shù)來說，如果有，則稱x是自變量；與x相對(duì)應(yīng)的y，稱為在f作用下x的像點(diǎn)，或稱y是函數(shù)f在x處的值。通常用

表示。4函數(shù)5.1函數(shù)的基本概念和性質(zhì)從A到B的函數(shù)f，是具有下列性質(zhì)的從A到B的二元關(guān)系。（1）每一個(gè)元素，都必須關(guān)系到某一個(gè)；也就是說，關(guān)系f的定義域是集合A本身，而不是A的真子集。（2）如果有，則函數(shù)f在x處的值y是唯一的，亦即因?yàn)楹瘮?shù)是關(guān)系，所以關(guān)系的一些術(shù)語也適用于函數(shù)。例如，如果f是從A到B的函數(shù)，則集合A是函數(shù)f的定義域，亦即；集合B稱為f的陪域；是f的值域，且。有時(shí)也用表示f的值域，亦即

有時(shí)也稱是函數(shù)f的像點(diǎn)。55.1函數(shù)的基本概念和性質(zhì)例5.1設(shè)E是全集，是P(E)的冪集。對(duì)任何兩個(gè)集合的并運(yùn)算和相交運(yùn)算，都是從到p(E)的映射；對(duì)任何集合的求補(bǔ)運(yùn)算，則是從到的映射。例5.2試說明下面的二元關(guān)系是否是函數(shù)。（1）（2）解：（1）是函數(shù)，滿足函數(shù)的任意性和唯一性條件；（2）不是函數(shù)，不滿足唯一性條件。例如時(shí)，。此例告訴我們，這里給出的函數(shù)的概念和高等數(shù)學(xué)中給出的函數(shù)的概念是有所區(qū)別的，在高等數(shù)學(xué)中，一直是把反正弦當(dāng)作函數(shù)的。65.1函數(shù)的基本概念和性質(zhì)定義5.2給定函數(shù)和。如果f和g具有同樣的定義域和陪域，亦即和，并且對(duì)于所有的或都有，則稱函數(shù)f和g是相等的，記作75.1函數(shù)的基本概念和性質(zhì)定義5.3給定函數(shù)，且有。（1）試構(gòu)建一個(gè)從A到Y(jié)的函數(shù)通常稱g是函數(shù)f的縮小，并記作。（2）如果g是f的縮小，則稱f是g的擴(kuò)大。從定義可以看出，函數(shù)的定義域是集合A，而函數(shù)f的定義域則是集合X。和f的陪域均是集合Y。于是若g是f的縮小，則應(yīng)和并且對(duì)于任何都有85.1函數(shù)的基本概念和性質(zhì)例5.4：令X1={0,1},X2={0,1,2},Y={a,b,c,d}。定義從

到Y(jié)的函數(shù)f為：f={<0,0,a>,<0,1,b>,<1,0,c>,<1,1,b>}。g=f{<0,2,a>,<1,2,c>,<2,0,b>,<2,1,a>,<2,2,d>}是從

到Y(jié)的函數(shù)。于是f=g/，因此f是g在

上的縮?。ɑ蚍Q限制），g是f到

上的擴(kuò)大（或稱延拓）。

95.1函數(shù)的基本概念和性質(zhì)因?yàn)楹瘮?shù)是二元關(guān)系，所以可以用關(guān)系圖和關(guān)系矩陣來表達(dá)函數(shù)。

此外，由函數(shù)的定義可知，在關(guān)系矩陣的每一個(gè)行上，都有且僅有一個(gè)元素的值是1，而此行上的其他元素都必定為0。因此，可以用一個(gè)單獨(dú)的列來代替關(guān)系矩陣。在這個(gè)單獨(dú)的列上，應(yīng)標(biāo)明所對(duì)應(yīng)的給定函數(shù)的各個(gè)值。這樣，該列上的各元素也說明了自變量與其函數(shù)值之間的對(duì)應(yīng)關(guān)系。

10函數(shù)f:X→Y的圖解5.1函數(shù)的基本概念和性質(zhì)例5.5設(shè)集合X={a,b,c,d}和Y={1,2,3,4,5}，并且有

f={<a,1>,<b,3>,<c,4>,<d,4>}試求出domf，ranf和f的矩陣表達(dá)式。解：domf={a,b,c,d}ranf={1,3,4}f的簡(jiǎn)化關(guān)系矩陣為：

115.1函數(shù)的基本概念和性質(zhì)定義5.4

設(shè)A和B是任意兩個(gè)集合，記：為從A到B的所有函數(shù)的集合。例5.6設(shè)集合X={a,b,c}和集合Y={0,1}。試求出所有可能的函數(shù)f:X→Y。解：首先求出的X×Y所有序偶，于是應(yīng)有于是，有26個(gè)可能的子集，但其中僅有下列23個(gè)子集可以用來定義函數(shù)：

125.1函數(shù)的基本概念和性質(zhì)設(shè)A和B都是有限集合，且|A|=m和|B|=n，因?yàn)槿魏魏瘮?shù)f:A→B的域都是集合A，所以每個(gè)函數(shù)中都恰有m個(gè)序偶。而且，任何元素x∈A，都可以在B的n個(gè)元素中任選其一作為自己的象點(diǎn)。因此，應(yīng)有nm

個(gè)可能的不同函數(shù)，亦即|BA|=|B||A|=nm例5.7

設(shè)A為任意集合，B為任意非空集合。（1）因?yàn)榇嬖谖ㄒ坏囊粋€(gè)從Ф到A的函數(shù)，所以AФ={Ф}。（2）因?yàn)椴淮嬖趶腂到Ф的函數(shù)，所以ФB=Ф。

13PART01函數(shù)的基本概念和性質(zhì)主要內(nèi)容PART02函數(shù)的合成和合成函數(shù)的性質(zhì)PART03特殊函數(shù)PART04反函數(shù)PART05特征函數(shù)PART06基數(shù)PART07不可解問題5.2函數(shù)的合成和合成函數(shù)的性質(zhì)定義5.5

設(shè)f:X→Y和g:Y→Z是兩個(gè)函數(shù)。于是，合成關(guān)系f?g為f與g的合成函數(shù)，并用g?f表示。即注意：合成函數(shù)g?f與合成關(guān)系f?g實(shí)際上表示同一個(gè)集合。這種表示方法的不同有其方便之處：對(duì)合成函數(shù)g?f，當(dāng)z=(g?f)(x)時(shí)，必有z=g(f(x))

g?f與g(f(x))的次序是理想的。

155.陳2函數(shù)狗的合翠成和蛇合成主函數(shù)銀的性槐質(zhì)定理5.熟1設(shè)壤和販?zhǔn)莾伤貍€(gè)函澆數(shù)。（1）合煎成函堡數(shù)墳是從驗(yàn)的婦函數(shù)鐮，并避且，芽對(duì)于純每一幼個(gè)亞，都剪有億。（2）其中賴表示g的定環(huán)義域連在f下的原像于集，詳表示f的值扯域在g下的像點(diǎn)規(guī)集。165.滋2函數(shù)腔的合豬成和藏合成湊函數(shù)宏的性錘質(zhì)例5.藝8設(shè)集礙合X=嗚{x1,x2,x3,x4},易Y詞={購(gòu)y1,y2,y3,y4,y5}，Z=旋{z1,z2,z3}。函統(tǒng)數(shù)f:眾X→Y和g:語Y深→Z分別擴(kuò)是試求障出函駛數(shù)g?f=最X→腥Z，并值給出努它的勉圖解限。解：175.義2函數(shù)擱的合溉成和別合成妥函數(shù)陷的性斷質(zhì)例5.國(guó)9設(shè)集炎合校，代函數(shù)驅(qū)和閉分纖別為試求倍出合恰成函余數(shù)睛，低，,。解：由上薄面的恐例子?jì)尶梢孕钥闯鲋?，弟，液即函碼數(shù)的合成古運(yùn)算帳是不瓣可交央換的者，但選它是召可結(jié)咱合的。185.窗2函數(shù)拌的合肢成和武合成構(gòu)函數(shù)站的性童質(zhì)定理5.宜2函數(shù)衫的合秒成運(yùn)度算是夕可結(jié)碗合的探，即膏如果f適,集g爬,宋h都是嘗函數(shù)炒，則懸應(yīng)有下面獨(dú)把恒降等式憶所給饅出的豪關(guān)系肉，推監(jiān)廣到放更為長(zhǎng)一般觀的情悶況。兄設(shè)有n個(gè)函第數(shù)：螺，腸，…，踐，柜于是暑無括鑒號(hào)表甩達(dá)式驢，唯尤一地似表達(dá)棄了從垃到號(hào)的茅函數(shù)滔。如系果蛙和族，陡則可羊用獸表測(cè)示從X到X的合辜成函天數(shù)撫。195.持2函數(shù)儉的合琴成和呼合成田函數(shù)搬的性戒質(zhì)例5.怒10設(shè)Z是整椅數(shù)集餃合，開并且慘函數(shù)f:側(cè)Z帆→Z給定忍成f(今i)滿=2冶i+升1。試陳求出坐合成度函數(shù)f3(泛i祖)。解：踐合成綠函數(shù)f3(貓i還)是一叢個(gè)由Z到Z的函羞數(shù)，押于是訊有205.蓬2函數(shù)份的合恩成和辜合成桿函數(shù)兄的性抓質(zhì)定義5.晴6給定嘴函數(shù)f:逗X→X，如即果有f2=f，則送稱f是個(gè)等冪挺函數(shù)。例5.岸11設(shè)Z是整握數(shù)集葵合和Nm={晨0,壓1,體2,近…m呀-1牢}，并馬且函斗數(shù)f:綢Z→Nm是f(雜i)訴=i休(m糞od音m章)。試古證明膛，對(duì)齊于n≥宰1都有fn=f。證明：刮（歸賣納證席法）石當(dāng)n=曬2時(shí)假設(shè)準(zhǔn)當(dāng)n=云k時(shí)，辛滿足fk=f際;那么濁當(dāng)n=瞇k+占1時(shí)，fk+挖1=戒fk?f圍=哥f?完f淘=附f得證紐奉。對(duì)膊于所閱有的n≥凳1，都禮有fn=f21等冪潑函數(shù)PART01函數(shù)總的基閱本概普念和砍性質(zhì)主要內(nèi)容PART02函數(shù)賞的合城成和粒合成創(chuàng)函數(shù)烏的性胖質(zhì)PART03特殊演函數(shù)PART04反函儲(chǔ)數(shù)PART05特征秋函數(shù)PART06基數(shù)PART07不可桶解問袖題5.疫3特殊鋼函數(shù)某些課類型慎的函寺數(shù)，船具有然一些寬十分總重要寄的性趟質(zhì)，亞而這燥些性臣質(zhì)對(duì)送于我肆們研緣瑞究某租些具枝體領(lǐng)嶄域中復(fù)的實(shí)拆際問言題是袋十分站有用鑒的。校例如童，可遼以通抖過雙洪射函鞋數(shù)來督研究伯無限左集的句基數(shù)溜的比傻較，法通過最特征雄函數(shù)州來研膏究集敵合間屑的關(guān)竭系等貸等。激下面驢我們豪將專拉門定嶼義這抽些函翅數(shù)，鏈并且少給出猛相應(yīng)聰?shù)男g(shù)位語。235.積3特殊圾函數(shù)定義5.稠7給定詠函數(shù)f:蛋X→Y。（a）如毛果函隱數(shù)f的值敗域Rf=Y，則弦稱f為映凝上的際映射杠，或允稱滿射師函數(shù)。（b）如雨果函螺數(shù)f的值湯域RfY，則拌稱f為映廁入的仗映射獅或內(nèi)射。定義5.誤8給定貞函數(shù)f:貪X→Y,對(duì)于x1,x2∈X來說醉，如仙果有或者面是則稱f為一脫對(duì)一買的映溉射，絹或稱f為單射館函數(shù)。245.奪3特殊笨函數(shù)定義5.瞎9給定逼函數(shù)f:盾X→Y。如付果f既是患滿射境的又疫是單蘇射的膊，則笛稱f為一銀對(duì)一茄映滿蟲的映羊射，磨或稱f為雙射欣函數(shù)。定義噴中的辟條件灑說明題構(gòu)成評(píng)雙射遲函數(shù)舉的必巴要條豬件是鈴。后旨面我縮慧們將比會(huì)看憐到，另如果扇兩個(gè)諷無限輪集之暈間存趙在一桶個(gè)雙鋼射函村數(shù)，衫那么廣這兩炭個(gè)無揀限集危是等胡勢(shì)的敢。255.盟3特殊獵函數(shù)例5.紛12判斷紡下列弱函數(shù)記是否嘆為單沃射、物滿射交、雙椅射的拔，并胞給出此原因帥。（1）（2）禮為姓正整原數(shù)集紫。（3）（4）避為透正實(shí)列數(shù)集凍。解：鍬（1）函診數(shù)f(未x)為開胖口向余下的雷拋物悠線，紀(jì)不是土單調(diào)稿函數(shù)跡，并塘且在x=虧1處取沸得極蒙大值0，因莖此它委既不溉是單掏射也暫不是施滿射妨的。（2）函凳數(shù)f(街x)是單然調(diào)上囑升的魯，因貍此是擋單射恢的。厚但不厭是滿劍射的柜，因末為（3）函筐數(shù)f(籌x)是滿拿射，糖單射珠和雙交射的猾。因方為它險(xiǎn)是單荒調(diào)函耐數(shù)并虛且（4）函篩數(shù)f(討x)既不寺是單肆射的配，也攝不是晴滿射舍的。督因?yàn)楦诞?dāng)x=陪1和x=完4時(shí)f(羨x)緒=4，所喊以f(無x)不是糖單射擋的。敬當(dāng)蝕時(shí)巧，f(考x)取得涼最小銜值瞇，所蕩以f(仔x)不是私滿射腰的。265.禮3特殊糕函數(shù)定理5.需3給定涂函數(shù)f和g，并鋤且有竭合成銳函數(shù)g?尿f。于撓是（a）如器果f和g都是衫滿射載函數(shù)悔，則戀合成出函數(shù)g?吵f也是辛個(gè)滿太射函摸數(shù)。（b）如挽果f和g都是庫單射策函數(shù)援，則近合成當(dāng)函數(shù)g?分f也是蛙個(gè)單棉射函社數(shù)。（c）如波果f和g都是難雙射續(xù)函數(shù)吃，則昌合成匆函數(shù)g?瓜f也是譯個(gè)雙牌射函掌數(shù)。275.壺3特殊夸函數(shù)285.們3特殊電函數(shù)定理5.比4：給定肉函數(shù)f和g，并治且有霉合成滅函數(shù)g?別f,于是（1）如渠果g?掛f是滿甜射函鵝數(shù)，兩則g必定蒙是滿澇射的攪。（2）如羨果g?遼f是個(gè)毫單射銳函數(shù)搶，則f必定板是個(gè)奪單射鴉函數(shù)歐。（3）如壩果g?遲f是個(gè)頸雙射成函數(shù)法，則g必定漿是滿千射的浩，f是單弦射的統(tǒng)。295.譯3特殊軟函數(shù)305.悅3特殊間函數(shù)定義5.銅10：給定藏集合X，并膀且有穩(wěn)函數(shù)IX:妨X→X。對(duì)率于所替有的x∈X，有IX(x胃)=死x，亦儉即IX={范<x化,x罪>|痕x∈X}則稱IX為恒等鍵函數(shù)。315.備3特殊謹(jǐn)函數(shù)定理5.改5給定而集合X和Y。對(duì)縫于任憐何函訊數(shù)f:性X→Y，都蝴有f=罷f?痛IX=IY?f證明天：設(shè)x∈X和y∈Y，根擋據(jù)定貨義IX(x吼)=文x,印IY(y哄)=嶼y，得證趟！32PART01函數(shù)粉的基故本概蔥念和漏性質(zhì)主要內(nèi)容PART02函數(shù)躬的合禽成和彩合成貿(mào)函數(shù)工的性束質(zhì)PART03特殊濫函數(shù)PART04反函增數(shù)PART05特征錄函數(shù)PART06基數(shù)PART07不可街解問振題5.監(jiān)4反函膝數(shù)定義5.隸11設(shè)擔(dān)是蒙一個(gè)風(fēng)雙射競(jìng)函數(shù)揚(yáng)。于憲是f的逆設(shè)關(guān)系牽是f的反函攪數(shù)（或依稱逆函雪數(shù)），斧并記翁作羨。偵對(duì)于f來說之，如姨果存漏在丑，則志函數(shù)f是可逆就的。應(yīng)該混注意酸，僅閉當(dāng)鈴是雙直射函渴數(shù)時(shí)票，才歇有對(duì)窩應(yīng)于荷的反誘函數(shù)攝。若存秘在函保數(shù)緩，漂使得握，療則稱g為f的左逆；若證存在索函數(shù)燙，溜使得邊，則權(quán)稱g為f的右逆。345.淚4反函層數(shù)定理5.掛6設(shè)襲是一普個(gè)雙蓋射函爸?jǐn)?shù)。椅于是鈴，反統(tǒng)函數(shù)狗也是贊一個(gè)怎雙射衛(wèi)函數(shù)制，并碼且是悟從Y到X的函笑數(shù)赤。355.略4反函競(jìng)數(shù)定理5.目6設(shè)翼是一待個(gè)雙稿射函程數(shù)。們于是瞞，反孕函數(shù)減也是剪一個(gè)贊雙射攔函數(shù)展，并錢且是靜從Y到X的函驚數(shù)激。365.壟4反函孕數(shù)定理5.耕7如果騎函數(shù)和是商可逆王的，雜則有37函數(shù)f和的合晉成，饒總會(huì)幻玉生成物一個(gè)晴恒等鋤函數(shù)貨，由盞于合方成的債次序裙不同皮，合賺成函仆數(shù)的摘值域版或者除是集攻合X，或剩者是偽集合Y。5.態(tài)4反函檢數(shù)例5.毛15給定皮集合絨和壤并獵且函至數(shù)描給獻(xiàn)定成渣，反鉗函數(shù)白給言定成圾。未試求達(dá)出嘩和誓。解：定理5.擊8如果f是個(gè)憂雙射掃函數(shù)乏，則文應(yīng)有385.沈4反函避數(shù)定理5.辜9給定拜函數(shù)壞和胖，并化且f和g都是逼可逆蕩的。遺于是鬼應(yīng)有例5.躲16給定死集合鼠，和設(shè)函旦數(shù)和分別劉為：，。試說冒明解：39PART01函數(shù)產(chǎn)的基恭本概煤念和鑼性質(zhì)主要內(nèi)容PART02函數(shù)淺的合勞成和改合成足函數(shù)閘的性滿質(zhì)PART03特殊嗓函數(shù)PART04反函勿數(shù)PART05特征擁函數(shù)PART06基數(shù)PART07不可素解問蟻題5.遺5特征事函數(shù)定義5.胡12設(shè)X為任銀意集曠合，申，f和g是從X到Y(jié)的函穩(wěn)數(shù)。（1）態(tài)表示祥，對(duì)醉每個(gè)填，盜皆有（2）龍，對(duì)德每個(gè)鋪皆有，稱f兔+撇g為f和g的和（3）鉤，對(duì)接每個(gè)展皆有，稱f劣-潔g為f和g的差獅。（4）徐，對(duì)掌每個(gè)憑皆有，稱f藍(lán)*拿g為f和g的積謀。415.據(jù)5特征愚函數(shù)定義5.綿13設(shè)E為全渠集，米，廳為如悄下定臘義的毛從E到{隸0落,繼1挽}的函饑數(shù)。稱因?yàn)槠羌螦的特括征函行數(shù)。425.析5特征燭函數(shù)下面爭(zhēng)列舉存特征冷函數(shù)以的一腸些重洪要性早質(zhì)，跳其中0表示寫從E到{藍(lán)0,炊1候}的函些數(shù)1表示動(dòng)從E到{議0,閣1臥}的函話數(shù)（1）0≤團(tuán)≤1,對(duì)于惱任意職的鴿成立傳。（2）方，預(yù)當(dāng)且淚僅當(dāng)們。（3）鞭，當(dāng)炮且僅定當(dāng)（4）姓，當(dāng)盟且僅活當(dāng)（5）代，當(dāng)掏且僅饑當(dāng)（6）=演1廢-（7）（8）（9）（10）濾當(dāng)且肅僅當(dāng)（11）435.貍5特征謝函數(shù)例5.稀18用特壞征函紡數(shù)證炸明證明圈：通察過直蚊接計(jì)雅算可基得及所以從而永得到44PART01函數(shù)橫的基邁本概學(xué)念和私性質(zhì)主要內(nèi)容PART02函數(shù)屢的合保成和夜合成烏函數(shù)狀的性助質(zhì)PART03特殊徒函數(shù)PART04反函炭數(shù)PART05特征排函數(shù)PART06基數(shù)PART07不可止解問私題5.忌6基數(shù)定義5.憂14設(shè)A和B是兩良個(gè)集父合。哭從A到B如果臟存在舊一個(gè)率雙射習(xí)函數(shù)銷，則姓稱A和B是等位虹的或等勢(shì)屈的，記篇作乎，但讀作A等勢(shì)挪于B。例5.毛19設(shè)集躁合,試證畏明夕。解：未設(shè)傍，圾且對(duì)逆于墾，梢令壤。齒顯然滑，f是從N到郊的雙血射函勿數(shù)，逮因而疲有莊。46等勢(shì)訊（等年位）這里紋。對(duì)焦于有鈔限集繁絕不棚會(huì)有憲這種尿情況烤。這貞既是繪有限雅集和借無限婆集之散間本屈質(zhì)上焦的差排別，翁也是愉對(duì)無痰限集面的一戒種定喪義方碌法。5.值6基數(shù)定義5.槍15設(shè)A和B為兩改個(gè)集誦合。（1）如筑果畝，就脹稱A和B的基去數(shù)相齡等，嶄記為（2）如篩果存神在從A到B的單籠射，個(gè)就稱A的基罰數(shù)小枝于等矮于B的基顯數(shù)，充記為|A違|≤|B駕|。（3）如冷果扎且盲，營(yíng)就稱A的基壤數(shù)小曠于B的基譯數(shù)，暴記為|A甚|<米|B六|。任何曉兩個(gè)撲基數(shù)辟都可宏以比惕較大尊小。扮對(duì)于餓無限桿集的閥基數(shù)何，我局們規(guī)前定特戀殊的抵記號(hào)柜，令穩(wěn)，逮讀作阿列異夫零；令溜實(shí)數(shù)降集合R的基蘿數(shù)為揀，協(xié)讀作阿列消夫一。475.欣6基數(shù)例5.烘21設(shè)A為任薦意集船合，川則證明水：構(gòu)脹建函夠數(shù)惰，其罩中并是夾集合屑的雜特征譜函數(shù)慕。很幅明顯f為雙發(fā)射函標(biāo)數(shù)，善因此家有定理5.昆10設(shè)A，B，C為任滔意集密合。（1）（2）若息，則（3）若槳，稠，睡則485.飛6基數(shù)定理5.張11（康疤托定社理）（1）（2）對(duì)遣于任弊意集攔合A都有49康托殖定理5.燥6基數(shù)定義5.鑄17如果元集合A同自真然數(shù)駕集合梢或自境然數(shù)次集合貓的真速子集拆等勢(shì)西，則倉稱某是可蜻計(jì)數(shù)騙的或駱可數(shù)碼集；州否則歪稱A是不么可計(jì)中數(shù)的鋪或不礎(chǔ)可數(shù)紫集。從定冶義可昌以看味出，叼不是今所有淡無限魂集合軋都是俊可數(shù)亞的。飽例如翼，實(shí)西數(shù)集剩合就頃是不刮可數(shù)顏的。至此應(yīng)，我月們可偷以得羅出如蟲下的嬸結(jié)論撒。（1）和伴自然千數(shù)等峰勢(shì)的油無限蔬集的銀基數(shù)徒為（2）和穿實(shí)數(shù)梨集合書等勢(shì)匆的無晝限集葵的基色數(shù)為（3）505.賞6基數(shù)在計(jì)擾算機(jī)題科學(xué)草中，讀廣泛滿地應(yīng)恰用了梯本節(jié)雪的概庸念，有特別腸是可抓計(jì)算兩性理炸論?？拊诜呛跀?shù)值薯系統(tǒng)免中的烘元素酸與自茫然數(shù)貨之間棍，可僅以制窩定出禽一種拼雙射造函數(shù)余關(guān)系行。這哥樣就拐能夠攻把非嘴數(shù)值裳系統(tǒng)巨中的樣命題魂，變勒換成秀相對(duì)脂應(yīng)的爹自然跡數(shù)的教命題聚。因懲此，誦可以縣用證襖明自東然數(shù)袋系統(tǒng)射中相腐應(yīng)的尋命題兇，來滑間接肌地證泊明非舒數(shù)值北系統(tǒng)瓜中給嘆定的幫命題趕。51PART01函數(shù)刻的基寒本概醉念和臺(tái)性質(zhì)主要內(nèi)容PART02函數(shù)教的合另成和盲合成綠函數(shù)鳴的性水質(zhì)PART03特殊毛函數(shù)PART04反函固數(shù)PART05特征精函數(shù)PART06基數(shù)PART07不可褲解問萌題5.拳7*不可代解問現(xiàn)題現(xiàn)代夫數(shù)字塘計(jì)算究機(jī)已表經(jīng)應(yīng)辛用于膊社會(huì)疏生活弊的各愿?jìng)€(gè)方共面，工似乎嗽計(jì)算郊機(jī)無罷所不沉能，鼠若不襯考慮泥運(yùn)算炸時(shí)間療的限網(wǎng)制，箏對(duì)于廊任何稻問題氧，只混要能向把它美抽象傷成計(jì)囑算機(jī)縫可接處受的知輸入批形式研，就杏能用煉計(jì)算已機(jī)進(jìn)銹行求貧解。泰然后緣瑞，實(shí)貫際情沖況并告非如美此，舒可計(jì)害算性都理論衣告訴眼我們米：確叉實(shí)存毅在計(jì)館算機(jī)馳無法鞏解決英的問懸題，染盡管款他們勢(shì)可以續(xù)表示箱成計(jì)折算機(jī)灘可接勇受的州輸入當(dāng)形式心。以下易將粗碗淺的綱討論綿一下點(diǎn)可計(jì)姜算性短的問膏題，胳首先鹽利用涌可數(shù)找集的亂概念到證明葵不可護(hù)計(jì)算嘉的問躺題確谷實(shí)存俊在，撥然后迎給出演著名俱的不蛋可判軟定的倍停機(jī)亡問題潤(rùn)。535.膊7*不可拒解問劣題所謂勝不可屠解問情題是輸指使蹦用數(shù)固字計(jì)會(huì)算機(jī)緞無法都解決繳的問害題，邪在這吃里更帶具體困地說虎，就棉是指烈使用秀某種令程序俊設(shè)計(jì)訊語言射無法循解決盆的問掩題，濱即不鹿存在脹可為堵它們叢求解傷的程儀序。下面預(yù)將說是明不耐可解削問題籠確實(shí)拔存在序。基喉本方從法是屯：首先獸說明排程序秋的集鵲合是辦無限凍可數(shù)膝的，騎然后沿說明小問題管的集剝合是查無限烘不可警數(shù)的色，所愛以問誕題比楚程序有多得乳多，恨確實(shí)濫無法遠(yuǎn)為每見個(gè)問畢題都幸編寫柄出解繩決它教的程現(xiàn)序。假定垮所考耳察的壩程序調(diào)設(shè)計(jì)藥語言鍬是C語言叫（其紫他程腿序設(shè)屢計(jì)語盒言也驕可以影）。C語言基的字塞符集勝是有簽限集絡(luò)，設(shè)牧為妙。C語言細(xì)（源糊程序晃）是葛中的綱字符裁所構(gòu)蟻成的款有限垮字符蟻串。休設(shè)所儲(chǔ)有的方合法術(shù)的C程序淡組成濫集合C則翠，其忌中蓮是棒上辱有限添字符霉串的紋集合浴。由把于純是有延限集抬，而慶字符釀串長(zhǎng)粗度透，因?qū)４诵朗强刹鞌?shù)集鐮，所榆以C也是澆可數(shù)甲集。54不可聰解問坊題存鬧在性5.閘7*不可藏解問霜題任何惹問題殺都可虹以抽鉗象為州從輸福入到餃輸出肢的函迷數(shù)，調(diào)通過紋適當(dāng)暢的編即碼，刻輸入器和輸待出可窗以分魔別編富碼為偷兩個(gè)發(fā)自然豆數(shù)，怪所以移可以吉用自重然數(shù)警集N上的字函數(shù)辜來為保問題踩建模答。反剪過來部，N上的貴函數(shù)仆也都品是問務(wù)題。負(fù)于是體，可抵以用N上的匹函數(shù)霞的集詠合來慢為問師題的較集合慈建立蔑數(shù)學(xué)慢模型住。設(shè)自隆然數(shù)陪集N上的鵲函數(shù)鴿的集駐合是F，則由康映托定舒理可痰知F是不稼可數(shù)凈集。店因此C為可疑數(shù)，F(xiàn)為不溉可數(shù)強(qiáng)，焰，衫所以熊一定鳳存在坑某個(gè)講函數(shù)智（問園題）阿，計(jì)滔算它助的程求序是盛不存驕在的屯。55不可揪解問網(wǎng)題存該在性5.眾7*不可暗解問常題具有懸實(shí)際賓應(yīng)用糖價(jià)值忍的不斤可解潤(rùn)問題怒是否然存在絮？答綢案是例肯定憑的，黨著名械的停讀機(jī)問暫題就康是其挎中之告一。停機(jī)躬問題躁是不布可解多問題崗的經(jīng)奪典例小子，勤它的練不可撕解性氏是計(jì)航算機(jī)耕科學(xué)建中最盼著名辛的定學(xué)理之網(wǎng)一，登圖靈述在19葡36年證換明了贏停機(jī)循問題結(jié)的不惰可解覽性。謝停機(jī)廉問題虛的定涂義如壟下。輸入挨：一席個(gè)程辮序和鮮這個(gè)販程序準(zhǔn)要處為理的串一個(gè)下輸入定。輸出與：若初改程丑序在展該輸卻入下趁能終襖止，充則輸造出“疊是”點(diǎn)，否宿則，成輸出賭“否旋”。停機(jī)姓問題映是一壞個(gè)很瞧有意緊義的撕現(xiàn)實(shí)慨問題鬧，它勢(shì)的成偷功解誼決將構(gòu)對(duì)程悼序員雪的工騙作提午供很成大的崗幫助漿，比束如，直自動(dòng)揀判斷牧程序宅中是輝否有芹死循爆環(huán)等底等。厭但是黑，遺倚憾的歌是這維樣的葡檢測(cè)內(nèi)工具佳是構(gòu)蹲造不罩出來掙的56停機(jī)塊問題5.秘7*不可歸解問領(lǐng)題在證毫明停腦機(jī)問賤題的債不可莫解性嬌之前譯，首淚先注茅意，母不能楚通過更簡(jiǎn)單槍的運(yùn)掏行一灑個(gè)程窩序并辯觀察丈它的功行為傲來確鍋定在瓣給定跑的輸慮入下臺(tái)它是內(nèi)否能干終止僵。若抹程序鞋運(yùn)行制一段銳時(shí)間塘后停升止了若，則避可以浪簡(jiǎn)單凱的得棗出答剖案。攤但是啞若在渠運(yùn)行氧一段菜時(shí)間鄙之后還未停調(diào)止，東則無深法確屯定它盜是永剛不停釘機(jī)，婚還是商我們糞等待舅的時(shí)泉間不語夠。假定幫停機(jī)櫻問題躲是可范借的坐，有漸一個(gè)攤名為ha丹lt的解盒決停磁機(jī)問退題的C函數(shù)兄：in筋t是ha典lt白(c覆ha較r專*p王ro精g,省c杜ha楚r謠*i叔np冠ut茫)它有秋兩個(gè)櫻輸入毫：“摸*pr允og流”是一闖個(gè)C函數(shù)慮的源扶代碼魄字符師串，械“*in永pu夾t”是表碗示輸張入的葛字符兵串。災(zāi)如果隊(duì)函數(shù)惑“*pr批og寒”在給虜定的陣輸入籮“*in盡pu闖t”下能索終止拍，ha腹lt返回1，否巨則返齒回0。57停機(jī)坐問題5.酬7*不可會(huì)解問日題再給褲出一塑個(gè)簡(jiǎn)抵單的哥函數(shù)co汁nt脖ra粘ry如下禿。vo遵id附c稅on谷tr博ar邁y(菌ch撤ar睡*惱pr瞇og屠){證if隱(毒ha局lt吐(p服ro壟g,吸pr筑og芳))wh傻il湯e誕(1鴿);班}現(xiàn)將圾函數(shù)co泰nt栗ra胖ry本身腔作為旱輸入歡調(diào)用co晃nt墨ra戚ry，考勒察其青執(zhí)行捷過程寸。（1）若滅其中棵對(duì)ha殼lt的調(diào)托用返丙回1，則營(yíng)表明co券nt呼ra吳ry在對(duì)首自身濱運(yùn)行