第八章形式語言與自動(dòng)機(jī)第1頁，共70頁，2023年，2月20日，星期三4-1函數(shù)的概念定義4-1.1

設(shè)A和B是兩個(gè)任意集合，而f是A到B的二元關(guān)系，如果對(duì)于A中的每一個(gè)元素x，B中都存在惟一元素y，使得x,yf，則稱關(guān)系f是A到B的函數(shù)或映射。記為f：A→B或

A

B假如x,yf，x稱為自變?cè)蛳裨矗瑈稱為在f作用下x的像或函數(shù)值。x,yf，常記為y=f(x)，且記f(X)={f(x)|xX}。第2頁，共70頁，2023年，2月20日，星期三由函數(shù)的定義可以看出，函數(shù)是一種特殊的二元關(guān)系。若f是A到B的函數(shù)。它與一般二元關(guān)系的區(qū)別如下：①函數(shù)的定義中強(qiáng)調(diào)A中的每一個(gè)元素x有像，所以A=domf。這稱為像的存在性。函數(shù)的定義域是A，而不是A的某個(gè)真子集。②函數(shù)的定義中還強(qiáng)調(diào)像y是惟一的，一個(gè)x

A只能對(duì)應(yīng)唯一的一個(gè)y，稱做像的惟一性。像的惟一性可以描述為：設(shè)f(x1)=y1且f(x2)=y2。如果x1=x2，那么y1=y2。或者，如果y1≠y2，那么x1≠x2。第3頁，共70頁，2023年，2月20日，星期三

【例4.1.1】設(shè)N為自然數(shù)集合，下列N上的二元關(guān)系是否為函數(shù)？

f=x,2x|xN

g=x,2|xN

解：f和g都是從自然數(shù)集合N到自然數(shù)集合N的函數(shù)，常記為f：N→N，f(x)=2x和g：N→N，g(x)=2。第4頁，共70頁，2023年，2月20日，星期三

定義

設(shè)A和B是兩個(gè)任意的集合，f：A→B，A1A，集合f(x)|xA1稱為集合A1在f下的像，記為f(A1)。集合A在f下的像f(A)=f(x)|xA稱為函數(shù)f的像。顯然，函數(shù)f的像f(A)就是二元關(guān)系f的值域，即f(A)=ranf

B。有時(shí)也記作Rf，即Rf

={y|(x)(xA)∧(y=f(x))}，集合B稱為f的共域，ranf

亦稱為函數(shù)的像集合。

【例4.1.2】設(shè)f：1,2,3→a,b，

f=1,a,2,a,3,b，A1=1,2，試求A1在f下的像f(A1)和函數(shù)f的像f(A)。解：f(A1)=f(x)|xA1=f(1),f(2)=af(A)=f(x)|xA=f(1),f(2),f(3)=a,b第5頁，共70頁，2023年，2月20日，星期三

定義4-1.2

設(shè)函數(shù)f：A→B，g：C→D，若A=C，B=D且xA和xC，有f(x)=g(x)，則稱函數(shù)f和g相等，記為f=g。例如，函數(shù)f：N→N，f(x)=x3

函數(shù)g：1,2,3→N，g(x)=x3

雖然函數(shù)f和g有相同的表達(dá)式x3，但是它們是兩個(gè)不同的函數(shù)。如果把f和g看成二元關(guān)系，

fN×N，用列舉法表示為：

0,0,1,1,2,8,3,27,4,64,…g1,2,3×N，用列舉法表示為：

0,0,1,1,2,8,3,27

按二元關(guān)系相等的條件衡量，它們也是不等的。函數(shù)相等和二元關(guān)系相等是一致的。第6頁，共70頁，2023年，2月20日，星期三設(shè)A和B是兩個(gè)任意集合，A×B任意子集是A到B的二元關(guān)系，但不一定是A到B的函數(shù)。當(dāng)A和B是有限集時(shí)，A到B的二元關(guān)系共有2|A||B|個(gè)，A到B的函數(shù)有多少個(gè)呢？以下研究這個(gè)問題。設(shè)A和B是兩個(gè)任意的有限集合，分別由m個(gè)和n個(gè)不同的元素，由于從A到B的任意一個(gè)函數(shù)的定義域是A，在這些函數(shù)中每一個(gè)恰有m個(gè)序偶。另外任何元素xA，可以有Y的n個(gè)元素中的任何一個(gè)作為他的像，故共有nm個(gè)不同的函數(shù)。f|f：A→B是A到B的所有函數(shù)構(gòu)成的集合，常記為BA。讀作B上A。第7頁，共70頁，2023年，2月20日，星期三

【例4.1.3】設(shè)A=1,2,3，B=a,b，求BA。

解：由A到B的函數(shù)有以下8個(gè)：

f0=1,a,2,a,3,af1=1,a,2,a,3,bf2=1,a,2,b,3,af3=1,a,2,b,3,bf4=1,b,2,a,3,af5=1,b,2,a,3,bf6=1,b,2,b,3,af7=1,b,2,b,3,bBA=

f0,f1,f2,f3,f4,f5,f6,f7

A到B的函數(shù)共8個(gè)，8=23=|B||A|。當(dāng)A和B都是有限集時(shí)，這個(gè)結(jié)論可以推廣。一般地說，若|A|=m，|B|=n，則|BA|=nm=|B||A|。第8頁，共70頁，2023年，2月20日，星期三定義4-1.3

設(shè)f：A→B，若f的值域ranf=B，即B的每一個(gè)元素是A中一個(gè)或多個(gè)元素的象點(diǎn)，則稱這個(gè)映射f為滿射（或到上映射）。設(shè)f是A到B的函數(shù)，由定義不難看出，如果yB，都存在xA，使得f(x)=y，則f是滿射函數(shù)。例如，A=a,b,c,d，B=1,2,3，f是由A到B的函數(shù)，定義為：f=a,1,b,1,c,3,d,2

因?yàn)閞anf=f(A)=1,2,3=B，所以f是滿射。圖4.1.1是f的示意圖。由圖4.1.1可得出如下的結(jié)論：若A、B是有限集，f：A→B是滿射，在f的示意圖中，B中每個(gè)元素至少是一個(gè)有向邊的終點(diǎn)且|A|≥|B|第9頁，共70頁，2023年，2月20日，星期三

定義4-1.4設(shè)f：A→B，若yranf，存在惟一的xA，使得f(x)=y，則稱f為入射。即A中沒有兩個(gè)元素有相同的象，則稱這個(gè)映射為入射（或一對(duì)一映射）。設(shè)f是A到B的函數(shù)，由定義不難看出，如果對(duì)于x1A，x2A，f(x1)=y1，f(x2)=y2。①當(dāng)y1=y2時(shí)，一定有x1=x2，則f是入射函數(shù)。②當(dāng)x1≠x2時(shí)，一定有y1≠y2，則f是入射函數(shù)。第10頁，共70頁，2023年，2月20日，星期三【例4.1.4】設(shè)f：a,b→2,4,6，定義

f=a,2,b,6函數(shù)f是否為入射？f是否為滿射？

解：因?yàn)閒(a)=2，f(b)=6，所以f是入射。因?yàn)閒的值域ranf=2,6≠2,4,6，所以f不是滿射。圖4.1.2是f的示意圖。由圖4.1.2可得出如下的結(jié)論：若A、B是有限集，f：A→B是入射，在f的示意圖中，B中每個(gè)像點(diǎn)是且僅是一條有向邊的終點(diǎn)且|A|≤|B|第11頁，共70頁，2023年，2月20日，星期三

定義4-1.5

設(shè)f：A→B，若f既是入射，又是滿射，則稱f為雙射。

例如：A=1,2,3，B=a,b,c，f=1,a,2,c,3,b，f是A到B的雙射函數(shù)，圖4.1.3是f的示意圖。第12頁，共70頁，2023年，2月20日，星期三若A、B是有限集，f：A→B是雙射，則f一定是滿射。故B中每個(gè)元素至少是一個(gè)有向邊的終點(diǎn)；f也是單射，故B中每個(gè)像點(diǎn)是且僅是一條有向邊的終點(diǎn)。所以，在雙射函數(shù)的示意圖中，B中每一個(gè)元素是且僅是一條有向邊的終點(diǎn)。若A、B是有限集，f：A→B是雙射，則f一定是滿射，所以|A|≥|B|；f也是入射，所以|A|≤|B|。于是|A|=|B|。第13頁，共70頁，2023年，2月20日，星期三【例4.1.5】判斷下列函數(shù)是否為入射、滿射或雙射。為什么？⑴f：R→R，f(x)=-

x2+2x-1，其中，R是實(shí)數(shù)集合⑵f：I＋→R，f(x)=lnx，其中，I＋是正整數(shù)集合⑶f：R→I，f(x)=[x]，其中，[x]是不大于x的最大整數(shù)⑷f：R→R，f(x)=2x+1⑸f：R＋→R＋，f(x)=，其中，R＋是正實(shí)數(shù)集合第14頁，共70頁，2023年，2月20日，星期三解：⑴f(x)=-x2+2x-1=-(x-1)2，f是開口向下的拋物線，不是單調(diào)函數(shù)，所以不是入射。在x=1處取得極大值0，所以f不是滿射。f既不是入射也不是滿射。⑵f是單調(diào)增加函數(shù)。因此是入射，但不是滿射，因?yàn)閞anf=ln1，ln2，…R⑶f是滿射，但不是入射，例如f(1.5)=[1.5]=1，而f(1.2)=[1.2]=1⑷f是單調(diào)增加函數(shù)且ranf=R，它既是入射，也是滿射，因此它是雙射。⑸f不是入射也不是滿射。當(dāng)x→0時(shí)，f(x)→＋∞；而當(dāng)x→＋∞時(shí)，f(x)→＋∞。在x=1處函數(shù)f(x)取得極小值f(1)=2。因此它既不是入射也不是滿射。第15頁，共70頁，2023年，2月20日，星期三

定理4-1.1

令X和Y為有限集，若X和Y的元素個(gè)數(shù)相同，即|X|=|Y|，則f：X→Y是入射的，當(dāng)且僅當(dāng)他是一個(gè)滿射。證明：a若f是入射，則|X|=|f(X)|，因此|f(X)|=|Y|，從f的定義我們有f(X)

Y，而|f(X)|=|Y|，又因?yàn)閨Y|是有限的，故f(X)=Y，因此f是一個(gè)入射推出f是滿射。b若f是一個(gè)滿射，根據(jù)滿射的定義f(X)

=Y，于是|X|=|Y|=|f(X)

|。因?yàn)閨X|=|f(X)

|和|X|是有限的，故f是一個(gè)入射，因此f是滿射推出f是一個(gè)入射。這個(gè)定理必須在有限集情況下才能成立，在無限集上不一定有效，如f：I→I是f(X)=2x，在這種情況下整數(shù)映射到偶整數(shù)，顯然這是一個(gè)入射，但不是滿射。第16頁，共70頁，2023年，2月20日，星期三4-2逆函數(shù)和復(fù)合函數(shù)定理4.2.1設(shè)f：A→B是雙射函數(shù)，則f的逆關(guān)系fC是B→

A的雙射函數(shù)。

證明：先證逆關(guān)系fC是B到A的函數(shù)。因?yàn)閒是函數(shù)，所以fC是B到A的二元關(guān)系。以下證明B到A的二元關(guān)系fC是B到A的函數(shù)。⑴yB，因?yàn)閒：A→B是滿射，所以，yB必有xA，使x,yf，由逆關(guān)系的定義得，y,xfC。⑵設(shè)y1,x1fC，y2,x2fC，y1=y2，由逆關(guān)系的定義知，x1,y1f，x2,y2f，因?yàn)閒是入射，所以x1=x2

故fC是B到A的函數(shù)。第17頁，共70頁，2023年，2月20日，星期三再證fC是滿射。因?yàn)閞anfC=domf。又因?yàn)閒是A到B的函數(shù)，所以domf=A。于是ranfC=A。所以fC是B到A的滿射。最后證fC是入射。設(shè)y1,x1fC，y2,x2fC且x1=x2，由逆關(guān)系的定義有x1,y1f，x2,y2f，又因?yàn)閒是函數(shù)，必有y1=y2。所以fC是入射。這就證明了fC是雙射函數(shù)。第18頁，共70頁，2023年，2月20日，星期三

定義4.2.1設(shè)f：A→B是雙射函數(shù)，稱B→A的雙射函數(shù)fC為f的逆函數(shù)，記為：f-1。例如，設(shè)A=1,2,3，B=a,b,c。

f=1,a,2,c,3,b

顯然，f是A到B的雙射函數(shù)。f的逆關(guān)系

fC=a,1,c,2,b,3是B到A的雙射函數(shù)，記為f-1，f–1是f的逆函數(shù)。又如g=1,a,2,a,3,b也是A到B的函數(shù)，但g不是滿射，也不是入射，因而不是雙射。逆關(guān)系

gC=a,1,a,2,b,3不是B到A的函數(shù)。第19頁，共70頁，2023年，2月20日，星期三二元關(guān)系的復(fù)合關(guān)系定義為：設(shè)X，Y，Z是集合，R

X×Y，SY×Z，集合x,zxX∧zZ∧(y)(yY∧x,yR∧y,zS)叫做R和S的復(fù)合關(guān)系。記為R°S。即

R°S=x,zxX∧zZ∧(y)(yY∧x,yR∧y,zS)

將R°S=x,zxX∧zZ∧(y)(yY∧x,yR∧y,zS)記為S°R，即

S°R=x,zxX∧zZ∧(y)(yY∧x,yR∧y,zS)前者叫做R和S的復(fù)合關(guān)系。為了與前者區(qū)別，后者叫做二元關(guān)系S在二元關(guān)系R左邊的復(fù)合關(guān)系，簡(jiǎn)稱為S和R的左復(fù)合關(guān)系。第20頁，共70頁，2023年，2月20日，星期三前面已經(jīng)講過，函數(shù)是滿足一定條件的二元關(guān)系，當(dāng)然它可以進(jìn)行左復(fù)合運(yùn)算。函數(shù)的左復(fù)合關(guān)系描述為：設(shè)f：A→B，g：C→D，若f(A)C，集合

g°f=a,d|aA∧dD∧(b)(bB∧a,bf∧b,dg)=a,d|aA∧dD∧(b)(bB∧b=f(a)∧d=g(b))

定義4.2.2

設(shè)f：A→B，g：C→D，若f(A)C，集合

g°f

=a,d|aA∧dD∧(b)(bB∧b=f(a)∧d=g(b))稱函數(shù)g在函數(shù)f左邊可復(fù)合。記為g°f。第21頁，共70頁，2023年，2月20日，星期三定理4.2.2

兩個(gè)函數(shù)的復(fù)合是一個(gè)函數(shù)。證明設(shè)g：W→Z，f：X→Y為左復(fù)合，即f(X)W。a對(duì)于任意xX，因?yàn)閒為函數(shù)，故必有唯一的序偶x,y使y=f(x)成立，而f(x)f(X)即f(x)W，又因?yàn)間是函數(shù)，故必有唯一序偶y,z使z=g(y)成立，根據(jù)復(fù)合定義，x,zg°f，即X中每個(gè)x對(duì)應(yīng)Z中某個(gè)z。第22頁，共70頁，2023年，2月20日，星期三b假定g°f中包含序偶x,z1和x,z2且z1≠z2，這樣在Y中必存在y1和y2，使得在f中有x,y1和x,y2在g中有y1,z1和y2,z2。因?yàn)閒是一個(gè)函數(shù)，故y1=y2。于是g中有y,z1和y,z2，但g是一個(gè)函數(shù)，故z1=z2，即每個(gè)xX只能有唯一的x,zg°f

。由a，b可知g°f

是一個(gè)函數(shù)。在定義4-2.2中，當(dāng)W=Y時(shí)，則函數(shù)f：X→Y，g：Y→Z。

g°f

=x,z|xX∧zZ∧(y)(yY∧y=f(x)∧z=g(y))稱為復(fù)合函數(shù)，或稱g°f

為g對(duì)f的左復(fù)合。根據(jù)復(fù)合函數(shù)的定義，顯然有g(shù)°f(x)=g(f(x))。第23頁，共70頁，2023年，2月20日，星期三定理

設(shè)f：A→B，g：C→D，f(A)C，則函數(shù)g在函數(shù)f左邊的復(fù)合關(guān)系g°f是A到D的函數(shù)。

證明：aA，因?yàn)閒是A到B函數(shù)，必存在惟一的bB，使得a,bf。即b=f(a)。而b=f(a)f(A)C，故bC。又因?yàn)間是C到D函數(shù)，必存在惟一的dD，使得b,dg。即d=g(b)。故由定義4.2.2，a,dg°f，即g°f(a)=d。所以g°f是A到D的函數(shù)。第24頁，共70頁，2023年，2月20日，星期三

定義

設(shè)f：A→B，g：C→D，若f(A)C，函數(shù)g在函數(shù)f左邊的復(fù)合關(guān)系g°f稱為函數(shù)g在函數(shù)f左邊可復(fù)合函數(shù)，簡(jiǎn)稱為g和f的左復(fù)合函數(shù)或g和f的復(fù)合函數(shù)。仍然記為g°f。g°f是A到D的函數(shù)。推論設(shè)f：A→B，g：C→D，f(A)C，則g°f(x)=g(f(x))。證明：由前面定理的證明過程可以看出，aA，b=f(a)且d=g(b)，g°f(a)=d，于是，g°f(a)=d=g(b)=g(f(a))。所以，g°f(x)=g(f(x))。第25頁，共70頁，2023年，2月20日，星期三

定理4.2.3設(shè)f：A→B，g：B→C，g°f：A→C。⑴如果f和g都是滿射，則g°f也是滿射。⑵如果f和g都是入射，則g°f也是入射。⑶如果f和g都是雙射，則g°f也是雙射。

證明：⑴cC，因?yàn)間是B到C的滿射，所以cC必有bB，使c=g(b)。又因?yàn)閒是A到B滿射，所以bB必有aA，使b=f(a)。于是，g°f(a)=g(f(a))=g(b)=c，所以g°f是滿射。⑵設(shè)a1A且a2A，a1≠a2，因?yàn)閒是A到B入射，所以f(a1)≠f(a2)，f(a1)B，f(a2)B。又因?yàn)間是B到C入射，所以g(f(a1))≠g(f(a2))，即g°f(a1)≠g°f(a2)，故g°f是入射。⑶f和g都是雙射，則f和g都是滿射和入射，由⑴和⑵知，g°f是滿射和入射，故g°f是雙射。第26頁，共70頁，2023年，2月20日，星期三

定義4.2.3函數(shù)f：A→B叫做常函數(shù)，如果存在某個(gè)y0

Y，對(duì)于每個(gè)x

X都有f(x)

=y0，即f(X)=

{y0}

。

定義4.2.4如果Ix={<x,x>|xX}則稱函數(shù)Ix：X→X為恒等函數(shù)。定義設(shè)A是任意集合，A′A，xA，定義：A→0,1如下：叫做A′的特征函數(shù)。設(shè)R是A上的等價(jià)關(guān)系，[x]R是x形成的R等價(jià)類，A/R是A關(guān)于R的商集，f：A→A/R，定義為：f(x)=[x]R，稱f為A到商集A/R的自然函數(shù)或自然映射。第27頁，共70頁，2023年，2月20日，星期三在二元關(guān)系的復(fù)合運(yùn)算，介紹了復(fù)合運(yùn)算性質(zhì)。這些性質(zhì)有：設(shè)RX×Y，SY×Z，T

Z×W。①(R°S)°T=R°(S°T)②R°IY=IX°R=R③R°RC=IX，RC°R=IY④(R°S)C=SC°RC

函數(shù)的復(fù)合運(yùn)算也有類似的性質(zhì)。以下幾個(gè)定理介紹了這些性質(zhì)。第28頁，共70頁，2023年，2月20日，星期三

定理

設(shè)f：A→B，g：B→C，h：C→D，則

h°(g°f)=(h°g)°f

證明：由定義可知，

g°f：A→C，h°(g°f)：A→D。類似地h°g：B→D，(h°g)°f：A→D。令f(x)=y，g(y)=z，h(z)=u。由前面定理可知，

g°f(x)=g(f(x))=g(y)=z，h°g(y)=h(g(y))=h(z)=uh°(g°f)(x)=h°((g°f)(x))=h(z)=u

=h°g(y)=h°g(f(x))=(h°g)°f(x)所以h°(g°f)=(h°g)°f

因?yàn)楹瘮?shù)的復(fù)合運(yùn)算滿足結(jié)合律，所以可略去函數(shù)復(fù)合運(yùn)算中的括號(hào)，即用h°g°f記h°(g°f)=(h°g)°f，另外，還可以定義函數(shù)的冪：f2=f°f，f3=f°f°f，……第29頁，共70頁，2023年，2月20日，星期三

【例4.2.1】設(shè)R是實(shí)數(shù)集合，下面是R到R的函數(shù)f(x)=x+2，g(x)=x-2，h(x)=3x

先求g和f的復(fù)合函數(shù)g°f，h和g的復(fù)合函數(shù)h°g。再驗(yàn)證h°(g°f)=(h°g)°f

解：顯然h°(g°f)：R→R(h°g)°f

：R→Rg°f(x)=g(f(x))=g(x+2)=(x+2)-2=xh°g(x)=h(g(x))=h(x-2)=3(x-2)=3x-6h°(g°f)(x)=h°(g°f(x))=h(x)=3x(h°g)°f(x)=h°g(f(x))=h°g(x＋2)=3(x＋2)-6=3x所以

h°(g°f)(x)=(h°g)°f(x)

故

h°(g°f)=(h°g)°f

第30頁，共70頁，2023年，2月20日，星期三定理4.2.4設(shè)f：A→B，IA是A上的恒等函數(shù)，IB是B上的恒等函數(shù)，則IB°f=f°IA=f

證明：先證f°IA=f

f°IA：A→B，

又f°IA(x)=f°(IA(x))=f(x)

所以

f°IA=f

類似地可以證明IB°f=f第31頁，共70頁，2023年，2月20日，星期三定理4.2.5設(shè)f：A→B為雙射函數(shù)，f－1：B→A是f的逆函數(shù)，則f-1°f=IA，f°f-1=IB

證明：先證明f-1°

f=IA

f-1°f：A→A。IA：A→A。

xA，設(shè)f(x)=y，則f-1(y)=x。

f-1°

f(x)=f-1(f(x))=f-1(y)=x=IA(x)所以

f-1°

f=IA

類似地可以證明f°f-1=IB第32頁，共70頁，2023年，2月20日，星期三

【例4.2.2】設(shè)

A=0,1,2，B=a,b,c，f：A→B，定義為：f=0,c,1,a,2,b，求f–1、f-1°f和f°f-1，驗(yàn)證

f-1°f=IA和f°f-1=IB

解：f-1=

a,1,b,2,c,0f-1°f=0,0,1,1,2,2f°f-1=a,a,b,b,c,cf-1°f：A→A，IA：A→Af-1°f(0)=0=IA(0)，f-1°f(1)=1=IA(1)，f-1°f(2)=2=IA(2)所以f-1°

f=IAf°f-1：B→B，IB：B→B

f°f-1(a)=a=IB(a)，f°f-1(b)=b=IB(b)，

f°f-1(c)=c=IB(c)所以f°f-1=IB第33頁，共70頁，2023年，2月20日，星期三定理4.2.6設(shè)f：A→B，是一一對(duì)應(yīng)的函數(shù)，則(f-1)-1=f。

證明：

a因f：A→B是一一對(duì)應(yīng)的函數(shù)，故f-1：B→A也是一一對(duì)應(yīng)的函數(shù)，因此(f-1)-1

：A→B又為一一對(duì)應(yīng)的函數(shù)，顯然domf=dom(f-1)-1=AbxA

f：x→f(x)

f-1

：f(x)

→x

(f-1)-1

：x→f(x)

。由a，b可知(f-1)-1=f。第34頁，共70頁，2023年，2月20日，星期三定理4.2.7

設(shè)f：A→B，g：B→C且

f和g均為雙射函數(shù)，則

(g°f)-1=f-1°g-1

證明：⑴因?yàn)閒和g均為雙射函數(shù)，f-1和g-1存在且

f-1：B→A，g-1：C→B所以

f-1°g-1：C→A

另一方面，g°f：A→C。所以

(g°f)-1：C→A。⑵zC，因?yàn)間為雙射函數(shù)，yB

使g(y)=z，又因?yàn)閒為雙射函數(shù)，xA，使f(x)=y，于是，g°f(x)=g(f(x))=g(y)=z故

(g°f)-1(z)=x。另一方面，f-1(y)=x，g-1(z)=y。于是，f-1°g-1(z)=f-1°(g-1(z))=f-1(y)=x

所以(g°f)-1=f-1°

g-1第35頁，共70頁，2023年，2月20日，星期三4-3特征函數(shù)與模糊子集定義4.3.1令E是全集，A是E的子集，AE，由定義的函數(shù)：E→{0,1}，稱為集合A的特征函數(shù)。第36頁，共70頁，2023年，2月20日，星期三設(shè)A和B是全集E的任何兩個(gè)子集，對(duì)于xE，特征函數(shù)有如下一些性質(zhì)。第37頁，共70頁，2023年，2月20日，星期三對(duì)于特征函數(shù)進(jìn)行推廣可以導(dǎo)出模糊子集的概念。設(shè)E={x1,x2,…,xn},我們可以將E的任何一個(gè)子集A表示為：當(dāng)

我們將的取值范圍不局限于0和1，而是取0和1之間的任何數(shù)，例如

其中0.2，0.3.0.8…..分別稱為該集合中對(duì)應(yīng)元素的隸屬程度。第38頁，共70頁，2023年，2月20日，星期三定義4.3.2給定論域E，指定E上的一個(gè)模糊子集是指對(duì)任意xE

都有一個(gè)隸屬程度與它對(duì)應(yīng)，稱為的隸屬函數(shù)。從模糊子集的定義可以看出，當(dāng)只取0，1兩值時(shí)，便成為普通子集。第39頁，共70頁，2023年，2月20日，星期三4-4基數(shù)的概念定義4.4.1給定集合A的后繼集定義為集合：A+=A∪{A}

。若A為空集?

，則后繼集為?+，(?+)+,((?+)+)+,….這些集合可寫成如下形式：?∪{?}，?∪{?}∪{?∪{?}},?∪{?}∪{?∪{?}}∪{?∪{?}∪{?∪{?}}},………..可簡(jiǎn)化為{?}，{?∪{?}}，{?∪{?}∪{?∪{?}}},………..若我們命名集合?為0，那么， ?+=0+={?}=1 1+={?∪{?}}=2 2+={?∪{?}∪{?∪{?}}}=3這就得到了自然數(shù)集合{0,1,2,3,…….}這個(gè)集合也可以概括為如下公理形式（G.Peano公理）。第40頁，共70頁，2023年，2月20日，星期三G.Peano公理?1、0N(其中0=?)。2、如果nN，那么n+N(其中n+=n∪{n}).3、如果一個(gè)子集SN具有性質(zhì)：a0S。b如果nS，有n+S，則S=N。性質(zhì)3稱極小性質(zhì)，它指明了自然數(shù)系統(tǒng)的最小性，即自然數(shù)系統(tǒng)是滿足公理1和2的最小集合。第41頁，共70頁，2023年，2月20日，星期三定義4.4.2給定兩個(gè)集合P與Q，如果我們對(duì)P中每個(gè)不同元素，與Q中每個(gè)不同元素，可以分別兩兩成對(duì)，那么我們說P的元素與Q的元素間存在著一一對(duì)應(yīng)。定義4.4.3當(dāng)且僅當(dāng)集合A的元素與集合B的元素之間存在著一一對(duì)應(yīng)，集合A與集合B稱為是等勢(shì)的(或稱同濃的)。記作A～B。關(guān)于等勢(shì)的定義：設(shè)A和B是集合，如果存在A到B的雙射函數(shù)，則稱集合A和集合B等勢(shì)。記作A~B。設(shè)A和B是有限集合，A~B，則存在A到B的雙射函數(shù)，根據(jù)雙射的性質(zhì)，|A|=|B|。即A和B中元素的個(gè)數(shù)相等。第42頁，共70頁，2023年，2月20日，星期三

【例4.4.1】設(shè)I是整數(shù)集，N是自然數(shù)集。試證明I~N。證明：設(shè)f：I→N，定義為：按照這個(gè)定義將I中的元素如下排列與N中的元素對(duì)應(yīng)：

I0-11-22-33-44…

↓

↓

↓

↓

↓

↓

↓

↓

↓

N012345678…第43頁，共70頁，2023年，2月20日，星期三以下證明f是I到N的雙射函數(shù)。任取nN，若n是偶數(shù)，有I且≥0，使f()=2=n；若n是奇數(shù)，有I且＜0，使f()=-2()-1=n。

所以f是滿射。第44頁，共70頁，2023年，2月20日，星期三若有n1I，n2I且n1≠n2。分下列4種情況討論：⑴假定n1≥0且n2≥0，則f(n1)-f(n2)=2n1-2n2=2(n1-n2)≠0，所以f(n1)≠f(n2)。⑵假定n1＜0且n2＜0，則f(n1)-f(n2)=(-2n1-1)-(-2n2-1)=2(n2-n1)≠0，所以f(n1)≠f(n2)。⑶假定n1≥0且n2＜0，則f(n1)-f(n2)=2n1-(-2n2-1)=2(n1＋n2)+1≠0(因?yàn)橐粋€(gè)偶數(shù)與1的和或差永遠(yuǎn)不能為0)，所以f(n1)≠f(n2)。⑷假定n1＜0且n2≥0，類似⑶，同樣有f(n1)≠f(n2)。所以f是入射。于是f是I到N的雙射函數(shù)。

I~N第45頁，共70頁，2023年，2月20日，星期三定理4.4.1

設(shè)A，B，C是任意三個(gè)集合。則集合的等勢(shì)有下列性質(zhì)。（在集合族上等勢(shì)關(guān)系是一個(gè)等價(jià)關(guān)系。）⑴

自反性:即A~A。⑵

對(duì)稱性:即若A~B，則B~A。⑶

傳遞性:即若A~B，B~C，則A~C。證明：僅證明⑶。因?yàn)锳~B，B~C，由等勢(shì)的定義知，存在雙射函數(shù)f：A→B和雙射函數(shù)g：B→C，因?yàn)間°f是A到C的雙射函數(shù)。所以A~C。

第46頁，共70頁，2023年，2月20日，星期三定義4.4.4

如果集合A與集合0,1,2,…,n-1(n是某個(gè)自然數(shù))等勢(shì)，即存在雙射函數(shù)，則稱A為有限集，如果集合A不是有限集，則稱A為無限集。定理4.4.2

自然數(shù)集N是無限集。證明：nN，設(shè)f是任意集合0,1,2,…,n-1到N的函數(shù)，令k=1+maxf(0),f(1),…,f(n-1)，kN。x0,1,2,…,n-1,f(x)≠k。因此，f不是從0,1,2,…,n-1到N的滿射函數(shù)。當(dāng)然不是從0,1,2,…,n-1到N的雙射函數(shù)。因?yàn)閚和f都是任意的，所以，自然數(shù)集N不是有限集，而是無限集。第47頁，共70頁，2023年，2月20日，星期三定義4.4.5將相互等勢(shì)的集合歸于同一類，對(duì)這樣的每一類集合規(guī)定一個(gè)記號(hào)，稱這個(gè)記號(hào)是這一類集合中每一個(gè)集合的基數(shù)或者勢(shì)。集合A的勢(shì)記為K[A](或或|A|)。根據(jù)定義，任何等勢(shì)的集合具有相同的基數(shù)；而不等勢(shì)的集合基數(shù)也不相同。規(guī)定有限集的勢(shì)是該集合中元素的個(gè)數(shù)，空集的勢(shì)為0?？梢钥吹?，如果兩個(gè)集合能夠建立雙射函數(shù)，則兩個(gè)集合元素間必一一對(duì)應(yīng)，從基數(shù)的定義可以知道，該兩集合應(yīng)具有相同的基數(shù)。第48頁，共70頁，2023年，2月20日，星期三4-5可數(shù)集與不可數(shù)集定義4.5.1設(shè)N是自然數(shù)集合，凡與N等勢(shì)的集合稱為可數(shù)集或可列集，也叫無限可數(shù)集或無限可列集。通常記可數(shù)集的基數(shù)為0。讀作“阿列夫零”。根據(jù)此定義，可知自然數(shù)集合N和整數(shù)集I都是可數(shù)集，|N|=|I|=0。有時(shí)我們把有限集和可數(shù)集統(tǒng)稱為至多可數(shù)集。第49頁，共70頁，2023年，2月20日，星期三定理4.5.1

集合A是可數(shù)集的充分必要條件是A的全部元素可以排成一個(gè)無限序列A

={a0,a1,…}。證明：設(shè)A是可數(shù)集，下證A的全部元素可以排成一個(gè)無限序列a0,a1,…。因?yàn)锳是可數(shù)集，由可數(shù)集的定義有N~A。由等勢(shì)的定義知，存在N到A的雙射函數(shù)。設(shè)f：N→A是雙射函數(shù)，令an=f(n)A。

則A可寫成一個(gè)無限序列a0,a1,…。設(shè)A的全部元素可以排成一個(gè)無限序列a0,a1,…，下證A是可數(shù)集。因?yàn)锳的全部元素可以排成一個(gè)無限序列a0,a1,…，所以可定義N到A一個(gè)雙射函數(shù)f(n)=an，故A是可數(shù)集。該定理說明一個(gè)能用自然數(shù)編號(hào)的無限集是可數(shù)集。第50頁，共70頁，2023年，2月20日，星期三

【例4.5.1】設(shè)N為自然數(shù)集，證明集合

M=x|x=10n∧nN是可數(shù)集。證明：令ai=10i，則集合M可用列舉法表示為：

M=0,10,20,30,…

=

a0,a1,…

M是能用自然數(shù)編號(hào)的無限集，所以M是可數(shù)集。定理

有限集不與它的任何真子集等勢(shì)。證明：設(shè)A為任一有限集，BA，則C=A-B≠?。

|B|=|A|-|C|＜|A|，即|A|≠|(zhì)B|，根據(jù)雙射的性質(zhì)，A與B之間不存在雙射函數(shù)。A與B不等勢(shì)。第51頁，共70頁，2023年，2月20日，星期三定理4.5.2

任何無限集必含有可數(shù)子集。證明：設(shè)A為無限集，則A≠?，在A中任取一個(gè)元素，記為a0。

因?yàn)榧螦是無限集，顯然，集合A-a0不空。再從A-a0中取一個(gè)元素a1。

同樣A-a0,a1不空?？梢岳^續(xù)做下去，從A中取出一系列元素a0,a1,……

令A(yù)′=a0,a1,…A′是可數(shù)集。顯然A′A。第52頁，共70頁，2023年，2月20日，星期三定理4.5.3無限集必與其某個(gè)真子集等勢(shì)。證明：首先證明在任何一個(gè)無限集A中，一定能取出一系列元素a1,a2,…。在A中任取一個(gè)元素，記為a1。

因?yàn)榧螦是無限集，顯然，集合A-a1不空。再從A-a1中取一個(gè)元素，記為a2。

同樣，集合A-a1,a2不空。繼續(xù)做下去，可從A中取出一系列元素a1,a2,…。記?=A-a1,a2,…，令?=a2,a3,…∪?，顯然?A。

f：A→?，定義為：

f(ai)=ai+1i=1,2,…

f(x)=x

x?

顯然，f是A到?的雙射。A~?可以給出有限集與無限集的另外一個(gè)定義如下：不能和自己的任何真子集等勢(shì)的集合稱作有限集。能與自己的某個(gè)真子集等勢(shì)的集合稱作無限集。第53頁，共70頁，2023年，2月20日，星期三這個(gè)定理可以用圖4.5.1所示。設(shè)線段AB，其上有線段CD，則線段AB與CD上所有的點(diǎn)，可以做成一一對(duì)應(yīng)。做法：把CD移出與AB平行，聯(lián)AC、BD延長(zhǎng)交于G，則AB上任意點(diǎn)E與G的聯(lián)線EG必與CD相交于F。反之，CD上任意點(diǎn)F，與G的聯(lián)線FG延長(zhǎng)必交AB于E，上述E，F(xiàn)的對(duì)應(yīng)做法，即說明AB～CD。ABCDABCDGFE圖4.5.1第54頁，共70頁，2023年，2月20日，星期三定理4.5.4

可數(shù)集的無限子集仍為可數(shù)集。證明：設(shè)A為可數(shù)集，它的元素編號(hào)如下：

a0,a1,…,an,…

任取A的無限子集B，在A的元素中，從a0開始逐個(gè)檢查，將遇到的第一個(gè)B的元素記為，第二個(gè)記為，…。因?yàn)锽是無限集，所以B中的元素可排為，，…，，…。因此B是可數(shù)集。第55頁，共70頁，2023年，2月20日，星期三定理4.5.5

可數(shù)個(gè)兩兩不相交可數(shù)集的并集仍為可數(shù)集。證明：設(shè)可數(shù)個(gè)可數(shù)集分別為：

A0=

a00,a01,a02,a03,a04,…A1=

a10,a11,a12,a13,a14,…A2=

a20,a21,a22,a23,a24,…A3=

a30,a31,a32,a33,a34,………p+q=h稱為元素apq(p,q=0,1,2,…)的高度。對(duì)上述集合的所有元素，先按高度大小編號(hào)，在同一高度中按q的值由小到大編號(hào)。這樣就可以把并集A0∪A1∪A2∪…中所有的元素按下列順序(箭頭所指順序)編成一列：第56頁，共70頁，2023年，2月20日，星期三

a00，a01，a02，a03，a04,…↓

↗

↗

↗

↗a10，a11，a12，a13，a14,…

↗

↗

↗a20，a21，a22，a23，a24,…

↗

↗

a30，a31，a32，a33，a34,……

將各斜線上的元素排列為

a00;a10,a01;a20,a11,a02;…所以并集A=A0∪A1∪A2∪…是可數(shù)集。第57頁，共70頁，2023年，2月20日，星期三

【例4.5.2】在直角坐標(biāo)系下，兩坐標(biāo)x，y均為整數(shù)的點(diǎn)(x,y)稱為格點(diǎn)。證明全體格點(diǎn)構(gòu)成可數(shù)集。證明：對(duì)每個(gè)固定的整數(shù)n，An=n,m|m是整數(shù)中的元素可排列為：

n,0，n,1，n,-1，n,2，n,-2，…

所以An是可數(shù)集。顯然，右半平面上的格點(diǎn)全體構(gòu)成的集合就是并集A0∪A1∪A2∪…，這是可數(shù)個(gè)可數(shù)集的并，因而是可數(shù)集。左半平面上的格點(diǎn)全體構(gòu)成的集合就是并集A-1∪A-2∪A-3∪…，這也是可數(shù)個(gè)可數(shù)集的并，因而是可數(shù)集。因?yàn)榭蓴?shù)集的并是可數(shù)集，所以平面上的格點(diǎn)全體構(gòu)成的集合A0∪A1∪A2∪…∪A-1∪A-2∪A-3∪…是可數(shù)集。第58頁，共70頁，2023年，2月20日，星期三定理4.5.6

設(shè)自然數(shù)集合N，則N×N是可數(shù)集。證明省略。定理4.5.7有理數(shù)的全體組成的集合是可數(shù)集。證明：有理數(shù)r可寫成分?jǐn)?shù)，其中q≠0，p,q為互質(zhì)的整數(shù)。把分?jǐn)?shù)記為序偶p,q，就成為平面上的格點(diǎn)。在平面上的全體格點(diǎn)構(gòu)成的集合中刪除q=0和p,q不互質(zhì)的序偶得集合S，S就是有理數(shù)集合,它是平面上的全體格點(diǎn)構(gòu)成的集合的無限子集，而平面上的全體格點(diǎn)構(gòu)成的集合是可數(shù)集。因此，有理數(shù)全體是可數(shù)集。第59頁，共70頁，2023年，2月20日，星期三定理4.5.8設(shè)R為實(shí)數(shù)集，則集合x|xR∧0＜x＜1是不可數(shù)集。同樣R也為不可數(shù)集。證明：因?yàn)閒:(0,1)→R是雙射函數(shù)，令S=x|xR∧0＜x＜1，如果S是不可數(shù)集，則R也必為不可數(shù)集。所以先證x|xR∧0＜x＜1是不可數(shù)集。如果x|xR∧0＜x＜1是可數(shù)集，那么，其中所有實(shí)數(shù)可排成一數(shù)列：t1,t2,…,tn,…，將這些實(shí)數(shù)用十進(jìn)制無限小數(shù)表示為(0.2可表示為0.19999….，0.123可表示為0.12299999…..)：

t1=0.t11t12t13t14…t2=0.t21t22t23t24…t3=0.t31t32t33t34………第60頁，共70頁，2023年，2月20日，星期三其中所有tij都是0，1，2，…，9十個(gè)數(shù)字中的一個(gè)，并且對(duì)每一個(gè)i，ti=0.ti1ti2ti3ti4…中無限項(xiàng)后不全為0。作十進(jìn)制小數(shù)

a=0.a1a2a3a4…

于是所作成的數(shù)a應(yīng)該在集合x|xR∧0＜x＜1中，但不會(huì)在數(shù)列t1,t2,…,tn,…中，因?yàn)閷?duì)于每個(gè)n，an≠tnn，所以a≠tn，這和ti|i=1,2,…是區(qū)間x|xR∧0＜x＜1中實(shí)數(shù)全體的假設(shè)相矛盾。因此x|xR∧0＜x＜1是不可數(shù)集。從而R也是不可數(shù)集。定義

集合x|xR∧0＜

x＜1的基數(shù)稱為連續(xù)點(diǎn)集的基數(shù)或稱作連續(xù)統(tǒng)的勢(shì)。記為k[R]=。讀作“阿列夫”。第61頁，共70頁，2023年，2月20日，星期三4-6基數(shù)的比較定義4.6.1

若集合A到集合B存在一個(gè)入射，則稱A的基數(shù)不大于B的基數(shù)或稱A的基數(shù)小于等于B的基數(shù)，記為K[A]≤K[B]。若集合A到集合B存在一個(gè)入射，但不存在雙射，則稱A的基數(shù)小于B的基數(shù)，記為K[A]＜K[B]。定理4.6.1

(Zermelo定理)設(shè)A和B是集合，則以下三條中恰有一條成立。aK[A]＜K[B]bK[B]＜K[A]

cK[A]=K[B] 證明從略。第62頁，共70頁，2023年，2月20日，星期三定理4.6.2

(Cantor-Schroder-Bernstein定理)設(shè)A和B是集合，如果K[A]≤K[B]且K[B]≤K[A]，則K[A]=K[B]。

證明從略。這個(gè)定理對(duì)證明集合的基數(shù)相同提供了有效方法。如果我們能夠構(gòu)造一入射函數(shù)f：A→B，即說明有K[A]≤K[B]。另外，如能夠構(gòu)造入射函數(shù)f：B→A，即有K[B]≤K[A]。根據(jù)本定理